How do I implement lazy constraints in Gurobi?

There are two ways to implement lazy constraints for a MIP model.

1. If the constraints can be enumerated upfront, set theLazyattribute on the constraints that should be treated as lazy.
2. If the constraints must be generated during the MIP search, you need to write a callback function and set theLazyConstraintparameter to 1. Details can be found in the reference manuals of the various APIs, seeModel.cbLazy()for example. Additionally, there is aTraveling Salesman Problem(TSP) example that illustrates adding lazy constraints via a callback (also available in the examples subdirectory of your Gurobi installation).

When deciding between enumerating lazy constraints upfront and adding them during search using a callback function, there are a number of tradeoffs to keep in mind:

• Memory: Often the order-of-magnitude of the constraints in question will dictate whether they can be enumerated upfront or not. Take the TSP as an example. A common model uses variables for each pair of cities, constraints to ensure each city is connected to two other cities, and an exponential number of constraints to ensure that sub-tours cannot occur. For even relatively small instances with 50 cities, the number of sub-tour elimination constraints required is intractable and thus the constraints must be added lazily through a callback function. Otherwise, the machine will run out of memory.

• Convenience: Writing a callback function to detect if a constraint is violated and then adding appropriate constraints to correct this violation can be a challenging problem and time-consuming for the user. If the constraints can be enumerated upfront, then you can rely on Gurobi to add constraints when required without having to invest the effort to develop a callback function by yourself.

• Control: Writing a callback function gives the user total control over which constraints are added to the model and at what point during the search. With the enumerated lazy constraints the user has less control. The constraints are only used to cut off feasible solutions, i.e., they cannot be used to tighten the linear relaxation. In saying that, the user can still specify how aggressively Gurobi should pull constraints into the model using theLazyparameter:

With a value of 1, the constraint can be used to cut off a feasible solution, but it won't necessarily be pulled in if another lazy constraint also cuts off the solution. With a value of 2, all lazy constraints that are violated by a feasible solution will be pulled into the model. With a value of 3, lazy constraints that cut off the relaxation solution at the root node are also pulled in.

• Communication Overhead:Gurobi Instant Cloudand Gurobi'sCompute Serverboth work on the client-server paradigm, where the model is built through a Gurobi API on one machine (the client) but actually solved on another (the server). It is important to note that in such scenarios the callback functions are executed on the client machine. If the callback function is called often, then this can create latency issues due to the additional communication required.

There is no support for lazy constraints in continuous models (LP, QP, or SOCP). To add lazy constraints to a continuous model, you have to wait until it is solved (or manually stop it), add the new constraints, and start solving again.

Further information

• What is the difference between user cuts and lazy constraints?
• TSP example