Disable Crossover for MILP that is reduced to LP in Presolve
Answered
I have a problem that is formulated as an MILP, however is reduced to an LP (0 integer variables) in Presolve (which is absolutely correct and a great feature that Gurobi detects that automatically). I then apply the barrier algorithm.
There are two things I wonder about:
1. Can Gurobi imply from the Presolve solution that the problem is in fact linear and thus apply a linear solution algorithm, i.e., only solve the root and not go into the branch-and-bound?
2. Can Crossover then be disabled, because this does not change the solution of my problem? Gurobi spends about 2/3 of the solution time in Crossover, even though this does not change anything. I have set Method = 2, Presolve = 2, CrossoverBasis = 0, Crossover = 0
I could theoretically reformulate my optimization problem to detect beforehand if it is in fact an LP but I trusted/relied on the "intelligence" of Gurobi to do so itself in Presolve.
-
Can Gurobi imply from the Presolve solution that the problem is in fact linear and thus apply a linear solution algorithm, i.e., only solve the root and not go into the branch-and-bound?
Gurobi does this. What you should see is only 1 line of the B&B algorithm. The output is of the B&B is there because the model is originally a MIP so Gurobi does use MIP logging instead of LP logging. Do you see something different?
Can Crossover then be disabled, because this does not change the solution of my problem? Gurobi spends about 2/3 of the solution time in Crossover, even though this does not change anything. I have set Method = 2, Presolve = 2, CrossoverBasis = 0, Crossover = 0
Could you try adding NodeMethod=2 to your set of parameters. You need this to completely disable Crossover for MIPs. If this does not help, could you please share your model? Uploading model files is not possible in the Community but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił1 -
Dear Jaromił,
once again, thanks for this quick and helpful comment!
NodeMethod = 2 disabled the crossover for the barrier solver.
I have a final question: can I set the concurrent solver as well while disabling the crossover? I know that crossover only applies to the barrier, but I'm not sure on how to disable crossover for the case that barrier is chosen as the solver.Thanks and best wishes,
Jacob0 -
Hi Jacob,
Setting NodeMethod=2, Crossover=0 should work with concurrent as well (please let me know if you observe any different). However, it will most likely hurt performance, because NodeMethod=2 forces Gurobi to use the Barrier algorithm in every node. This is a difficult situation, because you can easily lose all the time gained from Crossover=0 through the Barrier calls in the B&B tree, unless using Barrier in every MIP node is not an issue.
Best regards,
Jaromił1 -
Hi Jaromił,
thanks!
What is your general recommendation? My model with mostly turn out to be linear, however it might be MIP, so I would like to entrust Presolve with figuring that out. I saw that some others experienced the same behavior that the solver spent more time in Crossover than in actually solving the problem (e.g., https://support.gurobi.com/hc/en-us/community/posts/360072667551-barrier-and-crossover-restart). What would you do to get rid of this overhead?
Thanks so much for the great support work!
Jacob0 -
Hi Jacob,
Usually, Crossover only takes an extraordinary amount of time if the problem is very large or if it has numerical issues. Do your models have any numeric issues? See Guidelines for Numerical Issues for more information.
If you think that your models are numerically acceptable, then I would extract the problematic instances and analyze them in more detail. Maybe they are somewhat different from the rest and you can find fitting parameters to overcome the performance difficulties. If your MIP instances don't require many B&B iterations then NodeMethod=2 might indeed be the best option here.
Best regards,
Jaromił1 -
Hi Jaromił,
Ok that is a great hint to look out for! So, to get that straight: the long crossover time has nothing to do with the fact that I am passing a MIP model to Gurobi that is in fact LP, but because the LP (root) model is difficult to solve/has numerical issues? My matrix and bounds are in an acceptable range, but maybe I can find the culprit :)
Cheers
Jacob0 -
Hi Jacob,
So, to get that straight: the long crossover time has nothing to do with the fact that I am passing a MIP model to Gurobi that is in fact LP, but because the LP (root) model is difficult to solve/has numerical issues?
Correct. Of course, it is also possible that your model is numerically perfectly fine and it is just difficult to solve. You might want to try to reduce the size of the models even further in this case and experiment with Presolve=2, Aggregate=2, and for MIPs PreSparsify=1.
Best regards,
Jaromił1
Please sign in to leave a comment.
Comments
7 comments