I'm trying to use lazy constraints to solve an optimization problem. In some software such as CPLEX or GUROBI, they have some tools to handle them directly (in the original model) or using callback functions. I was wondering what is the difference between them?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Lazy constraints will only be checked when an MIP solution satisfying all other constraints, including integrality, is found.
If you provide all your lazy constraints in advance to CPLEX, for example, then your main benefit is that these constraints are only checked against solutions that would otherwise be feasible.
However, you may have an exponential number of such constraints, even though in some cases you could easily tell if any of those constraints would be violated by a particular solution. In such case, implementing a lazy cut callback is a good idea because you can provide these constraints to CPLEX only when they are needed, and consequently you speed up the solving process.
One classic example of that is the subtour elimination constraint for the traveling salesperson problem. If a binary variable $x_{ij}$ is 1 when you go from city $i$ to city $j$, then you can start with the assignment constraints (you should get in and out of every city exactly once). If a solution is found in which you cycle through a subset $S$ of the cities, you add the corresponding subtour elimination constraint to ensure that you visit one city in $S$ coming from a city outside $S$ or vice-versa. The number of such constraints is exponential, but you know how to efficiently identify which one matters for your current assignment.
