Slow MIP performance
Answered
I am trying to solve a MIP but the solution and the bound seem to improve very slowly and eventually took far more time to converge than I would have expected it to. I understand MIPs are difficult to solve; however, this particular instance is not huge in size, so I was expecting an indeed quick optimal solution. Additionally, I tried fixing the `MIPFocus` to 2 and 3, `NodeMethod` to 2, `ConcurrentMIP` to 6 (all parameters tried separately) but it didn't help much. Also, I am providing a MIP start. Following is the log:
So, I guess my question is, is it normal for a MIP with just 90 binary variables to take ~1800 s? I am right now solving another MIP with the same size but slightly different data, and it seems to be stuck at 49% gap after 30 minutes. The matrix coefficients seem to be OK, so I was wondering if it's typical for problems of this (small) size to not get solved within a few hours?
Academic license - for non-commercial use only - expires 2022-07-04
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threadsOptimize a model with 5286 rows, 6286 columns and 25069 nonzeros
Model fingerprint: 0xcfcee553
Model has 2642 SOS constraints
Variable types: 6196 continuous, 90 integer (90 binary)
Coefficient statistics:
Matrix range [6e-02, 3e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+03, 1e+03]
RHS range [1e+00, 1e+03]
User MIP start produced solution with objective 26.965 (0.15s)
Loaded user MIP start with objective 26.965
Presolve removed 1834 rows and 914 columns
Presolve time: 0.02s
Presolved: 3452 rows, 5372 columns, 18091 nonzeros
Presolved model has 2641 SOS constraint(s)
Variable types: 5282 continuous, 90 integer (90 binary)
Presolve removed 875 rows and 3551 columns
Presolved: 2577 rows, 1866 columns, 10326 nonzeros
Root relaxation: objective 4.278000e+00, 1636 iterations, 0.08 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 4.27800 0 153 26.96500 4.27800 84.1% - 0s
H 0 0 26.9650000 4.27800 84.1% - 0s
0 0 4.27800 0 203 26.96500 4.27800 84.1% - 0s
0 0 4.27800 0 268 26.96500 4.27800 84.1% - 0s
0 0 4.27800 0 172 26.96500 4.27800 84.1% - 1s
0 0 4.27800 0 172 26.96500 4.27800 84.1% - 1s
H 0 0 26.9650000 4.27800 84.1% - 1s
0 2 4.27800 0 172 26.96500 4.27800 84.1% - 1s
H 35 40 26.9650000 4.27800 84.1% 949 3s
H 35 40 26.9649998 4.27800 84.1% 949 3s
H 40 55 15.1750000 4.27800 71.8% 930 3s
H 46 55 13.1140000 4.27800 67.4% 883 3s
93 139 4.27800 7 340 13.11400 4.27800 67.4% 675 5s
H 101 139 13.1140000 4.27800 67.4% 660 5s
H 255 312 13.1139999 4.27800 67.4% 478 8s
H 259 312 13.1139999 4.27800 67.4% 490 8s
H 332 344 13.1139933 4.27800 67.4% 453 8s
473 524 infeasible 10 13.11399 4.27800 67.4% 394 11s
739 801 4.27800 13 373 13.11399 4.27800 67.4% 366 15s
H 744 801 12.8030000 4.27800 66.6% 366 15s
863 940 4.95069 15 29 12.80300 4.27800 66.6% 355 20s
H 916 958 12.8030000 4.27800 66.6% 350 20s
H 1191 1167 12.8029997 4.27800 66.6% 338 24s
1217 1258 4.27800 12 299 12.80300 4.27800 66.6% 335 27s
H 1280 1298 12.8029997 4.27800 66.6% 335 27s
H 1367 1368 12.8029993 4.27800 66.6% 329 27s
H 1425 1408 12.8029991 4.27800 66.6% 331 27s
H 1504 1387 12.8029807 4.27800 66.6% 329 28s
1509 1390 6.09657 14 10 12.80298 4.27800 66.6% 328 30s
1519 1402 4.27800 15 28 12.80298 4.27800 66.6% 338 38s
1526 1413 4.27800 16 24 12.80298 4.27800 66.6% 345 46s
1556 1421 7.10117 18 319 12.80298 4.27800 66.6% 358 50s
1588 1435 4.27800 19 16 12.80298 4.27800 66.6% 378 55s
1622 1456 4.27800 23 10 12.80298 4.27800 66.6% 396 61s
1643 1466 4.27800 21 30 12.80298 4.27800 66.6% 413 70s
H 1657 1395 12.7930000 4.27800 66.6% 417 70s
1661 1438 4.27800 21 31 12.79300 4.27800 66.6% 420 77s
1721 1441 4.27800 21 26 12.79300 4.27800 66.6% 438 99s
H 1723 1375 12.7930000 4.27800 66.6% 439 99s
1738 1461 4.27800 22 37 12.79300 4.27800 66.6% 452 116s
1865 1545 4.27800 29 20 12.79300 4.27800 66.6% 461 136s
H 2022 1502 12.7930000 4.27800 66.6% 451 136s
2155 1632 4.41612 30 293 12.79300 4.27800 66.6% 456 153s
H 2164 1569 12.7929996 4.27800 66.6% 454 153s
2297 1641 4.27800 26 34 12.79300 4.27800 66.6% 458 170s
2513 1700 5.71286 34 260 12.79300 4.27800 66.6% 457 182s
H 2517 1645 12.7929996 4.27800 66.6% 462 182s
2554 1719 5.75969 26 276 12.79300 4.27800 66.6% 466 195s
2749 1823 6.06878 27 293 12.79300 4.27800 66.6% 464 208s
2884 1899 4.27800 23 32 12.79300 4.27800 66.6% 468 220s
3048 1983 4.27800 25 34 12.79300 4.27800 66.6% 468 234s
3235 2074 4.73414 26 420 12.79300 4.27800 66.6% 465 245s
3368 2145 4.27800 28 35 12.79300 4.27800 66.6% 467 261s
3408 2192 4.45121 24 416 12.79300 4.27800 66.6% 472 274s
3563 2286 5.74876 28 396 12.79300 4.27800 66.6% 471 285s
3709 2345 4.37131 28 377 12.79300 4.27800 66.6% 472 296s
H 3735 2298 12.7929992 4.27800 66.6% 471 296s
H 3754 2256 12.7929968 4.27800 66.6% 473 296s
H 3785 2223 12.7929961 4.27800 66.6% 475 315s
H 3791 2176 12.7929937 4.27800 66.6% 475 315s
3812 2249 4.33064 28 334 12.79299 4.27800 66.6% 477 327s
3945 2367 7.39044 28 371 12.79299 4.27800 66.6% 476 338s
4099 2413 4.59158 25 351 12.79299 4.27800 66.6% 474 350s
4185 2435 7.87502 32 272 12.79299 4.27800 66.6% 477 360s
H 4189 2438 12.7929892 4.27800 66.6% 478 360s
H 4196 2445 12.7929890 4.27800 66.6% 480 360s
4201 2515 5.24980 29 251 12.79299 4.27800 66.6% 481 372s
4420 2691 4.62257 27 319 12.79299 4.31349 66.3% 473 385s
4620 2877 5.61058 30 414 12.79299 4.36164 65.9% 467 398s
4866 3095 5.28812 33 263 12.79299 4.40356 65.6% 458 411s
5127 3310 5.18168 25 368 12.79299 4.45354 65.2% 450 425s
5372 3533 5.75892 29 343 12.79299 4.52504 64.6% 445 440s
5652 3772 5.47674 26 408 12.79299 4.57101 64.3% 438 455s
5931 4012 5.34338 32 272 12.79299 4.62416 63.9% 432 469s
6232 4329 12.45100 31 66 12.79299 4.67036 63.5% 427 485s
6570 4601 5.21576 31 233 12.79299 4.72429 63.1% 420 501s
6909 4862 5.63077 22 415 12.79299 4.77340 62.7% 414 521s
6984 4963 5.75829 28 388 12.79299 4.80154 62.5% 412 538s
7273 5211 9.74379 30 323 12.79299 4.83319 62.2% 408 554s
7620 5494 5.78761 28 358 12.79299 4.86387 62.0% 402 573s
7994 5783 4.94497 34 360 12.79299 4.91451 61.6% 398 593s
8349 6136 5.80089 32 349 12.79299 4.96766 61.2% 395 614s
8651 6389 6.84727 30 295 12.79299 5.02186 60.7% 391 635s
9069 6743 5.68158 34 334 12.79299 5.06516 60.4% 387 657s
9490 7131 7.72085 32 214 12.79299 5.12333 60.0% 383 679s
9930 7480 5.94445 33 235 12.79299 5.16266 59.6% 379 704s
10402 7915 5.24731 25 342 12.79299 5.20767 59.3% 376 728s
10911 8327 5.45679 19 381 12.79299 5.25767 58.9% 372 753s
11458 8799 6.76017 25 395 12.79299 5.30789 58.5% 368 778s
12010 9222 5.93515 34 356 12.79299 5.36310 58.1% 365 803s
12457 9598 7.36031 21 419 12.79299 5.41105 57.7% 363 834s
12600 9720 6.38870 28 390 12.79299 5.43336 57.5% 362 861s
13172 10191 5.68248 32 228 12.79299 5.48759 57.1% 360 890s
13768 10652 8.35889 41 289 12.79299 5.53915 56.7% 358 919s
14402 11184 9.34475 32 248 12.79299 5.57884 56.4% 355 951s
15090 11859 5.93624 29 363 12.79299 5.64168 55.9% 353 985s
15839 12428 cutoff 27 12.79299 5.69273 55.5% 350 1020s
16459 12931 8.23137 32 324 12.79299 5.72628 55.2% 349 1054s
17170 13529 6.70987 34 406 12.79299 5.78984 54.7% 348 1087s
17918 14125 cutoff 34 12.79299 5.83134 54.4% 346 1112s
18257 14429 5.98207 31 348 12.79299 5.86329 54.2% 345 1152s
19339 15162 6.51228 34 241 12.79299 5.90016 53.9% 339 1192s
H20952 16306 12.5690000 5.99599 52.3% 335 1279s
21780 17053 6.70646 22 351 12.56900 6.01638 52.1% 332 1322s
22816 17839 8.23568 35 258 12.56900 6.05485 51.8% 330 1369s
24281 18710 6.67970 26 226 12.56900 6.09533 51.5% 322 1414s
25331 19494 6.96145 28 306 12.56900 6.12463 51.3% 320 1462s
26326 20382 6.99652 30 354 12.56900 6.16160 51.0% 320 1508s
27476 21240 11.57800 32 92 12.56900 6.19761 50.7% 318 1556s
H28519 7728 7.2690000 6.20374 14.7% 314 1556s
28941 6895 cutoff 27 7.26900 6.22379 14.4% 313 1584s
29935 6692 7.19230 24 277 7.26900 6.36705 12.4% 312 1612s
31026 6476 6.84757 31 336 7.26900 6.47934 10.9% 311 1641s
32228 6561 6.77404 32 182 7.26900 6.58721 9.38% 309 1681s
33081 5919 cutoff 43 7.26900 6.63919 8.66% 306 1710s
H33436 0 6.7160000 6.64107 1.12% 305 1710s
Cutting planes:
Gomory: 17
Cover: 1
MIR: 1197
Flow cover: 4047
Relax-and-lift: 6
Explored 34666 nodes (10453372 simplex iterations) in 1710.70 seconds
Thread count was 16 (of 16 available processors)
Solution count 10: 6.716 7.269 12.569 ... 12.793
Optimal solution found (tolerance 1.00e-04)
Best objective 6.716000000000e+00, best bound 6.716000000000e+00, gap 0.0000%
-
Hi Tushar,
The size of a model is not a good indicator of its complexity. There are small MIP instances in the MIPlib2017 which are not still not solved.
Your model has many SOS constraints, looks like it has only SOS constraints correct? From the log, it is hard to tell whether it is the primal or the dual bound pushing the convergence forward. Did you try not providing a mip start? You could also try the NoRelHeurTime parameter to run the no relaxation heuristic before the first LP solve to possibly find a better feasible point early in the run. Experimenting with the BranchDir and VarBranch parameters might help.
If it's fine for you, you could also share the model and someone might have a closer look. It is not possible to upload files in the Community Forum but we discuss a workaround for this in Posting to the Community Forum.
Best regards,
Jaromił0 -
Hi Jaromił,
Thanks for the reply. I want to add some more comments and things I tried:
1. My model does have constraints other than the SOS constraints too. Somehow, the line showing the model size didn't get copied correctly, and it is shown here:
Optimize a model with 5286 rows, 6286 columns and 25069 nonzeros
Also, what exactly do 25069 nonzeros mean? Does it indicate the number of nonzero elements in the coefficient matrix? I looked here , but it's not explicitly mentioned.
2. Yes, I tried without MIP start (that's what I tried before experimenting with other parameters). However, the performance was slightly worse or almost similar without the MIP start.
3. I modified my model and saw the performance improve slightly. I had a constant term in the objective function, leading to slower convergence since it indirectly affects the gap.
4. I tried NoRelHeurTime, and it does seem to help the most in increasing convergence by finding a good feasible solution initially; however, the models still take time to converge or do not converge at all to the set MIPGap. It usually gets stuck around ~5% gap. Also, the VarBranch parameter seems to make no difference.
5. The model I am trying to solve is a bilevel model, which I am reformulating using a package in Julia language, which eventually feeds it to Gurobi. I will see if I can somehow get the mps format file.
With the new model size data shown in point 1 above, do you still think it is not uncommon for models of this size to have difficulty getting converged even if there are no numerical issues in the data? Please let me know if you have some other comments that can be helpful in such a scenario.
Thanks for the help!
0 -
Hi Tushar,
Also, what exactly do 25069 nonzeros mean? Does it indicate the number of nonzero elements in the coefficient matrix? I looked here , but it's not explicitly mentioned.
Correct, it's the number of nonzeros in the coefficient matrix.
With the new model size data shown in point 1 above, do you still think it is not uncommon for models of this size to have difficulty getting converged even if there are no numerical issues in the data?
One cannot say anything about the complexity of a model just from its model statistics. This market-split model from MIPlib2017 is way smaller than yours and is unsolved since several years.
If running NoRelHeurTime improves the primal bound faster than default parameters, then I would stick to it and now focus on the dual bound. You could try experimenting with the BranchDir, Presolve, PreSparsify, and MIPFocus=2/3 parameters.
Maybe our recent Tech Talk on Converting Weak to Strong MIP Formulations hold something useful for your case.
Best regards,
Jaromił1 -
Thanks Jaromił. I will check the parameters you mentioned and the talk too.
0
Please sign in to leave a comment.
Comments
4 comments