Not that large MILP model took ages to obtain the optimal results
AnsweredHi, Sir or Madam,
excuse me.
I was working on a MILP design&UC model(bilevel MILP), which is not that large, but now it took ages to obtain the optimal results(34 days), too long to wait, the MIPgap, best bound and incumbent all moved slowly. I have tried several methods based on a guideline online, like:
1. check model formulation, but from my knowledge, it is good.
2. parameters tuning, tried several parameters combination:
ops.gurobi.MIPGap = 0.02;
ops.gurobi.Threads = 4;
ops.gurobi.NormAdjust = 1;
ops.gurobi.Cuts = 2;
ops.gurobi.MIPFocus = 1;
ops.gurobi.Heuristics = 0.1;
ops.gurobi.Method = 3;
The log was shown as following, could you please help look at it and give some suggestions?
Thanks a lot, and looking forward to your reply.

Dear Dr. Sonja,
Here is the log file:
Optimize a model with 583933 rows, 3007851 columns and 9740838 nonzeros
Model fingerprint: 0x4267a30c
Variable types: 130287 continuous, 2813372 integer (2812000 binary)
SemiVariable types: 192 continuous, 64000 integer
Coefficient statistics:
Matrix range [1e01, 6e+05]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 3e+00]
RHS range [1e+00, 1e+07]
Presolve removed 282177 rows and 2702146 columns (presolve time = 7s) ...
Presolve removed 350856 rows and 2702166 columns (presolve time = 10s) ...
Presolve removed 351872 rows and 2702182 columns (presolve time = 16s) ...
Presolve removed 351872 rows and 2767169 columns (presolve time = 20s) ...
Presolve removed 415915 rows and 2767189 columns (presolve time = 25s) ...
Presolve removed 415915 rows and 2767189 columns (presolve time = 31s) ...
Presolve removed 415847 rows and 2767121 columns
Presolve time: 30.98s
Presolved: 168086 rows, 240730 columns, 995578 nonzeros
Variable types: 128661 continuous, 112069 integer (112000 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...
Presolved: 168086 rows, 240730 columns, 995578 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 6.8870400e+03 1.061600e+04 2.868687e+09 39s
27564 6.1515244e+03 2.779822e+03 1.934845e+10 40s
54135 9.7138508e+10 0.000000e+00 3.319229e+09 44s
67973 9.4368476e+10 0.000000e+00 4.419820e+10 45s
95720 8.7804727e+10 0.000000e+00 1.130559e+10 50s
146842 8.7675430e+10 0.000000e+00 1.879597e+10 55s
189586 7.0040968e+07 0.000000e+00 1.319235e+09 60s
207114 3.2795941e+07 0.000000e+00 2.675595e+09 65s
223917 5.4836499e+06 0.000000e+00 9.813118e+08 70s
238340 4.6060952e+05 0.000000e+00 4.798973e+07 75s
264177 4.3146288e+05 0.000000e+00 1.150660e+06 80s
285244 4.1915193e+05 0.000000e+00 2.414251e+06 85s
308024 4.0950657e+05 0.000000e+00 4.344521e+06 90s
327165 4.0382635e+05 0.000000e+00 1.053032e+06 95s
349021 3.9731106e+05 0.000000e+00 1.183320e+06 100s
371053 3.9257048e+05 0.000000e+00 3.550259e+05 105s
390693 3.9089642e+05 0.000000e+00 1.909635e+05 110s
405117 3.8830537e+05 0.000000e+00 5.644955e+03 115s
420334 3.8812836e+05 0.000000e+00 1.091260e+03 120s
433956 3.8808418e+05 0.000000e+00 2.494808e+02 125s
441741 3.8806238e+05 0.000000e+00 1.279263e+05 130s
443656 3.8803758e+05 0.000000e+00 4.024126e+03 136s
445176 3.8802382e+05 0.000000e+00 1.005324e+04 141s
446726 3.8801138e+05 0.000000e+00 1.683153e+04 145s
448321 3.8799809e+05 0.000000e+00 3.882315e+03 150s
449736 3.8798221e+05 0.000000e+00 1.835246e+04 155s
451046 3.8797212e+05 0.000000e+00 6.098656e+03 160s
Concurrent spin time: 0.00s
Solved with dual simplex
Root relaxation: objective 3.878547e+05, 72200 iterations, 123.81 seconds
Total elapsed time = 201.84s
Total elapsed time = 216.76s
Total elapsed time = 231.60s
Total elapsed time = 250.87s
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 387854.684 0 8693  387854.684   262s
H 0 0 2.363126e+09 387854.684 100%  266s
0 0 387935.181 0 3917 2.3631e+09 387935.181 100%  1042s
H 0 0 4557969.6699 387935.181 91.5%  1049s
0 0 387975.383 0 4741 4557969.67 387975.383 91.5%  1059s
0 0 387975.383 0 4883 4557969.67 387975.383 91.5%  1062s
0 0 387983.223 0 4943 4557969.67 387983.223 91.5%  1097s
H 0 0 2555460.9099 387983.223 84.8%  1105s
0 0 387991.066 0 4950 2555460.91 387991.066 84.8%  1109s
0 0 387991.066 0 4931 2555460.91 387991.066 84.8%  1111s
0 0 388002.538 0 4925 2555460.91 388002.538 84.8%  1148s
H 0 0 444010.62999 388002.538 12.6%  1157s
0 0 388003.250 0 4918 444010.630 388003.250 12.6%  1165s
0 0 388003.250 0 4939 444010.630 388003.250 12.6%  1168s
0 0 388154.742 0 954 444010.630 388154.742 12.6%  1206s
0 0 388157.971 0 936 444010.630 388157.971 12.6%  1213s
0 0 388157.971 0 989 444010.630 388157.971 12.6%  1214s
0 0 388159.357 0 1023 444010.630 388159.357 12.6%  1235s
0 0 388160.706 0 999 444010.630 388160.706 12.6%  1243s
0 0 388160.706 0 1227 444010.630 388160.706 12.6%  1244s
0 0 388164.145 0 1051 444010.630 388164.145 12.6%  1282s
0 0 388164.208 0 1045 444010.630 388164.208 12.6%  1287s
0 0 388164.208 0 981 444010.630 388164.208 12.6%  1288s
0 0 388165.785 0 819 444010.630 388165.785 12.6%  1325s
0 0 388165.812 0 901 444010.630 388165.812 12.6%  1332s
0 0 388165.896 0 1211 444010.630 388165.896 12.6%  1349s
0 0 388165.899 0 1532 444010.630 388165.899 12.6%  1355s
0 0 388165.899 0 1495 444010.630 388165.899 12.6%  1372s
0 0 388165.899 0 966 444010.630 388165.899 12.6%  1378s
0 0 388165.899 0 1277 444010.630 388165.899 12.6%  1394s
0 0 388165.899 0 545 444010.630 388165.899 12.6%  1523s
H 0 0 393359.81406 388165.899 1.32%  1595s
Cutting planes:
Gomory: 28
Clique: 88
MIR: 95
Flow cover: 3
Zero half: 134
RLT: 104
Explored 1 nodes (306422 simplex iterations) in 1618.32 seconds
Thread count was 12 (of 12 available processors)
Solution count 5: 393360 444011 2.55546e+06 ... 2.36313e+09
Solve interrupted
Best objective 3.933598140566e+05, best bound 3.881658989644e+05, gap 1.3204% 
Hi,
I am sorry, I don't see the issue in the log. It looks very different from the log of the original post.
However, this is quite a big model with 3 million variables 0.5 million constraints, and almost 10 million nonzeros. Even after presolve there are almost 1 million nonzeros left over. Gurobi is able to reduce the MIP gap to less than 1.5% in less than 30 minutes. This does not sound too bad to me.
 What are your time limit and your target MIP gap?
 Have you tried to do some parameter tuning on this model?
Best,
Sonja

Dear Dr. Sonja,
Thanks for your reply, I am sorry for using an old post to ask about a similar issue.
for your questions:
 What are your time limit and your target MIP gap? I use certain termination criteria with soft limit and hard time with 2% gap and 5% gap.
 Have you tried to do some parameter tuning on this model? Yes, I have tried tuning the model, and that's why I am asking as MIP focus, improve start node, etc. did not reflect any changes on the model which is strange for me as I used to improve my models using tuning parameters.
Any advice regarding improving and decreasing the solution time?

Hi,
I would try each of the following parameters on its own first
MIPFocus=1
Presolve=2
Method=2
Cuts=1
CutPasses=3to see if there is any improvement in the runtime. I would then probably combine a few of those parameters. You can also try to run the parameter tuning tool for a while. Maybe it comes up with a good idea.
Best regards,
Sonja
Please sign in to leave a comment.
Comments
8 comments