Not that large MILP model took ages to obtain the optimal results
Answered
Hi, Sir or Madam,
excuse me.
I was working on a MILP design&UC model(bi-level MILP), which is not that large, but now it took ages to obtain the optimal results(3-4 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.
-
When is the first feasible solution found? Can you post the 5 log lines before and the 5 lines after this event?
Thanks,
Sonja
0 -
Dear. Dr.Sonja,
I am facing the same issue in another MIP model, Could you please advise?
Thanks in advance
0 -
Hi Ibrahim,
Can you share a log file or parts of a log file that show the important stages of the solving?
Thanks,
Sonja
0 -
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)
Semi-Variable types: 192 continuous, 64000 integer
Coefficient statistics:
Matrix range [1e-01, 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%0 -
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
0 -
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?
0 -
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
1 -
Thanks Dr.Sonja
0
Please sign in to leave a comment.
Comments
8 comments