Best practice for implementing branch and cut algorithm with gurobi
I am implementing a solver for binary linear optimization problem. This optimization problem consist of a large number of necessary inequalities. Besides the inequalities that are necessary to describe the set of feasible binary solutions, other classes of other valid inequalities are known. These classes have exponential size but violated inequalities can be found efficiently.
From the gurobi documentation and various forum entries if learned the following:
- The best method for dealing with the large number of necessary constraints is to use lazy constraints.
- Additional valid inequalities can be added to the model as "user cuts" with the cbCut method.
For my problem I have found that both lazy constraints and user cuts do not work particularly well. My guess is that lazy constraints have the following two problems:
- Lazy constraints can only be added when a integer feasible solution is found. I imagine that it is computationally quite expensive to get an integer feasible solution from an LP relaxation. All this work is "wasted" when the new found integer solution is cut off afterwards by a new lazy constraint.
- Typically, many lazy constraints are added over many iterations. This results in quite a large model which slows the solver down significantly.
Regarding the user cuts, I found that the cuts are mostly ignored. I know that the cuts that are added significantly improve the LP bound (if they are used) but the LP bound that the gurobi log reports does not reflect this improvement.
The best solution I have found to address all these problems is the following:
Instead of defining a binary linear model I define a model with continuous variables and only solve the LP relaxation. Every time the LP relaxation is solved, I search for new violated inequalities (both necessary inequalities and other valid inequalities) and add them to the model (the advantage of this is that the solver does not spend any resources to find an integer feasible solution). I also remove inequalities from the model that have not been active for a few iterations (this ensures that the total number of inequalities does not become to large to slow down the solver). Finally, if no additional violated inequalities are found and if the solution is still fractional I start branching. I implement this branching manually by simply creating two copies of the model and adding the constraints x = 0 and x = 1 to the two models, respectively.
While this implementation is much faster than lazy constraints + user cuts, I feel like this is not the intended method. In particular, the manual copying of the model during the branching seems highly inefficient. Also with this implementation the very sophisticated heuristics of gurobi for finding integer solutions are not used.
To summarize my question: What is the best practice to implement a solver with gurobi for an ILP with a large number of necessary constraints and a large number of additional strong valid inequalities that can be separated efficiently?
[An example of such an optimization problem is the clique partitioning problem. It is described, for instance by Sørensen (2020).]
-
Official comment
-
Gurobi Staff
> 1. The best method for dealing with the large number of necessary constraints is to use lazy constraints.
Despite adding lazy constraints in a callback you can also add them or some of them to the starting model. Also a mix of both approaches is possible, not necessarily being better.
> 1. Lazy constraints can only be added when a integer feasible solution is found. I imagine that it is computationally quite expensive to get an integer feasible solution from an LP relaxation. All this work is "wasted" when the new found integer solution is cut off afterwards by a new lazy constraint.
It's correct that some of the time is “wasted”, but often finding integer feasible solution should be a lot easier on the base model (the one without lazy constraints) and therefore the overhead should be not too big. It might also be possible to repair the now cut off solution if the added lazy constraints do not change the solution too much. But currently, if you know how to repair it even, maybe it would be good to also provide a repaired solution back to Gurobi via the callback.
>2 .Typically, many lazy constraints are added over many iterations. This results in quite a large model which slows the solver down significantly.
Yes, this may be true and depend on the problem. But I'm not sure that too much can be done about it internally but I see some possibilities to maybe improve:
1. Is it possible to derive stronger lazy constraints before hand that maybe replace more than one of the once you currently added?
2. What you could try is to first generate a number of lazy constraints (not sure if you have a good estimate here on when to stop), and then restart the solve where you added the already generated lazy constraint (either as normal constraints or as lazy constraints).
> Regarding the user cuts, I found that the cuts are mostly ignored. I know that the cuts that are added significantly improve the LP bound (if they are used) but the LP bound that the gurobi log reports does not reflect this improvement.
Is this still at the root node? Did you set PreCrush to value 1 (maybe try Gurobi 12.0.x) which may increase chances that you cut can and will be implied, still there are certain heuristics that might decided to not add a user cut.
If all of the above are true, I'm not sure sure why the cuts are not resulting in an improved lower bound. Maybe you can share a model + user cuts that combined give you a better bound and if I would add the user cuts in a separation routine would not lead to an improved bound (or a bound that is far away from the one from the former approach). -
-
Thanks for the response!
I have created a small example and uploaded it to github: https://github.com/JannikIrmai/clique-partitioning-gurobi
By playing around a bit more I found that lazy constraints together with user cuts performs quite poorly. In contrast, if I add all constraints at the root node, then adding user cuts results in better bounds and faster convergence compared to not using user cuts. However, iteratively solving an LP (instead of ILP) and adding violated inequalities still finds good bounds significantly faster than ILP+user cuts.
0 -
Please sign in to leave a comment.
Comments
2 comments