Advice on performance tuning of MILP
AnsweredHi everyone!
I'm working on a power plant dispatchment model which has been becoming larger and larger (& slower and slower ;) ) lately. I'm using Excel with the plugin OpenSolver, which allows me to define an MILP problem in Excel but run it through Gurobi. Lately, solving just a tiny version of the model is taking longer than I expected. However, since I'm very unfamiliar with Gurobi and optimisation in general, I find it hard to read the log and figure out what kind of parameters I should tune to improve performance. Or perhaps it's already performing just fine and I just underestimated the computing time it would require.
I was wondering whether based on the solution log below, anyone can see whether or not I should perhaps tune some of the default solver parameters? I feel like since usually the most progress is achieved by heuristics, I should perhaps play around with parameters within the field of heuristics?
Thanks in advance!
Solution log:
"Obj: 68891 rows, 30261 columns, 76428260 nonzeros"
Set parameter MIPGap to value 0.05
Set parameter TimeLimit to value 2147483647
Set parameter IterationLimit to value 2147483647
Set parameter NodefileStart to value 0.5
Set parameter Threads to value 8
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))
"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 8 threads"
"Optimize a model with 68891 rows, 30261 columns and 76428260 nonzeros"
Model fingerprint: 0x30c3ee37
"Variable types: 13451 continuous, 16810 integer (16810 binary)"
Coefficient statistics:
" Matrix range [4e-04, 1e+05]"
" Objective range [1e-02, 6e+06]"
" Bounds range [1e+00, 1e+00]"
" RHS range [1e+00, 1e+05]"
Presolve removed 0 rows and 3 columns (presolve time = 5s) ...
Presolve removed 8405 rows and 3363 columns (presolve time = 13s) ...
Presolve removed 16811 rows and 3367 columns (presolve time = 17s) ...
Presolve removed 16814 rows and 3367 columns (presolve time = 20s) ...
Presolve removed 16814 rows and 5052 columns (presolve time = 35s) ...
Presolve removed 16814 rows and 5052 columns (presolve time = 77s) ...
Presolve removed 16814 rows and 5059 columns (presolve time = 92s) ...
Presolve removed 21851 rows and 5059 columns (presolve time = 96s) ...
Presolve removed 21851 rows and 5059 columns (presolve time = 100s) ...
Presolve removed 21851 rows and 5059 columns (presolve time = 105s) ...
Presolve removed 21851 rows and 5059 columns (presolve time = 110s) ...
Presolve removed 21851 rows and 5059 columns (presolve time = 117s) ...
Presolve removed 22050 rows and 5258 columns (presolve time = 120s) ...
Presolve removed 22050 rows and 5259 columns (presolve time = 126s) ...
Presolve removed 22050 rows and 5259 columns (presolve time = 130s) ...
Presolve removed 22066 rows and 5460 columns (presolve time = 137s) ...
Presolve removed 22071 rows and 5462 columns (presolve time = 140s) ...
Presolve removed 22073 rows and 5466 columns (presolve time = 145s) ...
Presolve removed 22076 rows and 5471 columns (presolve time = 151s) ...
Presolve removed 22076 rows and 5472 columns (presolve time = 160s) ...
Presolve removed 22076 rows and 5472 columns (presolve time = 169s) ...
Presolve removed 22076 rows and 5472 columns (presolve time = 172s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 181s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 188s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 190s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 195s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 200s) ...
Presolve removed 22076 rows and 5473 columns (presolve time = 206s) ...
Presolve removed 22276 rows and 5673 columns (presolve time = 210s) ...
Presolve removed 22276 rows and 5673 columns (presolve time = 215s) ...
Presolve removed 22276 rows and 5873 columns (presolve time = 220s) ...
Presolve removed 22279 rows and 5878 columns (presolve time = 225s) ...
Presolve removed 22282 rows and 5884 columns (presolve time = 232s) ...
Presolve removed 22284 rows and 5887 columns (presolve time = 235s) ...
Presolve removed 22284 rows and 5888 columns (presolve time = 244s) ...
Presolve removed 22284 rows and 5888 columns (presolve time = 247s) ...
Presolve removed 22284 rows and 5888 columns (presolve time = 253s) ...
Presolve removed 22284 rows and 5888 columns (presolve time = 256s) ...
Presolve removed 22284 rows and 5889 columns (presolve time = 265s) ...
Presolve removed 22284 rows and 5889 columns (presolve time = 272s) ...
Presolve removed 22284 rows and 5889 columns (presolve time = 275s) ...
Presolve removed 22284 rows and 5889 columns (presolve time = 280s) ...
Presolve removed 22284 rows and 5889 columns (presolve time = 285s) ...
Presolve removed 22484 rows and 6089 columns (presolve time = 292s) ...
Presolve removed 22484 rows and 6089 columns (presolve time = 297s) ...
Presolve removed 22484 rows and 6089 columns (presolve time = 301s) ...
Presolve removed 22486 rows and 6292 columns (presolve time = 307s) ...
Presolve removed 22488 rows and 6296 columns (presolve time = 311s) ...
Presolve removed 22490 rows and 6300 columns (presolve time = 315s) ...
Presolve removed 22492 rows and 6304 columns (presolve time = 328s) ...
Presolve removed 22492 rows and 6304 columns (presolve time = 330s) ...
Presolve removed 22492 rows and 6305 columns (presolve time = 340s) ...
Presolve removed 22492 rows and 6305 columns (presolve time = 340s) ...
Presolve removed 22492 rows and 6305 columns (presolve time = 345s) ...
Presolve removed 22692 rows and 6505 columns (presolve time = 352s) ...
Presolve removed 22692 rows and 6505 columns (presolve time = 355s) ...
Presolve removed 22692 rows and 6705 columns (presolve time = 360s) ...
Presolve removed 22696 rows and 6712 columns (presolve time = 367s) ...
Presolve removed 22698 rows and 6716 columns (presolve time = 371s) ...
Presolve removed 22700 rows and 6719 columns (presolve time = 375s) ...
Presolve removed 22700 rows and 6720 columns (presolve time = 384s) ...
Presolve removed 22700 rows and 6720 columns (presolve time = 387s) ...
Presolve removed 22700 rows and 6721 columns (presolve time = 396s) ...
Presolve removed 22700 rows and 6721 columns (presolve time = 401s) ...
Presolve removed 22900 rows and 6921 columns (presolve time = 406s) ...
Presolve removed 22900 rows and 6921 columns (presolve time = 410s) ...
Presolve removed 22900 rows and 7121 columns (presolve time = 416s) ...
Presolve removed 22903 rows and 7126 columns (presolve time = 421s) ...
Presolve removed 22905 rows and 7130 columns (presolve time = 425s) ...
Presolve removed 22908 rows and 7135 columns (presolve time = 431s) ...
Presolve removed 22908 rows and 7136 columns (presolve time = 440s) ...
Presolve removed 22908 rows and 7137 columns (presolve time = 452s) ...
Presolve removed 22908 rows and 7137 columns (presolve time = 457s) ...
Presolve removed 23108 rows and 7337 columns (presolve time = 462s) ...
Presolve removed 23108 rows and 7337 columns (presolve time = 465s) ...
Presolve removed 23108 rows and 7537 columns (presolve time = 471s) ...
Presolve removed 23111 rows and 7542 columns (presolve time = 477s) ...
Presolve removed 23113 rows and 7546 columns (presolve time = 481s) ...
Presolve removed 23115 rows and 7550 columns (presolve time = 485s) ...
Presolve removed 23116 rows and 7552 columns (presolve time = 495s) ...
Presolve removed 23116 rows and 7553 columns (presolve time = 507s) ...
Presolve removed 23116 rows and 7553 columns (presolve time = 512s) ...
Presolve removed 23359 rows and 7796 columns (presolve time = 517s) ...
Presolve removed 23359 rows and 7796 columns (presolve time = 521s) ...
Presolve removed 23481 rows and 8199 columns (presolve time = 526s) ...
Presolve removed 23543 rows and 8261 columns (presolve time = 530s) ...
Presolve removed 23549 rows and 8323 columns (presolve time = 536s) ...
Presolve removed 23549 rows and 8323 columns (presolve time = 541s) ...
Presolve removed 23549 rows and 8323 columns (presolve time = 545s) ...
Presolve removed 23549 rows and 8323 columns (presolve time = 558s) ...
Presolve removed 23557 rows and 8331 columns (presolve time = 560s) ...
Presolve removed 23557 rows and 8331 columns (presolve time = 565s) ...
Presolve removed 23557 rows and 8331 columns (presolve time = 570s) ...
Presolve removed 23557 rows and 8331 columns (presolve time = 580s) ...
Presolve removed 23953 rows and 8822 columns (presolve time = 580s) ...
Presolve removed 23953 rows and 8822 columns (presolve time = 585s) ...
Presolve added 0 rows and 4473 columns
Presolve removed 10658 rows and 0 columns
Presolve time: 587.08s
"Presolved: 58233 rows, 34734 columns, 16101952 nonzeros"
"Variable types: 11381 continuous, 23353 integer (10079 binary)"
"Deterministic concurrent LP optimizer: primal simplex, dual simplex, and barrier"
Showing barrier log only...
Root barrier log...
Elapsed ordering time = 5s
Elapsed ordering time = 6s
Elapsed ordering time = 9s
Elapsed ordering time = 10s
Ordering time: 10.63s
Barrier statistics:
Dense cols : 9505
AA' NZ : 1.938e+07
Factor NZ : 1.091e+08 (roughly 1.0 GB of memory)
Factor Ops : 6.667e+11 (roughly 3 seconds per iteration)
Threads : 5
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.26806564e+15 -1.91472050e+16 5.80e+10 1.32e+04 6.37e+12 637s
1 6.90801157e+14 -7.08608026e+15 1.82e+10 3.40e+04 1.92e+12 642s
2 8.89721930e+13 -2.96968348e+15 2.50e+09 3.14e+03 2.83e+11 648s
3 2.45631849e+13 -9.39874964e+14 8.03e+07 6.52e+02 1.81e+10 654s
4 1.96512907e+13 -1.63449332e+14 6.06e+06 1.26e+02 2.42e+09 660s
5 7.86229452e+12 -1.05411865e+13 1.66e+06 4.71e+00 3.07e+08 665s
6 1.96921398e+12 -3.91656052e+12 2.01e+05 1.42e+00 8.42e+07 672s
7 4.85947627e+11 -9.23892262e+11 3.85e+04 2.56e-01 1.88e+07 678s
8 5.62376101e+10 -9.23274028e+10 3.00e+03 9.59e-03 1.76e+06 685s
9 4.82057429e+09 -1.11086987e+10 1.73e+02 1.87e-03 1.57e+05 692s
10 6.33102549e+07 -7.93819862e+08 1.74e-09 2.73e-04 7.47e+03 698s
11 2.03882078e+07 -2.37674457e+07 1.86e-09 4.02e-06 3.85e+02 705s
12 1.53302288e+07 -4.93114384e+06 1.13e-09 1.56e-06 1.76e+02 711s
13 8.73131931e+06 5.42531367e+06 3.47e-10 3.67e-07 2.88e+01 719s
14 7.53293567e+06 6.21087926e+06 1.19e-10 1.40e-07 1.15e+01 726s
15 7.17429523e+06 6.50975534e+06 5.86e-11 6.58e-08 5.79e+00 732s
16 7.04109686e+06 6.60975466e+06 3.79e-11 4.43e-08 3.76e+00 739s
Barrier performed 16 iterations in 743.20 seconds (649.02 work units)
Barrier solve interrupted - model solved by another algorithm
Concurrent spin time: 10.24s
Solved with dual simplex
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
22177 6.8120604e+06 0.000000e+00 0.000000e+00 754s
"Root relaxation: objective 6.812060e+06, 22177 iterations, 155.26 seconds (193.69 work units)"
Total elapsed time = 757.97s (DegenMoves)
Total elapsed time = 760.53s (DegenMoves)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 6812060.44 0 1348 - 6812060.44 - - 761s
H 0 0 2.558719e+07 6812060.44 73.4% - 812s
0 0 6812189.15 0 1852 2.5587e+07 6812189.15 73.4% - 830s
0 0 6812294.20 0 2036 2.5587e+07 6812294.20 73.4% - 898s
0 0 6812320.97 0 2433 2.5587e+07 6812320.97 73.4% - 913s
0 0 6812335.05 0 2572 2.5587e+07 6812335.05 73.4% - 927s
0 0 6812335.05 0 2572 2.5587e+07 6812335.05 73.4% - 947s
0 2 6812335.05 0 2572 2.5587e+07 6812335.05 73.4% - 1043s
1 4 6812335.05 1 2573 2.5587e+07 6812335.05 73.4% 140 1047s
3 8 6812335.05 2 2574 2.5587e+07 6812335.05 73.4% 75.3 1053s
7 16 6812335.05 3 2575 2.5587e+07 6812335.05 73.4% 81.1 1066s
15 24 6812335.05 4 2576 2.5587e+07 6812335.05 73.4% 86.4 1072s
23 32 6813154.46 4 8427 2.5587e+07 6812335.05 73.4% 63.9 1078s
31 40 6812335.05 5 2577 2.5587e+07 6812335.05 73.4% 55.9 1612s
39 48 6813154.46 5 8428 2.5587e+07 6812335.05 73.4% 48.5 1619s
47 60 6812335.05 6 2578 2.5587e+07 6812335.05 73.4% 48.3 1625s
59 72 6813154.46 6 8420 2.5587e+07 6812335.05 73.4% 45.3 1631s
71 85 6812335.05 7 2579 2.5587e+07 6812335.05 73.4% 41.1 1637s
84 96 6813154.46 7 8424 2.5587e+07 6812335.05 73.4% 39.4 1643s
95 110 6812335.05 8 2580 2.5587e+07 6812335.05 73.4% 37.9 1650s
109 122 6813154.46 8 8431 2.5587e+07 6812335.05 73.4% 36.9 1657s
121 135 6812335.05 9 2581 2.5587e+07 6812335.05 73.4% 36.6 1663s
134 149 6813154.46 9 8433 2.5587e+07 6812335.05 73.4% 36.6 1672s
148 165 6812335.05 10 2582 2.5587e+07 6812335.05 73.4% 36.2 1679s
164 181 6812335.05 12 2584 2.5587e+07 6812335.05 73.4% 35.8 1687s
180 197 6812335.05 14 2586 2.5587e+07 6812335.05 73.4% 35.1 1696s
196 213 6812335.05 15 2587 2.5587e+07 6812335.05 73.4% 35.2 1705s
212 230 6812335.05 16 2588 2.5587e+07 6812335.05 73.4% 35.3 1713s
229 246 6812335.05 17 2589 2.5587e+07 6812335.05 73.4% 35.3 1722s
245 262 6812335.05 18 2590 2.5587e+07 6812335.05 73.4% 35.3 1730s
261 279 6812335.05 19 2591 2.5587e+07 6812335.05 73.4% 35.3 1739s
278 298 6812335.05 20 2592 2.5587e+07 6812335.05 73.4% 35.3 1747s
297 321 6812335.05 21 2593 2.5587e+07 6812335.05 73.4% 35.0 1757s
320 344 6812335.05 22 2594 2.5587e+07 6812335.05 73.4% 34.5 1765s
343 370 6812335.05 23 2595 2.5587e+07 6812335.05 73.4% 34.0 1776s
369 392 6813154.46 25 8452 2.5587e+07 6812335.05 73.4% 33.3 1786s
391 415 6812335.05 26 2598 2.5587e+07 6812335.05 73.4% 32.4 1796s
414 436 6812335.05 27 2599 2.5587e+07 6812335.05 73.4% 31.9 1807s
435 458 6812335.05 28 2600 2.5587e+07 6812335.05 73.4% 32.2 1817s
457 475 6813159.95 31 8453 2.5587e+07 6812335.05 73.4% 32.1 1828s
474 501 6812335.06 32 2604 2.5587e+07 6812335.05 73.4% 32.5 1840s
500 527 6812335.06 34 2606 2.5587e+07 6812335.05 73.4% 32.7 1854s
526 550 6812335.06 36 2608 2.5587e+07 6812335.05 73.4% 33.1 1866s
549 582 6812335.06 38 2610 2.5587e+07 6812335.05 73.4% 33.5 1880s
581 617 6812335.06 43 2615 2.5587e+07 6812335.05 73.4% 33.0 1895s
616 662 6812335.06 48 2620 2.5587e+07 6812335.05 73.4% 31.9 1913s
661 715 6812335.06 55 2627 2.5587e+07 6812335.05 73.4% 30.6 1938s
714 795 6812335.06 63 2635 2.5587e+07 6812335.05 73.4% 29.8 1965s
794 905 6812335.06 71 2643 2.5587e+07 6812335.05 73.4% 28.5 2590s
904 1000 6812335.06 81 2653 2.5587e+07 6812335.05 73.4% 27.1 2627s
999 1128 6812335.06 95 2667 2.5587e+07 6812335.05 73.4% 26.5 2672s
1127 1292 6812335.06 112 2684 2.5587e+07 6812335.05 73.4% 25.8 2725s
1291 1474 6812335.06 129 2701 2.5587e+07 6812335.05 73.4% 25.1 2784s
1473 1702 6812335.06 152 2724 2.5587e+07 6812335.05 73.4% 24.5 2852s
1701 1948 6812340.87 178 2746 2.5587e+07 6812335.05 73.4% 23.5 2928s
1947 2246 6812343.15 208 2746 2.5587e+07 6812335.05 73.4% 22.2 3036s
2245 2419 6812483.27 247 2745 2.5587e+07 6812335.05 73.4% 20.0 3122s
2418 2515 6812493.67 248 2745 2.5587e+07 6812335.05 73.4% 18.8 3357s
H 2429 2515 2.558185e+07 6812335.05 73.4% 18.7 3358s
2514 2937 6812532.30 260 2746 2.5582e+07 6812335.05 73.4% 18.2 3517s
2936 3396 6812987.25 333 2637 2.5582e+07 6812335.05 73.4% 16.0 3698s
3395 3869 6813051.84 372 2668 2.5582e+07 6812335.05 73.4% 14.1 3890s
3868 4369 6813197.81 401 2697 2.5582e+07 6812335.05 73.4% 12.6 4090s
4368 4918 6813197.81 432 2721 2.5582e+07 6812335.05 73.4% 11.4 4300s
4917 5613 6819408.33 487 2419 2.5582e+07 6812335.05 73.4% 10.3 4520s
H 5612 5621 1.875565e+07 6812335.05 63.7% 9.1 5033s
H 5613 5621 1.510742e+07 6812335.05 54.9% 9.1 5034s
H 5615 5621 1.372574e+07 6812335.05 50.4% 9.1 5035s
H 5619 5621 1.364192e+07 6812335.05 50.1% 9.1 5035s
5620 5629 6819408.33 563 2495 1.3642e+07 6812335.05 50.1% 9.1 6050s
5628 6268 6819408.33 564 2496 1.3642e+07 6812335.05 50.1% 9.1 6290s
6267 7036 6819408.33 633 2565 1.3642e+07 6812335.05 50.1% 8.5 6521s
7035 7806 6819408.33 713 2645 1.3642e+07 6812335.05 50.1% 8.5 6753s
H 7805 7804 7033573.0564 6812335.05 3.15% 8.0 6918s
7806 7805 6816825.07 819 2572 7033573.06 6812335.05 3.15% 8.0 8284s
Explored 7806 nodes (85254 simplex iterations) in 8288.32 seconds (9132.32 work units)
Thread count was 8 (of 16 available processors)
Solution count 7: 7.03357e+06 1.36419e+07 1.37257e+07 ... 2.55872e+07
Optimal solution found (tolerance 5.00e-02)
"Best objective 7.033573056390e+06, best bound 6.812335050544e+06, gap 3.1455%"
-
Hi Jesse,
In the log file, you can see that the best bound does not improve after the root node is solved; it stays at the value 6812335.05. Only incumbents improve the gap from 73% to 3%.
You could try parameters that focus on finding good solutions, for example- set MIPFocus=1
- experiment with Heuristics, for example, Heuristics=0.5
- test the no-relaxation heuristic by setting the parameter NoRelHeurTime to the number of seconds the heuristic should run, for example, NoRelHeurTime=600
Additionally, you could experiment with the parameter PrePasses to try to reduce the time spent in Presolve (without losing too much performance) or try to reduce Presolve with Presolve=1 (but this might already be the default here).
Best regards,
Marika1 -
Hi Marika,
Thank you so much for your quick response, I will try playing around with these parameters immediately ;)
Regards,
Jesse
0 -
In case anyone is dealing with a comparable situation and manages to find this post: the suggestion above worked and the solution is now found within 1000 seconds generally ;) A huge improvement!
1
Please sign in to leave a comment.
Comments
3 comments