How to speed up a MILP?
Answered
Dear Gurobi Community,
I've worked on a MILP problem with 441 binary and 496 integer variables. I've set the "MIPFocus" to 3 and used "NoRelHeurTime" to limit the amount of time spent in the NoRel heuristic. These two parameters do help, but it still looks like it's taking too long (around 2000 seconds) to solve the problem. More precisely, the best bound and the gap improve very slow after 1400 and 24%. Since my real goal is solving the same MILP with 10000 variables, so the current speed is still too slow. Therefore, I am wondering if there are any more parameters I should be considering. Thanks! Here is the log:
Set parameter MIPFocus to value 3
Set parameter NoRelHeurTime to value 10
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (linux64)
Thread count: 40 physical cores, 40 logical processors, using up to 32 threads
Optimize a model with 945 rows, 903 columns and 3885 nonzeros
Model fingerprint: 0x5a467acc
Variable types: 0 continuous, 903 integer (441 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [3e+00, 8e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+00]
Found heuristic solution: objective 6470.0000000
Presolve removed 814 rows and 407 columns
Presolve time: 0.01s
Presolved: 131 rows, 496 columns, 1527 nonzeros
Variable types: 0 continuous, 496 integer (441 binary)
Starting NoRel heuristic
Found heuristic solution: objective 6020.0000000
Found heuristic solution: objective 4557.0000000
Found heuristic solution: objective 4541.0000000
Found heuristic solution: objective 4329.0000000
Found heuristic solution: objective 3949.0000000
Found heuristic solution: objective 3497.0000000
Found heuristic solution: objective 3454.0000000
Found heuristic solution: objective 3308.0000000
Found heuristic solution: objective 2927.0000000
Found heuristic solution: objective 2620.0000000
Found heuristic solution: objective 2596.0000000
Found heuristic solution: objective 2580.0000000
Found heuristic solution: objective 2541.0000000
Found heuristic solution: objective 2430.0000000
Found heuristic solution: objective 2360.0000000
Found heuristic solution: objective 2317.0000000
Found heuristic solution: objective 2163.0000000
Found heuristic solution: objective 2019.0000000
Found heuristic solution: objective 1993.0000000
Found heuristic solution: objective 1983.0000000
Found heuristic solution: objective 1911.0000000
Found heuristic solution: objective 1907.0000000
Found heuristic solution: objective 1899.0000000
Found heuristic solution: objective 1841.0000000
Elapsed time for NoRel heuristic: 5s (best bound 0)
Elapsed time for NoRel heuristic: 11s (best bound 0)
Root relaxation presolve removed 1 rows and 0 columns
Root relaxation presolved: 130 rows, 496 columns, 1506 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 0.0000000e+00 5.700000e+01 0.000000e+00 11s
169 0.0000000e+00 0.000000e+00 0.000000e+00 11s
169 0.0000000e+00 0.000000e+00 0.000000e+00 11s
Root relaxation: objective 0.000000e+00, 169 iterations, 0.01 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 58 1841.00000 0.00000 100% - 10s
0 0 34.01987 0 69 1841.00000 34.01987 98.2% - 10s
0 0 60.62815 0 96 1841.00000 60.62815 96.7% - 10s
0 0 93.87334 0 134 1841.00000 93.87334 94.9% - 11s
0 0 170.76074 0 141 1841.00000 170.76074 90.7% - 11s
0 0 217.07117 0 148 1841.00000 217.07117 88.2% - 11s
0 0 253.01258 0 151 1841.00000 253.01258 86.3% - 11s
0 0 271.12344 0 177 1841.00000 271.12344 85.3% - 12s
0 0 281.89168 0 186 1841.00000 281.89168 84.7% - 12s
0 0 321.16107 0 180 1841.00000 321.16107 82.6% - 12s
0 0 329.38681 0 197 1841.00000 329.38681 82.1% - 13s
0 0 334.83465 0 229 1841.00000 334.83465 81.8% - 13s
0 0 334.83465 0 229 1841.00000 334.83465 81.8% - 13s
0 2 335.98268 0 229 1841.00000 335.98268 81.7% - 13s
91 111 344.84742 7 236 1841.00000 344.84742 81.3% 299 15s
2585 1989 infeasible 52 1841.00000 479.19416 74.0% 364 20s
2962 2150 585.37591 65 206 1841.00000 585.37591 68.2% 353 25s
2976 2159 716.54295 78 254 1841.00000 678.96795 63.1% 352 30s
2987 2166 733.17663 34 278 1841.00000 733.17663 60.2% 350 35s
2993 2173 735.76878 11 268 1841.00000 735.76878 60.0% 358 40s
3015 2189 infeasible 14 1841.00000 739.02369 59.9% 362 45s
3275 2316 1030.31290 22 257 1841.00000 795.15425 56.8% 395 50s
3437 2367 1560.74036 26 228 1841.00000 815.31257 55.7% 404 58s
3612 2466 1648.33964 31 230 1841.00000 822.82458 55.3% 417 62s
3982 2680 853.67896 42 216 1841.00000 845.58901 54.1% 442 70s
4798 3297 934.82293 74 199 1841.00000 934.82293 49.2% 483 75s
5711 3907 1554.32078 46 191 1841.00000 1032.17438 43.9% 520 80s
6592 4421 1126.42007 44 217 1841.00000 1051.28529 42.9% 542 85s
7731 4911 1722.51601 48 187 1841.00000 1077.55154 41.5% 568 90s
8795 5624 1736.30699 49 175 1841.00000 1096.11835 40.5% 580 95s
10172 6553 1278.81767 54 170 1841.00000 1123.19595 39.0% 585 100s
11590 7747 1351.40273 44 182 1841.00000 1143.09474 37.9% 581 105s
13263 8893 1392.72952 56 192 1841.00000 1159.55210 37.0% 579 111s
14421 10030 1502.17062 30 181 1841.00000 1169.93613 36.5% 576 115s
16695 11746 1187.65571 28 219 1841.00000 1187.65571 35.5% 567 120s
18308 13105 1617.21764 40 220 1841.00000 1201.37508 34.7% 563 125s
21477 15522 1620.45510 52 172 1841.00000 1217.39082 33.9% 545 131s
23526 16916 1226.40241 36 182 1841.00000 1225.90069 33.4% 539 136s
25795 18626 1623.38210 52 171 1841.00000 1234.99989 32.9% 532 141s
28545 20752 1645.24602 78 172 1841.00000 1246.48416 32.3% 521 147s
30068 21981 1476.65356 73 130 1841.00000 1250.40120 32.1% 513 150s
33023 23972 1268.47299 37 176 1841.00000 1265.46607 31.3% 502 155s
36000 25884 1297.50350 67 168 1841.00000 1276.43082 30.7% 489 161s
39090 27823 1441.61617 53 160 1841.00000 1284.47306 30.2% 479 166s
42521 30378 1475.36937 50 164 1841.00000 1294.06761 29.7% 469 172s
44435 31733 cutoff 63 1841.00000 1299.06758 29.4% 463 175s
48379 34200 cutoff 45 1841.00000 1307.02058 29.0% 452 181s
52679 37067 1335.49223 39 187 1841.00000 1316.73323 28.5% 442 188s
55018 38557 1390.06929 80 134 1841.00000 1321.67535 28.2% 437 191s
57448 40078 cutoff 81 1841.00000 1326.42705 28.0% 432 195s
60000 42232 1330.72579 52 196 1841.00000 1330.43855 27.7% 427 200s
63492 43029 1526.57266 56 122 1841.00000 1335.38276 27.5% 421 206s
64808 44863 1771.83157 64 151 1841.00000 1337.09694 27.4% 419 211s
68146 46974 1342.68921 41 197 1841.00000 1342.25299 27.1% 413 215s
71548 49079 cutoff 66 1841.00000 1348.91223 26.7% 408 220s
78855 53269 1656.43739 52 117 1841.00000 1359.21825 26.2% 396 230s
85857 57863 cutoff 58 1841.00000 1366.50476 25.8% 386 239s
89874 60791 1590.80612 80 132 1841.00000 1371.70710 25.5% 380 245s
98630 64484 1739.04551 72 171 1841.00000 1380.95284 25.0% 371 253s
101996 66552 cutoff 50 1841.00000 1383.69464 24.8% 367 257s
105658 68409 1391.14970 100 164 1841.00000 1387.43539 24.6% 363 261s
109003 70331 1609.84771 83 131 1841.00000 1390.67073 24.5% 360 265s
115862 73705 cutoff 53 1841.00000 1395.70250 24.2% 355 273s
119364 76222 1809.41111 65 158 1841.00000 1399.29679 24.0% 352 278s
124182 78007 1735.24478 62 100 1841.00000 1401.98387 23.8% 349 282s
127707 79390 1406.86054 86 190 1841.00000 1405.22554 23.7% 346 287s
130248 81265 cutoff 66 1841.00000 1407.48376 23.5% 344 292s
133739 83243 cutoff 45 1841.00000 1409.73216 23.4% 342 296s
137650 85032 1413.02510 96 145 1841.00000 1412.62426 23.3% 340 300s
144866 88559 1764.80654 68 131 1841.00000 1417.80865 23.0% 336 308s
148451 90892 1607.93112 87 116 1841.00000 1420.10454 22.9% 334 313s
153179 92574 1435.41867 83 194 1841.00000 1423.62826 22.7% 331 317s
156758 94171 1521.68089 57 146 1841.00000 1425.27037 22.6% 329 321s
163774 97371 cutoff 108 1841.00000 1429.62806 22.3% 326 328s
167106 99107 1451.97891 58 148 1841.00000 1432.24724 22.2% 324 332s
170652 100525 1705.66290 70 109 1841.00000 1434.12631 22.1% 323 336s
173707 102198 cutoff 48 1841.00000 1435.22976 22.0% 321 340s
177303 104297 cutoff 99 1841.00000 1437.97843 21.9% 320 345s
185865 107375 1512.76748 62 137 1841.00000 1442.11267 21.7% 316 352s
189004 108932 1797.50103 78 134 1841.00000 1443.88695 21.6% 315 356s
195842 111906 cutoff 41 1841.00000 1447.26596 21.4% 312 363s
199381 113270 cutoff 61 1841.00000 1448.70688 21.3% 311 367s
202562 114442 cutoff 63 1841.00000 1450.06721 21.2% 310 371s
205109 116143 1821.63300 78 102 1841.00000 1451.84588 21.1% 309 375s
209033 117921 cutoff 53 1841.00000 1453.33653 21.1% 308 380s
217203 120025 1603.47921 45 104 1841.00000 1457.49752 20.8% 305 387s
218902 121096 1458.82489 86 173 1841.00000 1458.59199 20.8% 304 392s
222025 122572 cutoff 66 1841.00000 1459.05082 20.7% 303 396s
225898 124086 1768.46133 70 114 1841.00000 1461.71964 20.6% 302 400s
233558 126767 cutoff 60 1841.00000 1465.06095 20.4% 300 407s
237294 128298 1792.93032 47 151 1841.00000 1467.12541 20.3% 299 411s
241036 129828 1472.90703 94 160 1841.00000 1469.04056 20.2% 298 415s
248991 132376 1474.51509 85 122 1841.00000 1473.43110 20.0% 296 423s
252754 133623 cutoff 70 1841.00000 1475.33438 19.9% 295 427s
256311 134833 1501.23701 98 136 1841.00000 1477.40154 19.8% 294 430s
263610 137347 cutoff 75 1841.00000 1480.70951 19.6% 292 438s
267130 138576 cutoff 82 1841.00000 1482.59426 19.5% 291 441s
270624 139958 1626.31434 94 143 1841.00000 1483.91020 19.4% 290 446s
278706 142351 cutoff 53 1841.00000 1487.55851 19.2% 288 453s
282426 143485 1514.14612 58 148 1841.00000 1489.03200 19.1% 287 457s
285917 144465 cutoff 55 1841.00000 1490.88998 19.0% 287 461s
288412 144645 1538.32713 33 146 1841.00000 1491.36492 19.0% 286 469s
288996 146092 1836.90009 54 126 1841.00000 1492.12324 19.0% 286 473s
293329 147413 1772.83434 103 122 1841.00000 1493.88892 18.9% 285 477s
297381 148725 cutoff 101 1841.00000 1495.50197 18.8% 284 481s
301305 150218 1826.93669 52 180 1841.00000 1497.32110 18.7% 283 485s
309375 152499 1780.80584 65 131 1841.00000 1500.55315 18.5% 281 492s
312845 153666 cutoff 85 1841.00000 1501.51015 18.4% 281 496s
320173 155829 cutoff 54 1841.00000 1504.78369 18.3% 279 503s
323931 156971 1555.95663 68 149 1841.00000 1506.30917 18.2% 278 506s
327330 158265 1602.52995 60 157 1841.00000 1507.78531 18.1% 278 510s
335693 160827 cutoff 121 1841.00000 1510.66615 17.9% 276 518s
339372 161759 cutoff 55 1841.00000 1512.06243 17.9% 275 522s
342566 162713 1523.74839 92 143 1841.00000 1513.07738 17.8% 274 525s
350015 165130 1521.35070 51 151 1841.00000 1515.89205 17.7% 273 532s
353796 166412 cutoff 81 1841.00000 1517.55120 17.6% 272 535s
361159 168964 1633.77865 72 126 1841.00000 1519.76975 17.4% 271 543s
365796 169812 cutoff 60 1841.00000 1521.27785 17.4% 270 546s
368972 170355 infeasible 86 1841.00000 1522.77204 17.3% 269 551s
375332 172772 cutoff 64 1841.00000 1524.66239 17.2% 268 558s
379479 173965 1531.61649 65 152 1841.00000 1526.05398 17.1% 267 562s
383470 175182 1530.63927 47 158 1841.00000 1527.40097 17.0% 266 565s
391215 177771 cutoff 70 1841.00000 1530.08617 16.9% 265 573s
395821 178842 1838.18389 62 118 1841.00000 1531.44749 16.8% 264 577s
399732 179993 1533.89628 68 125 1841.00000 1532.66900 16.7% 264 580s
403402 180592 1718.27384 99 150 1841.00000 1533.89670 16.7% 263 587s
405260 181690 cutoff 66 1841.00000 1534.11486 16.7% 263 591s
413157 183876 1546.88276 68 145 1841.00000 1536.87318 16.5% 261 597s
417194 185007 cutoff 67 1841.00000 1538.02386 16.5% 260 600s
^Z
[45]+ Stopped ./gurobi.sh cluster.py
0
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Hi Yansong,
It is possible that parameters won't be helpful here. You could try running the No Relaxation heuristic for more time to get a better feasible point. However, to me it looks like the lower bound progress is taking too long. You might want to have a look at our recent Tech Talk on strong MIP formulations to possibly improve your model formulation.
Best regards,
Jaromił0 -
Post is closed for comments.
Comments
2 comments