What is the correct "where" for a callback to add a cutting plane to a linear programme?
AnsweredI am using Gurobi 9.1.2 and the Python API. Having read the documentation for callback codes, it is not clear to me which one I should use to add a new cut to a linear programme (LP). For example, if I have an LP with an exponential family of inequalities (these are "real" cuts which are required for the correctness of the model, not merely valid inequalities) and a separation procedure to find violated cuts, how do I add them using a callback?
One solution which occurred to me is to solve without the cuts, separate using the optimal solution of the (relaxed) LP, modify the model adding the cut, and then solve again, etc. until no cuts are violated. Such a solution, though, is more inconvenient than just having a callback. Is there a way to implement a cutting plane algorithm for an LP (not MIP) using callbacks?
The reason why it is inconvenient to follow the above approach for me is the following. My model "makes sense" both as a MIP and as an LP. When I solve it as a MIP, I can separate cuts for integer solutions only. When I solve it as an LP, I must operate on fractional solutions. Separating a cut for an integer solution is much easier than separating it for a fractional solution, so it makes sense that I use two different routines. (Think of the TSP: detecting subtours for an integer solution is a linear scan; for a fractional solution, you must solve a sequence of max-flow problems.)
So, I have a \(\texttt{MyModel}\) class, with a \(\texttt{self.integer}\) attribute. If \(\texttt{self.integer == True}\), I build the Gurobi model with integer variables; otherwise, with continuous variables. It would be very nice to have a unique way to solve both models using callbacks. (The alternative being that for the MIP model I can use callbacks, but for the LP model I have to write a "wrapper" that solves-changes-resolves the model.)
For example, can I write a callback such as the following?
def callback(model, where):
if where == GRB.Callback.MIPSOL:
integer_separation(model)
elif where == ??? and not self.integer:
continuous_separation(model)
Is there currently a way to achieve this, replacing \(\texttt{???}\) with an appropriate code?
-
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 Alberto,
Is there a way to implement a cutting plane algorithm for an LP (not MIP) using callbacks?
No, because it is only possible to add cuts in a \(\texttt{MIPSOL}\) or a \(\texttt{MIPNODE}\) callback, which both are MIP callback codes.
However, you could introduce a dummy integer variable which you add to your objective function with a correct sign depending on whether you are minimizing or maximizing your objective function. This way, you would still be able to add cuts whenever a solution is found.
Best regards,
Jaromił0 -
Thanks for your answer, Jaromił, neat trick.
Best,
AS
0
Post is closed for comments.
Comments
3 comments