Skip to main content

BestBd not updating in a MIQCP problem

Answered
Haoge Chang
  • Edited
Gurobi-versary
First Comment
First Question

Hi! I am trying to solve a MIQCP problem with 10 continuous variables and 1000 binary variables. I have one quadratic constraint that restricts the continuous variables on a unit ball.

I find that the number in the Obj column has been increasing but the number in the BestBd column does not change at all. I was wondering if this makes sense...

Thank you!

 

Here is the output that 

 

Gurobi Optimizer version 10.0.2 build v10.0.2rc0 (mac64[rosetta2])

CPU model: Apple M1
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 12001 rows, 1010 columns and 127972 nonzeros
Model fingerprint: 0xc29fa255
Model has 1 quadratic constraint
Variable types: 10 continuous, 1000 integer (1000 binary)
Coefficient statistics:
  Matrix range     [2e-05, 1e+01]
  QMatrix range    [1e+00, 1e+00]
  Objective range  [1e+00, 1e+00]
  Bounds range     [1e+00, 4e+00]
  RHS range        [1e+00, 5e+01]
  QRHS range       [1e+00, 1e+00]
Presolve time: 0.07s
Presolved: 12002 rows, 1019 columns, 127981 nonzeros
Presolved model has 9 quadratic constraint(s)
Variable types: 19 continuous, 1000 integer (1000 binary)
Starting NoRel heuristic
Found phase-1 solution: relaxation 4.76804
Found phase-1 solution: relaxation 1.76804
Found heuristic solution: objective 3.0000000
Transition to phase 2
Found heuristic solution: objective 2.0000000
Elapsed time for NoRel heuristic: 5s (best bound -1.5)
Elapsed time for NoRel heuristic: 11s (best bound -1.5)
Elapsed time for NoRel heuristic: 19s (best bound -1.5)
Elapsed time for NoRel heuristic: 26s (best bound -1.5)
Elapsed time for NoRel heuristic: 33s (best bound -1.5)
Elapsed time for NoRel heuristic: 39s (best bound -1.5)
Elapsed time for NoRel heuristic: 45s (best bound -1.5)
Elapsed time for NoRel heuristic: 53s (best bound -1.5)
Elapsed time for NoRel heuristic: 59s (best bound -1.5)
Elapsed time for NoRel heuristic: 66s (best bound -1.5)
Elapsed time for NoRel heuristic: 72s (best bound -1.5)
Elapsed time for NoRel heuristic: 83s (best bound -1.5)
Elapsed time for NoRel heuristic: 89s (best bound -1.5)
Elapsed time for NoRel heuristic: 95s (best bound -1.5)
Found heuristic solution: objective 1.5085565
Elapsed time for NoRel heuristic: 108s (best bound -1.5)
Found heuristic solution: objective 1.4859919
Elapsed time for NoRel heuristic: 114s (best bound -1.5)
Found heuristic solution: objective 1.1999996
Elapsed time for NoRel heuristic: 121s (best bound -1.5)
Root relaxation presolved: 11957 rows, 1054 columns, 127557 nonzeros


Root simplex log...

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -9.8036828e+01   2.450518e+04   0.000000e+00    121s
     353   -1.5000000e+00   0.000000e+00   0.000000e+00    121s
     353   -1.5000000e+00   0.000000e+00   0.000000e+00    121s

Root relaxation: objective -1.500000e+00, 353 iterations, 0.16 seconds (0.35 work units)

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

     0     0   -1.50000    0   94    1.20000   -1.50000   225%     -  121s
     0     0   -1.50000    0   93    1.20000   -1.50000   225%     -  122s
     0     0   -1.50000    0   93    1.20000   -1.50000   225%     -  122s
     0     0   -1.50000    0   86    1.20000   -1.50000   225%     -  124s
     0     0   -1.50000    0   87    1.20000   -1.50000   225%     -  125s
     0     0   -1.50000    0   86    1.20000   -1.50000   225%     -  125s
     0     0   -1.50000    0   86    1.20000   -1.50000   225%     -  126s
     0     0   -1.50000    0   86    1.20000   -1.50000   225%     -  126s
     0     0   -1.50000    0   86    1.20000   -1.50000   225%     -  127s
H    0     0                       1.1506758   -1.50000   230%     -  127s
     0     0   -1.50000    0   86    1.15068   -1.50000   230%     -  127s
     0     0   -1.50000    0   88    1.15068   -1.50000   230%     -  128s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  129s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  130s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  130s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  131s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  131s
     0     0   -1.50000    0   87    1.15068   -1.50000   230%     -  131s
H    0     0                       1.1506746   -1.50000   230%     -  154s
     0     2   -1.50000    0   87    1.15067   -1.50000   230%     -  155s
H   31    33                       1.1506741   -1.50000   230%   381  157s
H   33    33                       1.1341423   -1.50000   232%   371  157s
H   67    67                       1.0599894   -1.50000   242%   210  181s
   936   883    0.83765  173    -    1.05999   -1.50000   242%  24.4  189s
   971   892   -1.02710   37  200    1.05999   -1.50000   242%  25.4  229s
H  976   892                       1.0599883   -1.50000   242%  25.4  233s
   979   926   -1.50000   37   68    1.05999   -1.50000   242%  25.6  237s
  1264  1177   -1.50000   41   73    1.05999   -1.50000   242%  22.0  255s
  2063  1822   -1.50000   73   72    1.05999   -1.50000   242%  16.3  266s
  2382  2084    0.11644  224   87    1.05999   -1.50000   242%  15.0  523s
  2385  2086    0.23868   49   89    1.05999   -1.50000   242%  15.0  526s
  2386  2087    0.03451  128   87    1.05999   -1.50000   242%  15.0  534s
  2388  2088    0.75025  242   87    1.05999   -1.50000   242%  15.0  535s
  2398  2095    0.07609   27   88    1.05999   -1.50000   242%  14.9  540s
  2406  2100    0.76476  223   87    1.05999   -1.50000   242%  14.9  545s
  2408  2101    0.36287  100   87    1.05999   -1.50000   242%  14.9  555s
  2439  2123   -0.37483   19   92    1.05999   -1.50000   242%  25.3  567s
  2472  2137    0.92600   23    1    1.05999   -1.50000   242%  26.2  571s
  2949  2432   -0.09963   29   72    1.05999   -1.50000   242%  28.5  586s
  3014  2418   -1.50000   30   78    1.05999   -1.50000   242%  28.5  596s
  3109  2481   -1.50000   31   78    1.05999   -1.50000   242%  28.2  610s
  5333  3593   -1.50000   42   80    1.05999   -1.50000   242%  22.6  615s
 11334  7971   -1.50000   55   76    1.05999   -1.50000   242%  16.6  620s
 14262 10227   -0.37567   61   67    1.05999   -1.50000   242%  15.2  643s
 14570 10919   -1.50000   63   77    1.05999   -1.50000   242%  15.2  645s
 19699 15376   -1.50000   72   77    1.05999   -1.50000   242%  12.7  667s
 22595 20539   -1.50000   82   77    1.05999   -1.50000   242%  12.5  670s
 35736 31687   -1.50000   92   79    1.05999   -1.50000   242%   9.3  675s
 44542 38883    1.05253  592    1    1.05999   -1.50000   242%   8.5  681s
 49957 43975   -1.50000  115   82    1.05999   -1.50000   242%   8.3  685s
H53127 47018                       1.0438069   -1.50000   244%   8.7  689s
 54518 48097   -1.50000  133   83    1.04381   -1.50000   244%   8.8  690s
H54954 47178                       1.0034430   -1.50000   249%   8.8  714s
H54958 47178                       1.0034430   -1.50000   249%   8.8  714s
H54974 46764                       0.9587022   -1.50000   256%   8.8  719s
H54975 46743                       0.9506084   -1.50000   258%   8.8  722s
 56496 47885   -1.50000  139   83    0.95061   -1.50000   258%   8.8  745s
 56498 47885   -0.03215  657   63    0.95061   -1.50000   258%   8.8  755s
H56501 47885                       0.9506084   -1.50000   258%   8.8  761s
H56502 47885                       0.9506084   -1.50000   258%   8.8  762s
 56505 47885    0.67621  405   43    0.95061   -1.50000   258%   8.8  767s
 57963 49646   -1.50000  144   84    0.95061   -1.50000   258%   8.8  778s
 61328 52080   -0.06079  150   77    0.95061   -1.50000   258%   8.8  780s
 63605 52740   -1.50000  173   82    0.95061   -1.50000   258%  10.0  785s
 66440 55026   -0.05786  180   66    0.95061   -1.50000   258%  10.2  808s
H66446 55026                       0.9506073   -1.50000   258%  10.2  811s
 66874 55546   -1.50000  183   84    0.95061   -1.50000   258%  10.2  816s
 67567 55547   -1.50000  186   85    0.95061   -1.50000   258%  10.2  845s
 67582 55572   -0.04898  186   72    0.95061   -1.50000   258%  10.3  854s
 67633 55631   -0.03314  188   87    0.95061   -1.50000   258%  10.3  855s
 73768 60793   -1.50000  209   90    0.95061   -1.50000   258%  10.5  866s
 80804 66275   -1.50000  222   81    0.95061   -1.50000   258%  10.2  870s
 86051 70213   -1.50000  231   83    0.95061   -1.50000   258%  10.1  880s
 92723 75260   -1.50000  246   81    0.95061   -1.50000   258%   9.8  885s
 97870 78776   -1.50000  267   81    0.95061   -1.50000   258%   9.8  890s
 98347 78830   -1.50000  270   81    0.95061   -1.50000   258%   9.9  897s
 100816 80393   -1.50000  282   80    0.95061   -1.50000   258%  10.0  900s
 101278 80448   -1.50000  287   81    0.95061   -1.50000   258%  10.1  907s
 101992 80630   -0.04179  297   84    0.95061   -1.50000   258%  10.3  910s
 105466 83567   -1.50000  307   80    0.95061   -1.50000   258%  10.3  915s
 107827 85415   -1.50000  321   79    0.95061   -1.50000   258%  10.5  923s
 109129 86386   -1.50000  327   80    0.95061   -1.50000   258%  10.6  932s
 110270 87010   -1.50000  335   79    0.95061   -1.50000   258%  10.6  935s
 112989 89503   -0.02829  355   71    0.95061   -1.50000   258%  10.8  948s
 114463 90314   -1.50000  363   80    0.95061   -1.50000   258%  10.8  950s
 116065 91776    0.90710  578    1    0.95061   -1.50000   258%  10.9  955s
 118505 94119   -1.50000  375   81    0.95061   -1.50000   258%  10.9  965s
 121165 94975   -0.02855  390   67    0.95061   -1.50000   258%  11.1  971s
 121850 95163   -1.50000  403   80    0.95061   -1.50000   258%  11.4  980s
 122347 95604   -1.50000  428   82    0.95061   -1.50000   258%  11.9  985s
 122442 95667   -1.50000  433   80    0.95061   -1.50000   258%  12.0  991s
 122679 95848    0.67621  686   41    0.95061   -1.50000   258%  12.2  996s
 123005 96132   -1.50000  451   80    0.95061   -1.50000   258%  12.5 1004s
 123098 96359   -1.50000  453   82    0.95061   -1.50000   258%  12.6 1006s
 123385 96739   -0.01571  457   81    0.95061   -1.50000   258%  12.7 1012s
 124479 97266   -0.07440  470   63    0.95061   -1.50000   258%  12.8 1045s
 124488 97870   -1.50000  471   82    0.95061   -1.50000   258%  12.8 1051s
 125147 98216   -0.05160  476   76    0.95061   -1.50000   258%  12.9 1058s
 125690 98432   -1.50000  489   81    0.95061   -1.50000   258%  13.1 1068s
 125813 98596   -1.50000  492   80    0.95061   -1.50000   258%  13.2 1070s
 126022 99617    0.00000  496   71    0.95061   -1.50000   258%  13.3 1078s
 127398 100719   -1.50000  499   81    0.95061   -1.50000   258%  13.3 1080s
 128706 102133   -1.50000  505   81    0.95061   -1.50000   258%  13.3 1098s
 130442 103552   -1.50000  508   81    0.95061   -1.50000   258%  13.2 1100s
 133928 105479   -1.50000  517   81    0.95061   -1.50000   258%  13.0 1108s
 134406 105479    0.94858  524    -    0.95061   -1.50000   258%  13.0 1111s
 136033 107843   -1.50000  523   81    0.95061   -1.50000   258%  13.0 1115s
 141214 111960   -1.50000  535   81    0.95061   -1.50000   258%  12.8 1120s
 145784 114096   -1.50000  539   81    0.95061   -1.50000   258%  12.6 1125s
 149282 115804   -1.50000  550   81    0.95061   -1.50000   258%  12.6 1130s
 149658 116516   -1.50000  553   86    0.95061   -1.50000   258%  12.6 1139s
 150522 116775   -0.02673  553   78    0.95061   -1.50000   258%  12.5 1140s
 152920 118837    0.94041  318    -    0.95061   -1.50000   258%  12.5 1145s
 155163 119929   -1.50000  578   82    0.95061   -1.50000   258%  12.7 1153s
 155356 120406   -1.50000  584   82    0.95061   -1.50000   258%  12.7 1155s
 157081 121521   -1.50000  594   82    0.95061   -1.50000   258%  12.8 1168s
 157502 122058   -1.50000  599   83    0.95061   -1.50000   258%  12.8 1170s
 158862 123116   -1.50000  620   85    0.95061   -1.50000   258%  13.1 1175s
 160978 124630   -1.50000  633   83    0.95061   -1.50000   258%  13.1 1193s
 161379 125091   -1.50000  641   84    0.95061   -1.50000   258%  13.2 1195s
 163078 127280   -1.50000  658   84    0.95061   -1.50000   258%  13.3 1200s
 165363 128394   -1.50000  675   83    0.95061   -1.50000   258%  13.5 1206s
 166011 128498   -1.50000  680   83    0.95061   -1.50000   258%  13.5 1215s
 167371 129797   -1.50000  690   84    0.95061   -1.50000   258%  13.6 1220s
 168332 130008   -1.50000  708   82    0.95061   -1.50000   258%  13.8 1236s
 169232 130655   -0.02625  723   79    0.95061   -1.50000   258%  14.0 1240s
 170131 130829   -0.01912  740   78    0.95061   -1.50000   258%  14.2 1271s
 170354 131097   -1.50000  754   82    0.95061   -1.50000   258%  14.4 1280s
 170594 131283   -1.50000  768   82    0.95061   -1.50000   258%  14.6 1290s
 170850 131640   -1.50000  781   83    0.95061   -1.50000   258%  14.8 1297s
 171371 132530   -1.50000  798   82    0.95061   -1.50000   258%  15.0 1301s
 173265 133829   -1.50000  817   82    0.95061   -1.50000   258%  15.1 1310s
 174112 134115   -0.22648  826   76    0.95061   -1.50000   258%  15.2 1315s
(some outputs omitted)
 393327 289951    0.67621  741   41    0.95061   -0.44566   147%  16.3 1650s
 396032 291924    0.67621  814   42    0.95061   -0.44566   147%  16.4 1655s
 401612 295609    0.67020  726   53    0.95061   -0.44532   147%  16.4 1660s
 405102 297616    0.94630  583   38    0.95061   -0.44532   147%  16.4 1666s
 406626 298396    0.67621  589   59    0.95061   -0.44532   147%  16.5 1670s
 407063 298784    0.67621  634   57    0.95061   -0.44532   147%  16.7 1675s
 407692 299857    0.67621  664   56    0.95061   -0.44532   147%  16.8 1680s
 411486 302915    0.67621  703   61    0.95061   -0.44532   147%  16.8 1685s
 412450 304404    0.67621  746   58    0.95061   -0.44532   147%  16.9 1691s
 414950 305107    0.67621  777   62    0.95061   -0.44532   147%  17.0 1695s
 415475 305872    0.67621  880   60    0.95061   -0.44532   147%  17.1 1701s
 417410 308203    0.67621  919   62    0.95061   -0.44532   147%  17.2 1705s
 420465 309857 infeasible  811         0.95061   -0.44532   147%  17.2 1710s
 424224 312630     cutoff  594         0.95061   -0.44532   147%  17.2 1715s
 427590 314970     cutoff  625         0.95061   -0.44532   147%  17.2 1720s
 429110 315458 infeasible  651         0.95061   -0.44532   147%  17.3 1725s
 429909 316534    0.82955  674   43    0.95061   -0.44532   147%  17.3 1730s
 433892 320071     cutoff  703         0.95061   -0.44532   147%  17.3 1736s
 437042 322472 infeasible  726         0.95061   -0.44532   147%  17.3 1740s
 440585 324858 infeasible  753         0.95061   -0.44532   147%  17.3 1745s
 445095 327789    0.67621  781   53    0.95061   -0.44532   147%  17.3 1751s
 447444 329485    0.67621  799   52    0.95061   -0.44532   147%  17.3 1755s
 449167 330020 infeasible  824         0.95061   -0.44532   147%  17.4 1760s
 450680 330387    0.67621  860   51    0.95061   -0.44532   147%  17.5 1765s
 451421 331466     cutoff  911         0.95061   -0.44532   147%  17.7 1771s
 454540 334164    0.66787  537   47    0.95061   -0.43885   146%  17.7 1775s
 458555 338941    0.67621  634   49    0.95061   -0.43885   146%  17.6 1780s
 466376 345746    0.67621  680   45    0.95061   -0.43885   146%  17.5 1785s
 472708 349662    0.67621  725   48    0.95061   -0.43885   146%  17.3 1790s
 476946 353203    0.67621  754   47    0.95061   -0.43885   146%  17.3 1795s
 478382 353984    0.67621  798   48    0.95061   -0.43885   146%  17.4 1800s
 480203 356491    0.67621  846   47    0.95061   -0.43885   146%  17.4 1806s
 485464 359849    0.67621  891   46    0.95061   -0.43885   146%  17.4 1810s
 488949 361879    0.94978  683    1    0.95061   -0.43885   146%  17.3 1816s
 493025 366248    0.94812  246   15    0.95061   -0.39584   142%  17.2 1820s
 496289 367622     cutoff  565         0.95061   -0.39584   142%  17.3 1825s
 502034 371290    0.67371  834   41    0.95061   -0.39584   142%  17.2 1830s
 506138 373726    0.67621  712   50    0.95061   -0.38527   141%  17.3 1835s
 509753 376338    0.94095  629    -    0.95061   -0.38527   141%  17.3 1843s
 511502 376568    0.67621  753   45    0.95061   -0.38527   141%  17.3 1845s
 514779 377775    0.67621  777   46    0.95061   -0.38527   141%  17.3 1850s
 517118 379273    0.67621  818   45    0.95061   -0.38527   141%  17.3 1855s
 520117 381059    0.67621  858   42    0.95061   -0.38527   141%  17.4 1860s
 520860 381588    0.67621  906   45    0.95061   -0.38527   141%  17.5 1865s
 521404 382903    0.80473  135   30    0.95061   -0.36791   139%  17.6 1870s
 521888 382903    0.95045  576    -    0.95061   -0.36791   139%  17.6 1876s
 524787 384193    0.67621  676   59    0.95061   -0.36791   139%  17.6 1880s
 525672 384837    0.67621  716   56    0.95061   -0.36791   139%  17.7 1885s
 526190 385399    0.67621  756   57    0.95061   -0.36791   139%  17.8 1890s
 527980 386535    0.67621  805   55    0.95061   -0.36791   139%  17.9 1895s
 529036 386939    0.67621  710   57    0.95061   -0.36791   139%  18.0 1900s
 529393 387325    0.67621  751   56    0.95061   -0.36791   139%  18.1 1905s
 531012 388371    0.67621  798   55    0.95061   -0.36791   139%  18.2 1911s
 531813 389307    0.67621  817   57    0.95061   -0.36791   139%  18.3 1915s
 534616 390678    0.67621  867   57    0.95061   -0.36791   139%  18.3 1921s
 535426 391354    0.67621  900   55    0.95061   -0.36791   139%  18.4 1925s
 536931 392077    0.67621  763   58    0.95061   -0.36791   139%  18.5 1931s
 538351 392928    0.67621  806   54    0.95061   -0.36791   139%  18.6 1937s
 539280 393723    0.67621  845   54    0.95061   -0.36791   139%  18.7 1940s
 540654 394622    0.67621  901   52    0.95061   -0.36791   139%  18.8 1947s
 541854 395929    0.67621  867   64    0.95061   -0.36791   139%  18.9 1952s
 543316 396149    0.67621  902   63    0.95061   -0.36791   139%  19.0 1957s
 543482 397065    0.67621  919   61    0.95061   -0.36791   139%  19.0 1960s
 546293 398201    0.67621  894   62    0.95061   -0.36791   139%  19.1 1966s
 549598 401412    0.67621  928   60    0.95061   -0.36791   139%  19.1 1971s
 553437 404072    0.66837  912   55    0.95061   -0.36791   139%  19.1 1975s
 562973 409989    0.70922  939   59    0.95061   -0.36791   139%  18.9 1980s
 564539 410755    0.94576  269    4    0.95061   -0.36312   138%  18.9 1986s
 568570 413530    0.30379  667   62    0.95061   -0.34097   136%  18.8 1990s
 (omitted some outputs)
 640102 466701    0.67621  414   33    0.95061   -0.31018   133%  17.7 2065s
 643970 468851    0.67621  446   32    0.95061   -0.31018   133%  17.7 2071s
 647524 470995    0.67466  618   31    0.95061   -0.31018   133%  17.7 2075s
 650860 473266     cutoff  379         0.95061   -0.31018   133%  17.6 2080s
 651427 473791    0.94901  594    1    0.95061   -0.31018   133%  17.7 2085s
 655718 477449    0.67621  115   51    0.95061   -0.31018   133%  17.6 2091s
 657847 478521    0.67621  166   39    0.95061   -0.31018   133%  17.7 2096s
 661605 481173    0.67621  223   41    0.95061   -0.31018   133%  17.6 2100s
 665404 483570    0.67621  254   36    0.95061   -0.31018   133%  17.6 2105s
 666743 484422    0.67621  297   36    0.95061   -0.31018   133%  17.6 2110s
 669031 486411    0.67621  341   36    0.95061   -0.31018   133%  17.6 2115s
 670921 488016    0.67621  409   37    0.95061   -0.31018   133%  17.7 2121s
 672740 488188    0.67621  448   37    0.95061   -0.31018   133%  17.7 2125s
 675613 490514    0.67621  493   36    0.95061   -0.31018   133%  17.7 2130s
 678214 491779    0.67621  531   36    0.95061   -0.31018   133%  17.7 2135s
 683605 495470    0.67621  568   36    0.95061   -0.31018   133%  17.6 2140s
 686678 496136    0.67621  604   36    0.95061   -0.31018   133%  17.6 2145s
 688221 497943    0.67621  619   36    0.95061   -0.31018   133%  17.6 2151s
 690150 498841    0.67621  672   36    0.95061   -0.31018   133%  17.7 2155s
 691703 499777    0.67621  734   38    0.95061   -0.31018   133%  17.7 2160s
9 410755    0.94576  269    4    0.95061   -0.36312   138%  18.9 1986s
 568570 413530    0.30379  667   62    0.95061   -0.34097   136%  18.8 1990s
 576947 420502    0.67621  787   56    0.95061   -0.33162   135%  18.7 1995s
 578320 421075    0.67621  796   53    0.95061   -0.33162   135%  18.6 2000s
 578628 421262    0.94989  624    -    0.95061   -0.33162   135%  18.7 2005s
 582445 423811    0.67621  833   51    0.95061   -0.33162   135%  18.6 2010s
 584802 425089    0.67621  861   50    0.95061   -0.33162   135%  18.6 2015s
(omitted some outputs)
 615729 445408    0.95047  691    1    0.95061   -0.31018   133%  18.1 2045s
 624466 453034    0.94784  515   25    0.95061   -0.31018   133%  17.9 2050s
 627303 455855    0.67621  327   46    0.95061   -0.31018   133%  17.9 2055s
 633859 460941    0.67621  362   34    0.95061   -0.31018   133%  17.8 2060s
 640102 466701    0.67621  414   33    0.95061   -0.31018   133%  17.7 2065s
 643970 468851    0.67621  446   32    0.95061   -0.31018   133%  17.7 2071s
 647524 470995    0.67466  618   31    0.95061   -0.31018   133%  17.7 2075s
 650860 473266     cutoff  379         0.95061   -0.31018   133%  17.6 2080s
 651427 473791    0.94901  594    1    0.95061   -0.31018   133%  17.7 2085s
 655718 477449    0.67621  115   51    0.95061   -0.31018   133%  17.6 2091s
 657847 478521    0.67621  166   39    0.95061   -0.31018   133%  17.7 2096s
 661605 481173    0.67621  223   41    0.95061   -0.31018   133%  17.6 2100s
 665404 483570    0.67621  254   36    0.95061   -0.31018   133%  17.6 2105s
 

Related to

1

Comments

7 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi,

    The behavior you see makes sense. The reason is the constraint

    I have one quadratic constraint that restricts the continuous variables on a unit ball.

    which most likely introduces a lot of symmetry into the model. The best way to deal with the symmetry is to introduce an ordering of variables, e.g., \(x_1 \leq x_2 \leq x_3 \leq ...\).

    Out of curiosity, could you please share the model? Maybe there is something we could improve on. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Best regards, 
    Jaromił

    0
  • Haoge Chang
    • Edited
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromił,

    Thank you for your prompt response! 

    1. I want to check how the BestBound is generated. Since my problem is a minimization problem, the Bestbound is the minimum (not the maximum) of all relaxations at the leaf nodes, right? Does it mean that, if the Bestbound is not improving, there are lots of leaf nodes that need to be explored?

    2. Regarding the ordering constraints, there is no guarantee that a particular ordering is optimal for my problem. Trying out all (#continuous variable)! seems impossible.

    3. Here is the link to the replication files

    https://drive.google.com/drive/folders/1mt-2IkEsLdh5vk4hafYNmu5Y1hj_PduV?usp=drive_link 

    'Trial_0919.m' will replicate the results I posted above.

    The file 'CR_draw.m', 'D_cr.m', and 'gen_diag_matrix_cr.m' are auxiliary files that generate inputs to the main file. 

    'Trial_0911.m' solves the same problem as the one in 'Trial_0919.m', but with fewer constraints. Unfortunately, Trial_0911.m works better than Trial_0919.m based on my experiments. Trial_0911.m converges in one hour on a computer node with 48 cores. I have not tried Trial_0919.m, but on my computer Trial_0919.m performs worse.

    Finally, let me briefly mention the setup of my problem. This is a Value-at-Risk problem, where I want to minimize the quantile of a linear combination of random variables with weights that square-sum to 1.

    Decision Variable:

    1. w (continuous): a n-dimensional vector restricted on a unit ball;

    2. D_i, i=1,...,n_s: binary variable 

    3. t (continuous): a scalar: We have a priori knowledge that t is between -1.5 to 3. 

    Parameters:

    1. \{Z_i \}_{i=1}^{ns} a set of n-dimensional vector, cardinality=ns

    2. qmax: a scalar: it would be on the order of sqrt( |#continuous variable|)

    4. qmin: a scalar: it would be on the order of -sqrt( |#continuous variable|)

    5. q_alpha: a scalar: it is set to -3

    6. ns: number of binary variables

    7. alpha(ns): a small positive number: for example, 0.05 or 0.025

    The problem Trial_0911.m solves

    The first set of constraints requires D_i=0 if w'Z_i-t > q_{max}. The second constraint restricts the number of D_i. 

    The file Trial_0919.m solves

    where cij = ||Z_i-Z_j||, the Euclidean distance between Z_i and Z_j. The set of constraint (3) requires D_i and D_j to obey the order of w'Z_i and w'Z_j. There are ns * (ns-1) such constraints. I know the optimal solution will satisfy. There are too many of them so I subsampled some in my implementation.

    The additional set of constraints (2) adds on (1), which requires that the condition D_i=0 and w'Z_i-t > q_{max} mutually imply each other (up to the equality sign), as oppose to a one-way direction if we only impose (1).

    Thank you!

    Haoge

     

     

     

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Haoge,

    1. I want to check how the BestBound is generated. Since my problem is a minimization problem, the Bestbound is the minimum (not the maximum) of all relaxations at the leaf nodes, right?

    Correct.

    Does it mean that, if the Bestbound is not improving, there are lots of leaf nodes that need to be explored?

    Yes, additionally this means that there may be symmetry involved and the solver has to explore all symmetrical areas before the lower bound improves. Usually, adding more user knowledge as constraint helps to overcome such cases. Of course this is not always possible.

    2. Regarding the ordering constraints, there is no guarantee that a particular ordering is optimal for my problem. Trying out all (#continuous variable)! seems impossible.

    There may be no guarantee that a particular ordering is optimal, but is there a guarantee that if an ordering is optimal, that you can swap some variable values while remaining the same optimal objective value? If so, then you should try adding this knowledge into the model.

    3. Here is the link to the replication files

    Could you please generate an MPS or LP file via the gurobi_write() function and share the generated model file? This would avoid user error on my side.

    Best regards, 
    Jaromił

    0
  • Haoge Chang
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromił,

    Thank you very much for the clarification and explanation!

    I uploaded the mps file on to the 

    https://drive.google.com/drive/folders/1mt-2IkEsLdh5vk4hafYNmu5Y1hj_PduV?usp=drive_link 

    They are under the name trial_0919.mps and trial_0911.mps.

    Looking forward to hearing from you!

    Thank you!

    Haoge

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Haoge,

    I guess that sticking to the trial_911 formulation looks more promising. I cannot explain why the trial_919 formulation performs so much worse.

    I think that the best way to improve performance now is to provide more model specific knowledge that you have. For example, add bounds \([-1.5, 3]\) for variable \(t\). In best case, you might be able to deduce a better lower bound for variable \(t\), maybe it is always \(t\geq \delta > 0\) for some \(\delta > 0\)?

    Do you think that one could say something about the values of the \(Z_i\) variables? For example, could you say that the values in an optimal solution for some of those variables are rather close to \(1\) and for others close to \(0\) or should all always be close to \(\approx 0.5\) (or any other value)? It might make sense to introduce finite bounds, e.g., \(-0.75 \leq Z_i \leq 0.75\), if any are available. It would be even better if you somehow have the information which of the variables should be positive and which negative.

    Playing with the MIPFocus might also bring some performance.

    Best regards, 
    Jaromił

    0
  • Haoge Chang
    Gurobi-versary
    First Comment
    First Question

    Hi Jaromił,

    Thank you very much for the suggestions! Would you mind if I ask you three additional questions?

    1. I saw in the documentation of the MIPFocus parameter that it only affects MIP problems. Will it also affect the MIQCP problem that I am solving?

    2. Would you mind explaining what the Symmetry parameter does? I wonder if it may be an additional parameter that I can play around, since you mentioned symmetry in your comment.

    3. If I have a guess (that is, a feasible solution that, I think, is close to the optimal value), is there a way that I can incorporate it into my problem? Do you think it would increase the performance, in particular, in terms of closing the distance with the BestBound?

    Thank you!

    Haoge

    Haoge

     

     

     

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Haoge,

    I saw in the documentation of the MIPFocus parameter that it only affects MIP problems. Will it also affect the MIQCP problem that I am solving?

    Yes, it will always affect quadratic models since these are handled in the same way as MIPs.

    Would you mind explaining what the Symmetry parameter does? I wonder if it may be an additional parameter that I can play around, since you mentioned symmetry in your comment.

    The Symmetry parameter controls Gurobi's symmetry detection level. A higher setting means that more time is spent to find symmetries. I don't think that this parameter will help your model, because the symmetry you construct through the "border of an n-dimensional ball" constraint is not something that can be exploited in general. It is just often the case that with additional model knowledge, in such a case, it is actually correct to introduce symmetry breaking constraints of the form \(x_1 \leq x_2 \leq \dots\). However, this has to be decided by the modeler.

    If I have a guess (that is, a feasible solution that, I think, is close to the optimal value), is there a way that I can incorporate it into my problem? Do you think it would increase the performance, in particular, in terms of closing the distance with the BestBound?

    You can provide your guess as described in the Knowledge Base article How do I use MIP starts? Often a good initial feasible point improves performance. However, there is no guarantee.

    I think that shrinking the domains of the variables with the knowledge you have together with a good initial point might be the way to go here.

    Maybe you could also do some manual presolving and check whether there are some constraints which can be dropped from the beginning due to some properties that you know about.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post