.. _tutorial_user_lazy_cuts:

Adding User Cuts and Lazy Constraints
=====================================

.. contents:: Table of Contents
    :local:
    :depth: 2

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 :ref:`UserCutCallback <api_UserCutCallback>` and :ref:`LazyCutCallback <api_LazyCutCallback>` classes.
In case you are interested in creating your own callback functions, you can refer to :ref:`this page <tutorial_create_callback>`.

Now, both classes are derived from the :ref:`CallbackFactory <api_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 :ref:`UserCutCallback <api_UserCutCallback>` class is called
whenever an invalid solution is found, e.g., a point which violates integer requirements, while the :ref:`LazyCutCallback <api_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 :ref:`UserCutCallback <api_UserCutCallback>`, and
* a straightforward Bender's decomposition algorithm using the :ref:`LazyCutCallback <api_LazyCutCallback>` class.

.. contents:: Table of Contents
    :local:
    :depth: 2

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 <https://en.wikipedia.org/wiki/Knapsack_problem>`_ and
    `Cover inequalities <https://www.lancaster.ac.uk/staff/letchfoa/other-publications/2010-EORMS-cover-ineqs.pdf>`_ are recommended.

Consider the following knapsack problem.

.. math::

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

Here, :math:`x` is a binary vector, :math:`p` is a vector of profits, :math:`w` is a vector of weights, and :math:`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

.. math::

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

where :math:`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 :math:`\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.

.. math::

    \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}

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.

.. code:: cpp

    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.

.. code:: cpp

    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 :math:`C`.
**Cuts are always expressed as if they were part of the original problem**. What we mean by this is that, here, :math:`x`
should be seen as a *variable* while :math:`z` should be seen as a *constant*.

We therefore have, for a given :math:`z`,

.. code:: cpp

    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.

.. code:: cpp

    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 :ref:`UserCutCallback <api_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 <https://en.wikipedia.org/wiki/Linear_programming#Duality>`_ and
    `Benders Decomposition <https://en.wikipedia.org/wiki/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 <https://www.imus.us.es/IMUS-MSRI2016/assets/media/docs/lectures/lec_blanco_1.pdf>`_.

.. math::

    \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}

The Benders reformulation of this problem, by considering :math:`y` as the complicating variable, leads to

.. math::

    \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}

with :math:`\Lambda` defined as the set of all dual feasible m_n_points_bound, i.e., those :math:`\lambda\in\mathbb R^2_+` such that

.. math::

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

Now, we will show how to implement the Benders decomposition algorithm using the :ref:`LazyCutCallback <api_LazyCutCallback>` class.
This will be done so that constraints :math:`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 :math:`\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.

.. code:: cpp


    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 :math:`\Lambda` can be defined as follows.


.. code::

    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 :math:`\lambda`.
**Cuts are always expressed as if they were part of the master problem**. What we mean by this is that, here, :math:`y`
should be seen as a *variable* while :math:`\lambda` should be seen as a *constant*.

We therefore have, for a given :math:`\lambda`,

.. code::

    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.

.. code::

    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 :code:`Gurobi::with_lazy_cut`. This is because the Gurobi optimizer does not support lazy cuts by default
    and one needs to explicitly enable them.

