L-shaped Method

The L-shaped method [1] is a specific application of Benders decomposition tailored for two-stage stochastic linear programming. These problems involve making a decision now (first stage) in the face of uncertainty about the future, which is revealed later (second stage). The problem structure consists of first-stage decisions that must hold for all future scenarios, and second-stage (recourse) decisions that adapt to the outcome of a specific scenario.

Note

The relationship between the L-shaped method and the Classical Benders Decomposition (see StackExchange/OR):

  • They are essentially the same. (“In Section 2, an algorithm which is essentially the same as the algorithm developed by Benders is described and a geometric interpretation is given.” [1] This was explicitly noted by Van Slyke and Wets in their original 1969 paper [1] introducing the L-shaped method).

  • In the literature, the term “L-shaped method” is reserved for two-stage stochastic programming problems, while “Benders decomposition” is a more general technique, sometimes it is interchangeably used for two-stage stochastic programs as well.

Original Problem

Let \(x\) be the first-stage decision variables and \(y\) be the second-stage decision variables. The uncertainty is modeled through a set of discrete scenarios \(\Omega\), where each scenario \(\omega \in \Omega\) occurs with a probability \(p_\omega\). The deterministic equivalent of a two-stage stochastic program is as

\[\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 \\ & y_\omega \in Y, \quad \forall \omega \in \Omega \end{aligned}\end{split}\]

where \(x\) are the first-stage (here-and-now) variables, which are the complicating variables. \(y_\omega\) are the second-stage (wait-and-see) variables for each scenario \(\omega\). The first-stage constraints \(Ax \geq b\) are independent of any scenario. The second-stage constraints \(T_\omega x + W y_\omega \geq h_\omega\) link the first-stage decisions to the second-stage decisions. The matrix \(W\) is known as the recourse matrix and is typically assumed to be fixed across scenarios.

Note

Assumptions commonly made in the L-shaped method include:

  • Linear recourse: The second-stage problem is a Linear Programming problem for each scenario.

  • Fixed recourse: The recourse matrix \(W\) is the same for all scenarios.

  • Complete recourse: The second-stage problem is always feasible for any first-stage decision \(x\).

The method’s name originates from the block structure of the constraint matrix in the deterministic equivalent formulation. When the variables are ordered with the first-stage variables \(x\) first, followed by the recourse variables \(y_\omega\) for each scenario, the matrix of constraint coefficients has a clear “L” shape. The first-stage constraint matrix \(A\) forms the top horizontal bar, and the technology matrices \(T_\omega\) stack vertically below it. The recourse matrix \(W\) forms a block-diagonal pattern, and the top-right of the overall matrix is all zeros.

\[\begin{split}\begin{pmatrix} A & 0 & 0 & \cdots & 0 \\ T_1 & W & 0 & \cdots & 0 \\ T_2 & 0 & W & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ T_{|\Omega|} & 0 & 0 & \cdots & W \end{pmatrix}\end{split}\]

This structure is the key to the decomposition. Since the second-stage blocks are independent of one another, fixing the first-stage variables \(x\) causes the problem to “decompose” into smaller parallel subproblems.

Reformulation

The problem is reformulated by separating the first-stage variables from the second-stage variables. The second-stage costs and constraints are handled in subproblems that are solved for each scenario independently. The master problem is defined over the first-stage variables \(x\) and an auxiliary variable \(\theta\) that represents the expected future cost of the second-stage decisions.

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

For a given first-stage decision \(\bar{x}\), the second-stage problem decomposes into \(|\Omega|\) independent linear programs, one for each scenario \(\omega\). The primal subproblem for scenario \(\omega\) is 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 \end{aligned}\end{split}\]

As in classical Benders, we are interested in the dual of the subproblem to generate cuts. The dual subproblem for scenario \(\omega\) is as follows.

\[\begin{split}\begin{aligned} \max_{\pi_\omega} \quad & \pi_\omega^T (h_\omega - T_\omega \bar{x}) \\ \text{s.t.} \quad & W^T \pi_\omega \leq q_\omega \\ & \pi_\omega \geq 0 \end{aligned}\end{split}\]

The solution to these dual subproblems provides the necessary information to generate feasibility and optimality cuts for the master problem.

Hint

An attractive feature of the L-shaped method is that the subproblems for each scenario can be solved in parallel, making it well-suited for large-scale stochastic programming problems with many scenarios.

L-shaped Cuts

The cuts improve the master problem’s estimate of the expected second-stage cost. Feasibility cuts are created when a subproblem is infeasible, whereas optimality cuts arise when all subproblems are feasible. Optimality cuts come in two forms: single-cut and multi-cut.

Feasibility Cut

A feasibility cut is generated if, for a given \(\bar{x}\), the subproblem for some scenario \(\omega\) is infeasible. This corresponds to the dual subproblem for that scenario being unbounded. An extreme ray \(\bar{r}_\omega\) of the dual feasible region provides a certificate of infeasibility.

  • When is it generated? When a subproblem for scenario \(\omega\) is infeasible.

  • The Cut: To cut off the infeasible \(\bar{x}\), we add the constraint as follows.

    \[0 \geq \bar{r}_\omega^T (h_\omega - T_\omega x)\]

This cut makes any first-stage decision \(x\) that would cause the same infeasibility in scenario \(\omega\) invalid.

Note

  • On may chose to add feasibility cuts for all infeasible scenarios found in an iteration, or just for the first one encountered (the subsequent subproblems is not required to be solved).

  • The above feature can be controlled in BendersLib via the BendersParams.multi_feas_cut parameter.

Optimality Cut

An optimality cut is generated when the subproblems for all scenarios \(\omega \in \Omega\) are feasible for a given \(\bar{x}\). This yields an optimal dual solution \(\bar{\pi}_\omega\) for each scenario. There are two common ways to formulate optimality cuts.

Single Optimality Cut

The single-cut approach, also known as the classical L-shaped method, adds one aggregated cut to the master problem per iteration.

  • When is it generated? When all subproblems are feasible for the given \(\bar{x}\), but the subproblem solutions suggest that the estimator \(\theta\) in the master problem underestimates the true expected recourse cost.

  • Logic: The variable \(\theta\) in the master problem represents the expected future cost, \(\mathbb{E}[Q(x, \omega)] = \sum_{\omega \in \Omega} p_\omega Q(x, \omega)\). The cut provides a lower bound on this expectation. Using the optimal dual solutions \(\bar{\pi}_\omega\), we construct a valid lower bound for any \(x\).

  • The Cut: The aggregated cut is as follows.

    \[\theta \geq \sum_{\omega \in \Omega} p_\omega \left[ \bar{\pi}_\omega^T (h_\omega - T_\omega x) \right]\]

This cut is a linearization of the convex expected recourse function \(\mathbb{E}[Q(x, \omega)]\) at the point \(\bar{x}\).

Multi Optimality Cut

The multi-cut approach generates a separate cut for each scenario, leading to a tighter but larger master problem, since the number of cuts added per iteration equals the number of scenarios.

  • When is it generated? When all subproblems are feasible for the given \(\bar{x}\), but the subproblem solutions suggest that the estimator \(\theta_\omega\) in the master problem underestimate the true recourse cost for the corresponding scenario.

  • Logic: First, the master problem is reformulated to include a separate recourse cost variable \(\theta_\omega\) for each scenario. The master problem then becomes as follows.

    \[\begin{split}\begin{aligned} \min_{x, \theta_\omega} \quad & c^T x + \sum_{\omega \in \Omega} p_\omega \theta_\omega \\ \text{s.t.} \quad & Ax \geq b \\ & x \in X \\ & \theta_\omega \geq \dots (\text{optimality cuts for } \omega), \forall \omega \in \Omega \\ & 0 \geq \dots (\text{feasibility cuts}) \end{aligned}\end{split}\]

  • The Cut: For each scenario \(\omega\), a separate optimality cut is added to the master problem. This cut is identical in form to the classical Benders optimality cut, applied to a single subproblem.

    \[\theta_\omega \geq \bar{\pi}_\omega^T (h_\omega - T_\omega x)\]

Note

  • 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.

  • Users can control which variant to use in BendersLib via the BendersParams.multi_opti_cut parameter.

Algorithm

The L-shaped algorithm proceeds as follows, shown here for the single-cut and multi-cut variants.

  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 (dual) subproblem with the fixed value \(\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.

    • Obtain an extreme ray \(\bar{r}_{\omega_j}\) from its dual subproblem.

    • Add a feasibility cut to the master problem: \(0 \geq \bar{r}_{\omega_j}^T (h_{\omega_j} - T_{\omega_j} x)\).

    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.

    • Obtain the optimal dual solutions \(\bar{\pi}_\omega\) for all \(\omega \in \Omega\).

    • Calculate the expected recourse cost: \(Q(\bar{x}_k) = \sum_{\omega \in \Omega} p_\omega \left[ \bar{\pi}_\omega^T (h_\omega - T_\omega \bar{x}_k) \right]\).

    • Update the upper bound: \(UB = \min(UB, c^T \bar{x}_k + Q(\bar{x}_k))\).

    • Add optimality cut to the master problem:

      • Single optimality cut: \(\theta \geq \sum_{\omega \in \Omega} p_\omega \left[ \bar{\pi}_\omega^T (h_\omega - T_\omega x) \right]\).

      • Multi optimality cut: \(\theta_\omega \geq \bar{\pi}_\omega^T (h_\omega - T_\omega x)\) for each \(\omega\) that \(\bar{\theta}_\omega < \bar{\pi}_\omega^T (h_\omega - T_\omega \bar{x}_k)\), where \(\bar{\pi}_\omega^T (h_\omega - T_\omega \bar{x}_k)\) is the objective value of the subproblem for scenario \(\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.

The L-shaped method requires master and subproblem formulations that align with the two-stage stochastic programming structure. We implemented it in LShaped. Users may formulate their problems to deterministic equivalents manually for comparison or benchmarking purposes.

See also

References