LazyCutCallback

Lazy cuts are essentially constraints which are part of an optimization model but which have been omitted in the current definition of the model. Lazy cuts typically arise in models with a large number of constraints. Instead of enumerating then all, it may be judicious to omit some of them to get a smaller optimization model. Then, the returned solution is checked for feasibility against the whole set of constraints. If a violated constraint is identified, we add the constraint to the model and resolve. If not, then all the constraints are satisfied and the solution is optimal for the original model in which all constraints materializes.

The LazyCutCallback can be used to implement lazy cut constraint generation on the fly, during the optimization process.

Consider the following optimization problem:

\[\begin{split}\begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X, \\ & \xi^\top x \le \xi_0 \quad (\xi_0,\xi) \in \Xi, \end{align}\end{split}\]

in which assume that \(|\Xi|\) is large (potentially infinite). The idea is to start by solving the following relaxed master problem in which constraints associated to \((\xi_0,\xi)\) have been omitted.

\[\begin{split}\begin{align} \min_x \ & c^\top x \\ \text{s.t.} \ & x\in X. \end{align}\end{split}\]

If we assume that this problem is feasible and bounded, we can denote by \(x^*\) a solution of this problem. Then, we search for a violated constraint “\(\xi^\top x \le \xi_0\)” for some \((\xi_0,\xi)\in\Xi\). Observe that a constraint is violated if, and only if, the following holds:

\[\left(\exists(\xi_0,\xi)\in\Xi, \ \xi^\top x^* > \xi_0\right) \Leftrightarrow \left(\max_{(\xi_0,\xi)\in\Xi} \xi_0 - \xi^\top x^* < 0\right).\]

Thus, the LazyCutCallback automatically solve the optimization problem on the right handside and checks for its value. A new constraint is added if, and only if,

\[\max_{\xi\in\Xi} \xi_0 - \xi^\top x^* < -\varepsilon,\]

with \(\varepsilon\) a given tolerance (by default, Tolerance::Feasibility).

Hint

You may also be interested by a tutorial showing how you can implement a simple Benders Decomposition using lazy cuts. See Benders Decomposition tutorial.

class LazyCutCallback : public idol::CallbackFactory

Public Functions

inline LazyCutCallback(const Model &t_model, TempCtr t_cut)

inline virtual Callback *operator()() override

inline virtual CallbackFactory *clone() const override

inline LazyCutCallback &with_separation_optimizer(const OptimizerFactory &t_optimizer_factory)

class Strategy : public idol::impl::CutSeparation

Public Functions

inline explicit Strategy(Model *t_separation_problem, TempCtr t_cut)