Skip to main content

BestBd of MILP hardly moves

Answered

Comments

4 comments

  • Suyue Xu
    Curious
    Gurobi-versary
    Conversationalist

    as the big-M method is introduced to solve the C&CG subpoblem,I'm wondering if the value of constant M could make any difference.So I changed the constant value from 10^6 to 10^4,here is the log :

    Set parameter Username
    Set parameter TimeLimit to value 600
    Set parameter CrossoverBasis to value 0
    Set parameter NodefileDir to value ""
    Set parameter NoRelHeurTime to value 200
    Set parameter PreSOS2BigM to value 0
    Set parameter TuneTrials to value 3
    Academic license - for non-commercial use only - expires 2024-06-06
    Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)

    CPU model: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz, instruction set [SSE2|AVX|AVX2]
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

    Optimize a model with 34225 rows, 18648 columns and 83412 nonzeros
    Model fingerprint: 0xa66355f9
    Variable types: 10920 continuous, 7728 integer (7728 binary)
    Coefficient statistics:
      Matrix range     [3e-02, 1e+04]
      Objective range  [6e-13, 1e+03]
      Bounds range     [1e+00, 1e+00]
      RHS range        [6e-13, 1e+04]
    Presolve removed 28884 rows and 15024 columns
    Presolve time: 0.64s
    Presolved: 5341 rows, 3624 columns, 21129 nonzeros
    Variable types: 2440 continuous, 1184 integer (1182 binary)
    Starting NoRel heuristic
    Found phase-1 solution: relaxation 3.52895e+07
    Found phase-1 solution: relaxation 3.52765e+07
    Found phase-1 solution: relaxation 3.52661e+07
    Found phase-1 solution: relaxation 3.50789e+07
    Found phase-1 solution: relaxation 37716.3
    Found phase-1 solution: relaxation 37559.8
    Found phase-1 solution: relaxation 35293
    Found phase-1 solution: relaxation 35199.1
    Found phase-1 solution: relaxation 32906.8
    Found phase-1 solution: relaxation 31663.4
    Found phase-1 solution: relaxation 29934.9
    Found phase-1 solution: relaxation 28062.8
    Found phase-1 solution: relaxation 26299.4
    Found phase-1 solution: relaxation 25944.7
    Found phase-1 solution: relaxation 25297.4
    Found phase-1 solution: relaxation 24461.1
    Found phase-1 solution: relaxation 24270.5
    Found phase-1 solution: relaxation 23919.5
    Found phase-1 solution: relaxation 22990.9
    Found phase-1 solution: relaxation 22827.8
    Found phase-1 solution: relaxation 22670.1
    Found phase-1 solution: relaxation 21586.7
    Found phase-1 solution: relaxation 21037.7
    Found phase-1 solution: relaxation 19891.6
    Found phase-1 solution: relaxation 17855.8
    Found phase-1 solution: relaxation 17844.4
    Found phase-1 solution: relaxation 17579.4
    Found phase-1 solution: relaxation 17578.4
    Found phase-1 solution: relaxation 16859.4
    Found phase-1 solution: relaxation 16858.4
    Found phase-1 solution: relaxation 16179.4
    Found phase-1 solution: relaxation 14428.1
    Found phase-1 solution: relaxation 14405.8
    Found phase-1 solution: relaxation 14393.5
    Found phase-1 solution: relaxation 14197.2
    Found phase-1 solution: relaxation 14065.2
    Found phase-1 solution: relaxation 13951.2
    Found phase-1 solution: relaxation 13717.1
    Elapsed time for NoRel heuristic: 5s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 13582.6
    Found phase-1 solution: relaxation 13422.7
    Found phase-1 solution: relaxation 13398.3
    Found phase-1 solution: relaxation 12965.1
    Found phase-1 solution: relaxation 12825.4
    Found phase-1 solution: relaxation 12821.4
    Found phase-1 solution: relaxation 2804.28
    Found phase-1 solution: relaxation 2725.47
    Found phase-1 solution: relaxation 2684.4
    Found phase-1 solution: relaxation 1815.77
    Found phase-1 solution: relaxation 1579.38
    Found phase-1 solution: relaxation 1579.21
    Found phase-1 solution: relaxation 1146.84
    Found phase-1 solution: relaxation 1112.28
    Found phase-1 solution: relaxation 1110.04
    Found phase-1 solution: relaxation 1110.04
    Found phase-1 solution: relaxation 1091.52
    Found phase-1 solution: relaxation 1072.18
    Found phase-1 solution: relaxation 1011.42
    Elapsed time for NoRel heuristic: 10s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 931.928
    Found phase-1 solution: relaxation 915.943
    Found phase-1 solution: relaxation 913.943
    Found phase-1 solution: relaxation 891.207
    Found phase-1 solution: relaxation 529.64
    Found phase-1 solution: relaxation 511.603
    Found phase-1 solution: relaxation 511.603
    Found phase-1 solution: relaxation 483.005
    Found phase-1 solution: relaxation 467.778
    Found phase-1 solution: relaxation 437.803
    Elapsed time for NoRel heuristic: 16s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 437.67
    Found phase-1 solution: relaxation 335.91
    Found phase-1 solution: relaxation 318.605
    Found phase-1 solution: relaxation 120.7
    Found phase-1 solution: relaxation 118.261
    Found phase-1 solution: relaxation 113.412
    Found phase-1 solution: relaxation 111.522
    Elapsed time for NoRel heuristic: 21s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 15
    Found phase-1 solution: relaxation 12
    Elapsed time for NoRel heuristic: 27s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 12
    Elapsed time for NoRel heuristic: 32s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 11
    Elapsed time for NoRel heuristic: 38s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 10
    Elapsed time for NoRel heuristic: 47s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 55s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 64s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 72s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 80s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 9
    Elapsed time for NoRel heuristic: 91s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 97s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 111s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 123s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 130s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 148s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 161s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 176s (best bound -9.48039e+06)
    Found phase-1 solution: relaxation 5
    Elapsed time for NoRel heuristic: 190s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 195s (best bound -9.48039e+06)
    Elapsed time for NoRel heuristic: 208s (best bound -9.48039e+06)

    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0   -1.8401646e+08   2.885733e+05   0.000000e+00    209s
        4287   -9.4803881e+06   0.000000e+00   0.000000e+00    209s

    Root relaxation: objective -9.480388e+06, 4287 iterations, 0.09 seconds (0.06 work units)

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

         0     0 -9480388.1    0   88          - -9480388.1      -     -  209s
         0     0 -8960557.7    0  125          - -8960557.7      -     -  209s
         0     0 -8865934.9    0  125          - -8865934.9      -     -  209s
         0     0 -8801680.4    0  121          - -8801680.4      -     -  209s
         0     0 -8766215.9    0  122          - -8766215.9      -     -  209s
         0     0 -8749661.2    0  122          - -8749661.2      -     -  209s
         0     0 -8749661.2    0  122          - -8749661.2      -     -  209s
         0     0 -8713024.3    0  117          - -8713024.3      -     -  209s
         0     0 -8712874.2    0  117          - -8712874.2      -     -  209s
         0     0 -8700112.1    0  119          - -8700112.1      -     -  209s
         0     0 -8700054.0    0  120          - -8700054.0      -     -  209s
         0     0 -8700054.0    0  119          - -8700054.0      -     -  209s
         0     0 -8700054.0    0  119          - -8700054.0      -     -  209s
         0     0 -8700054.0    0  120          - -8700054.0      -     -  209s
         0     0 -8700054.0    0  120          - -8700054.0      -     -  209s
         0     0 -8700054.0    0  114          - -8700054.0      -     -  209s
         0     0 -8313874.2    0  114          - -8313874.2      -     -  209s
         0     2 -8313874.2    0  114          - -8313874.2      -     -  210s
      1064  1012 -4351658.8   47  112          - -7938954.4      -  26.7  215s
      1067  1014 -3352068.3   60  109          - -7938954.4      -  26.7  220s
      1760  1472 -214308.53  118   34          - -7845205.0      -  17.1  225s
    * 2366  1461             179    -214420.4510 -7726247.4  3503%  17.9  225s
    * 2565  1402             229    -250091.9937 -7726247.4  2989%  18.5  226s
      4186  2361 -6031490.6   18  120 -250091.99 -7417377.0  2866%  21.8  230s
    * 6898  4411             156    -250273.5190 -7234558.6  2791%  24.4  234s
    * 7181  4372             154    -250535.7058 -7229166.6  2785%  24.2  234s
      7310  4653 -2769168.2   78  125 -250535.71 -7223175.0  2783%  24.6  235s
      9918  6679 -3521849.7   70  139 -250535.71 -7121080.9  2742%  25.5  240s
    *12061  8357             205    -250941.1222 -7066082.1  2716%  25.5  242s
    *12441  8444             181    -253463.1323 -7035693.7  2676%  25.6  243s
     13814  9331 -262361.81  131   39 -253463.13 -6932375.4  2635%  25.5  245s
    *15126 10083             220    -254628.6374 -6915319.6  2616%  26.7  247s
    H17125 11037                    -262182.0860 -6875468.3  2522%  26.6  251s
     18745 12796 -4301973.7   45  143 -262182.09 -6826285.2  2504%  27.4  255s
    *19310 13169             215    -262923.8553 -6764632.5  2473%  27.3  255s
     20584 13981 -836507.11  130  114 -262923.86 -6742171.4  2464%  27.4  272s
     20595 13988 -2521012.9   79  206 -262923.86 -6742171.4  2464%  27.4  275s
     20603 13994 -5637842.2   26  180 -262923.86 -6742171.4  2464%  27.4  280s
     20610 13998 -1245085.5   87  188 -262923.86 -6742171.4  2464%  27.4  285s
     20618 14007 -6742171.4   22  199 -262923.86 -6742171.4  2464%  28.0  290s
     20971 14251 -3687552.7   66  196 -262923.86 -6539741.6  2387%  28.6  295s
     22458 14734     cutoff   72      -262923.86 -6468787.4  2360%  29.4  300s
     24862 15932 -3477883.4   65  211 -262923.86 -6319874.9  2304%  30.2  305s
    H25768 15510                    -263192.8512 -6195600.2  2254%  30.5  307s
    H25769 14744                    -265022.3301 -6195600.2  2238%  30.5  307s
     26505 15483 -845968.56  110  129 -265022.33 -6127243.5  2212%  30.8  310s
     28848 16718 -2414135.1   71  154 -265022.33 -6029341.7  2175%  32.0  315s
     31170 18108 -2837347.7   70  202 -265022.33 -5974578.9  2154%  33.1  321s
     32883 18728 -4042225.7   65  258 -265022.33 -5935873.3  2140%  34.1  325s
     35022 20196 -2925800.0   77  180 -265022.33 -5885268.0  2121%  34.6  330s
     37255 21236 -892581.34   61  116 -265022.33 -5833785.6  2101%  35.0  335s
     38986 21789 -907453.08   51  123 -265022.33 -5803992.5  2090%  35.5  340s
     40871 22746 -3887950.5   65  216 -265022.33 -5776410.6  2080%  36.1  345s
     42341 23637 -3678162.7   67  211 -265022.33 -5754121.5  2071%  36.5  350s
     44400 24854 -5392158.5   32  221 -265022.33 -5722090.1  2059%  37.1  355s
     46611 25826 -3027206.2   77  205 -265022.33 -5689489.9  2047%  37.6  361s
     48312 26498 -282971.13  118   99 -265022.33 -5674758.8  2041%  37.8  365s
     49788 26987 -4333708.4   44  195 -265022.33 -5663389.7  2037%  38.2  370s
     51818 27607 -2944502.7   68  214 -265022.33 -5650029.5  2032%  38.7  375s
     53482 28630 -2912379.5   80  202 -265022.33 -5640344.9  2028%  39.2  380s
     55290 29322 -926429.93  106  148 -265022.33 -5617223.0  2020%  39.6  385s
     56819 30088 -2767406.7   80  189 -265022.33 -5595039.2  2011%  40.1  390s
     58610 30609 -746622.15  113  138 -265022.33 -5584257.7  2007%  40.3  395s
     60827 31832 -637966.87   74  129 -265022.33 -5562796.3  1999%  40.7  400s
     62543 32860     cutoff   79      -265022.33 -5548081.9  1993%  41.1  405s
    H63616 33315                    -265022.8936 -5539002.9  1990%  41.4  408s
     63877 33856 -2765690.6   77  181 -265022.89 -5535979.3  1989%  41.4  410s
    H64750 33085                    -294634.2794 -5535979.3  1779%  41.6  412s
     65171 33723 -1102717.7   97  161 -294634.28 -5530849.0  1777%  41.8  415s
     67012 35217 -4698404.2   34  173 -294634.28 -5520142.9  1774%  42.3  420s
     68651 36535 -1172166.6   82  173 -294634.28 -5507695.2  1769%  42.6  425s
    H69803 35872                    -327632.4896 -5501934.2  1579%  43.0  428s
     70561 36637 -2588478.1   54  162 -327632.49 -5495402.1  1577%  43.0  430s
     72469 38419 -2752166.1   79  176 -327632.49 -5465175.3  1568%  43.4  436s
     74449 39842 -2756338.1   55  189 -327632.49 -5452502.1  1564%  43.5  440s
    H75375 39486                    -348527.7199 -5447147.7  1463%  43.9  444s
     75503 39874 -1688450.6   94  165 -348527.72 -5442939.7  1462%  43.9  445s
     77454 41347 -3795268.5   54  271 -348527.72 -5427769.5  1457%  44.0  451s
    H77652 40979                    -358651.1618 -5427769.5  1413%  44.1  451s
     79114 42240 -4454175.0   51  183 -358651.16 -5418920.3  1411%  44.2  455s
     81267 43564 -3515754.4   72  224 -358651.16 -5402896.7  1406%  44.5  460s
     82748 44760 -2909984.4   73  221 -358651.16 -5393068.6  1404%  44.9  465s
    H83511 45453                    -358672.7858 -5390783.3  1403%  45.1  468s
    H83834 44923                    -371383.6617 -5390783.3  1352%  45.2  468s
     84331 45566 -4513254.1   42  201 -371383.66 -5387219.7  1351%  45.3  470s
     86148 47170 -2454716.3   83  207 -371383.66 -5371139.7  1346%  45.5  475s
     87979 48740 -2440914.0   80  199 -371383.66 -5361464.4  1344%  45.6  480s
     90370 50483 -1830332.7   82  168 -371383.66 -5351620.9  1341%  45.7  485s
     91655 51163 -3098274.6   74  219 -371383.66 -5346675.8  1340%  45.8  490s
    H91657 49152                    -408217.1297 -5346675.8  1210%  45.8  490s
    H91866 48575                    -425288.6404 -5346675.8  1157%  45.8  491s
     93076 49786 -2159036.0   88  189 -425288.64 -5342086.9  1156%  46.0  495s
     94742 51231 -3558891.6   48  207 -425288.64 -5337080.8  1155%  46.4  500s
     96368 52716 -3553387.0   71  215 -425288.64 -5328239.1  1153%  46.7  505s
     98425 54480 -2960566.9   57  231 -425288.64 -5320995.1  1151%  46.9  510s
     100481 56242 -1143711.2  102  168 -425288.64 -5309877.3  1149%  47.1  516s
     102038 57559 -2491923.5   83  186 -425288.64 -5300265.4  1146%  47.4  520s
     103753 59118 -3495701.9   72  217 -425288.64 -5295397.9  1145%  47.6  525s
     105603 60687 -4764006.7   46  226 -425288.64 -5287303.9  1143%  47.7  530s
     107589 62558 -4144405.3   50  219 -425288.64 -5275714.5  1141%  47.9  536s
     109383 63639 -893435.30  105  140 -425288.64 -5270155.7  1139%  48.0  540s
     111473 65482 -450156.94  267   19 -425288.64 -5263923.1  1138%  48.2  545s
     113421 67130 -1747463.5   88  183 -425288.64 -5253315.2  1135%  48.3  550s
     115108 68543 -2685781.8   70  227 -425288.64 -5249466.2  1134%  48.4  555s
     116699 69977 -1975335.1   87  192 -425288.64 -5243805.7  1133%  48.6  560s
     118756 71695 -3878133.8   54  212 -425288.64 -5238842.4  1132%  48.8  565s
     120613 73316 -4393592.2   47  201 -425288.64 -5231773.6  1130%  49.0  570s
     122148 74743 -850602.99  103  117 -425288.64 -5228608.1  1129%  49.3  575s
    H123022 75234                    -426297.2041 -5227187.9  1126%  49.4  577s
    H123191 73945                    -443105.9948 -5227187.9  1080%  49.4  579s
    H123194 72835                    -456542.1075 -5227187.9  1045%  49.4  579s
     123195 73105 -609612.46  108  133 -456542.11 -5227121.5  1045%  49.4  580s
     125182 74726 -4647458.2   39  223 -456542.11 -5220736.6  1044%  49.6  585s
     126880 76206 -4199821.9   48  207 -456542.11 -5215748.9  1042%  49.6  590s
     128656 77755 -791386.37  109  141 -456542.11 -5210952.9  1041%  49.9  595s
     130391 79176 -2587077.5   75  218 -456542.11 -5205069.4  1040%  50.0  600s

    Cutting planes:
      Gomory: 387
      Cover: 106
      Implied bound: 46
      Projected implied bound: 1
      Clique: 13
      MIR: 230
      Flow cover: 546
      Inf proof: 12
      Network: 2
      RLT: 10
      Relax-and-lift: 13

    Explored 130781 nodes (6571454 simplex iterations) in 600.05 seconds (772.42 work units)
    Thread count was 8 (of 8 available processors)

    Solution count 10: -456542 -443106 -426297 ... -327632

    Time limit reached
    Best objective -4.565421075178e+05, best bound -5.204216981606e+06, gap 1039.9205%

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Suyue,

    Can you try running the NoRel heuristic for much much longer and see how it goes?  The NoRel heuristic has 2 phases. In the first phase, the heuristic focuses on finding a feasible solution. The relaxation value tells how far the current infeasible solution is from a feasible one. The lower the value, the closer the heuristic is to shifting to phase 2. In phase 2, a feasible point is available and the heuristics tries to improve the objective value.  In both your logs NoRel is finishing before it has moved to phase 2, which is why your B&B tree is not starting with an incumbent.  If NoRel does not reach phase 2 then it is no help to the solve.

    - Riley

    0
  • Suyue Xu
    Curious
    Gurobi-versary
    Conversationalist

    Hi Riley

    Thank you for your suggestion!I tried to run the NoRel heuristic for 1200s,and it turns out shifting to phase 2 quickly.Here is the log:

    Set parameter Username
    Set parameter CrossoverBasis to value 0
    Set parameter MIPFocus to value 2
    Set parameter NodefileDir to value ""
    Set parameter NoRelHeurTime to value 1200
    Set parameter PreSOS2BigM to value 0
    Set parameter TuneTrials to value 3
    Academic license - for non-commercial use only - expires 2024-06-06
    Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)

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

    Optimize a model with 31874 rows, 17376 columns and 78324 nonzeros
    Model fingerprint: 0x98635255
    Variable types: 10152 continuous, 7224 integer (7224 binary)
    Coefficient statistics:
      Matrix range     [9e-01, 1e+04]
      Objective range  [3e-14, 1e+03]
      Bounds range     [1e+00, 1e+00]
      RHS range        [3e-14, 1e+04]
    Presolve removed 29980 rows and 15574 columns
    Presolve time: 0.17s
    Presolved: 1894 rows, 1802 columns, 7757 nonzeros
    Variable types: 1280 continuous, 522 integer (522 binary)
    Starting NoRel heuristic
    Found phase-1 solution: relaxation 2.35164e+07
    Found phase-1 solution: relaxation 2.35143e+07
    Found phase-1 solution: relaxation 2.34377e+07
    Found phase-1 solution: relaxation 2.33672e+07
    Found phase-1 solution: relaxation 2.3318e+07
    Found phase-1 solution: relaxation 80948.9
    Found phase-1 solution: relaxation 73235.3
    Found phase-1 solution: relaxation 62411.2
    Found phase-1 solution: relaxation 61308.5
    Found phase-1 solution: relaxation 61303.9
    Found phase-1 solution: relaxation 61210.8
    Found phase-1 solution: relaxation 60794.8
    Found phase-1 solution: relaxation 59540.8
    Found phase-1 solution: relaxation 49330.9
    Found phase-1 solution: relaxation 48553.3
    Found phase-1 solution: relaxation 48107.6
    Found phase-1 solution: relaxation 47827
    Found phase-1 solution: relaxation 43995.1
    Found phase-1 solution: relaxation 43802.7
    Found phase-1 solution: relaxation 43775.1
    Found phase-1 solution: relaxation 37603.3
    Found phase-1 solution: relaxation 36476.5
    Found phase-1 solution: relaxation 16553.5
    Found phase-1 solution: relaxation 16438.7
    Found phase-1 solution: relaxation 16418.6
    Found phase-1 solution: relaxation 14695.2
    Found phase-1 solution: relaxation 14579.1
    Found phase-1 solution: relaxation 14457.7
    Found phase-1 solution: relaxation 14150.9
    Found phase-1 solution: relaxation 14000.8
    Found phase-1 solution: relaxation 13804.6
    Found phase-1 solution: relaxation 13725.1
    Found phase-1 solution: relaxation 13156.6
    Found phase-1 solution: relaxation 12779.1
    Found phase-1 solution: relaxation 12421.7
    Found phase-1 solution: relaxation 12052.1
    Found phase-1 solution: relaxation 11868.2
    Found phase-1 solution: relaxation 6004
    Found phase-1 solution: relaxation 5918.1
    Found phase-1 solution: relaxation 5907.01
    Found phase-1 solution: relaxation 5333.12
    Found phase-1 solution: relaxation 5318.08
    Found phase-1 solution: relaxation 4806.83
    Found phase-1 solution: relaxation 4415.63
    Found phase-1 solution: relaxation 4367.03
    Found phase-1 solution: relaxation 4314.67
    Found phase-1 solution: relaxation 3889.66
    Found phase-1 solution: relaxation 3818.12
    Found phase-1 solution: relaxation 1076.55
    Found phase-1 solution: relaxation 1040.62
    Found phase-1 solution: relaxation 1027.46
    Found phase-1 solution: relaxation 1015.1
    Found phase-1 solution: relaxation 1008.86
    Found phase-1 solution: relaxation 1002
    Found phase-1 solution: relaxation 979.55
    Found phase-1 solution: relaxation 968.501
    Found phase-1 solution: relaxation 968.298
    Found phase-1 solution: relaxation 948.577
    Found phase-1 solution: relaxation 946.949
    Found phase-1 solution: relaxation 944.603
    Found phase-1 solution: relaxation 940.167
    Found phase-1 solution: relaxation 890.83
    Found phase-1 solution: relaxation 884.087
    Found phase-1 solution: relaxation 556.016
    Found phase-1 solution: relaxation 435.551
    Found phase-1 solution: relaxation 282.481
    Found phase-1 solution: relaxation 258.447
    Found phase-1 solution: relaxation 253.83
    Found phase-1 solution: relaxation 198.464
    Found phase-1 solution: relaxation 192.311
    Found phase-1 solution: relaxation 177.379
    Found phase-1 solution: relaxation 177.379
    Found phase-1 solution: relaxation 163.331
    Found phase-1 solution: relaxation 160.774
    Found phase-1 solution: relaxation 160.087
    Found phase-1 solution: relaxation 157.461
    Found phase-1 solution: relaxation 156.337
    Found phase-1 solution: relaxation 27.7935
    Found phase-1 solution: relaxation 22.3438
    Found phase-1 solution: relaxation 22.2074
    Found phase-1 solution: relaxation 21.5348
    Found phase-1 solution: relaxation 0
    Found heuristic solution: objective -28578.86394
    Transition to phase 2
    Found heuristic solution: objective -28578.86549
    Found heuristic solution: objective -28578.86549
    Found heuristic solution: objective -28578.86550
    Found heuristic solution: objective -28578.86550
    Found heuristic solution: objective -49375.36820
    Found heuristic solution: objective -63436.93335
    Found heuristic solution: objective -84233.43452
    Found heuristic solution: objective -84233.43606
    Found heuristic solution: objective -85103.47582
    Found heuristic solution: objective -85103.47737
    Found heuristic solution: objective -91880.14071
    Found heuristic solution: objective -91880.14085
    Found heuristic solution: objective -113161.5898
    Found heuristic solution: objective -113161.5960
    Elapsed time for NoRel heuristic: 5s (best bound -2.96101e+06)
    Found heuristic solution: objective -113161.5974
    Found heuristic solution: objective -113161.5974
    Found heuristic solution: objective -122912.3808
    Found heuristic solution: objective -129981.4582
    Found heuristic solution: objective -144659.3042
    Found heuristic solution: objective -144659.3058
    Found heuristic solution: objective -151878.1813
    Found heuristic solution: objective -156654.8909
    Elapsed time for NoRel heuristic: 10s (best bound -2.96101e+06)
    Found heuristic solution: objective -156654.9450
    Found heuristic solution: objective -156654.9778
    Elapsed time for NoRel heuristic: 15s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.1454
    Elapsed time for NoRel heuristic: 21s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.1482
    Found heuristic solution: objective -156655.1562
    Elapsed time for NoRel heuristic: 27s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.1563
    Elapsed time for NoRel heuristic: 32s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.5054
    Found heuristic solution: objective -156655.5089
    Found heuristic solution: objective -156655.5091
    Found heuristic solution: objective -156655.5322
    Elapsed time for NoRel heuristic: 38s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 43s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 51s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 56s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 65s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.5322
    Elapsed time for NoRel heuristic: 70s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 76s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 82s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 91s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 97s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 104s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 111s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 120s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 127s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 134s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 142s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 151s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.5322
    Elapsed time for NoRel heuristic: 158s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 165s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 174s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 181s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 189s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 198s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 207s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 214s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 223s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 231s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 241s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 249s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 258s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 267s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 275s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 284s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 293s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 302s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 310s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 319s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 326s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 335s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 344s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 353s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 362s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 372s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 382s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 391s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 401s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 410s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 420s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 430s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 439s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 449s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 458s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 468s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 478s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 488s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 497s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 507s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 517s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 527s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 536s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 546s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 556s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 566s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 576s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 593s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 610s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 627s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 643s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 661s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 678s (best bound -2.96101e+06)
    Found heuristic solution: objective -156655.5322
    Elapsed time for NoRel heuristic: 695s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 703s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 725s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 741s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 758s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 776s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 793s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 810s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 827s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 844s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 860s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 877s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 894s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 911s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 928s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 945s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 962s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 979s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 997s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1013s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1030s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1047s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1064s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1081s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1098s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1115s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1132s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1150s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1166s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1184s (best bound -2.96101e+06)
    Elapsed time for NoRel heuristic: 1200s (best bound -2.96101e+06)
    Root relaxation presolve removed 484 rows and 474 columns
    Root relaxation presolved: 1410 rows, 1338 columns, 6797 nonzeros


    Root simplex log...

    Iteration    Objective       Primal Inf.    Dual Inf.      Time
           0   -2.1889945e+07   3.680978e+05   0.000000e+00   1201s
         797   -2.9610118e+06   0.000000e+00   0.000000e+00   1201s
         998   -2.9610118e+06   0.000000e+00   0.000000e+00   1201s
    Extra simplex iterations after uncrush: 201

    Root relaxation: objective -2.961012e+06, 998 iterations, 0.03 seconds (0.02 work units)

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

         0     0 -2961011.8    0   56 -156655.53 -2961011.8  1790%     - 1200s
         0     0 -2584061.7    0  100 -156655.53 -2584061.7  1550%     - 1200s
         0     0 -328852.81    0   40 -156655.53 -328852.81   110%     - 1200s
         0     0 -322016.68    0   42 -156655.53 -322016.68   106%     - 1200s
         0     0 -278200.62    0   52 -156655.53 -278200.62  77.6%     - 1201s
         0     0 -278200.62    0   54 -156655.53 -278200.62  77.6%     - 1201s
         0     0 -252655.66    0   90 -156655.53 -252655.66  61.3%     - 1201s
         0     0 -250743.27    0   95 -156655.53 -250743.27  60.1%     - 1201s
         0     0 -249586.98    0  100 -156655.53 -249586.98  59.3%     - 1201s
         0     0 -249539.29    0  112 -156655.53 -249539.29  59.3%     - 1201s
         0     0 -221785.42    0  109 -156655.53 -221785.42  41.6%     - 1201s
         0     0 -221465.44    0  108 -156655.53 -221465.44  41.4%     - 1201s
         0     0 -204212.16    0   95 -156655.53 -204212.16  30.4%     - 1201s
         0     0 -202795.80    0   86 -156655.53 -202795.80  29.5%     - 1201s
         0     0 -202795.77    0   88 -156655.53 -202795.77  29.5%     - 1201s
         0     0 -190807.89    0   84 -156655.53 -190807.89  21.8%     - 1202s
         0     0 -185142.25    0   98 -156655.53 -185142.25  18.2%     - 1202s
         0     0 -177358.50    0   93 -156655.53 -177358.50  13.2%     - 1202s
         0     0 -177358.50    0   91 -156655.53 -177358.50  13.2%     - 1202s
         0     0 -170088.81    0   81 -156655.53 -170088.81  8.58%     - 1202s
         0     0 -169689.93    0   62 -156655.53 -169689.93  8.32%     - 1202s
         0     0 -167209.16    0   79 -156655.53 -167209.16  6.74%     - 1202s
         0     0 -167203.01    0   77 -156655.53 -167203.01  6.73%     - 1202s
         0     0 -163342.63    0   30 -156655.53 -163342.63  4.27%     - 1202s
         0     0 -161827.26    0   49 -156655.53 -161827.26  3.30%     - 1202s
         0     0 -161243.42    0   46 -156655.53 -161243.42  2.93%     - 1202s
         0     0 -160106.42    0   60 -156655.53 -160106.42  2.20%     - 1202s
         0     0 -157756.71    0   39 -156655.53 -157756.71  0.70%     - 1202s
         0     0 -157502.27    0   24 -156655.53 -157502.27  0.54%     - 1202s
         0     0 -157381.93    0   41 -156655.53 -157381.93  0.46%     - 1202s
         0     0 -157191.26    0   22 -156655.53 -157191.26  0.34%     - 1202s
         0     0     cutoff    0      -156655.53 -156655.53  0.00%     - 1202s

    Cutting planes:
      Learned: 2
      Gomory: 63
      Lift-and-project: 92
      Cover: 12
      Implied bound: 78
      Projected implied bound: 1
      Clique: 47
      MIR: 26
      StrongCG: 1
      Flow cover: 84
      RLT: 14
      Relax-and-lift: 19
      PSD: 1

    Explored 1 nodes (4120 simplex iterations) in 1202.80 seconds (792.94 work units)
    Thread count was 16 (of 16 available processors)

    Solution count 10: -156656 -156656 -156656 ... -156655
    No other solutions better than -156656

    Optimal solution found (tolerance 1.00e-04)
    Best objective -1.566555589689e+05, best bound -1.566555589689e+05, gap 0.0000%

    It's very inspiring to see gurobi successfully find the result.However, I'm also focusing on the efficiency.Are there any factors contributing to the time requied for the transition to phase 2?

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Suyue,

    So previously the NoRel heuristic was taking 200s and not moving to Phase 2 within this time, and in this last log it is moving to Phase 2 in under 5s.  This would not be expected by simply changing the NoRelHeurTime parameter and now I see that the three logs are for three different models (they all have different Fingerprints)

    Optimize a model with 34225 rows, 18648 columns and 83412 nonzeros
    Model fingerprint: 0x36eec57f
    Variable types: 10920 continuous, 7728 integer (7728 binary)

    Optimize a model with 34225 rows, 18648 columns and 83412 nonzeros
    Model fingerprint: 0xa66355f9
    Variable types: 10920 continuous, 7728 integer (7728 binary)

    Optimize a model with 31874 rows, 17376 columns and 78324 nonzeros
    Model fingerprint: 0x98635255
    Variable types: 10152 continuous, 7224 integer (7224 binary)

    Based on the last log I would have said run NoRel for 10 seconds...  What has changed?  Given the completely different objective values I'm guessing there may have been significant changes?

    Here are some general tips:

    • It is a good idea to always use the latest version of Gurobi (currently v11)
    • Only set algorithmic parameters if you understand what they mean and have good justification (such as rigorous experimental results supporting the choice). The following parameters have no place here:
      - CrossoverBasis: this is relevant if using the Barrier algorithm, but your logs would suggest that one of the simplex algorithms is solving the LP relaxations every time.
      - PreSOS2BigM: the logs show that you do not have SOS constraints, or any constraints that would be translated to SOS constraints
      - TuneTrials: this is only relevant for a tuning experiment - which this is not
      Consequently I'd also question whether MIPFocus=2 is the right choice, purely because of these other strange choices.
    • Your objective range and RHS range are not ideal due to the large spread of magnitudes:
      Coefficient statistics:
        Matrix range     [9e-01, 1e+04]
        Objective range  [3e-14, 1e+03]
        Bounds range     [1e+00, 1e+00]
        RHS range        [3e-14, 1e+04]
      Whenever we see an objective range like this we would ask if the objective is arising from blending multiple objectives together, with different weights.  If this is the case here then using our multi-objective functionality would be better.

    - Riley

    0

Please sign in to leave a comment.