Controlling cut generation in the root node setting the CutPasses parameter
Answered
Hi,
I'm developing a Branch-and-cut algorithm, where I add user specific cuts and lazy constraints through a callback. I have encountered the problem that the cut generation in the root node seems to abort prematurely. I've been reading the responses in the following thread: https://groups.google.com/forum/#!topic/gurobi/_JUHVqdNy7s suggesting to set the CutPasses parameter sufficiently high in order to override the default heuristic abort criterion in Gurobi. However, setting this to it's maximum level I still encounter the same problem.
Currently I have three types of cuts, where the first type is fast to separate and the two last ones are slow to separate. Therefore, I would like to run a sequential separation routine where I first check for type 1 cuts, if none are found check for type 2 cuts, if none are found check for type 3 cuts, if none are found start branching. Setting the CutPasses parameter to it's maximum level I would expect the algorithm to go through all checks before starting to branch, but instead it will sometimes start branching immediately after adding a cut of type 1 without even checking for the other cut types.
Therefore, it seems to me that the heuristic abort criterion in Gurobi is still active, namely that the cut generation will abort once the marginal improvement of the objective value of the LP-relaxation (or the dual bound of the MILP problem) is below a given limit when adding a cut. If I have understood this correctly, does that mean the CutPasses parameter only overrides the abort criterion for the Gurobi-internal cuts, and not for the user specific callback cuts? Thus starting to branch as soon as no more Gurobi-internal cuts are added to the model, or the marginal improvement from the user specific cuts are too small.
I'm grateful for any feedback or clarification regarding this matter.
-
No, the CutPasses parameter should do the trick. Could it be that you encountered an integer solution on the way (I mean that the LP solution was integral)? When lazy constraints are involved, things get more complicated (and I would need to look more carefully at our source code).
If lazy constraints are not involved and the CutPasses parameter is set to a large value, then I am pretty sure that the cut loop will only be aborted if no cuts have been found.
Maybe, you are adding a cutting plane that is violated only a little bit and Gurobi (after scaling the cut) dismisses the cut as being not violated enough. In this case, if this was the only cut that was added, it will then think that no cuts have been found and abort the loop.
0 -
Thank you for the reply. I do encounter integer solutions on the way, but after some more debugging I find that the cut loop is aborted after adding a lazy constraint in MIPNODE. What I referred to as cuts of type 1 should probably be explained a bit more precise. They are actually subtour elimination constraints consisting of two subgroups, namely capacitated subtour eliminations and standard subtour eliminations. I referred to them as cuts of type 1 as they are both found using the same separation algorithm. However, the capacitated subtour eliminations are actually not cutting planes, they are added as lazy constraints, because they define the original model. The standard subtour eliminations are then used as tightening cutting planes, added as lazy constraints in MIPSOL and as cutting planes in MIPNODE. The loop does not abort the first time a lazy constraint is added, but after several iterations, probably when the improvement of the dual bound is too small. Could that be the problem, that Gurobi doesn't find any cut to be violated enough and only being left with the lazy constraints the algorithm decides to start branching?
An alternative approach would be to solve the root node as an LP and add the cuts and the lazy constraints in my own loop resolving the LP until no more cuts or lazy constraints can be found. Then after this, change the definition back to an integer program and start branching. However, I was hoping to do this setting a parameter, because then I could get the same behavior throughout the branch-and-bound tree. Do you think this is still possible when including lazy constraints?
0 -
Hi Jorgen,
It could be that the solver decides to stop cutting due to small dual bound movement... if you think about it, it is always possible to find a violated cut (e.g. a Gomory cut), and so the solver has to decide when is time to branch. Maybe a log could shed some light into the behavior you are seeing
0
Please sign in to leave a comment.
Comments
3 comments