Solve the relaxation of the MIP and then solve the MIP without re-solving the root node relaxation
Answered
I have a large MIP model with a very strong LP relaxation. The main strategy for solving such problem in the literature is to solve the LP relaxation (what takes a long time) and then use the LP objective value (an upper bound for the MIP maximization) to fix-to-zero/remove variables and then change the remaining variables to integer/binary for solving the simplified MIP. However, it seems like this throws the LP basis out and re-solves the root relaxation. For me, this is a dealbreaker. I cannot use the solver if I cannot give an LP basis to the MIP solving process in order to skip/speed-up the root relaxation and instead be forced to solve the relaxation two times.
Is there a way to do it that I missed? Currently I am creating the model with continuous variables, solving it, and then changing the variable type to integer/binary. I could save the basis and use PStart/DStart after changing the variable type, but PStart/DStart documentation explicitly tells it is ignored for MIP models.
-
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?. -
Yes, it is not possible to pass an LP basis to a MIP solve. This is mostly because the MIP preprocessing would usually invalidate any warm start basis anyways, because most of the MIP preprocessing techniques are incompatible with dual solutions and LP bases.
But you might be able to get what you want in a different way: solve your full model with integrality status and install a callback. In your callback function, query the LP solution and create a user cut `xj <= 0` for each variable that you want to fix to zero.
If the problem is large, you may need to adjust certain presolve parameters in order to turn off things that would take too long, for example clique merging or probing.
Regards,
Tobias
0 -
Thank you very much for your answer, it was the last resort solution I was converging to (after studying the docs yesterday) it is good to get confirmation it is the only way possible before doing it.
This leads me to two quick follow up questions:
1) There is no way to change variable bounds inside a callback, right? I searched the docs but only found explicitly confirmation that was impossible to set solver parameters inside a callback, not variable attributes.
2) Can I use a non-lazy cut for it? These cuts to zero can cut a integer solution, but not all optimal solutions. Even so the solver behavior could cut optimal solution if I did use non-lazy cuts? I say that because non-lazy cuts seems less aggressive in the disabling presolve.0 -
1) Correct, you cannot set variable attributes in a callback. But you can produce the cut "x <= 0" and add this as a user cut. Internally, this will then be converted into a bound change.
2) Yes, it could be possible. But there is one catch, which is dual presolve reductions (and also symmetry reductions). For example, consider the constraint x + y = 1, and assume that both variables appear identically in all other constraints and the objective. Then, a valid dual presolve reduction is to fix x = 0. This reduction may discard feasible and even optimal solutions, but for any solution with x = 1, there is also an equivalent solution with y = 1. Hence, fixing x = 0 is fine. But now, if you fix y = 0 in your callback, because you use the same reasoning in the opposite direction (for any solution with y = 1 there is an equivalent one with x = 1), then Gurobi has cut off one set of solutions, you have cut off the other set of solutions, and as a result you have lost all solutions.
So, overall, whether you can use regular user cuts or whether you have to resort to lazy constraints depends on what you are actually doing. If you know that your additional fixings will always keep at least one optimal solution, and you know that this optimal solution may not have been discarded already by Gurobi's presolve or due to symmetry reductions, then it is fine.
Tobias
0 -
Thank you for the detailed explanation.
I will try the user cuts with care, then, if something goes wrong I will use lazy cuts or try to understand if I can work around it (by disabling a specific presolve or changing something else).
0
Post is closed for comments.
Comments
5 comments