How to speed up a milp problem?
AnsweredHi all,
I'm using gurobi to solve a MILP problem. The problem size is not very large (the full problem has over 4000 continuous variables and more than 1000 integer variables), but the solving process is extremely slow, taking several hours without finding a feasible solution. Then I reduced the problem size, and now it has 1822 continuous variables and 571 integer variables, but it still takes around 200 seconds to solve, which feels a bit slow. Is there any way to speed up the solution process?
x1: 3610 rows, 2393 columns, 13867 nonzeros
Set parameter TimeLimit to value 200
Set parameter Cuts to value 3
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 11.0 (22631.2))
CPU model: 12th Gen Intel(R) Core(TM) i5-12500H, instruction set [SSE2|AVX|AVX2]
Thread count: 12 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 3610 rows, 2393 columns and 13867 nonzeros
Model fingerprint: 0xace4bdac
Variable types: 1822 continuous, 571 integer (557 binary)
Coefficient statistics:
Matrix range [3e-04, 8e+03]
Objective range [1e+00, 1e+00]
Bounds range [4e-01, 1e+04]
RHS range [2e-03, 8e+03]
Presolve removed 2049 rows and 1237 columns
Presolve time: 0.09s
Presolved: 1561 rows, 1156 columns, 8227 nonzeros
Variable types: 805 continuous, 351 integer (345 binary)
Root relaxation: objective 4.256023e+00, 846 iterations, 0.02 seconds (0.02 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 4.25602 0 37 - 4.25602 - - 0s
0 0 7.27500 0 18 - 7.27500 - - 0s
0 0 7.27500 0 19 - 7.27500 - - 0s
0 0 11.20292 0 45 - 11.20292 - - 1s
0 0 13.67001 0 72 - 13.67001 - - 1s
0 0 13.67001 0 65 - 13.67001 - - 1s
0 0 13.67001 0 67 - 13.67001 - - 1s
0 0 17.31419 0 58 - 17.31419 - - 2s
0 0 18.55879 0 48 - 18.55879 - - 3s
0 0 18.55879 0 69 - 18.55879 - - 3s
0 0 18.55879 0 69 - 18.55879 - - 3s
0 0 18.55879 0 70 - 18.55879 - - 3s
0 0 18.55879 0 70 - 18.55879 - - 3s
0 0 20.54120 0 67 - 20.54120 - - 4s
0 0 21.23674 0 63 - 21.23674 - - 4s
0 0 21.29087 0 114 - 21.29087 - - 4s
0 0 21.29364 0 110 - 21.29364 - - 4s
0 0 21.38805 0 69 - 21.38805 - - 5s
0 0 21.50135 0 76 - 21.50135 - - 5s
0 0 21.50135 0 60 - 21.50135 - - 6s
0 0 21.50135 0 66 - 21.50135 - - 6s
0 0 21.50135 0 64 - 21.50135 - - 6s
0 0 21.50135 0 68 - 21.50135 - - 6s
0 0 21.50135 0 63 - 21.50135 - - 6s
0 0 21.50135 0 61 - 21.50135 - - 7s
0 1 21.50135 0 61 - 21.50135 - - 7s
1167 531 infeasible 49 - 23.78252 - 105 10s
2803 1260 95.44934 52 149 - 26.35539 - 87.8 15s
2809 1264 45.71212 23 199 - 31.08660 - 87.6 20s
2813 1267 43.42056 23 213 - 34.42754 - 87.4 26s
2823 1275 95.14799 32 180 - 38.71265 - 90.3 30s
2827 1278 54.53859 31 192 - 44.47729 - 90.2 36s
2945 1363 50.20698 33 144 - 44.47729 - 13.0 40s
3641 1344 67.17543 32 145 - 44.47729 - 37.6 45s
4965 1368 56.28354 38 94 - 47.74095 - 52.9 50s
6944 1556 infeasible 41 - 57.52028 - 67.1 55s
8637 2033 86.87709 47 144 - 60.34068 - 73.9 60s
10755 2810 infeasible 48 - 65.46078 - 78.3 65s
13240 3644 75.26261 43 140 - 69.06773 - 77.8 70s
15266 4495 77.08262 44 137 - 72.06686 - 79.3 75s
16602 4654 81.80927 48 100 - 73.17810 - 80.0 80s
18669 5294 101.46582 57 93 - 75.06213 - 82.5 86s
*19107 5039 94 130.1655566 75.62973 41.9% 82.3 86s
H19521 4939 124.5989086 75.99266 39.0% 82.3 89s
H19528 4909 122.1359825 75.99266 37.8% 82.3 89s
19550 4914 93.44562 47 100 122.13598 76.12738 37.7% 82.5 90s
H20529 4970 122.1359780 77.11603 36.9% 85.0 94s
*20653 4950 97 120.8526621 77.43233 35.9% 85.4 94s
21015 5073 113.29568 47 110 120.85266 77.88391 35.6% 87.1 97s
H21386 5066 120.6601056 78.13159 35.2% 88.3 97s
21862 5106 infeasible 52 120.66011 78.51085 34.9% 89.4 100s
H21865 5039 118.0251879 78.51085 33.5% 89.4 100s
H22729 5090 118.0166287 79.20174 32.9% 91.7 103s
H23039 5021 115.5987292 79.43011 31.3% 92.8 103s
23450 5140 102.56290 58 90 115.59873 79.84390 30.9% 94.2 106s
25396 5141 88.24368 62 78 115.59873 81.45520 29.5% 99.1 113s
H25448 4960 110.9577303 81.53437 26.5% 99.2 113s
25569 4929 89.36156 50 106 110.95773 81.55912 26.5% 100 116s
26415 4924 99.49332 48 121 110.95773 82.38965 25.7% 104 120s
H27449 4805 109.5458195 83.28811 24.0% 108 124s
27847 4796 88.71758 54 98 109.54582 83.74607 23.6% 109 128s
28708 4727 91.95116 54 103 109.54582 84.40597 22.9% 114 132s
29752 4774 infeasible 61 109.54582 85.40995 22.0% 118 137s
31156 4742 infeasible 45 109.54582 86.29663 21.2% 121 142s
32496 4707 cutoff 50 109.54582 87.55079 20.1% 125 147s
33999 4527 cutoff 45 109.54582 88.47280 19.2% 127 152s
35447 4219 95.72747 63 77 109.54582 89.95890 17.9% 130 157s
36948 3958 99.88163 50 114 109.54582 91.66728 16.3% 133 162s
38781 3671 107.71591 69 45 109.54582 93.48947 14.7% 134 167s
40868 3210 infeasible 56 109.54582 96.10130 12.3% 134 173s
43036 2793 infeasible 54 109.54582 98.25516 10.3% 133 178s
44628 1830 108.57743 71 55 109.54582 100.07697 8.64% 132 184s
47682 757 infeasible 64 109.54582 103.76270 5.28% 127 188s
50056 30 infeasible 65 109.54582 106.71924 2.58% 124 192s
*51547 30 99 109.5280562 106.74377 2.54% 122 192s
Cutting planes:
Learned: 14
Gomory: 53
Lift-and-project: 71
Cover: 234
Implied bound: 129
Projected implied bound: 1
Clique: 14
MIR: 451
Mixing: 3
StrongCG: 6
Flow cover: 351
Inf proof: 25
Zero half: 1
RLT: 477
Relax-and-lift: 318
BQP: 10
PSD: 9
Explored 51899 nodes (6539502 simplex iterations) in 192.59 seconds (141.05 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 109.528 109.528 109.546 ... 122.136
Optimal solution found (tolerance 1.00e-04)
Best objective 1.095280561619e+02, best bound 1.095280561619e+02, gap 0.0000%
-
Hi Sirui,
There are some parameters to control Gurobi's Behavior: Please see Parameter Guidelines.
The log shows that finding an incumbent is one of the issue. Here are parameters that may be useful:- MIPFocus=1: Focus on finding a feasible solution
- NoRelHeurTime=Appropriate seconds: Runs the no-relaxation heuristic before solving the root relaxation to find a high quality solution.
Also, reformulation may be helpful in improving Bounds: General modeling tips to improve a formulation
Thanks,
Ryuta0
Please sign in to leave a comment.
Comments
1 comment