MILP takes too much time
Awaiting user inputHey,
I am wondering what the reason might could for a long running time of my MILP. I have a quite similar MILP which runs quite fast but when slightly changing one condition it runs somehow for ever. I cant really find a reason for that. I guess the LP Relaxtion works fine ("Solved with dual simplex") but what happen then ?/ What is Gurobi trying to do before the Branch and Bound Algorithm starts ?
Set parameter MIPGap to value 0.05
Set parameter TimeLimit to value 500
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (mac64[x86])
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 560656 rows, 560656 columns and 1597778 nonzeros
Model fingerprint: 0xafd29e9d
Variable types: 280328 continuous, 280328 integer (280328 binary)
Coefficient statistics:
Matrix range [1e-01, 4e+00]
Objective range [2e-01, 9e-01]
Bounds range [1e+00, 6e+01]
RHS range [2e-04, 5e+01]
Presolve removed 257187 rows and 229010 columns
Presolve time: 2.89s
Presolved: 303469 rows, 331646 columns, 830795 nonzeros
Variable types: 55972 continuous, 275674 integer (223859 binary)
Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 2.6661490e+02 3.066533e+06 1.682095e+13 6s
Concurrent spin time: 0.00s
Solved with dual simplex
Root relaxation: objective 4.323134e+02, 25893 iterations, 2.70 seconds (1.99 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 432.31343 0 12855 - 432.31343 - - 11s
0 0 432.60851 0 12012 - 432.60851 - - 18s
0 0 432.90816 0 10956 - 432.90816 - - 21s
0 0 433.14680 0 11700 - 433.14680 - - 23s
0 0 433.28650 0 12678 - 433.28650 - - 27s
0 0 433.30156 0 13096 - 433.30156 - - 28s
0 0 433.30254 0 13250 - 433.30254 - - 30s
0 0 433.30276 0 13303 - 433.30276 - - 31s
0 0 433.30277 0 13319 - 433.30277 - - 33s
0 0 433.43848 0 13631 - 433.43848 - - 41s
0 0 433.59443 0 12926 - 433.59443 - - 43s
0 0 433.62791 0 13681 - 433.62791 - - 44s
0 0 433.63227 0 14122 - 433.63227 - - 45s
0 0 433.63303 0 14274 - 433.63303 - - 46s
0 0 433.63326 0 14361 - 433.63326 - - 46s
0 0 433.63327 0 14384 - 433.63327 - - 47s
0 0 433.77941 0 13868 - 433.77941 - - 54s
0 0 433.89729 0 13318 - 433.89729 - - 56s
0 0 433.92159 0 14047 - 433.92159 - - 57s
0 0 433.92613 0 14551 - 433.92613 - - 58s
0 0 433.92693 0 14750 - 433.92693 - - 59s
0 0 433.92771 0 14778 - 433.92771 - - 60s
0 0 433.92795 0 14833 - 433.92795 - - 60s
0 0 434.02130 0 14086 - 434.02130 - - 64s
0 0 434.07073 0 14736 - 434.07073 - - 66s
-
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 try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
In your log snippet, Gurobi is in the root node, adding cuts and trying to find a feasible solution. You could try turning off Cuts and running the No Relaxation Heuristic for let's say 60 second to see whether it finds any feasible point before the root relaxation is solved.
Are you sure that your model is still feasible after the change you made? It can take a lot of time to prove that a model is infeasible. Please also note that even what you think might be a small change to the model can make the problem way harder to solve by completely changing the shape of the feasible region and thus affecting almost every step of the optimization process.
You could also share this particular model. Please note that uploading files in the Forum is currently not supported but you could upload an LP/MPS file to, e.g., Google Drive, as described in Posting to the Community Forum.
0 -
-
Hi Jaromił,
thank you very much for your response. I think the model should be feasible but I am not 100% sure. But when in the log is stated "solved with dual simplex" wasent the LP Relaxation successfull then ? So you mean a feasible solution as a start for the branch and bound algorithm ?
I just need kind of scientific reason for the Problem.
0 -
-
-
But when in the log is stated "solved with dual simplex" wasent the LP Relaxation successfull then ?
Yes, the LP relaxation has been solved successfully. However, this does not mean that your model is feasible.
So you mean a feasible solution as a start for the branch and bound algorithm ?
I don't know what you mean. I did not mention anything about a feasible solution as a start. But this is actually a good idea. You could try to provide an initial feasible point as described in How do I use MIP starts?
Did you try running the model for a really long time with MIPFocus=1 or used NoRelHeurTime=<some_very_large_number>?
0 -
-
Yes I have already tried MIPFocus =1 but it havent changed much in runtime over long time.
The shape of shape of the feasible region is the convex hull , right ? I put now the number of periods down ( I am modelling heat devices over one year with 15 min time steps (=35040time steps)) . I reduced now the number of steps to 1500 and it looks like that the modell is now performing at least the branch and bound - but still takes too much time. Do you might know a reason for such behaviour ?
Set parameter MIPGap to value 0.05
Set parameter TimeLimit to value 500
Gurobi Optimizer version 9.5.2 build v9.5.2rc0 (mac64[x86])
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 8000 rows, 8000 columns and 22497 nonzeros
Model fingerprint: 0x82d5a3ca
Variable types: 4000 continuous, 4000 integer (4000 binary)
Coefficient statistics:
Matrix range [1e-01, 7e+00]
Objective range [3e-01, 3e-01]
Bounds range [1e+00, 6e+01]
RHS range [8e-02, 5e+01]
Presolve removed 6575 rows and 6487 columns
Presolve time: 0.06s
Presolved: 1425 rows, 1513 columns, 3449 nonzeros
Variable types: 480 continuous, 1033 integer (600 binary)
Found heuristic solution: objective 3.0445425
Root relaxation: objective 1.007521e+00, 56 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1.00752 0 11 3.04454 1.00752 66.9% - 0s
H 0 0 3.0274425 1.00752 66.7% - 0s
0 0 1.23383 0 15 3.02744 1.23383 59.2% - 0s
0 0 1.24969 0 12 3.02744 1.24969 58.7% - 0s
H 0 0 2.8002600 1.24969 55.4% - 0s
0 0 1.25041 0 8 2.80026 1.25041 55.3% - 0s
0 0 1.25307 0 16 2.80026 1.25307 55.3% - 0s
0 0 1.26893 0 33 2.80026 1.26893 54.7% - 0s
0 0 1.27454 0 37 2.80026 1.27454 54.5% - 0s
0 0 1.28407 0 28 2.80026 1.28407 54.1% - 0s
0 0 1.28410 0 28 2.80026 1.28410 54.1% - 0s
0 0 1.28505 0 39 2.80026 1.28505 54.1% - 0s
H 0 0 2.7870900 1.28505 53.9% - 0s
0 0 1.28544 0 37 2.78709 1.28544 53.9% - 0s
0 0 1.29216 0 32 2.78709 1.29216 53.6% - 0s
0 0 1.29282 0 34 2.78709 1.29282 53.6% - 0s
0 0 1.29297 0 34 2.78709 1.29297 53.6% - 0s
H 0 0 2.7344550 1.29297 52.7% - 0s
0 0 1.29297 0 36 2.73445 1.29297 52.7% - 0s
0 0 1.29298 0 36 2.73445 1.29298 52.7% - 0s
0 0 1.29302 0 35 2.73445 1.29302 52.7% - 0s
0 0 1.29302 0 35 2.73445 1.29302 52.7% - 0s
H 0 0 2.7246600 1.31805 51.6% - 0s
H 0 2 2.7065625 1.31805 51.3% - 0s
0 2 1.31805 0 34 2.70656 1.31805 51.3% - 0s
H 65 44 2.6785725 1.35397 49.5% 3.9 0s
H 99 62 2.6709000 1.35397 49.3% 3.4 0s
H 109 62 2.6708250 1.35397 49.3% 3.3 0s
H 603 200 2.4467700 1.37341 43.9% 1.7 0s
H 1665 344 2.4347700 1.38543 43.1% 1.5 1s
H 2071 370 2.4341475 1.42448 41.5% 1.5 1s
H 2193 488 2.0190656 1.42448 29.4% 1.5 1s
6480 3430 1.99365 232 6 2.01907 1.53781 23.8% 3.2 5s
18991 12732 infeasible 160 2.01907 1.54214 23.6% 3.3 10s
21277 14244 1.97039 87 32 2.01907 1.54306 23.6% 3.2 15s
22493 14851 1.70383 65 14 2.01907 1.70335 15.6% 3.5 20s
30390 18021 1.92896 128 18 2.01907 1.70407 15.6% 3.8 25s
41094 22006 infeasible 102 2.01907 1.70430 15.6% 3.8 30s
48354 25550 1.87983 66 11 2.01907 1.70453 15.6% 3.8 35s
57543 29606 1.98498 205 6 2.01907 1.70471 15.6% 3.9 40s
68506 34789 infeasible 98 2.01907 1.70488 15.6% 3.9 45s
79380 43163 1.70680 75 8 2.01907 1.70508 15.6% 4.0 50s
92710 53315 infeasible 241 2.01907 1.70528 15.5% 3.9 55s
103394 61522 1.97535 87 7 2.01907 1.70549 15.5% 4.0 60s
116192 71249 1.71634 218 6 2.01907 1.70574 15.5% 4.0 65s
127273 80964 1.87503 77 14 2.01907 1.70586 15.5% 3.9 72s
139023 88456 1.70914 113 8 2.01907 1.70604 15.5% 4.0 75s0 -
-
-
The shape of shape of the feasible region is the convex hull , right ?
Correct. Please note that in general, the convex hull is not available, thus the feasible set of the relaxation is usually way bigger than the convex hull.
Do you might know a reason for such behaviour ?
There can be multiple reasons for that. One reason might be a weak formulation of the problem. You might want to have a look at our Tech Talk on Strong Formulations I & II.
Also, you might want to have a look at the most important parameters for MIPs.
It looks like you are solving the model on a personal notebook. You might want to consider switching to a more powerful machine. This might already speed up the solution process significantly.
0 -
-
Hi, thanks for your respone !
I already had a look into the Strong Formulations tech talk, but I cant change the formulations that much bc of the model formulation iteself.
I am looking more for a scientific reason for this long runtime -especially when chaning slightly the model formulation its getting exponential in runtime. I am wondering therfore which theoretical implications such slightly other formulation can have on shapes of convex hulls, etc. Do you may know some reasons or tech documentations where something is writen about such stuff ? I was already looking for literature but its pretty hard to find something on it.
0 -
-
-
Hi Marco,
I am looking more for a scientific reason for this long runtime -especially when chaning slightly the model formulation its getting exponential in runtime. I am wondering therfore which theoretical implications such slightly other formulation can have on shapes of convex hulls, etc. Do you may know some reasons or tech documentations where something is writen about such stuff ? I was already looking for literature but its pretty hard to find something on it.
I am not aware of any scientific paper that aims to explain such run time differences in any manner. I think to provide a more or less scientific explanation, you should try to use your model knowledge and try to find a possible explanation of why the model becomes so hard to solve when you add the particular constraint. Please note that often the explanation might just be that the optimization path changes completely by adding a particular constraint resulting in slow convergence. Sometimes, already a different Seed value is enough to completely change the optimization path. You should try experimenting with a model that solves rather quickly (1 hour is still quick) and try to find parameters to tune it. Hopefully, these parameters then also help for the bigger models. Providing a good initial point might also be a good idea.
You could also share the model you posted, maybe there is something we can learn from it.
0 -
Post is closed for comments.
Comments
8 comments