Solver takes to long too find Incumbent solution

Hi, I´m trying to solve a MILP problem with quadratic constraints. The solver is taking a fairly long time finding a incumbent solution. When it finds it, it´s when the optimization is done. The best boundary moves too slow. Is there any common reason for this? I´ve tried MIPFocus=3, but with this parameter the problem takes even longer to solve.

Thanks for your help

Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
Warning: Q constraint 0 doesn't have a name
Warning: default Q constraint names used to write mps file
Optimize a model with 87238 rows, 81720 columns and 166221 nonzeros
Model fingerprint: 0x98b093a2
Model has 17180 quadratic constraints
Variable types: 52200 continuous, 29520 integer (17640 binary)
Coefficient statistics:
  Matrix range     [1e-01, 2e+01]
  QMatrix range    [4e-05, 1e+01]
  QLMatrix range   [2e-01, 2e+02]
  Objective range  [3e-03, 4e+02]
  Bounds range     [1e+00, 5e+01]
  RHS range        [3e-02, 5e+01]
Presolve removed 44518 rows and 37630 columns
Presolve time: 0.55s
Presolved: 76204 rows, 49916 columns, 190577 nonzeros
Presolved model has 5085 bilinear constraint(s)
Variable types: 27073 continuous, 22843 integer (11624 binary)

Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...

Concurrent spin time: 0.00s

Solved with dual simplex

Root relaxation: objective 1.790563e+06, 14341 iterations, 0.85 seconds

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

     0     0 1790563.21    0 2298          - 1790563.21      -     -    4s
     0     0 1790435.57    0  876          - 1790435.57      -     -    5s
     0     0 1790434.16    0  735          - 1790434.16      -     -    5s
     0     0 1790424.05    0  720          - 1790424.05      -     -    6s
     0     0 1790424.02    0  716          - 1790424.02      -     -    7s
     0     0 1790423.19    0  651          - 1790423.19      -     -    8s
     0     0 1790423.16    0  647          - 1790423.16      -     -    9s
     0     0 1790423.10    0  643          - 1790423.10      -     -   11s
     0     0 1790423.09    0  641          - 1790423.09      -     -   12s
     0     0 1790423.09    0  638          - 1790423.09      -     -   12s
     0     0 1790423.09    0  638          - 1790423.09      -     -   14s
     0     2 1790423.09    0  638          - 1790423.09      -     -   17s
    89   147 1790398.41   36  635          - 1790413.72      -   9.1   20s
   320   426 1790365.08  113  635          - 1790413.72      -  14.6   27s
   425   543 1790349.64  148  635          - 1790413.72      -  15.1   31s
   542   665 1790335.52  188  636          - 1790413.72      -  15.0   35s
   664   796 1790316.85  229  636          - 1790413.72      -  15.1   41s
   795   922 1790296.84  272  636          - 1790413.72      -  15.1   45s
  1059  1194 1790256.31  360  636          - 1790413.72      -  15.2   52s
  1193  1342 1790235.81  405  636          - 1790413.72      -  15.2   55s
  1537  1826 1790192.10  521  633          - 1790413.72      -  14.7   63s
  1825  2096 1790178.91  617  633          - 1790413.72      -  13.0   74s
  2095  2378 1790166.55  707  633          - 1790413.72      -  11.9   81s
  2377  2714 1790154.84  805  629          - 1790413.72      -  11.0   87s
  2715  2995 1789981.05  961  623          - 1790413.72      -  10.0   91s
  2996  3232 1789971.77 1054  623          - 1790413.72      -   9.7   95s
  3437  3641 1789940.39 1210  620          - 1790413.72      -   9.2  102s
  3647  3643 1790150.92  867 2297          - 1790413.72      -   9.1  106s
  3650  3645 1790150.72  893  660          - 1790413.72      -   9.1  110s
  3656  3649 1787110.28  628  634          - 1790412.50      -   9.1  116s
  3658  3651 1786933.21  458  625          - 1790412.37      -   9.1  123s
  3660  3652 1789977.52  997  625          - 1790412.37      -   9.1  127s
  3661  3656 1790405.00   14  623          - 1790411.97      -  14.7  139s
  3671  3662 1790404.29   17  620          - 1790410.79      -  14.7  140s
  3704  3712 1790402.98   25  585          - 1790410.45      -  14.6  145s
  3734  3778 1790403.09   33  575          - 1790410.06      -  14.5  163s
  3810  3857 1790402.80   50  563          - 1790410.06      -  14.3  178s
  3914  4014 1790402.46   74  557          - 1790410.06      -  14.0  188s
  4106  4161 1790401.96  123  537          - 1790410.06      -  13.5  197s
  4317  4330 1786527.97  173  534          - 1790410.06      -  13.0  205s
  4557  4420 1790236.68  228  526          - 1790410.06      -  12.4  211s
  4727  4566 1790236.45  270  516          - 1790410.06      -  12.0  218s
  4930  4695 1790235.91  326  511          - 1790410.06      -  11.6  225s
  5126  4910 1790235.66  367  509          - 1790410.06      -  11.2  231s
  5407  5007 1790235.19  439  507          - 1790410.06      -  10.7  238s
  5597  5231 1790234.76  488  500          - 1790410.06      -  10.4  245s
  5885  5361 1790233.97  549  494          - 1790410.06      -  10.0  252s
  6111  5563 1790232.89  599  493          - 1790410.06      -   9.7  259s
  6388  5651 1790232.53  674  492          - 1790410.06      -   9.3  267s
  6568  5834 1790232.27  720  481          - 1790410.06      -   9.1  275s
  6811  6078 1790231.94  781  471          - 1790410.06      -   8.9  284s
  7136  6306 1790231.53  865  467          - 1790410.06      -   8.5  292s
  7473  6491 1790231.03  942  459          - 1790410.06      -   8.2  301s
  7770  6780 1790229.86 1016  453          - 1790410.06      -   8.0  310s
  8158  6939 1790229.08 1110  442          - 1790410.06      -   7.7  319s
  8446  7201 1790092.90 1178  443          - 1790410.06      -   7.5  328s
  8804  7430 1790227.93 1269  430          - 1790410.06      -   7.3  339s
  9153  7685 1790227.28 1356  436          - 1790410.06      -   7.1  349s
  9524  7985 1790226.36 1436  431          - 1790410.06      -   6.9  358s
  9948  8253 1790226.37 1544  429          - 1790410.06      -   6.6  368s
 10357  8535 1790226.34 1631  429          - 1790410.06      -   6.4  381s
 10775  8799 1790226.30 1739  430          - 1790410.06      -   6.2  396s
 11179  9074 1790226.12 1845  426          - 1790410.06      -   6.1  406s
 11588  9322 1790226.00 1949  426          - 1790410.06      -   5.9  415s
 11973  9539 1790225.80 2048  425          - 1790410.06      -   5.8  425s
 12318  9763 1790225.74 2149  425          - 1790410.06      -   5.7  433s
 12657  9944 1790225.69 2248  426          - 1790410.06      -   5.6  442s
 12953 10105 1790097.29 2332  424          - 1790410.06      -   5.5  451s
 13213 10330 1790097.26 2405  424          - 1790410.06      -   5.4  459s
 13524 10707 1790097.23 2489  425          - 1790410.06      -   5.3  468s
 14005 10864 1790097.15 2608  424          - 1790410.06      -   5.2  477s
 14322 11192 1790096.68 2694  415          - 1790410.06      -   5.2  486s
 14756 11420 1790096.50 2791  415          - 1790410.06      -   5.1  494s
 15082 11766 1790096.26 2871  414          - 1790410.06      -   5.0  503s
 15428 12180 1790095.69 2963  414          - 1790410.06      -   4.9  511s
 15842 12432 1790095.02 3074  414          - 1790410.06      -   4.8  520s
 16094 12775 1790093.72 3141  410          - 1790410.06      -   4.8  528s
 16437 13124 1790093.69 3214  407          - 1790410.06      -   4.7  538s
 16786 13444 1790093.68 3293  407          - 1790410.06      -   4.6  547s
 17107 13821 1789953.35 3371  409          - 1790410.06      -   4.6  556s
 17484 14236 1789953.28 3469  408          - 1790410.06      -   4.5  566s
 17899 14479 1789953.12 3562  408          - 1790410.06      -   4.5  581s
 18143 14871 1789952.91 3623  402          - 1790410.06      -   4.5  592s
 18535 15213 1789952.75 3718  402          - 1790410.06      -   4.4  601s
 18877 15561 1789952.50 3808  404          - 1790410.06      -   4.4  610s
 19225 15890 1789951.65 3899  403          - 1790410.06      -   4.4  618s
 19554 16184 1789951.44 3978  405          - 1790410.06      -   4.3  627s
 19848 16468 1789951.25 4046  404          - 1790410.06      -   4.3  636s
 20132 16791 1789951.10 4110  402          - 1790410.06      -   4.3  644s
 20455 17162 1789950.76 4193  404          - 1790410.06      -   4.2  656s
 20826 17400 1789950.57 4283  407          - 1790410.06      -   4.2  666s
 21065 17791 1789950.13 4339  406          - 1790410.06      -   4.2  674s
 21456 18200 1789950.05 4439  404          - 1790410.06      -   4.1  686s
 21865 18541 1789949.98 4547  404          - 1790410.06      -   4.1  697s
 22207 18939 1789948.96 4630  402          - 1790410.06      -   4.1  706s
 22605 19341 1789948.13 4740  402          - 1790410.06      -   4.0  716s
 23007 19651 1789947.27 4848  401          - 1790410.06      -   4.0  726s
 23318 20005 1789946.85 4918  395          - 1790410.06      -   4.0  734s
 23672 20369 1789946.76 5007  395          - 1790410.06      -   3.9  743s
 24036 20750 1789946.43 5084  389          - 1790410.06      -   3.9  752s
 24417 21101 1789945.66 5167  383          - 1790410.06      -   3.9  761s
 24768 21420 1789945.29 5242  381          - 1790410.06      -   3.9  770s
 25087 21754 1789944.83 5321  384          - 1790410.06      -   3.9  778s
 25421 22020 1789944.44 5399  377          - 1790410.06      -   3.9  786s
 25687 22320 1789944.33 5461  377          - 1790410.06      -   3.9  794s
 25987 22617 1789944.22 5530  377          - 1790410.06      -   3.9  802s
 26284 22910 1789943.84 5605  370          - 1790410.06      -   3.8  810s
 26577 23209 1789943.37 5666  374          - 1790410.06      -   3.8  818s
 26876 23423 1789943.21 5727  374          - 1790410.06      -   3.8  831s
 27094 23777 1789941.63 5777  373          - 1790410.06      -   3.8  843s
 27448 24075 1789940.63 5861  373          - 1790410.06      -   3.8  854s
 27746 24394 1789940.06 5921  373          - 1790410.06      -   3.7  868s
 28065 24757 1789939.86 5995  374          - 1790410.06      -   3.7  877s
 28428 25138 1789939.72 6086  371          - 1790410.06      -   3.7  885s
 28810 25397 1789937.82 6176  370          - 1790410.06      -   3.7  894s
 29069 25783 1789937.23 6245  371          - 1790410.06      -   3.7  902s
 29455 26167 1789937.12 6358  372          - 1790410.06      -   3.6  910s
 29839 26505 1789937.00 6459  371          - 1790410.06      -   3.6  918s
 30177 26807 1789936.97 6542  372          - 1790410.06      -   3.6  926s
 30480 27151 1789936.95 6632  370          - 1790410.06      -   3.6  934s
 30824 27397 1789936.93 6720  372          - 1790410.06      -   3.6  944s
 31070 27739 1789936.63 6777  366          - 1790410.06      -   3.5  959s
 31234 27739 1790075.10 6957  363          - 1790410.06      -   3.5  960s
 31412 28136 1789936.11 6859  364          - 1790410.06      -   3.5  970s
 31809 28487 1789936.11 6962  364          - 1790410.06      -   3.5  979s
 32160 28862 1789936.11 7058  364          - 1790410.06      -   3.5  989s
 32535 29213 1789936.02 7145  363          - 1790410.06      -   3.4  998s
 32886 29567 1789935.89 7234  363          - 1790410.06      -   3.4 1008s
 33240 29919 1789935.77 7322  364          - 1790410.06      -   3.4 1017s
 33592 30206 1789935.65 7410  364          - 1790410.06      -   3.4 1025s
 33879 30398 1789935.51 7469  363          - 1790410.06      -   3.4 1033s
 34071 30730 1789935.38 7512  363          - 1790410.06      -   3.4 1042s
 34403 31038 1789935.35 7599  362          - 1790410.06      -   3.4 1050s
 34711 31386 1789935.27 7673  360          - 1790410.06      -   3.3 1058s
 35059 31694 1789935.26 7760  360          - 1790410.06      -   3.3 1067s
 35367 31940 1789935.16 7828  361          - 1790410.06      -   3.3 1079s
 35614 32310 1789934.17 7887  363          - 1790410.06      -   3.3 1088s
 35984 32694 1789929.73 7993  363          - 1790410.06      -   3.3 1098s
 36368 33017 1789925.29 8099  363          - 1790410.06      -   3.3 1107s
 36691 33293 1789922.63 8192  364          - 1790410.06      -   3.3 1116s
 36967 33592 1789922.47 8261  358          - 1790410.06      -   3.3 1125s
 37266 33943 1789922.32 8319  357          - 1790410.06      -   3.3 1134s
 37617 34325 1789922.24 8403  358          - 1790410.06      -   3.3 1144s
 37999 34655 1789922.15 8509  359          - 1790410.06      -   3.2 1153s
 38329 34944 1789921.93 8592  358          - 1790410.06      -   3.2 1163s
 38618 35239 1789921.11 8657  359          - 1790410.06      -   3.2 1172s
 38918 35575 1789920.61 8709  352          - 1790410.06      -   3.2 1186s
 39254 35878 1789920.57 8796  352          - 1790410.06      -   3.2 1196s
 39559 36219 1789920.54 8878  352          - 1790410.06      -   3.2 1205s
 39900 36523 1789920.51 8964  352          - 1790410.06      -   3.2 1214s
 40204 36828 1789920.13 9030  355          - 1790410.06      -   3.2 1223s
 40509 37150 1789919.70 9098  352          - 1790410.06      -   3.2 1232s
 40831 37349 1789919.53 9177  350          - 1790410.06      -   3.2 1240s
 41030 37667 1789919.30 9239  350          - 1790410.06      -   3.2 1249s
 41348 38009 1789918.95 9325  349          - 1790410.06      -   3.2 1258s
 41690 38364 1789918.71 9415  349          - 1790410.06      -   3.1 1267s
 42045 38761 1789915.85 9507  349          - 1790410.06      -   3.1 1276s
 42442 39182 1789909.69 9633  348          - 1790410.06      -   3.1 1285s
 42863 39416 1789903.62 9758  349          - 1790410.06      -   3.1 1293s
 43097 39752 1789901.99 9824  348          - 1790410.06      -   3.1 1301s
 43433 40127 1789901.93 9907  348          - 1790410.06      -   3.1 1310s
 43808 40455 1789901.89 9991  348          - 1790410.06      -   3.1 1319s
 44136 40829 1789901.87 10064  348          - 1790410.06      -   3.1 1327s
 44510 41185 1789901.81 10147  348          - 1790410.06      -   3.1 1335s
 44866 41478 1789901.44 10222  345          - 1790410.06      -   3.1 1343s
 45160 41857 1789900.11 10286  339          - 1790410.06      -   3.1 1352s
 45539 42217 1789899.27 10390  339          - 1790410.06      -   3.0 1360s
 45899 42585 1789897.19 10490  339          - 1790410.06      -   3.0 1369s
 46267 42897 1789895.08 10591  339          - 1790410.06      -   3.0 1379s
 46580 43253 1789893.76 10666  334          - 1790410.06      -   3.0 1388s
 46936 43546 1789893.65 10743  334          - 1790410.06      -   3.0 1396s
 47229 43885 1789893.34 10791  333          - 1790410.06      -   3.0 1406s
 47568 44218 1789892.90 10860  331          - 1790410.06      -   3.0 1414s
 47901 44564 1789892.74 10933  332          - 1790410.06      -   3.0 1422s
 48247 44924 1789892.59 11008  333          - 1790410.06      -   3.0 1430s
 48607 45251 1789892.47 11089  333          - 1790410.06      -   3.0 1441s
 48934 45553 1789892.36 11170  334          - 1790410.06      -   3.0 1451s
 49236 45832 1789892.33 11241  331          - 1790410.06      -   2.9 1460s
 49515 46146 1789892.32 11319  332          - 1790410.06      -   2.9 1468s
 49829 46351 1789892.32 11400  331          - 1790410.06      -   2.9 1476s
 50034 46655 1789892.21 11452  331          - 1790410.06      -   2.9 1484s
 50338 46974 1789892.23 11524  330          - 1790410.06      -   2.9 1492s
 50657 47304 1789892.21 11604  330          - 1790410.06      -   2.9 1504s
 50987 47624 1789892.19 11686  330          - 1790410.06      -   2.9 1515s
 51307 47963 1789892.01 11765  330          - 1790410.06      -   2.9 1526s
 51646 48240 1789891.83 11833  330          - 1790410.06      -   2.9 1535s
 51923 48547 1789891.18 11892  323          - 1790410.06      -   2.9 1544s
 52230 48874 1789890.67 11963  321          - 1790410.06      -   2.9 1553s
 52557 49200 1789890.51 12045  321          - 1790410.06      -   2.9 1561s
 52883 49489 1789890.34 12126  321          - 1790410.06      -   2.9 1570s
 53172 49799 1789890.24 12190  322          - 1790410.06      -   2.9 1579s
 53482 50055 1789890.20 12271  322          - 1790410.06      -   2.9 1587s
 53738 50276 1789889.25 12330  319          - 1790410.06      -   2.9 1596s
H53844 50144                    1789840.7718 1790410.06  0.03%   2.9 1596s

Cutting planes:
  Gomory: 434
  Implied bound: 15
  MIR: 3417
  StrongCG: 218
  Flow cover: 78
  RLT: 8
  Relax-and-lift: 22

Explored 53959 nodes (174005 simplex iterations) in 1599.22 seconds
Thread count was 4 (of 4 available processors)

Solution count 1: 1.78984e+06 

Optimal solution found (tolerance 1.00e-02)
Best objective 1.789840771750e+06, best bound 1.790410062528e+06, gap 0.0318%

正式なコメント

Simranjit Kaur

Gurobi Staff

2024年12月06日 00:42

This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.

Eli Towle

2020年08月11日 22:13

It could be difficult to improve the dual bound much more. The first solution Gurobi found was within 0.03% of optimal, so the bound is already pretty good.

It might be better to focus on trying to find heuristic solutions faster. You can do this with MIPFocus=1 or by increasing the value of the Heuristics parameter. Unfortunately, there's no way of knowing if either of these will help until you try them out on your model.

David Mejía

2020年08月12日 07:11

Thank you Eli for your fast response.

I´ve tried your hint. When I use either MIPFocus=1 or Heuristics=0.1 the solver finds a solution really fast, but no nodes where explored during the optimization process. How can I asses the quality of this solution? How can I know if this is a reliable solution?

Here is the log with Heuristics = 0.1. The MIPFocus=1 log is pretty much the same.

Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (win64)
Warning: Q constraint 0 doesn't have a name
Warning: default Q constraint names used to write mps file
Optimize a model with 87241 rows, 81720 columns and 166231 nonzeros
Model fingerprint: 0xe5ee240c
Model has 17179 quadratic constraints
Variable types: 52200 continuous, 29520 integer (17640 binary)
Coefficient statistics:
Matrix range [1e-01, 2e+01]
QMatrix range [5e-04, 1e+01]
QLMatrix range [2e-01, 2e+02]
Objective range [3e-03, 4e+02]
Bounds range [1e+00, 5e+01]
RHS range [3e-02, 5e+01]
Presolve removed 44516 rows and 37641 columns
Presolve time: 0.53s
Presolved: 76179 rows, 49895 columns, 190513 nonzeros
Presolved model has 5086 bilinear constraint(s)
Variable types: 27055 continuous, 22840 integer (11619 binary)

Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...

Concurrent spin time: 0.01s

Solved with dual simplex

Root relaxation: objective 1.790556e+06, 14311 iterations, 0.75 seconds

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

0 0 1790556.08 0 2291 - 1790556.08 - - 3s
0 0 1790433.35 0 877 - 1790433.35 - - 5s
0 0 1790431.87 0 738 - 1790431.87 - - 5s
0 0 1790422.74 0 734 - 1790422.74 - - 6s
0 0 1790422.72 0 731 - 1790422.72 - - 7s
0 0 1790421.86 0 675 - 1790421.86 - - 8s
0 0 1790421.83 0 671 - 1790421.83 - - 9s
0 0 1790421.78 0 656 - 1790421.78 - - 10s
0 0 1790421.77 0 648 - 1790421.77 - - 11s
0 0 1790421.77 0 645 - 1790421.77 - - 11s
0 0 1790421.77 0 645 - 1790421.77 - - 13s
H 0 0 -2918.858500 1790421.77 - - 16s
H 0 0 1790120.9535 1790421.77 0.02% - 16s

Cutting planes:
Gomory: 308
Implied bound: 28
MIR: 3463
StrongCG: 217
Flow cover: 50
RLT: 7
Relax-and-lift: 21

Explored 1 nodes (19991 simplex iterations) in 16.99 seconds
Thread count was 4 (of 4 available processors)

Solution count 2: 1.79012e+06 -2918.86

Optimal solution found (tolerance 1.00e+00)
Best objective 1.790120953500e+06, best bound 1.790421765679e+06, gap 0.0168%

Matthias Miltenberger

2020年08月12日 07:43 編集済み

Hi David,

You should consider yourself lucky that Gurobi does not have to explore any other nodes except for the root node. This means that no branching was necessary and the problem could be solved using cutting planes and heuristics.

You can assess the solution quality just as usual by inspecting the reported gap, in this case 0.016%.

Cheers,
Matthias

2020年08月12日 11:48

Thank you for that explanation Matthias. It just seemed too good to be true.

Best Regards,

David

Solver takes to long too find Incumbent solution

コメント

お探しのものを見つけられませんでしたか？