Providing the optimal solution as warm start does not improve runtime of MIP.

Hi all, (related to this post)

I solve a MILP with Gurobi and then feed the optimal solution as warm start to the exact same model (plus a couple of lines where I provide the warm start) and solve it again expecting to see a good decrease in runtime. This, however, does not happen and I get longer runtimes. I notice that Gurobi is accepting the provided warm start since the incumbent obj is the optimal objective from the beginning but somehow this is not helping to reduce the runtime.

I recognize that even with the optimal solution provided as warm start, Gurobi still needs to prove optimality, but I still expected an improvement in runtime. All my paraemeters are set to default except Threads = 1. I am putting the logs of the two problems below for reference. Any help is much appreciated!

Sincerely,

Reza

Cold Start:

Set parameter Threads to value 1

Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)

Thread count: 4 physical cores, 8 logical processors, using up to 1 threads

Optimize a model with 2007 rows, 1423 columns and 10414 nonzeros

Model fingerprint: 0x72a7f3b4

Variable types: 803 continuous, 620 integer (620 binary)

Coefficient statistics:

Matrix range [6e-07, 1e+00]

Objective range [1e+00, 1e+00]

Bounds range [1e+00, 1e+00]

RHS range [1e+00, 1e+00]

Presolve removed 4 rows and 4 columns

Presolve time: 0.05s

Presolved: 2003 rows, 1419 columns, 10406 nonzeros

Variable types: 3 continuous, 1416 integer (1416 binary)

Found heuristic solution: objective 85.0000000

Root relaxation: objective 0.000000e+00, 536 iterations, 0.01 seconds (0.02 work units)

Nodes | Current Node | Objective Bounds | Work

Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 0.00000 0 172 85.00000 0.00000 100% - 0s

H 0 0 83.0000000 0.00000 100% - 0s

0 0 0.00000 0 224 83.00000 0.00000 100% - 0s

H 0 0 80.0000000 0.00000 100% - 0s

0 0 0.00000 0 210 80.00000 0.00000 100% - 0s

0 0 0.00000 0 183 80.00000 0.00000 100% - 0s

0 0 0.00000 0 236 80.00000 0.00000 100% - 0s

0 0 0.00000 0 197 80.00000 0.00000 100% - 0s

0 0 0.00000 0 279 80.00000 0.00000 100% - 0s

0 0 0.00000 0 247 80.00000 0.00000 100% - 0s

0 0 0.00000 0 183 80.00000 0.00000 100% - 0s

0 2 0.00000 0 183 80.00000 0.00000 100% - 0s

H 271 136 78.0000000 0.00000 100% 55.0 1s

885 436 50.30817 26 244 78.00000 0.00000 100% 55.0 5s

H 1067 432 75.0000000 0.00000 100% 75.6 5s

H 1080 416 74.0000000 0.00000 100% 76.7 6s

H 1135 411 73.0000000 0.00000 100% 76.8 6s

H 1746 470 72.0000000 0.00000 100% 79.4 8s

2210 598 4.13758 18 276 72.00000 0.00000 100% 80.2 10s

3306 1062 0.76078 23 350 72.00000 0.00000 100% 81.5 15s

5140 1647 2.74069 17 238 72.00000 0.53179 99.3% 78.7 20s

7618 2317 64.58297 30 95 72.00000 1.34231 98.1% 76.3 25s

10202 2976 cutoff 30 72.00000 2.46951 96.6% 74.8 33s

10905 3119 25.69093 21 228 72.00000 2.78814 96.1% 74.3 35s

13955 3828 4.04720 21 268 72.00000 3.96038 94.5% 71.7 40s

H15714 4160 71.0000000 4.56090 93.6% 70.8 43s

16542 4323 cutoff 29 71.00000 4.93327 93.1% 70.1 45s

19700 4921 cutoff 35 71.00000 6.27039 91.2% 68.5 50s

22530 5484 42.10248 29 214 71.00000 7.24928 89.8% 67.3 55s

25912 6020 45.12244 26 135 71.00000 8.48257 88.1% 65.7 60s

28655 6418 9.54349 26 246 71.00000 9.54349 86.6% 64.9 65s

32182 6928 29.91972 24 209 71.00000 11.16363 84.3% 63.8 70s

35707 7418 68.81075 30 63 71.00000 12.86779 81.9% 62.6 75s

39418 7917 68.51171 30 62 71.00000 14.54239 79.5% 61.4 80s

43044 8400 16.95940 26 281 71.00000 15.99465 77.5% 60.5 85s

46851 8911 63.35777 35 92 71.00000 17.47185 75.4% 59.5 90s

50732 9349 24.96410 26 259 71.00000 18.76860 73.6% 58.6 95s

54846 9754 53.84988 30 138 71.00000 20.25105 71.5% 57.7 100s

59034 10162 cutoff 27 71.00000 21.86202 69.2% 56.9 105s

63341 10590 23.63964 25 186 71.00000 23.35448 67.1% 56.0 110s

67791 11040 55.18601 27 67 71.00000 25.10738 64.6% 55.1 115s

72484 11424 cutoff 32 71.00000 26.60264 62.5% 54.2 120s

77110 11859 68.02626 32 75 71.00000 28.11140 60.4% 53.3 125s

81877 12303 39.00000 30 175 71.00000 29.49949 58.5% 52.6 130s

86646 12651 56.79191 27 100 71.00000 30.72545 56.7% 51.8 135s

H88254 12660 70.0000000 31.06847 55.6% 51.6 136s

90004 12735 cutoff 29 70.00000 31.48510 55.0% 51.3 140s

94712 13038 47.16076 25 133 70.00000 32.67649 53.3% 50.6 145s

99703 13362 67.70894 33 83 70.00000 33.79679 51.7% 49.9 150s

104838 13642 58.87825 25 50 70.00000 35.05599 49.9% 49.3 155s

109798 13974 68.00000 28 63 70.00000 36.10324 48.4% 48.8 160s

115195 14226 59.57943 35 106 70.00000 37.21187 46.8% 48.1 165s

120649 14479 42.37345 22 132 70.00000 38.37301 45.2% 47.6 170s

125744 14722 67.69983 41 85 70.00000 39.34237 43.8% 47.0 175s

130263 14855 cutoff 43 70.00000 40.27770 42.5% 46.5 180s

136084 15044 46.04586 37 99 70.00000 41.44483 40.8% 45.9 185s

142169 15345 58.99459 29 230 70.00000 42.46910 39.3% 45.2 190s

147471 15473 cutoff 38 70.00000 43.38751 38.0% 44.7 195s

152620 15614 67.35452 42 45 70.00000 44.26672 36.8% 44.3 200s

158697 15643 67.50959 39 60 70.00000 45.33469 35.2% 43.8 205s

164696 15696 48.43651 43 85 70.00000 46.33808 33.8% 43.3 210s

171069 15775 65.79559 29 60 70.00000 47.19855 32.6% 42.8 215s

177742 15799 56.70371 34 135 70.00000 48.13312 31.2% 42.2 220s

184110 15796 cutoff 32 70.00000 48.99305 30.0% 41.8 225s

190402 15770 63.90056 32 100 70.00000 49.82484 28.8% 41.4 230s

197127 15665 68.27773 32 147 70.00000 50.72251 27.5% 40.8 235s

203214 15521 53.33264 30 104 70.00000 51.45710 26.5% 40.4 240s

209923 15363 64.18582 34 57 70.00000 52.22346 25.4% 39.9 245s

216308 15162 68.01103 31 51 70.00000 53.00000 24.3% 39.5 250s

222460 14982 65.91176 28 67 70.00000 53.69521 23.3% 39.0 255s

228182 14647 63.24260 29 92 70.00000 54.42455 22.3% 38.7 260s

H231449 14080 69.0000000 54.82460 20.5% 38.4 262s

*231450 13351 34 68.0000000 54.82460 19.4% 38.4 262s

234062 13076 61.74865 33 51 68.00000 55.24207 18.8% 38.3 265s

241277 12350 62.63768 30 125 68.00000 56.19428 17.4% 37.9 270s

248802 11493 65.42340 31 55 68.00000 57.16884 15.9% 37.5 275s

256120 10499 64.95457 34 68 68.00000 58.21122 14.4% 37.1 280s

263843 9134 64.42189 28 62 68.00000 59.34642 12.7% 36.7 285s

271327 7305 62.32876 34 64 68.00000 60.81444 10.6% 36.2 290s

278667 5256 63.32775 28 116 68.00000 62.43572 8.18% 35.7 295s

284806 3090 cutoff 30 68.00000 64.13496 5.68% 35.3 300s

Cutting planes:

Learned: 19

Cover: 3

MIR: 3

Flow cover: 8

GUB cover: 16

Zero half: 2

Explored 289846 nodes (10145071 simplex iterations) in 302.82 seconds (390.98 work units)

Thread count was 1 (of 8 available processors)

Solution count 10: 68 69 70 ... 80

Optimal solution found (tolerance 1.00e-04)

Best objective 6.800000000000e+01, best bound 6.800000000000e+01, gap 0.0000%

Warm Start with Optimal Solution

Set parameter Threads to value 1

Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (win64)

Thread count: 4 physical cores, 8 logical processors, using up to 1 threads

Optimize a model with 2007 rows, 1423 columns and 10414 nonzeros

Model fingerprint: 0x699314de

Variable types: 803 continuous, 620 integer (620 binary)

Coefficient statistics:

Matrix range [6e-07, 1e+00]

Objective range [1e+00, 1e+00]

Bounds range [1e+00, 1e+00]

RHS range [1e+00, 1e+00]

Loaded user MIP start with objective 68

Presolve removed 4 rows and 4 columns

Presolve time: 0.02s

Presolved: 2003 rows, 1419 columns, 10406 nonzeros

Variable types: 3 continuous, 1416 integer (1416 binary)

Root relaxation: objective 0.000000e+00, 536 iterations, 0.01 seconds (0.02 work units)

Nodes | Current Node | Objective Bounds | Work

Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 0.00000 0 172 68.00000 0.00000 100% - 0s

0 0 0.00000 0 237 68.00000 0.00000 100% - 0s

0 0 0.00000 0 297 68.00000 0.00000 100% - 0s

0 0 0.00000 0 230 68.00000 0.00000 100% - 0s

0 0 0.00000 0 238 68.00000 0.00000 100% - 0s

0 0 0.00000 0 248 68.00000 0.00000 100% - 0s

0 0 0.00000 0 261 68.00000 0.00000 100% - 0s

0 0 0.00000 0 183 68.00000 0.00000 100% - 0s

0 0 0.00000 0 294 68.00000 0.00000 100% - 0s

0 0 0.00000 0 256 68.00000 0.00000 100% - 0s

0 2 0.00000 0 173 68.00000 0.00000 100% - 0s

1024 484 32.67683 11 319 68.00000 0.00000 100% 84.9 5s

2183 652 0.00000 17 296 68.00000 0.00000 100% 88.0 10s

3337 1017 10.89244 21 284 68.00000 0.55968 99.2% 84.5 15s

5306 1650 43.33492 25 219 68.00000 1.55570 97.7% 78.4 20s

7649 2364 23.97120 23 209 68.00000 2.68805 96.0% 74.3 25s

10114 3071 41.02580 26 174 68.00000 3.48583 94.9% 70.2 30s

10686 3188 47.84724 28 218 68.00000 3.82815 94.4% 69.9 35s

13343 3784 12.50000 24 194 68.00000 5.00000 92.6% 67.0 40s

15995 4310 57.93998 27 82 68.00000 6.39319 90.6% 65.3 45s

18609 4850 cutoff 26 68.00000 7.53763 88.9% 64.1 50s

21768 5453 cutoff 37 68.00000 8.78233 87.1% 61.7 55s

24926 6112 45.24113 26 127 68.00000 9.68401 85.8% 59.9 60s

27955 6559 64.71627 41 60 68.00000 10.69394 84.3% 58.9 65s

30867 7009 42.37881 28 148 68.00000 11.64604 82.9% 58.0 70s

33931 7460 16.44213 30 302 68.00000 12.67173 81.4% 57.0 75s

36868 7832 41.73535 22 100 68.00000 13.78936 79.7% 56.2 80s

39883 8197 63.83754 39 121 68.00000 14.94241 78.0% 55.7 85s

43060 8559 58.58417 31 227 68.00000 15.92375 76.6% 55.0 90s

46091 8926 65.93782 41 129 68.00000 16.82282 75.3% 54.3 95s

49287 9262 62.31775 32 183 68.00000 18.00973 73.5% 53.9 100s

52614 9651 cutoff 33 68.00000 19.11029 71.9% 53.3 105s

55407 9892 60.51889 35 245 68.00000 19.98661 70.6% 53.1 110s

58524 10241 50.48396 33 113 68.00000 20.68376 69.6% 52.6 115s

61740 10531 29.80289 30 148 68.00000 21.65296 68.2% 52.2 120s

64760 10844 53.48754 29 67 68.00000 22.41490 67.0% 52.0 125s

67500 11113 32.76890 30 276 68.00000 23.06163 66.1% 51.8 130s

70505 11330 29.55188 32 198 68.00000 23.87610 64.9% 51.7 135s

73612 11613 cutoff 27 68.00000 24.54876 63.9% 51.6 140s

76891 11817 28.89811 27 272 68.00000 25.28002 62.8% 51.5 145s

80344 12064 36.08806 29 235 68.00000 26.21483 61.4% 51.2 150s

83832 12251 50.06738 27 189 68.00000 27.05425 60.2% 50.8 155s

87406 12432 46.94104 27 136 68.00000 27.82834 59.1% 50.6 160s

90858 12584 62.96521 45 55 68.00000 28.62816 57.9% 50.3 165s

94526 12726 35.80055 25 120 68.00000 29.40363 56.8% 50.0 170s

98525 12931 57.84673 39 211 68.00000 30.25805 55.5% 49.6 175s

102353 13133 47.14446 30 174 68.00000 30.96343 54.5% 49.2 180s

106370 13285 cutoff 31 68.00000 31.69662 53.4% 48.8 185s

110282 13417 50.20698 25 222 68.00000 32.45800 52.3% 48.4 190s

114171 13437 39.75648 27 216 68.00000 33.28513 51.1% 48.0 195s

118361 13525 35.79768 29 151 68.00000 34.07255 49.9% 47.6 200s

122522 13621 59.92191 32 129 68.00000 34.93383 48.6% 47.3 205s

126709 13691 38.00672 27 217 68.00000 35.82608 47.3% 47.0 210s

130825 13818 cutoff 30 68.00000 36.56427 46.2% 46.8 215s

134771 13811 63.17190 36 208 68.00000 37.37387 45.0% 46.5 220s

139167 13871 52.85681 28 157 68.00000 38.21258 43.8% 46.2 225s

143632 13887 61.90673 30 207 68.00000 38.95120 42.7% 45.9 230s

148287 13840 59.33192 35 87 68.00000 39.79500 41.5% 45.5 235s

153121 13818 48.43771 32 109 68.00000 40.66538 40.2% 45.2 240s

157884 13713 50.11820 33 134 68.00000 41.45230 39.0% 44.8 245s

162860 13619 cutoff 38 68.00000 42.34322 37.7% 44.5 250s

167311 13539 cutoff 30 68.00000 43.05374 36.7% 44.1 255s

172161 13400 50.38009 31 186 68.00000 43.91223 35.4% 43.8 260s

176329 13267 cutoff 33 68.00000 44.74201 34.2% 43.5 265s

181487 13090 63.09037 31 103 68.00000 45.66002 32.9% 43.2 270s

186744 12843 60.24570 32 152 68.00000 46.55304 31.5% 42.8 275s

192114 12618 60.38548 35 125 68.00000 47.51278 30.1% 42.5 280s

197721 12435 49.99977 33 124 68.00000 48.32484 28.9% 42.1 285s

203205 12133 65.52398 33 81 68.00000 49.09142 27.8% 41.8 290s

208936 11767 63.78670 39 46 68.00000 50.00000 26.5% 41.4 295s

214358 11458 60.70267 47 55 68.00000 50.76252 25.3% 41.1 300s

218932 11254 59.47012 33 79 68.00000 51.35794 24.5% 40.8 305s

223556 10878 56.40169 36 196 68.00000 52.04475 23.5% 40.5 310s

228787 10478 65.29288 38 36 68.00000 52.78745 22.4% 40.3 315s

233352 10047 56.27296 35 216 68.00000 53.47223 21.4% 40.0 320s

238767 9502 infeasible 34 68.00000 54.41626 20.0% 39.7 325s

243504 8893 cutoff 51 68.00000 55.24023 18.8% 39.4 330s

249657 8008 60.67709 30 187 68.00000 56.28146 17.2% 39.1 335s

255309 7118 61.76147 49 206 68.00000 57.34876 15.7% 38.7 340s

262094 5969 62.25019 33 107 68.00000 58.66567 13.7% 38.3 345s

268995 4563 cutoff 36 68.00000 60.34195 11.3% 37.8 350s

275452 2995 infeasible 26 68.00000 62.00000 8.82% 37.5 355s

281890 704 65.76587 37 72 68.00000 64.83833 4.65% 37.0 360s

Cutting planes:

Learned: 21

Cover: 13

Clique: 2

MIR: 9

StrongCG: 2

Flow cover: 31

GUB cover: 251

Inf proof: 1

Zero half: 15

Explored 283134 nodes (10465358 simplex iterations) in 360.83 seconds (468.72 work units)

Thread count was 1 (of 8 available processors)

Solution count 1: 68

Optimal solution found (tolerance 1.00e-04)

Best objective 6.800000000000e+01, best bound 6.800000000000e+01, gap 0.0000%

Riley Clement

Gurobi Staff

February 09, 2024 02:09
Edited

Hi Reza,

I see that you are providing an optimal solution to the solver. Termination (via MIP Gap) will also require the bound to significantly improve from the initial linear relaxation of 0. In the solve where you provide the solution Gurobi does not know the solution is optimal so it will spend time with heuristics trying to improve it. It may be that when it fails to improve it with simpler heuristics it starts to engage more expensive heuristics, which take away time that can be used to improve the bound. In this particular instance you would want to try setting MIPFocus=3 to tell the solver to focus on improving the lower bound.

However, the fact that the solve with the MIP start was worse, may just be a coincidence - never trust a comparison using a single run. A comparison should always be made with a distribution of results (which is where our open source Python package Gurobi-logtools is useful).

A coin analogy
When a coin is fair, we expect that 50% of the time it will land heads up/tails down, and the other 50% of the time it will land heads down/tails up. To perform an experiment to test if the coin is fair, of if one side will land face up more than the other, we would flip the coin many times and analyze the results together. Flipping the coin once, and concluding that whichever way the coin landed is how it will always land would be incorrect.

How to compare two models or solvers?
Comparing two models with only one value of the Seed parameter is like flipping a coin once. If you are not deliberately changing this parameter then it will have the default value of 0. There are random actions that Gurobi performs when solving a model and these actions are based on randomly generated numbers. It is the seed value which controls the sequence of random numbers and therefore the random behavior. When the Seed parameter is kept constant the solver repeats the exact same sequence of actions - "the solution path" - every time it solves the same model. When you change the value of Seed we get a different solution paths, and variety of performance. When making comparisons between two models, or solvers, or machines, or parameter settings, it is important to do so across many values of Seed. The more values you use the more confidence you will have in your conclusions.

- Riley

Reza Belbasi

February 09, 2024 18:27
Edited

Hi Riley,

Thanks for your swift and helpful response! I experimented over a number of different parameter settings to see whether tuning these parameters would make the model having the optimal solution as warm start faster than the cold start model. In light of your suggestion and this post, I considered setting MIPFocus=3, Heuristics=0, RINS=0. Each row is reporting the average runtime of cold start vs warm start with optimal solutoin over 100 independent runs. In run number i, we fix the Seed parameter of Gurobi to i for both cold start and warm start models so that we cover different sees as well. Please find the results below:

Notice that although Seed is fixed, the cold start model returns different average runtimes across different settings. The results show that setting the MIPFocus=3, Heuristic=0 or RINS=0 does not help and indeed makes the difference noticeably larger. However, I realized that one thing works (at least with my model). Rather than warm starting, providing the optimal solution as a hint to Gurobi via VarHintVal. I could not find sources on how one should tune the hint confidence parameter VarHintPri so I tested across different values of VarHintPri={0, 1, 5, 10, 100, 100}. Please find the results below on these below:

We see that Hint with confidence 0 is giving very close averages to cold start. I am not sure how generalizable this is to other MIP problems, but a good option to keep in mind.

February 10, 2024 12:34

VarHintPri is a relative confidence. If you set VarHintPri to 1 for all variables in one experiment, then VarHintPri to 1000 for all variables in another, then in each case you are saying "I am equally confidence about these hints for all variables", but you are not saying that you have more confidence in the values where VarHintPri=1000. Essentially this would make your 6 experiment settings with VarHintPri equivalent (up to randomness) which would make sense as I don't see a trend in either the cold or warm-opt columns.

The results where you compare parameter MIPFocus and RINS settings are interesting and surprising. I would have expected the cold-start runs to be much worse with Heuristics=0, and I would not have expected it to be much worse with the warm-start. At this stage all I can do is offer to try and replicate your results (if you are willing to share an MPS model and MIP start) and explore further what is going on.

February 11, 2024 10:47

Thanks for your response. Understood about the VarHintP parameter. I am ahppy to share the MPS file, how can I share it with you?

February 11, 2024 12:44

Easiest way is to use either Github, or a share drive such as Filemail, Dropbox, Box, Google Drive, OneDrive.

Providing the optimal solution as warm start does not improve runtime of MIP.

Comments

Didn't find what you were looking for?