implement cutting plane algorithm
AnsweredHello,
I am trying to find the optimal integer solution of a IP by solving a sequence of LPs instead of MILPs. What I am currently doing is I resolve the entire LP from sketch after adding some certain cuts. LP can be solved relatively efficient via Simplex, but my LP model might be extremely large after several iterations after adding cuts.
Even though I can get my expected solution in this way, I am wondering if there is more efficient way in Gurobi to solve the problem after adding cuts (maybe use some certain Callback functions such that Gurobi does not need to use all constraints in the model?).
Given a MIP, my expected procedure is: solve its continuous relaxation (RP) --> add cuts to (RP) if needed and ignore nonlinear constraints, so that the new problem is a (LP) --> solve the new continuous problem(LP) --> add cuts to (LP) if needed-->...--> until get the integer solution.
Thanks.
-
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?. -
Followup: I am guessing that I could model my original MIP problem in Gurobi and then use callback function to add my cuts during Gurobi's branch and bound process. Am I right?
However, in my callback function (used to add cuts). The 'where' value is not equal to GRB.callback.MIPNODE, so that I could not add any cuts. Is there any way to fix this issue?
0 -
Hi Miranda,
In general, implementing a cutting plane approach like that is likely to fail sooner or later. It is important to "clean up" your cutting planes to avoid an ever-growing LP. Even then, it can be very hard to solve the problem just by cutting planes. This is the reason every MIP solver uses cutting planes in addition to the branch-and-bound technique.
To get your custom cutting planes into Gurobi via callbacks, you need to collect the cutting plane data in your callback and then add it using the appropriate callback 'where' state. Please check the callback.py example for more information on how to implement different callback states.
Cheers,
Matthias0 -
Hello Matthias,
Thank you for your quick response. I am currently model my problem as MIP and use callback function to add cuts. In my callback function, I set if where == GRB.Callback.MIPSOL, and meet 'some conditions', then add cbLazy(). I am not very clear of the difference between cbcut() and cbLazy(). In my circumstance, which one is better?
I tried cbcut(), but since my 'where' value is not equal to GRB.callback.MIPNODE, I failed to add the cbcut(). Do you know the reason why 'where' != GRB.callback.MIPNODE?
Furthermore, by using cbLazy, I got the following output, is 1+7+4 the total number of cuts added? and 1.2s is the total running time?
Thank you.
0 -
Hi Miranda,
This guide explains the differences between Lazy Constraints and User Cuts quite well:
What is the difference between user cuts and lazy constraints? – Gurobi Support Portal
Since lazy constraints are not cuts per se, the total number of cuts in your example is just 8 but using 4 additional lazy constraints.
To add a cut that was generated in a MIPSOL callback, you need to store the cut in a custom Model data structure, like \(\texttt{model._mycuts}\) and then add them when the solver reaches a MIPNODE callback.
Cheers,
Matthias0
Post is closed for comments.
Comments
5 comments