Originally posted by: SystemAdmin

Group,

I ran CPLEX's mipopt for a MIP with and without a starting solution. When started with a solution, I provided the optimal solution itself. To see how much performance I could gain when CPLEX is provided with a reasonably good starting solution. But I found the run with the starting solution performed worse compared to a run without the starting solution. Both the runs are done interactively and with default settings. When would a good starting solution help? This is done on CPLEX version 9.1.

Run without a starting solution:
Tried aggregator 3 times.
MIP Presolve eliminated 13657 rows and 41110 columns.
MIP Presolve modified 2438 coefficients.
Aggregator did 1850 substitutions.
Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros.
Presolve time = 2.96 sec.
Clique table members: 26575
MIP emphasis: balance optimality and feasibility
Root relaxation solution time = 215.98 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

0 0 1.0283e+07 340 1.0283e+07 206058

• 0+ 0 0 25640.7269 1.0283e+07 206058 ---

8988953.5351 223 25640.7269 Cuts: 437 214233 ---

• 0+ 0 0 5455528.9552 8988953.5351 214233 64.77%

8670198.7716 128 5455528.9552 Cuts: 216 216468 58.92%

• 0+ 0 0 7417984.4737 8670198.7716 216468 16.88%

8501360.8100 89 7417984.4737 Cuts: 115 217714 14.60%
8407740.3147 177 7417984.4737 Cuts: 113 218595 13.34%
8368787.2176 152 7417984.4737 Cuts: 110 219579 12.82%
8332607.6301 186 7417984.4737 Cuts: 100 220799 12.33%
8287951.6798 229 7417984.4737 Cuts: 102 221574 11.73%
8191733.7732 152 7417984.4737 Cuts: 117 223665 10.43%
8094561.1720 172 7417984.4737 Cuts: 98 224686 9.12%
8038967.2803 182 7417984.4737 Cuts: 99 225570 8.37%
8023982.4595 342 7417984.4737 Cuts: 82 226443 8.17%
8009446.3485 375 7417984.4737 Cuts: 48 227143 7.97%
7982005.9717 348 7417984.4737 Cuts: 85 228396 7.60%
7970592.8336 356 7417984.4737 Cuts: 68 229131 7.45%
7956774.4734 374 7417984.4737 Cuts: 48 230077 7.26%
7941875.2935 363 7417984.4737 Cuts: 74 231092 7.06%
7935462.1153 350 7417984.4737 Cuts: 87 231657 6.98%
7927872.0831 355 7417984.4737 Cuts: 63 232208 6.87%
7920798.0832 356 7417984.4737 Cuts: 46 232736 6.78%
7918316.7428 346 7417984.4737 Cuts: 71 233319 6.74%
7917149.5230 329 7417984.4737 Cuts: 17 233370 6.73%

• 0+ 0 0 7437382.2640 7917149.5230 233370 6.45%
• 0+ 0 0 7531350.7561 7917149.5230 233370 5.12%

Elapsed time = 344.10 sec. (tree size = 0.00 MB)
100 77 7914419.2561 362 7531350.7561 7915685.2813 234153 5.10%
200 172 7882116.6378 186 7531350.7561 7915685.2813 235965 5.10%
300 198 cutoff 7531350.7561 7914419.2561 242779 5.09%
400 148 cutoff 7531350.7561 7909170.9204 263860 5.02%
500 134 cutoff 7531350.7561 7898072.2307 276513 4.87%
600 36 cutoff 7531350.7561 7760648.2544 285072 3.04%

Implied bound cuts applied: 843
Flow cuts applied: 224

Integer optimal solution: Objective = 7.5313507561e+06
Solution time = 653.28 sec. Iterations = 286883 Nodes = 646
Run with optimal solution as the starting solution:
MIP start values provide initial solution with objective 7531350.7561.
Tried aggregator 3 times.
MIP Presolve eliminated 13657 rows and 41110 columns.
MIP Presolve modified 2438 coefficients.
Aggregator did 1850 substitutions.
Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros.
Presolve time = 3.10 sec.
Clique table members: 26575
MIP emphasis: balance optimality and feasibility
Root relaxation solution time = 235.42 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

0 0 1.0283e+07 340 7531350.7561 1.0283e+07 206058 36.54%
8984621.6673 274 7531350.7561 Cuts: 433 212782 19.30%
8637742.3055 149 7531350.7561 Cuts: 217 215507 14.69%
8468816.1202 169 7531350.7561 Cuts: 109 216830 12.45%
8397873.6161 190 7531350.7561 Cuts: 117 217767 11.51%
8363156.3300 159 7531350.7561 Cuts: 70 219024 11.04%
8329865.1148 216 7531350.7561 Cuts: 121 219791 10.60%
8299825.2757 255 7531350.7561 Cuts: 114 220794 10.20%
8230446.8867 164 7531350.7561 Cuts: 99 222275 9.28%
8139824.5525 162 7531350.7561 Cuts: 108 224098 8.08%
8098408.6470 125 7531350.7561 Cuts: 127 225132 7.53%
8072538.7616 365 7531350.7561 Cuts: 50 226011 7.19%
8000722.6410 215 7531350.7561 Cuts: 107 226657 6.23%
7965738.0629 276 7531350.7561 Cuts: 84 227623 5.77%
7953520.6007 107 7531350.7561 Cuts: 97 228410 5.61%
7941988.3356 177 7531350.7561 Cuts: 42 228620 5.45%
7936113.0841 213 7531350.7561 Cuts: 61 229016 5.37%
7923421.6191 195 7531350.7561 Cuts: 48 229874 5.21%
7912812.8736 199 7531350.7561 Cuts: 79 230187 5.06%
7910078.7010 217 7531350.7561 Cuts: 49 230303 5.03%
7907527.4434 241 7531350.7561 Cuts: 40 230612 4.99%
7903532.3083 215 7531350.7561 Cuts: 23 231123 4.94%
7901932.1089 142 7531350.7561 Cuts: 31 231662 4.92%
7900656.9746 160 7531350.7561 Cuts: 15 232164 4.90%
Heuristic still looking
Heuristic complete
Elapsed time = 529.66 sec. (tree size = 0.00 MB)
100 81 7895655.9164 275 7531350.7561 7900651.1002 233668 4.90%
200 169 7893280.7223 230 7531350.7561 7900651.1002 235653 4.90%
300 241 7851602.6817 179 7531350.7561 7900651.1002 237145 4.90%
400 297 7733721.6157 103 7531350.7561 7900651.1002 239757 4.90%
500 304 cutoff 7531350.7561 7895802.3710 254328 4.84%
600 238 cutoff 7531350.7561 7892682.5374 279945 4.80%
700 138 cutoff 7531350.7561 7851602.6817 295974 4.25%
800 57 cutoff 7531350.7561 7728215.5328 303747 2.61%

Implied bound cuts applied: 924
Flow cuts applied: 131

Integer optimal solution: Objective = 7.5313507561e+06
Solution time = 1055.04 sec. Iterations = 305600 Nodes = 875

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

http://Attaching you the results by running with RinsHeuristic = 50. (Also formatted the text of my earlier post)

Group,

I ran CPLEX's mipopt for a MIP with and without a starting solution. When started with a solution, I provided the optimal solution itself. To see how much performance I could gain when CPLEX is provided with a reasonably good starting solution. But I found the run with the starting solution performed worse compared to a run without the starting solution. Both the runs are done interactively and with default settings. When would a good starting solution help? This is done on CPLEX version 9.1.

Run without a starting solution:

Tried aggregator 3 times. MIP Presolve eliminated 13657 rows and 41110 columns. MIP Presolve modified 2438 coefficients. Aggregator did 1850 substitutions. Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros. Presolve time =    2.96 sec. Clique table members: 26575 MIP emphasis: balance optimality and feasibility Root relaxation solution time =  215.98 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap   0     0    1.0283e+07   340                  1.0283e+07   206058 *     0+    0                   0    25640.7269    1.0283e+07   206058     --- 8988953.5351   223    25640.7269    Cuts:  437   214233     --- *     0+    0                   0  5455528.9552  8988953.5351   214233   64.77% 8670198.7716   128  5455528.9552    Cuts:  216   216468   58.92% *     0+    0                   0  7417984.4737  8670198.7716   216468   16.88% 8501360.8100    89  7417984.4737    Cuts:  115   217714   14.60% 8407740.3147   177  7417984.4737    Cuts:  113   218595   13.34% 8368787.2176   152  7417984.4737    Cuts:  110   219579   12.82% 8332607.6301   186  7417984.4737    Cuts:  100   220799   12.33% 8287951.6798   229  7417984.4737    Cuts:  102   221574   11.73% 8191733.7732   152  7417984.4737    Cuts:  117   223665   10.43% 8094561.1720   172  7417984.4737     Cuts:  98   224686    9.12% 8038967.2803   182  7417984.4737     Cuts:  99   225570    8.37% 8023982.4595   342  7417984.4737     Cuts:  82   226443    8.17% 8009446.3485   375  7417984.4737     Cuts:  48   227143    7.97% 7982005.9717   348  7417984.4737     Cuts:  85   228396    7.60% 7970592.8336   356  7417984.4737     Cuts:  68   229131    7.45% 7956774.4734   374  7417984.4737     Cuts:  48   230077    7.26% 7941875.2935   363  7417984.4737     Cuts:  74   231092    7.06% 7935462.1153   350  7417984.4737     Cuts:  87   231657    6.98% 7927872.0831   355  7417984.4737     Cuts:  63   232208    6.87% 7920798.0832   356  7417984.4737     Cuts:  46   232736    6.78% 7918316.7428   346  7417984.4737     Cuts:  71   233319    6.74% 7917149.5230   329  7417984.4737     Cuts:  17   233370    6.73% *     0+    0                   0  7437382.2640  7917149.5230   233370    6.45% *     0+    0                   0  7531350.7561  7917149.5230   233370    5.12% Elapsed time = 344.10 sec. (tree size =  0.00 MB) 100    77  7914419.2561   362  7531350.7561  7915685.2813   234153    5.10% 200   172  7882116.6378   186  7531350.7561  7915685.2813   235965    5.10% 300   198        cutoff        7531350.7561  7914419.2561   242779    5.09% 400   148        cutoff        7531350.7561  7909170.9204   263860    5.02% 500   134        cutoff        7531350.7561  7898072.2307   276513    4.87% 600    36 cutoff        7531350.7561  7760648.2544   285072    3.04%   Implied bound cuts applied:  843 Flow cuts applied:  224   Integer optimal solution:  Objective =    7.5313507561e+06 Solution time =  653.28 sec.  Iterations = 286883  Nodes = 646

Run with optimal solution as the starting solution:

MIP start values provide initial solution with objective 7531350.7561. Tried aggregator 3 times. MIP Presolve eliminated 13657 rows and 41110 columns. MIP Presolve modified 2438 coefficients. Aggregator did 1850 substitutions. Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros. Presolve time =    3.10 sec. Clique table members: 26575 MIP emphasis: balance optimality and feasibility Root relaxation solution time =  235.42 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap   0     0    1.0283e+07   340  7531350.7561    1.0283e+07   206058   36.54% 8984621.6673   274  7531350.7561    Cuts:  433   212782   19.30% 8637742.3055   149  7531350.7561    Cuts:  217   215507   14.69% 8468816.1202   169  7531350.7561    Cuts:  109   216830   12.45% 8397873.6161   190  7531350.7561    Cuts:  117   217767   11.51% 8363156.3300   159  7531350.7561     Cuts:  70   219024   11.04% 8329865.1148   216  7531350.7561    Cuts:  121   219791   10.60% 8299825.2757   255  7531350.7561    Cuts:  114   220794   10.20% 8230446.8867   164  7531350.7561     Cuts:  99   222275    9.28% 8139824.5525   162  7531350.7561    Cuts:  108   224098    8.08% 8098408.6470   125  7531350.7561    Cuts:  127   225132    7.53% 8072538.7616   365  7531350.7561     Cuts:  50   226011    7.19% 8000722.6410   215  7531350.7561    Cuts:  107   226657    6.23% 7965738.0629   276  7531350.7561     Cuts:  84   227623    5.77% 7953520.6007   107  7531350.7561     Cuts:  97   228410    5.61% 7941988.3356   177  7531350.7561     Cuts:  42   228620    5.45% 7936113.0841   213  7531350.7561     Cuts:  61   229016    5.37% 7923421.6191   195  7531350.7561     Cuts:  48   229874    5.21% 7912812.8736   199  7531350.7561     Cuts:  79   230187    5.06% 7910078.7010   217  7531350.7561     Cuts:  49   230303    5.03% 7907527.4434   241  7531350.7561     Cuts:  40   230612    4.99% 7903532.3083   215  7531350.7561     Cuts:  23   231123    4.94% 7901932.1089   142  7531350.7561     Cuts:  31   231662    4.92% 7900656.9746   160  7531350.7561     Cuts:  15   232164    4.90% Heuristic still looking Heuristic complete Elapsed time = 529.66 sec. (tree size =  0.00 MB) 100    81  7895655.9164   275  7531350.7561  7900651.1002   233668    4.90% 200   169  7893280.7223   230  7531350.7561  7900651.1002   235653    4.90% 300   241  7851602.6817   179  7531350.7561  7900651.1002   237145    4.90% 400   297  7733721.6157   103  7531350.7561  7900651.1002   239757    4.90% 500   304        cutoff        7531350.7561  7895802.3710   254328    4.84% 600   238        cutoff        7531350.7561  7892682.5374   279945    4.80% 700   138        cutoff        7531350.7561  7851602.6817   295974    4.25% 800    57        cutoff        7531350.7561  7728215.5328   303747    2.61%   Implied bound cuts applied:  924 Flow cuts applied:  131   Integer optimal solution:  Objective =    7.5313507561e+06 Solution time = 1055.04 sec.  Iterations = 305600  Nodes = 875

Run with optimal solution as the starting solution and RinsHeuristic set to 50:

MIP start values provide initial solution with objective 7531350.7561. Tried aggregator 3 times. MIP Presolve eliminated 13657 rows and 41110 columns. MIP Presolve modified 2438 coefficients. Aggregator did 1850 substitutions. Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros. Presolve time =    3.98 sec. Clique table members: 26575 MIP emphasis: balance optimality and feasibility Root relaxation solution time =  249.78 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap   0     0    1.0283e+07   340  7531350.7561    1.0283e+07   206058   36.54% 8984621.6673   274  7531350.7561    Cuts:  433   212782   19.30% 8637742.3055   149  7531350.7561    Cuts:  217   215507   14.69% 8468816.1202   169  7531350.7561    Cuts:  109   216830   12.45% 8397873.6161   190  7531350.7561    Cuts:  117   217767   11.51% 8363156.3300   159  7531350.7561     Cuts:  70   219024   11.04% 8329865.1148   216  7531350.7561    Cuts:  121   219791   10.60% 8299825.2757   255  7531350.7561    Cuts:  114   220794   10.20% 8230446.8867   164  7531350.7561     Cuts:  99   222275    9.28% 8139824.5525   162  7531350.7561    Cuts:  108   224098    8.08% 8098408.6470   125  7531350.7561    Cuts:  127   225132    7.53% 8072538.7616   365  7531350.7561     Cuts:  50   226011    7.19% 8000722.6410   215  7531350.7561    Cuts:  107   226657    6.23% 7965738.0629   276  7531350.7561     Cuts:  84   227623    5.77% 7953520.6007   107  7531350.7561     Cuts:  97   228410    5.61% 7941988.3356   177  7531350.7561     Cuts:  42   228620    5.45% 7936113.0841   213  7531350.7561     Cuts:  61   229016    5.37% 7923421.6191   195  7531350.7561     Cuts:  48   229874    5.21% 7912812.8736   199  7531350.7561     Cuts:  79   230187    5.06% 7910078.7010   217  7531350.7561     Cuts:  49   230303    5.03% 7907527.4434   241  7531350.7561     Cuts:  40   230612    4.99% 7903532.3083   215  7531350.7561     Cuts:  23   231123    4.94% 7901932.1089   142  7531350.7561     Cuts:  31   231662    4.92% 7900656.9746   160  7531350.7561     Cuts:  15   232164    4.90% Elapsed time = 490.66 sec. (tree size =  0.00 MB) 100    81  7895655.9164   275  7531350.7561  7900651.1002   233668    4.90% 200   169  7893280.7223   230  7531350.7561  7900651.1002   235653    4.90% 300   241  7851602.6817   179  7531350.7561  7900651.1002   237145    4.90% 400   297  7733721.6157   103  7531350.7561  7900651.1002   239757    4.90% 500   304        cutoff        7531350.7561  7895802.3710   254328    4.84% 600   238        cutoff        7531350.7561  7892682.5374   279945    4.80% 700   138        cutoff        7531350.7561  7851602.6817   295974    4.25% 800    57        cutoff        7531350.7561  7728215.5328   303747    2.61%   Implied bound cuts applied:  924 Flow cuts applied:  131   Integer optimal solution:  Objective =    7.5313507561e+06 Solution time =  999.68 sec.  Iterations = 305600  Nodes = 875

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I did two more runs with lower cutoff set to the optimal solution. Rins Heuristic is at default setting in both the runs.

4) Run with starting solution and lower cutoff set to the optimal solution:

New value 

for lower objective cutoff: 7531350.7561 New value 

for lower objective cutoff: 7.53135e+06   MIP start values provide initial solution with objective 7531350.7561. Tried aggregator 3 times. MIP Presolve eliminated 13657 rows and 41110 columns. MIP Presolve modified 2438 coefficients. Aggregator did 1850 substitutions. Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros. Presolve time =    2.90 sec. Clique table members: 26575 MIP emphasis: balance optimality and feasibility Root relaxation solution time =  217.56 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap   0     0    1.0283e+07   306  7531350.7561    1.0283e+07   204203   36.54% 8976337.4738   252  7531350.7561    Cuts:  437   212360   19.19% 8636257.4224   156  7531350.7561    Cuts:  226   214637   14.67% 8454373.9105   115  7531350.7561    Cuts:  111   215721   12.26% 8377987.3753   185  7531350.7561    Cuts:  127   217162   11.24% 8351798.8792   223  7531350.7561    Cuts:  106   218273   10.89% 8293074.1034   173  7531350.7561    Cuts:  116   219599   10.11% 8182652.2678   205  7531350.7561     Cuts:  95   221945    8.65% 8118355.1779   126  7531350.7561    Cuts:  153   222809    7.79% 8082073.4678   117  7531350.7561     Cuts:  55   224101    7.31% 8024365.0299   170  7531350.7561     Cuts:  63   225062    6.55% 7994867.9814   353  7531350.7561     Cuts:  88   225757    6.15% 7979460.3380   354  7531350.7561     Cuts:  74   226253    5.95% 7968596.3319   353  7531350.7561     Cuts:  72   226376    5.81% 7952210.1885   356  7531350.7561     Cuts:  46   227490    5.59% 7937875.5383   358  7531350.7561     Cuts:  76   228663    5.40% 7932943.6708   327  7531350.7561     Cuts:  67   228814    5.33% 7924072.9539   355  7531350.7561     Cuts:  34   229564    5.21% 7922950.3045   166  7531350.7561     Cuts:  34   229910    5.20% 7879802.2791   240  7531350.7561      Cuts:  8   231640    4.63% 7872645.5651   185  7531350.7561     Cuts:  60   232177    4.53% 7869123.4462   232  7531350.7561     Cuts:  45   232343    4.48% 7865207.6689   170  7531350.7561     Cuts:  26   232961    4.43% 7860050.9665   200  7531350.7561     Cuts:  47   233815    4.36% 7859523.2718   196  7531350.7561     Cuts:  37   233925    4.36% Elapsed time = 546.50 sec. (tree size =  0.00 MB) 100    72  7854067.4277   271  7531350.7561  7859523.2718   235020    4.36% 200   152  7823252.5062   227  7531350.7561  7859523.2718   237446    4.36% 300   218  7780335.1040   221  7531350.7561  7859523.2718   242159    4.36% 400   287  7754697.8930    27  7531350.7561  7859523.2718   243955    4.36% 500   205        cutoff        7531350.7561  7852030.4804   269923    4.26% 600   145        cutoff        7531350.7561  7803129.7137   287507    3.61% 700 131  7756506.0676   237  7531350.7561  7767025.3375   296513    3.13% 800   221  7745990.1274   216  7531350.7561  7767025.3375   298125    3.13% 900   305  7737329.5830   144  7531350.7561  7767025.3375   299549    3.13% 1000   325  7583810.7671    32  7531350.7561  7760671.2268   307500    3.04% Elapsed time = 999.50 sec. (tree size = 167.27 MB) Nodefile size = 54.20 MB (23.82 MB after compression) 1100   363  7678045.3958    14  7531350.7561  7759704.1320   313047    3.03% 1200   359        cutoff        7531350.7561  7756248.5884   321186    2.99% 1300   312        cutoff        7531350.7561  7745990.1274   329208    2.85% 1400   220        cutoff        7531350.7561  7731192.2900   338091    2.65% 1500   126        cutoff        7531350.7561  7663791.8445   342013    1.76% 1600    66        cutoff        7531350.7561  7600391.6200   344344    0.92%   Implied bound cuts applied:  1000 Flow cuts applied:  130   Integer optimal solution:  Objective =    7.5313507561e+06 Solution time = 1231.32 sec.  Iterations = 345346  Nodes = 1680

5) Run without any starting solution and lower cutoff set to the optimal solution:

Tried aggregator 3 times. MIP Presolve eliminated 13657 rows and 41110 columns. MIP Presolve modified 2438 coefficients. Aggregator did 1850 substitutions. Reduced MIP has 32333 rows, 490576 columns, and 1084939 nonzeros. Presolve time =    2.90 sec. Clique table members: 26575 MIP emphasis: balance optimality and feasibility Root relaxation solution time =  276.04 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap   0     0    1.0283e+07   215                  1.0283e+07   203487 8972904.4985   176                  Cuts:  438   212764 8648954.0594   133                  Cuts:  225   214125 8494200.4365   198                  Cuts:  116   216160 8410314.9566   103                  Cuts:  127   217558 8361528.2825   150                   Cuts:  93   219026 8312840.0956   186                  Cuts:  102   219788 8281071.8374   197                   Cuts:  93   220538 8193765.6673   176                  Cuts:  101   221854 8092635.6882   173                  Cuts:  109   222650 8046396.4873   285                  Cuts:  140   224006 8003439.0763   334                  Cuts:  103   224958 7946541.9774   138                   Cuts:  51   225689 7934088.4916   375                   Cuts:  77   226430 7923465.6574   322                   Cuts:  78   226668 7913302.2569   358                   Cuts:  46   227708 7904756.1904   347                   Cuts:  63   228336 7886505.0863   349                   Cuts:  38   229049 7879165.6572   366                   Cuts:  38   229618 7874893.2732   347                   Cuts:  46   230088 7871769.9663   347                   Cuts:  34   230200 7867440.4406   353                   Cuts:  38   230312 7865025.6428   353                   Cuts:  33   230413 7862921.7398   356                   Cuts:  34   230533 7861603.4817   346                   Cuts:  17   230553 Elapsed time = 705.44 sec. (tree size =  0.00 MB) 100    98  7861344.4959   354                7861541.8308   231077 *   160+  152                   0  7531350.7561  7861541.8308   231599    4.38% 200   181        cutoff        7531350.7561  7861540.5828   234135    4.38% 300   221  7712347.7142   209  7531350.7561  7861344.3375   239637    4.38% 400   193        cutoff        7531350.7561  7860467.8756   250879    4.37% 500   145  7629693.5321    14  7531350.7561  7848984.1415   274083    4.22% 600   119  7535464.7503     8  7531350.7561  7767545.2589   292535    3.14% 700    73        cutoff        7531350.7561  7743050.7389   304791    2.81% 800    55        cutoff        7531350.7561  7690037.5786   311704    2.11%   Implied bound cuts applied:  906 Flow cuts applied:  120   Integer optimal solution:  Objective =    7.5313507561e+06 Solution time = 1099.16 sec.  Iterations = 313995  Nodes = 861

I was thinking that lower cutoff value would be automatically set when you start with a solution and the nodes worse than this value would be pruned off. But the number of nodes processed hasn't improved by either MIP start or cutoff or both. Wondering if the above two parameters would help at all? Are my tests not correct somewhere? Any other parameters? I could to do these runs on a newer CPLEX when I get access.

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

There is an expression that describes the process of solving MIPs: Some days you get the bear, and some days the bear gets you. Supplying a MIP start changes the path taken through the search tree (and in fact changes the tree itself). A good start allows earlier fathoming of nodes based on bound, and so probably helps more times than not, but on any given problem instance there is the danger that supplying the starting solution, even if optimal, shifts you from a fairly favorable path/tree to a less favorable path/tree.

You might try giving CPLEX the optimal solution as a start and switching the emphasis (MIPEmphasis parameter) to "best bound" (3), which will tell CPLEX to exert more energy trying to get the bound to converge to the incumbent value and less energy trying to improve the incumbent (which you know cannot be improved).

You might also consider an upgrade, if possible -- CPLEX 9.1 is pretty far behind the times (12.5 is out this month).

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Wouldn't you be wasting time with the heuristic if you gave it the optimal solution? You are searching the nearby neighborhood of a current solution for a better one. So you are spending time looking for a better solution that doesn't exist. You could try turning it off.

It might be helpful if you solve a real problem you don't know the solution for, though. Also, you said this:

"I was thinking that lower cutoff value would be automatically set when you start with a solution and the nodes worse than this value would be pruned off."

Why would you expect this to do any better than giving Cplex the optimal solution? You give a cutoff value near or equal to the optimal solution. If this was sufficient to prove optimality, cplex would prune the nodes based on the feasible solution and be done really quick. The problem is that regardless of how good your solution is, the LP relaxation and partially relaxed MIP is still better. You have to focus on pruning the tree quicker, but I doubt you can reduce the time by orders of magnitude. That is the nature of proving optimality in an MIP.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

"I was thinking that lower cutoff value would be automatically set when you start with a solution and the nodes worse than this value would be pruned off."

"Why would you expect this to do any better than giving Cplex the optimal solution?"

Run 2 had processed more nodes than run 1. I wasn't sure fathoming was happening so I tried with the cutoff. Which didn't help much. Maybe I need to look at other instances to conclude.

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Paul,

Best bound option didn't seem to help much for this instance. I will try with a more recent CPLEX.

Thanks for your help as usual!

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: rocarvaj

Hi, I've posted a small computational study on my blog regarding this issue:

http://scriptogr.am/rocarvaj/post/is-more-information-better

I don't have an answer. It seems that having the solution in advance could change dramatically the search tree since you are fathoming nodes at different points now.

Regards,
Rodolfo
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Great Rodolfo!

This study on larger instances is very good. It does make lot of sense compared to my experience from just one instance. Besides I am using a older version of CPLEX. Thanks!

Few questions:

1) Did you set MIP emphasis as the default one - balance optimality and feasibility?
2) Did you turn off Rins Heuristic as you are already providing optimal solution as start point? (but I think it's logical to leave it on as we can't be sure whether we would get optimal solution from the first run)
3) Was setting cutoffs (lower or upper) help at all?

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization