Adding User Cuts and Lazy Constraints

Introduction 

When solving a mixed-integer program (MIP), the underlying optimizers typically make use of a branch-and-cut algorithm. This algorithm iteratively solves a(n LP) relaxation of the problem, and then adds cuts to the problem to strengthen the relaxation. Typically, these cuts are generated by the solver itself. However, the user can also add his or her own cuts to the problem. This is useful when the user has domain-specific knowledge that can be used to strengthen the relaxation.

Classically, there are two types of cuts that can be added to a MIP: user cuts and lazy constraints.

User cuts are cuts which are not necessary to define the feasible region of the problem, but which can be used to strengthen the relaxation. As a matter of fact, User cuts never cut off feasible solutions to the original problem.
Lazy constraints are constraints which are necessary to define the feasible region of the problem but are either unlikely to be violated or impractical to generate in advance. Lazy constraints are only added to the problem if they are violated by a current solution.

In both cases, user cuts and lazy constraints are added to the problem within a callback function, given to the optimizer. Then, the optimizer will call this callback function at each node of the branch-and-cut tree, allowing to look for violated cuts and constraints that can be added to the problem.

Though it is possible for the user to create his or her own callback functions, the idol library provides a simple way to add user cuts and lazy constraints to a MIP, using the UserCutCallback and LazyCutCallback classes. In case you are interested in creating your own callback functions, you can refer to this page.

Now, both classes are derived from the CallbackFactory class, and are used to create callback objects that can be passed to the optimizer. They both have a similar interface: First, the user defines a model for the separation problem (i.e., the problem that will be solved to generate the cuts or constraints), and the corresponding cut to be added to the original problem. Then, the user creates a callback factory object, and passes the model and the cut to the factory. The user also specifies which optimizer should be used to solve the separation problem. Finally, the user passes the callback factory to the optimizer, which will manage the execution of the callback.

The main difference between the two classes is that the UserCutCallback class is called whenever an invalid solution is found, e.g., a point which violates integer requirements, while the LazyCutCallback class is called whenever a new valid solution is found to check that it satisfies all the lazy constraints.

In the next section, we will show how to implement

a simple separation procedure for knapsack cover inequalities using the UserCutCallback, and
a straightforward Bender’s decomposition algorithm using the LazyCutCallback class.

An Example of User Cuts: Knapsack Cover Inequalities 

Hint

This section is dedicated to the “advanced topic” of knapsack cover inequalities. Rudimentary notions on Knapsack problems and Cover inequalities are recommended.

Consider the following knapsack problem.

\[\begin{split}\begin{align} \max_{x} \ & p^\top x \\ \text{s.t.} \ & w^\top x \le W, \\ & x\in\{0,1\}^n. \end{align}\end{split}\]

Here, \(x\) is a binary vector, \(p\) is a vector of profits, \(w\) is a vector of weights, and \(W\) is the capacity of the knapsack.

It is well-known that the knapsack problem can be strengthened by adding cover inequalities. A cover inequality is a constraint of the form

\[\sum_{i\in C} x_i \le |C| - 1,\]

where \(C\) defines a cover of the knapsack, i.e., a set of items such that the sum of their weights is greater than the capacity of the knapsack.

Given a solution \(\hat x\) to the continuous relaxation of the knapsack problem, we can check whether it violates a cover inequality. This is done by solving the following separation problem.

\[\begin{split}\begin{align} \max_{z} \ & (1 - \hat x)^\top z & \ge 1 \\ \text{s.t.} \ & w^\top z \ge W + 1, \\ & z\in\{0,1\}^n. \end{align}\end{split}\]

A cover inequality is violated if and only if the optimal objective value of this problem is strictly less than 1. In such a case, a new cut should be added.

As anticipated, we need to define three different things:

the original problem, i.e., the problem to be solved by the branch-and-cut algorithm;
the feasible region of the separation problem, i.e., the set of all cover inequalities;
the shape of the cuts to be added.

Defining the original problem is straightforward and can be done as follows.

Env env;
Model knapsack(env, Maximize);

const auto x = knapsack.add_vars(Dim<1>(n), 0, 1, Binary, "x");

knapsack.add_ctr(idol_Sum(i, Range(n_items), w[i] * x[i]) <= W);
knapsack.set_obj_expr(idol_Sum(i, Range(n_items), p[i] * x[i]));

Similarly, the feasible region of the separation problem can be defined as follows.

Model cover(env);

const auto z = cover.add_vars(Dim<1>(n), 0, 1, Binary, "z");

cover.add_ctr(idol_Sum(i, Range(n_items), w[i] * z[i]) >= W + 1);

Finally, we need to define the cuts to be added to the original problem for a given cover inequality \(C\). Cuts are always expressed as if they were part of the original problem. What we mean by this is that, here, \(x\) should be seen as a variable while \(z\) should be seen as a constant.

We therefore have, for a given \(z\),

const auto cover_cut = idol_Sum(i, Range(n_items), !z[i] * x[i]) <= idol_Sum(i, Range(n_items), 1 - !z[i]);

See how the z variables are “turned into” constants by prepending them with an “!” symbol.

We are now ready to create the callback factory and pass it to the optimizer. This is done as follows.

knapsack.use(
    Gurobi::Continuous()
        .add_callback(
            UserCutCallback(cover, cover_cut)
                .with_separation_optimizer(Gurobi())
        )
);

knapsack.optimize();

Here, we solve the continuous relaxation of the knapsack problem using the Gurobi optimizer, and add the cover inequalities using the UserCutCallback.

An Example of Lazy Cut Constraints: Benders Optimality Cuts 

Hint

This section is dedicated to the “advanced topic” of Benders Decomposition. Rudimentary notions on Linear Programming duality and Benders Decomposition the following subjects are recommended.

We will base our example on the following model taken from Blanco, V., (2016), Benders Decomposition, MINLP School: Theory and Applications.

\[\begin{split}\begin{align} \min_{x,y} \ & 2 x_0 + 3x_1 + 2y \\ \text{s.t.} \ & x_0 + 2x_1 + y \ge 3, \\ & 2x_0 - x_1 + 3y \ge 4, \\ & x\ge 0, y\in \mathbb N. \end{align}\end{split}\]

The Benders reformulation of this problem, by considering \(y\) as the complicating variable, leads to

\[\begin{split}\begin{align} \min_{y,z} \ & 2y + z \\ \text{s.t.} \ & z \ge \lambda_1 ( 3 - y ) + \lambda_2(4 - 3y) \qquad \forall \lambda \in \Lambda, \\ & z \ge 0, y\in\mathbb N, \end{align}\end{split}\]

with \(\Lambda\) defined as the set of all dual feasible points, i.e., those \(\lambda\in\mathbb R^2_+\) such that

\[\begin{split}\begin{align} & \lambda_0 + 2 \lambda_1 \le 2, \\ & 2\lambda_0 - \lambda_1 \le 3. \end{align}\end{split}\]

Now, we will show how to implement the Benders decomposition algorithm using the LazyCutCallback class. This will be done so that constraints \(z \ge \hat \lambda_1 ( 3 - y ) + \hat \lambda_2(4 - 3y)\) are added to the master problem whenever a violated Benders cut is found.

As anticipated, we need to define three different things:

the master problem, i.e., the problem to be solved at each node of the branch-and-cut tree;
the dual space \(\Lambda\), i.e., the feasible region of the separation problem;
the shape of the cuts to be added.

Defining the master problem is straightforward and can be done as follows.

Env env;

Model master(env);

const auto y = master.add_var(0, Inf, Integer, "y");
const auto z = master.add_var(0, Inf, Continuous, "z");

master.set_obj_expr(2 * y + z);

Similarly, the dual space \(\Lambda\) can be defined as follows.

Model dual_space(env);

const auto lambda = dual_space.add_vars(Dim<1>(2), 0, Inf, Continuous, "lambda");

dual_space.add_ctr(lambda[0] + 2 + lambda[1] <= 2);
dual_space.add_ctr(2 * lambda[0] - lambda[1] <= 3);

Finally, we need to define the cuts to be added to the master problem for a given dual variable \(\lambda\). Cuts are always expressed as if they were part of the master problem. What we mean by this is that, here, \(y\) should be seen as a variable while \(\lambda\) should be seen as a constant.

We therefore have, for a given \(\lambda\),

const auto benders_cut = z >= !lambda[0] * (3 - y) + !lambda[1] * (4 - 3 * y);

See how the lambda variables are “turned into” constants by prepending them with an “!” symbol.

We are now ready to create the callback factory and pass it to the optimizer. This is done as follows.

master.use(
    Gurobi()
        .add_callback(
            LazyCutCallback(dual_space, benders_cut)
                .with_separation_optimizer(Gurobi())
        )
        .with_lazy_cut(true)
);

master.optimize();

That’s it! The optimizer will now call the callback function at each node of the branch-and-cut tree, and add the cuts to the master problem whenever a violated constraint is found.

Hint

Here, we added a call to Gurobi::with_lazy_cut. This is because the Gurobi optimizer does not support lazy cuts by default and one needs to explicitly enable them.

Adding User Cuts and Lazy Constraints

Introduction

An Example of User Cuts: Knapsack Cover Inequalities

An Example of Lazy Cut Constraints: Benders Optimality Cuts

Introduction 

An Example of User Cuts: Knapsack Cover Inequalities 

An Example of Lazy Cut Constraints: Benders Optimality Cuts 