Integer L-shaped Method

The Integer L-shaped method [1] extends the Combinatorial Benders Decomposition and L-shaped Method to handle two-stage stochastic integer programming with binary complicating variables in the first stage and integer recourse variables in the second stage. In these problems, the second-stage (recourse) decisions include integer variables, making the subproblems MILP rather than simple LP. Because MILPs do not have a strong, readily-available dual like LPs do, the classical Benders cuts derived from duality are not applicable. Instead, the Integer L-shaped method applies the principles of Combinatorial Benders Decomposition to the stochastic programming framework.

Original Problem

The problem structure is similar to that of the standard L-shaped method, but the second-stage variables now belong to a set that includes integers.

\[\begin{split}\begin{aligned} \min_{x, y_\omega} \quad & c^T x + \sum_{\omega \in \Omega} p_\omega q_\omega^T y_\omega \\ \text{s.t.} \quad & Ax \geq b \\ & T_\omega x + W y_\omega \geq h_\omega, \quad \forall \omega \in \Omega \\ & x \in X \subseteq \{0,1\}^n \\ & y_\omega \in Y_\omega, \quad \forall \omega \in \Omega \end{aligned}\end{split}\]

The key differences from the L-shaped Method are:

  • The first-stage complicating variables \(x\) are required to be binary for generating combinatorial cuts.

  • The second-stage feasible region \(Y_\omega\) contains integer variables, no longer just continuous ones.

Reformulation

The decomposition into a master problem and subproblems remains, but the nature of the cuts and the information gathered from subproblems changes. The master problem is defined over the first-stage binary variables \(x\) and an auxiliary variable \(\theta\) that estimates the expected recourse cost.

\[\begin{split}\begin{aligned} \min_{x, \theta} \quad & c^T x + \theta \\ \text{s.t.} \quad & Ax \geq b \\ & x \in X \subseteq \{0,1\}^n \\ & \dots (\text{no-good cuts}) \\ & \dots (\text{integer optimality cuts}) \end{aligned}\end{split}\]

For a given first-stage decision \(\bar{x}\), the subproblem for each scenario \(\omega\) is a MILP as follows.

\[\begin{split}\begin{aligned} Q(\bar{x}, \omega) = \min_{y_\omega} \quad & q_\omega^T y_\omega \\ \text{s.t.} \quad & W y_\omega \geq h_\omega - T_\omega \bar{x} \\ & y_\omega \in Y_\omega \end{aligned}\end{split}\]

Solving this subproblem can result in two outcomes:

  1. Infeasible: Leads to a no-good cut (feasibility cut) for the master problem.

  2. Feasible: Yields an optimal solution \(\bar{y}_\omega\) and cost \(Q_\omega^*\), leading to an integer optimality cut.

Integer L-shaped Cuts

Since LP duality cannot be used, the cuts are logic-based, identifying the specific combination of first-stage decisions \(x\) that caused either infeasibility or a certain level of cost in a subproblem.

No-good Cut (Feasibility Cut)

  • When is it generated? When the subproblem for a specific scenario \(\omega\) is found to be infeasible for a given first-stage solution \(\bar{x}\).

  • Logic: A no-good cut forbids the exact combination of master variables that led to the infeasibility. Let \(I_1\) be the indices of binary master variables \(x_i\) that are 1 in \(\bar{x}\), and \(I_0\) be the indices of those that are 0. The cut forces at least one of these variables to change its value.

  • The Cut:

    \[\sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \geq 1\]

Note

  • This cut is identical in form to the no-good cut in Combinatorial Benders Decomposition.

  • To strengthen the cut, the sets \(I_1\) and \(I_0\) should ideally form a minimal set of variables causing infeasibility, which can be found by solving for an Irreducible Inconsistent Subsystem (IIS) of the subproblem.

Integer Optimality Cut

  • When is it generated? When all subproblems are feasible for a given \(\bar{x}\), yielding optimal costs \(Q_\omega^*\).

  • From Logic to Math: The cut is derived from a simple logical statement, which is then translated into a linear inequality using a “big-M” approach. We show this for the single-cut case.

Single Integer Optimality Cut

This cut provides a lower bound on the expected recourse cost \(\theta\).

  • The Core Logic: The cut must enforce the following condition: IF the master problem chooses the same solution again (i.e., \(x = \bar{x}\)), THEN the expected future cost \(\theta\) must be greater than or equal to the cost \(Q^* = \sum_{\omega \in \Omega} p_\omega Q_\omega^*\) calculated, ELSE (if \(x \neq \bar{x}\)), this specific cut should not impose a new bound and must be relaxed.

    \[x = \bar{x} \implies \theta \geq Q^*\]

  • Linear Formulation: This logic is modeled by introducing a large constant \(M\). The expression \(\sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i\) is 0 if \(x=\bar{x}\) and at least 1 otherwise. This gives us the “big-M” cut as follows.

    \[\theta \geq Q^* - M \left( \sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \right)\]

    Note

    This is the form used in the Combinatorial Benders Decomposition.

    It is equivalent to the following form.

    \[\theta \geq Q^* - M \left( |I_1| - \sum_{i \in I_1} x_i + \sum_{i \in I_0} x_i \right)\]

  • Choosing M: Laporte & Louveaux [1] provide a tighter form by refining the choice of \(M\). The tightest valid value for \(M\) is \((Q^* - L)\), where \(L\) is a known lower bound on \(\theta\). Substituting this gives the following cut.

    \[\theta \geq Q^* - (Q^* - L) \left( |I_1| - \sum_{i \in I_1} x_i + \sum_{i \in I_0} x_i \right)\]

    It can be rearranged to the final form [1] as follows.

    \[\theta \geq (Q^* - L) \left ( \sum_{i \in I_1} x_i - \sum_{i \in I_0} x_i \right ) - (Q^* - L) (|I_1| - 1) + L\]

    Note

    How to choose the value of \(L\):

    • \(L\) can be a trivial lower bound 0.

    • \(L\) can also be the value of \(\theta\) from the previous iteration, which is valid since \(\theta\) is non-decreasing over iterations.

Multi Integer Optimality Cut

Similar to the L-shaped Method, a multi-cut version can be derived where each scenario contributes its own cut.

  • Logic: A separate recourse cost variable \(\theta_\omega\) is introduced for each scenario in the master problem, with the objective \(c^T x + \sum_{\omega \in \Omega} p_\omega \theta_\omega\). A separate optimality cut is added for each scenario.

  • The Cut: The cut for each scenario \(\omega\) is as follows.

    \[\theta_\omega \geq (Q_\omega^* - L_\omega) \left ( \sum_{i \in I_1} x_i - \sum_{i \in I_0} x_i \right ) - (Q_\omega^* - L_\omega) (|I_1| - 1) + L_\omega\]

    Here, \(Q_\omega^*\) is the optimal cost from scenario \(\omega\) subproblem, and \(L_\omega\) is a lower bound on the individual recourse cost \(\theta_\omega\).

Note

The tradeoff between single-cut and multi-cut in the L-shaped Method is also relevant to the Integer L-shaped method.

  • Single-cut vs. Multi-cut:

    • The single-cut method adds only one optimality cut per iteration, keeping the master problem smaller. However, it may require more iterations to converge due to the coarser approximation of the recourse function.

    • The multi-cut approach provides a more accurate piecewise linear approximation of the recourse function, so it typically converges in fewer iterations than the single-cut method. However, the master problem grows larger with each iteration, potentially increasing the time per iteration.

BendersLib provides parameters BendersParams.multi_opti_cut and BendersParams.multi_feas_cut to select the desired approach.

Algorithm

The iterative procedure combines the loops of the L-shaped Method method with the cut generation logic of the Combinatorial Benders Decomposition.

  1. Initialization

    • Initialize lower bound \(LB = -\infty\) and upper bound \(UB = +\infty\).

    • Set iteration counter \(k = 1\).

  2. Step 1: Solve the master problem

    • Solve the current master problem to get a solution \((\bar{x}_k, \bar{\theta}_k)\).

    • Update the lower bound: \(LB = \max(LB, c^T \bar{x}_k + \bar{\theta}_k)\).

  3. Step 2: Check for convergence

    • If \(UB - LB \leq \epsilon\), STOP. The optimal solution is found.

  4. Step 3: Solve the subproblems

    • For each scenario \(\omega \in \Omega\), solve the subproblem with \(x\) fixed to \(\bar{x}_k\).

  5. Step 4: Generate and add a cut

    • Case A: A subproblem is infeasible.

    • Let scenario \(\omega_j\) be the first one found to be infeasible.

    • For the scenario \(\omega_j\), identify the sets \((I_1, I_0)\).

    • Add a no-good cut to the master problem: \(\sum_{i \in I_1} (1 - x_i) + \sum_{i \in I_0} x_i \geq 1\).

    Note

    When BendersParams.multi_feas_cut is set to True, feasibility cuts are added for all infeasible scenarios. BendersLib will filter out duplicate cuts automatically.

    • Case B: All subproblems are feasible.

    • For each scenario \(\omega\), get an optimal subproblem cost \(Q_\omega^*\).

    • Calculate the objective for this feasible solution: \(c^T \bar{x}_k + \sum_{\omega \in \Omega} p_\omega Q_\omega^*\).

    • Update the upper bound: \(UB = \min(UB, c^T \bar{x}_k + \sum_{\omega \in \Omega} p_\omega Q_\omega^*)\).

    • Add an integer optimality cut (either single-cut or multi-cut version) to the master problem. In the multi-cut case, cuts are only added for scenarios where \(\bar{\theta}_{\omega} < Q_\omega^*\).

    Note

    When BendersParams.multi_opti_cut is set to True, multi optimality cuts are added. They are only added for scenarios where the current estimate underestimates the true recourse cost.

  6. Step 5: Loop

    • Increment \(k = k + 1\) and go back to Step 1.

See also

References