Speeding up binary LP?
Answered
I am running a big MIP, but all the integer variables are binary. The best bound is moving very slowly, and the objective doesn't improve much after the first few iterations. The below is the log of the run. Any thoughts on how to improve the performance of this problem?
Changed value of parameter TimeLimit to 7200.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 376843 rows, 133063 columns and 1051659 nonzeros
Model fingerprint: 0x37b7ae04
Variable types: 15 continuous, 133048 integer (133048 binary)
Coefficient statistics:
Matrix range [9e-02, 1e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e-02, 1e+04]
Presolve removed 269726 rows and 77626 columns
Presolve time: 4.65s
Presolved: 107117 rows, 55437 columns, 499607 nonzeros
Variable types: 7 continuous, 55430 integer (55406 binary)
Found heuristic solution: objective 1688.0000000
Found heuristic solution: objective 1666.0000000
Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...
Presolved: 107117 rows, 55437 columns, 499607 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.6650000e+03 1.062688e+01 6.617114e+09 6s
16180 0.0000000e+00 0.000000e+00 0.000000e+00 6s
Concurrent spin time: 0.03s
Solved with primal simplex (primal model)
Root relaxation: objective 0.000000e+00, 16180 iterations, 0.50 seconds
Total elapsed time = 10.18s
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 1624 1666.00000 0.00000 100% - 20s
0 0 0.00000 0 1688 1666.00000 0.00000 100% - 26s
H 0 0 1639.0000000 0.00000 100% - 27s
0 0 0.00000 0 1859 1639.00000 0.00000 100% - 32s
0 0 0.00000 0 1723 1639.00000 0.00000 100% - 41s
0 0 0.00000 0 1723 1639.00000 0.00000 100% - 43s
0 2 0.00000 0 1723 1639.00000 0.00000 100% - 55s
1 4 0.00000 1 5804 1639.00000 0.00000 100% 16425 61s
3 8 0.00000 2 16027 1639.00000 0.00000 100% 14375 70s
7 16 0.00100 3 15635 1639.00000 0.00000 100% 17429 152s
15 24 77.20126 4 12186 1639.00000 0.00000 100% 16865 231s
23 32 27.67615 4 20599 1639.00000 0.00000 100% 18752 323s
31 40 83.06211 5 10808 1639.00000 0.00000 100% 18433 344s
39 48 55.02149 5 19166 1639.00000 0.00000 100% 16426 367s
47 59 81.06089 6 6708 1639.00000 0.00000 100% 15053 394s
58 68 480.00000 7 3902 1639.00000 0.00000 100% 13469 412s
69 77 81.06089 7 6697 1639.00000 0.00000 100% 12175 431s
H 71 77 1617.0000000 0.00000 100% 12042 431s
H 73 77 1388.0000000 0.00000 100% 12045 431s
78 87 81.06089 8 6695 1388.00000 0.00000 100% 11698 447s
90 102 81.06089 9 6693 1388.00000 0.00000 100% 10771 457s
H 107 128 1363.0000000 0.00000 100% 9579 529s
H 108 128 1335.0000000 0.00000 100% 9490 529s
H 127 128 1279.0000000 0.00000 100% 8520 529s
152 158 81.95034 11 8373 1279.00000 0.00000 100% 7270 543s
211 177 infeasible 14 1279.00000 0.00000 100% 5735 559s
262 198 104.03743 17 6819 1279.00000 0.00000 100% 4877 576s
308 232 112.02943 22 6562 1279.00000 0.00000 100% 4424 613s
352 249 112.02943 26 4520 1279.00000 0.00000 100% 4196 696s
H 363 249 1278.0000000 0.00000 100% 4075 696s
H 365 249 1257.0000000 0.00000 100% 4081 696s
369 268 112.02943 27 4519 1257.00000 0.00000 100% 4045 734s
400 268 4.02670 18 7839 1257.00000 0.00000 100% 3864 735s
424 296 819.04908 31 5647 1257.00000 0.00000 100% 3816 789s
471 305 139.08377 34 12495 1257.00000 0.00000 100% 3741 897s
H 478 305 1242.0000000 0.00000 100% 3713 897s
491 325 139.06697 36 5777 1242.00000 0.00000 100% 3792 936s
545 333 210.00479 39 6192 1242.00000 0.00000 100% 3571 1118s
H 556 333 1229.0000000 0.00000 100% 3531 1118s
562 351 210.89423 40 11997 1229.00000 0.00000 100% 3610 1211s
598 357 infeasible 41 1229.00000 0.00000 100% 3577 1692s
608 389 87.01291 5 15654 1229.00000 0.00000 100% 3812 1765s
642 427 91.75362 6 18902 1229.00000 0.00000 100% 3910 1833s
702 436 330.35300 8 12178 1229.00000 0.00000 100% 3802 1974s
717 464 1079.16869 10 7755 1229.00000 0.00000 100% 3912 2046s
779 508 infeasible 16 1229.00000 0.00000 100% 3827 2133s
864 558 infeasible 28 1229.00000 0.00000 100% 3709 2255s
939 603 0.00000 5 21267 1229.00000 0.00000 100% 3644 2350s
1019 677 1.00000 6 20378 1229.00000 0.00000 100% 3538 2455s
1151 771 4.11000 7 14244 1229.00000 0.00000 100% 3295 2512s
1271 907 5.39744 9 16503 1229.00000 0.00000 100% 3098 2585s
1468 908 933.90870 23 1723 1229.00000 0.00000 100% 2822 2656s
1470 909 129.19418 6 4146 1229.00000 0.00000 100% 2818 2697s
1471 910 1036.00000 120 2962 1229.00000 0.00000 100% 2816 2714s
1472 911 1128.55407 43 2897 1229.00000 0.00000 100% 2814 2728s
1473 911 158.89020 21 2886 1229.00000 0.00000 100% 2812 2741s
1474 912 115.46052 12 3315 1229.00000 0.00000 100% 2810 2756s
1475 913 1036.00000 53 2789 1229.00000 0.00000 100% 2808 2779s
1476 913 933.90870 24 3857 1229.00000 0.00000 100% 2806 2790s
1477 914 294.21130 49 2013 1229.00000 0.00000 100% 2805 2803s
1478 915 1036.00000 47 4127 1229.00000 0.00000 100% 2803 2815s
1479 915 339.31310 17 2782 1229.00000 0.00000 100% 2801 2856s
1480 916 46.51237 14 3100 1229.00000 0.00000 100% 2799 2863s
1481 917 341.24639 22 2150 1229.00000 0.00000 100% 2797 2905s
1482 917 0.50000 8 3492 1229.00000 0.00000 100% 2795 2920s
1483 918 915.31381 24 2455 1229.00000 0.00000 100% 2793 2932s
1484 919 1158.20494 45 2455 1229.00000 0.00000 100% 2791 2938s
1485 919 450.00000 156 2455 1229.00000 0.00000 100% 2789 2950s
1486 923 0.00000 11 2674 1229.00000 0.00000 100% 3073 2977s
1488 926 0.00000 12 16331 1229.00000 0.00000 100% 3098 3015s
1492 933 0.00000 13 22340 1229.00000 0.00000 100% 3162 3081s
1500 938 0.00000 14 20270 1229.00000 0.00000 100% 3228 3197s
1508 944 0.00000 14 22195 1229.00000 0.00000 100% 3263 3228s
1516 948 0.00000 15 12498 1229.00000 0.00000 100% 3296 3267s
1524 950 0.00000 15 21434 1229.00000 0.00000 100% 3316 3291s
1532 955 0.00000 16 7502 1229.00000 0.00000 100% 3360 3308s
1546 955 infeasible 17 1229.00000 0.00000 100% 3374 3324s
1561 956 infeasible 17 1229.00000 0.00000 100% 3392 3388s
H 1567 907 1209.0000000 0.00000 100% 3412 3388s
1571 919 0.00000 16 18659 1209.00000 0.00000 100% 3439 3485s
1589 979 0.00000 17 9734 1209.00000 0.00000 100% 3460 3542s
1683 1000 infeasible 23 1209.00000 0.00000 100% 3372 3572s
1819 960 0.00000 15 17362 1209.00000 0.00000 100% 3271 3679s
1840 997 0.88980 16 15465 1209.00000 0.00000 100% 3261 3712s
1948 984 infeasible 22 1209.00000 0.00000 100% 3183 3845s
1997 964 infeasible 23 1209.00000 0.00000 100% 3142 4013s
2029 1004 608.10167 29 5850 1209.00000 0.00000 100% 3150 4054s
2147 1038 0.06526 17 18754 1209.00000 0.00000 100% 3098 4332s
2261 1013 29.00000 43 10012 1209.00000 0.00000 100% 3042 4655s
2318 1017 infeasible 47 1209.00000 0.00000 100% 3073 5039s
2353 1084 infeasible 47 1209.00000 0.00000 100% 3066 5567s
2504 1121 11.31368 26 7449 1209.00000 0.00000 100% 3023 5618s
2734 1036 0.00000 16 10794 1209.00000 0.00000 100% 2924 5727s
2762 1110 0.00000 17 10792 1209.00000 0.00000 100% 2940 5925s
2888 1114 58.18936 37 2219 1209.00000 0.00000 100% 2963 6030s
3021 1067 infeasible 70 1209.00000 0.00000 100% 2897 6207s
3053 1160 0.00000 20 8096 1209.00000 0.00000 100% 2944 6850s
3206 1127 infeasible 44 1209.00000 0.00000 100% 2943 6961s
3253 1269 226.30622 27 4621 1209.00000 0.00000 100% 2974 7043s
3714 1231 180.71536 49 9418 1209.00000 0.00000 100% 2797 7161s
4053 1115 infeasible 54 1209.00000 0.00000 100% 2660 7200s
Cutting planes:
Learned: 564
Gomory: 39
Cover: 35880
Clique: 8929
MIR: 483
Flow cover: 9222
GUB cover: 74
Zero half: 13
RLT: 2
Relax-and-lift: 1
Explored 4062 nodes (10934261 simplex iterations) in 7200.15 seconds
Thread count was 16 (of 16 available processors)
Solution count 10: 1209 1229 1242 ... 1617
Time limit reached
Best objective 1.209000000000e+03, best bound 0.000000000000e+00, gap 100.0000%
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 why not try our AI Gurobot?. -
-
-
Gurobi has a number of parameters that affect the solution time for this model. It may be beneficial to try non-default values to see if you are able to improve performance.
While it may be daunting to sift through all of these parameters by hand, Gurobi offers an automated tuning tool to help select quality parameter sets. Perhaps you can try this out.
0 -
Post is closed for comments.
Comments
2 comments