Difference between addLazy and addCut in Callbacks

[Kumar Amulya Yadav]

Hi,

I am trying to understand the difference between the functionalities of addLazy and addCut APIs.

For a MIP model, is it the case that addLazy adds a constraint to the original model (the one that is solved at the root node of the branch and bound tree)? And does the addCut add a constraint to the sub-MIP being solved at the current node, along with all the descendants of that node?

Maybe this is a beginner question, but if addLazy indeed adds a constraint to the original model, would it not have to modify the branch and bound tree that has been constructed so far?

Any help shall be appreciated.

Thanks,
Amulya

[Tobias Achterberg]

The difference between addLazy and addCut is pretty fundamental from a
semantical point of view but not so big from an algorithmic point of view.

Lazy constraints are added with addLazy, user cuts are added with addCut. Both
of these are linear inequalities that are added to the LP relaxation during the
branch-and-cut process.

The difference is that lazy constraints are fundamental to the semantics of the
model, while user cuts are optional. In other words, if you do not add some
violated user cut to the relaxation, then the final solution will still be
correct. It might be that the solving process becomes faster by adding the user
cut (this is actually the goal of user cuts), but given enough time, both
versions (with and without user cuts) will eventually find a correct optimal
solution to the model.

If you do not add a violated lazy constraint, then Gurobi may declare an integer
solution to be feasible that is actually violating some of your lazy
constraints. Thus, the resulting solution might be invalid.

Let's explain this with two examples:

Consider a knapsack problem

max 3x1 + 4x2 + 5x3 + 7x4 + 8x5
s.t. 4x1 + 6x2 + 9x3 + 10x4 + 11x5 <= 20
x1, x2, x3, x4, x5 binary

Then, as a user you could add the cut

x1 + x2 + x5 <= 2

with the addCut method from within the callback. This is a so-called "knapsack
cover cut" (this particular case does not make much sense, because Gurobi is
generating these cuts internally as well). But the point is: this cut does not
cut off any integer solution, it only tightens the LP relaxation and thus
(hopefully) helps to solve the problem faster. Without the cut, the model is
equally valid and has the same integer solution space.

Now consider the traveling salesman problem. The classical formulation has a
binary variable for each edge in the graph and requires that each node has
exactly two incident edges. But with these constraints alone, it could happen
that you get a solution that has multiple short cycles instead of just one big
cycle. In order to avoid these "sub-tours" you have to add "sub-tour elimination
constraints". These say that for each subset S of the nodes V in the graph with
1 <= |S| < |V|, the number of edges that have to go from S to V\S is at least 2.
The issue is that there are an exponential number of sub-sets S of V and thus an
exponential number of sub-tour elimination constraints. This is why these are
usually implemented as lazy constraints: you only want to add those sub-tour
elimination constraints that are violated by some tentative solution vector that
is produced during the solving process.

So, you see: if you do not add the sub-tour elimination constraints your final
solution could be wrong (it may contain sub-tours). On the other hand, if you do
not separate knapsack cover cuts, then nothing bad can happen except that the
solving time may go up.

Note also that you need to set the "LazyConstraints" parameter if your callback
wants to produce lazy constraints. This disables a certain set of presolve
reductions that are invalid in the presence of constraints that are not yet
known to Gurobi. For user cuts, this is not necessary, because the full
semantics of the model is already available in the original constraints.


Best regards,

Tobias