Skip to main content

Applying L-shaped method using callback in C++

Awaiting user input

Comments

4 comments

  • Amirhossein Abbaszadeh
    Curious
    First Comment

    Also, I want to add something else! According to the MIP logging I've attached, Gurobi explored 515 nodes when I used the callback function to solve the master problem. The last node is 514, and the best bound at this node is 1616.99. However, Gurobi stopped at this node and reported that the optimal solution was found. How is this possible?

    Set parameter Username
    Academic license - for non-commercial use only - expires 2025-03-08
    Indices of the middle 5 members of the vector (excluding member with index 0):
    Set parameter LazyConstraints to value 1
    Set parameter PreCrush to value 1
    Set parameter TimeLimit to value 1996.884
    Set parameter MIPGap to value 0
    Set parameter Threads to value 1
    Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2))

    CPU model: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
    Thread count: 8 physical cores, 16 logical processors, using up to 1 threads

    Optimize a model with 82649 rows, 81586 columns and 415060 nonzeros
    Model fingerprint: 0xc270a543
    Variable types: 70951 continuous, 10635 integer (0 binary)
    Coefficient statistics:
      Matrix range     [1e-02, 5e+02]
      Objective range  [1e-02, 1e-02]
      Bounds range     [2e+09, 2e+09]
      RHS range        [6e-01, 4e+01]
    Warning: Model contains large bounds
             Consider reformulating model or setting NumericFocus parameter
             to avoid numerical issues.
    Presolve removed 15900 rows and 13074 columns (presolve time = 5s) ...
    Presolve removed 15900 rows and 13074 columns
    Presolve time: 5.04s
    Presolved: 66749 rows, 68512 columns, 340115 nonzeros
    Variable types: 59533 continuous, 8979 integer (5999 binary)
     objVal = -1e+100    &     bestBound = 5313.23
    Root relaxation presolved: 66787 rows, 68512 columns, 352565 nonzeros


    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0    5.3132300e+03   3.308461e+04   0.000000e+00     24s
        9232    3.7692065e+03   6.652288e+04   0.000000e+00     25s
       14451    1.6234500e+03   0.000000e+00   0.000000e+00     26s

    Root relaxation: objective 1.623450e+03, 14451 iterations, 1.46 seconds (2.69 work units)

        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

         0     0 1623.45000    0  118          - 1623.45000      -     -   26s
     objVal = -1e+100    &     bestBound = 1623.45
         0     0 1623.45000    0  118          - 1623.45000      -     -   32s
     objVal = -1e+100    &     bestBound = 1623.45
     objVal = -1e+100    &     bestBound = 1623.45
     objVal = -1e+100    &     bestBound = 1623.45
    H    0     0                     670.9500000 1623.45000   142%     -   33s
     objVal = 670.95    &     bestBound = 1623.45
         0     0 1623.45000    0  118  670.95000 1623.45000   142%     -   37s
     objVal = 670.95    &     bestBound = 1623.45
     objVal = 670.95    &     bestBound = 1623.45
     objVal = 670.95    &     bestBound = 1623.45
    H    0     0                     704.7600000 1623.45000   130%     -   39s
     objVal = 704.76    &     bestBound = 1623.45
         0     0 1623.45000    0  118  704.76000 1623.45000   130%     -   41s
     objVal = 704.76    &     bestBound = 1623.45
     objVal = 704.76    &     bestBound = 1623.45
         0     0 1623.45000    0  118  704.76000 1623.45000   130%     -   48s
     objVal = 704.76    &     bestBound = 1623.45
         0     0 1623.45000    0  118  704.76000 1623.45000   130%     -   51s
     objVal = 704.76    &     bestBound = 1623.45
         0     0 1623.45000    0  118  704.76000 1623.45000   130%     -   55s
         0     0 1619.79926    0  142  704.76000 1619.79926   130%     -   58s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -   62s
     objVal = 704.76    &     bestBound = 1619.69
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -   67s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -   70s
     objVal = 704.76    &     bestBound = 1619.69
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -   87s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -  103s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -  118s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -  133s
     objVal = 704.76    &     bestBound = 1619.69
         0     0 1619.68731    0  142  704.76000 1619.68731   130%     -  149s
         0     0 1619.52699    0  146  704.76000 1619.52699   130%     -  153s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  157s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  161s
     objVal = 704.76    &     bestBound = 1619.49
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  168s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  172s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  181s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  190s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  204s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  215s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  229s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  238s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  245s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  253s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  261s
     objVal = 704.76    &     bestBound = 1619.49
         0     0 1619.48577    0  146  704.76000 1619.48577   130%     -  269s
     objVal = 704.76    &     bestBound = 1617
         0     0 1616.99826    0  266  704.76000 1616.99826   129%     -  277s
     objVal = 704.76    &     bestBound = 1617
         0     0 1616.99826    0  266  704.76000 1616.99826   129%     -  283s
     objVal = 704.76    &     bestBound = 1617
         0     0 1616.99826    0  266  704.76000 1616.99826   129%     -  288s
     objVal = 704.76    &     bestBound = 1617
         0     0 1616.99826    0  266  704.76000 1616.99826   129%     -  295s
     objVal = 704.76    &     bestBound = 1617
         0     0 1616.99826    0  266  704.76000 1616.99826   129%     -  302s
         0     2 1616.99826    0  266  704.76000 1616.99826   129%     -  302s
         2     4 1616.99826    2  264  704.76000 1616.99826   129%   872  306s
         6     8 1616.99826    6  143  704.76000 1616.99826   129%   507  310s
         8    10 1616.99826    7  258  704.76000 1616.99826   129%   857  319s
         9    11 1616.99826    8  141  704.76000 1616.99826   129%   809  323s
        10    12 1616.99826    9  255  704.76000 1616.99826   129%   871  328s
        11    13 1616.99826    9  146  704.76000 1616.99826   129%   960  332s
        12    14 1616.99826   10  253  704.76000 1616.99826   129%   947  335s
        14    16 1616.99826   12  249  704.76000 1616.99826   129%   881  342s
        15    17 1616.99826   13  213  704.76000 1616.99826   129%   881  346s
        16    18 1616.99826   14  208  704.76000 1616.99826   129%   899  353s
        17    19 1616.99826   15  243  704.76000 1616.99826   129%   857  357s
        18    20 1616.99826   16  247  704.76000 1616.99826   129%   818  360s
        20    22 1616.99826   17  239  704.76000 1616.99826   129%   893  369s
        21    23 1616.99826   18  233  704.76000 1616.99826   129%   867  371s
        23    25 1616.99826   20  230  704.76000 1616.99826   129%   809  375s
        25    27 1616.99826   22  225  704.76000 1616.99826   129%   774  381s
     objVal = 704.76    &     bestBound = 1617
        26    28 1616.99826   23  192  704.76000 1616.99826   129%   765  398s
        28    30 1616.99826   25  121  704.76000 1616.99826   129%   739  400s
        32    34 1616.99826   29  149  704.76000 1616.99826   129%   729  405s
        37    39 1616.99826   33  132  704.76000 1616.99826   129%   679  410s
        39    41 1616.99826   35  112  704.76000 1616.99826   129%   703  415s
        41    43 1616.99826   36  119  704.76000 1616.99826   129%   713  420s
        44    46 1616.99826   39  190  704.76000 1616.99826   129%   702  426s
        46    48 1616.99826   41  182  704.76000 1616.99826   129%   687  430s
        49    51 1616.99826   44  174  704.76000 1616.99826   129%   656  435s
     objVal = 704.76    &     bestBound = 1617
        52    54 1616.99826   47  155  704.76000 1616.99826   129%   631  464s
        53    55 1616.99826   48  153  704.76000 1616.99826   129%   629  465s
        60    62 1616.96457   55  157  704.76000 1616.99826   129%   577  470s
        68    70 1616.90670   63  108  704.76000 1616.99826   129%   528  475s
        75    77 1616.44320   69   96  704.76000 1616.99826   129%   509  480s
        88    90 1615.18948   79   85  704.76000 1616.99826   129%   488  485s
       101   103 1614.38415   90   76  704.76000 1616.99826   129%   467  490s
       108   110 1614.01267   96   76  704.76000 1616.99826   129%   461  495s
       117   119 1613.41062  104   70  704.76000 1616.99826   129%   439  500s
       127   129 1611.16137  111   67  704.76000 1616.99826   129%   425  505s
       143   145 1607.63533  122   36  704.76000 1616.99826   129%   401  510s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       158   160 1513.69200  132    4  704.76000 1616.99826   129%   374  517s
     objVal = 704.76    &     bestBound = 1617
       159   161 1506.86933  133    6  704.76000 1616.99826   129%   372  520s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       160   162 1616.99826    2  262  704.76000 1616.99826   129%   390  532s
       161   163 1616.99826    3  280  704.76000 1616.99826   129%   402  539s
       162   164 1616.99826    4  261  704.76000 1616.99826   129%   406  545s
       163   165 1616.99826    5  253  704.76000 1616.99826   129%   411  551s
       164   166 1616.99826    6  322  704.76000 1616.99826   129%   415  555s
       165   167 1616.99826    7  329  704.76000 1616.99826   129%   417  560s
       166   168 1616.99826    8  325  704.76000 1616.99826   129%   426  567s
       167   169 1616.99826    9  302  704.76000 1616.99826   129%   431  572s
       168   170 1616.99826   10  216  704.76000 1616.99826   129%   431  575s
       170   172 1616.99826   12  169  704.76000 1616.99826   129%   430  580s
       172   174 1616.99826   14  171  704.76000 1616.99826   129%   430  587s
       174   176 1616.99826   16  173  704.76000 1616.99826   129%   431  591s
       176   178 1616.99826   18  176  704.76000 1616.99826   129%   433  596s
       178   180 1616.99826   20  188  704.76000 1616.99826   129%   434  600s
       181   183 1616.99826   23  172  704.76000 1616.99826   129%   433  606s
       184   186 1616.99826   26  185  704.76000 1616.99826   129%   428  610s
       187   189 1616.99826   29  187  704.76000 1616.99826   129%   432  617s
       189   191 1616.99826   31  183  704.76000 1616.99826   129%   433  621s
       192   194 1616.99826   34  131  704.76000 1616.99826   129%   431  626s
       196   198 1616.99826   38  129  704.76000 1616.99826   129%   429  630s
       206   208 1616.99826   48  134  704.76000 1616.99826   129%   417  635s
       216   218 1615.25229   57  119  704.76000 1616.99826   129%   416  643s
       219   221 1616.13182   59  103  704.76000 1616.99826   129%   414  645s
       229   231 1615.62876   68  115  704.76000 1616.99826   129%   406  650s
       239   241 1614.96381   78   90  704.76000 1616.99826   129%   400  655s
       248   250 1612.14369   85   63  704.76000 1616.99826   129%   394  660s
     objVal = 704.76    &     bestBound = 1617
       261   263 1606.99926   94   40  704.76000 1616.99826   129%   386  710s
     objVal = 704.76    &     bestBound = 1617
       262   264 1608.22384   95   43  704.76000 1616.99826   129%   384  720s
     objVal = 704.76    &     bestBound = 1617
       281   283 1511.98600  105   12  704.76000 1616.99826   129%   371  727s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       283   285 1537.27280  105    8  704.76000 1616.99826   129%   370  732s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       285   287 1508.72000  106    7  704.76000 1616.99826   129%   369  736s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       288   290 1616.99826    5  275  704.76000 1616.99826   129%   374  747s
       289   291 1616.99826    6  270  704.76000 1616.99826   129%   379  752s
       290   292 1616.99826    7  274  704.76000 1616.99826   129%   382  758s
       291   293 1616.99826    8  213  704.76000 1616.99826   129%   382  761s
       292   294 1616.99826    9  262  704.76000 1616.99826   129%   386  767s
       293   295 1616.99826   10  280  704.76000 1616.99826   129%   388  773s
       294   296 1616.99826   11  224  704.76000 1616.99826   129%   389  776s
       295   297 1616.99826   12  342  704.76000 1616.99826   129%   401  789s
       296   298 1616.99826   13  356  704.76000 1616.99826   129%   403  793s
       297   299 1616.99826   14  253  704.76000 1616.99826   129%   402  795s
       299   301 1616.99826   16  165  704.76000 1616.99826   129%   402  802s
       301   303 1616.99826   18  215  704.76000 1616.99826   129%   405  807s
       303   305 1616.99826   20  211  704.76000 1616.99826   129%   406  811s
     objVal = 704.76    &     bestBound = 1617
       304   306 1616.68602   21  215  704.76000 1616.99826   129%   412  852s
       306   308 1616.36788   23  201  704.76000 1616.99826   129%   415  855s
       312   314 1616.08488   29  165  704.76000 1616.99826   129%   415  860s
       318   320 1614.29378   35  129  704.76000 1616.99826   129%   420  865s
       330   332 1611.97319   47  133  704.76000 1616.99826   129%   418  870s
       352   354 1610.25306   69   89  704.76000 1616.99826   129%   403  875s
     objVal = 704.76    &     bestBound = 1617
       386   388 1552.51521   91   11  704.76000 1616.99826   129%   379  882s
     objVal = 704.76    &     bestBound = 1617
       387   389 1528.56600   92    9  704.76000 1616.99826   129%   378  885s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
       392   394 1485.81619   94    8  704.76000 1616.99826   129%   375  890s
     objVal = 704.76    &     bestBound = 1617
     objVal = 704.76    &     bestBound = 1617
    *  395   395              96    1470.5500000 1616.99826  10.0%   372  893s
     objVal = 1470.55    &     bestBound = 1617
       397   395     cutoff   98      1470.55000 1616.99826  10.0%   371  895s
       399   395 1616.99826    8  272 1470.55000 1616.99826  10.0%   377  902s
       400   396 1616.99826    9  224 1470.55000 1616.99826  10.0%   381  908s
       401   397 1616.99826   10  274 1470.55000 1616.99826  10.0%   382  912s
       402   398 1616.99826   11  263 1470.55000 1616.99826  10.0%   385  919s
       403   399 1616.99826   12  362 1470.55000 1616.99826  10.0%   391  930s
       404   400 1616.99826   13  265 1470.55000 1616.99826  10.0%   393  936s
       405   401 1616.99826   14  268 1470.55000 1616.99826  10.0%   395  943s
       406   402 1616.99826   15  280 1470.55000 1616.99826  10.0%   396  948s
       407   403 1616.99826   15  197 1470.55000 1616.99826  10.0%   398  953s
       408   404 1616.95038   16  196 1470.55000 1616.99826  10.0%   398  956s
       410   406 1561.91103   17  227 1470.55000 1616.99826  10.0%   406  968s
       411   407 1616.84898   18  227 1470.55000 1616.99826  10.0%   405  970s
       412   408 1616.31481   19  227 1470.55000 1616.99826  10.0%   408  975s
       414   410 1616.12507   21  193 1470.55000 1616.99826  10.0%   410  980s
       418   414 1615.97511   25  217 1470.55000 1616.99826  10.0%   412  986s
       420   416 1615.79109   27  225 1470.55000 1616.99826  10.0%   413  990s
       427   423 1615.59894   34  195 1470.55000 1616.99826  10.0%   412  996s
       431   427 1615.48371   38  166 1470.55000 1616.99826  10.0%   410 1000s
       438   434 1615.21606   45  144 1470.55000 1616.99826  10.0%   409 1005s
       441   437 1614.64498   48  109 1470.55000 1616.99826  10.0%   410 1010s
       445   441 1613.93977   52  112 1470.55000 1616.99826  10.0%   410 1015s
       454   450 1612.83692   61  110 1470.55000 1616.99826  10.0%   406 1020s
       462   458 1611.53636   68  103 1470.55000 1616.99826  10.0%   404 1025s
       480   476 1606.01498   85   54 1470.55000 1616.99826  10.0%   394 1030s
     objVal = 1470.55    &     bestBound = 1617
     objVal = 1470.55    &     bestBound = 1617
       495   491 1506.73333   95   10 1470.55000 1616.99826  10.0%   385 1038s
     objVal = 1470.55    &     bestBound = 1617
       500   496 1489.84413   98    6 1470.55000 1616.99826  10.0%   381 1040s
     objVal = 1470.55    &     bestBound = 1617
     objVal = 1470.55    &     bestBound = 1617
     objVal = 1470.55    &     bestBound = 1617
       501   495     cutoff   98      1470.55000 1616.99826  10.0%   381 1045s
     objVal = 1470.55    &     bestBound = 1617
     objVal = 1470.55    &     bestBound = 1617
       503   497 1596.69407    4  237 1470.55000 1616.99826  10.0%   391 1059s
       504   498 1596.66326    5  294 1470.55000 1616.99826  10.0%   391 1060s
       506   500 1596.13939    7  231 1470.55000 1616.99826  10.0%   396 1068s
       507   501 1595.93108    8  339 1470.55000 1616.99826  10.0%   402 1079s
       508   502 1595.65134    9  209 1470.55000 1616.99826  10.0%   404 1088s
       509   503 1595.59132   10  210 1470.55000 1616.99826  10.0%   405 1090s
       511   505 1595.04184   12  209 1470.55000 1616.99826  10.0%   409 1100s
       514   508 1595.19540   14  181 1470.55000 1616.99826  10.0%   412 1106s

    Cutting planes:
      Gomory: 3
      MIR: 111
      Flow cover: 340
      RLT: 2
      Lazy constraints: 5434

    Explored 515 nodes (238900 simplex iterations) in 1108.01 seconds (1658.27 work units)
    Thread count was 1 (of 16 available processors)

    Solution count 3: 1470.55 704.76 670.95

    Optimal solution found (tolerance 0.00e+00)
    Best objective 1.470550000000e+03, best bound 1.470550000000e+03, gap 0.0000%

    User-callback calls 73284, time in user-callback 185.07 sec
    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    Hi,

    To your first question, why you do not get the same result when adding all generated cuts initially to your master problem: In the second case, the solver follows a different solution path, so potentially other solutions are found. If you do not check them in the callback, they are accepted. This is why you get a better solution in the second approach. You could check the final solution you get in the second run, I bet it is not feasible or would lead to further Benders cuts.

    To your second question on the solver log, I guess you added a Benders cut that closed the residual gap. Add some more outputs to debug this case. The solver only outputs log updates every few seconds. If the problem is solved within such an interval, you will see just the final summary, as in your case.

    Best regards,
    Mario

    0
  • Amirhossein Abbaszadeh
    Curious
    First Comment

    Dear Mario, 

    Thank you very much for your reply! 

    You could check the final solution you get in the second run, I bet it is not feasible or would lead to further Benders cuts.

    That's exactly why I'm confused here! The solution I got in the second run is both feasible and optimal.

    Additionally, I conducted two further tests:

    1. Test 1: I got the optimal solution of the problem using the extensive model (i.e., the model that includes all variables), which I'll refer to as optSol#1. I then solved the problem using Benders Decomposition. At each iteration, I checked the RHS of the generated Benders cut for optSol#1. None of them cut off this solution. However, in the end, I got another solution with a worse objective value. So, why doesn't the solver find optSol#1 (or a solution with the same objective value), especially considering that no cut was generated to exclude optSol#1 in the callback function? 
    2. Test 2: I fixed optSol#1 into the master problem and again solved it using Benders Decomposition. After one iteration, I got the optSol#1. 

    So, 
    I have a model for which I know the optimal solution. When I fix this solution into the master problem, everything works well. When I do not fix the solution into the master problem, I get a solution that is not optimal while no cut is generated to exclude the optimal solution!

    Could you please help me understand what might be going wrong? 

    Thanks, 
    Amirhossein

     

    0
  • Mario Ruthmair
    Gurobi Staff Gurobi Staff

    If there are no constraints in the initial master problem and not added Benders cuts that cut off optSol#1, and you obtain an "optimal" solution that is worse than optSol#1, then there is something fishy.

    Could you generate a very small example that I can try to reproduce on my side? Please remove all parts that are not needed to show the issue.

    0

Please sign in to leave a comment.