Order of variables & constraints vs. performance
Answered
Dear Gurobi community,
I have a question about the solving performance of Gurobi. I noticed that the order of variables & constraints of a MIP can have a significant impact on the solving performance (when solving to optimality, the quality of the solutions is the same). Is this behaviour expected? If so, can you give some intuition why?
Thanks in advance for any thoughts.
Kind regards,
Joost
-
Official comment
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?. -
Hi Joost,
There are several reasons why this might happen.... first, presolve, which include probing, is almost never fully performed on all variables and combinations, instead, there are several artificial limits imposed on the process to ensure that it never takes too long (you can force presolve to work harder on your model by setting the parameter presolve=2). Also, even the linear algebra (while performing simplex pivots) will depend in the order in which variables and constraints appear... and that is natural. Of course the algorithms will re-order some of this to improve performance, but the resulting set of conditions does not uniquely define the order of variables and constraints in each basis. Also, this ordering affects the choices in which the internal heuristics works.... thus, a given order might be lucky in terms of heuristics, and thus changing the overall running time quite a lot.
Hope this helps
Daniel
1 -
Dear Daniel,
Thanks a lot for your quick, helpful answer!
It sounds then, that there is some optimization potential in finding a beneficial ordering for a specific type of problem.
Kind regards, Joost
2 -
Hi Joost,
IMHO, no, there is not much to be (consistently) gain by finding the 'right' order for a problem, but there is a benefit on leaving 'related constraints' and 'related variables' close together (hopefully, define them in contiguous chunks). Of course these are loose statements.
Daniel
1
Post is closed for comments.
Comments
4 comments