The L-Shaped Method for Two-Stage Stochastic Programs

A two-stage stochastic linear program with recourse chooses a first-stage decision $\mathbf{x}$ before random data $\xi$ are observed, then a scenario-specific recourse $\mathbf{y}$ afterward:

$$\min_{\mathbf{x}}\: \mathbf{c}^T\mathbf{x} + \mathbb{E}_\xi[Q(\mathbf{x},\xi)] \quad \text{s.t.}\: A\mathbf{x}=\mathbf{b},\: \mathbf{x}\geq 0,$$

where the recourse function is

$$Q(\mathbf{x},\xi) = \min_{\mathbf{y}\geq 0}\: \mathbf{q}(\xi)^T\mathbf{y} \quad \text{s.t.}\: W\mathbf{y}\geq \mathbf{h}(\xi)-T(\xi)\mathbf{x}.$$

With finitely many scenarios $\xi_1,\ldots,\xi_S$ occurring with probabilities $p_1,\ldots,p_S,$ the expected recourse is

$$\mathcal{Q}(\mathbf{x}) = \sum_{s=1}^S p_s\, Q(\mathbf{x},\xi_s).$$

The L-shaped method is Benders decomposition specialized to this two-stage structure. It replaces $\mathcal{Q}(\mathbf{x})$ in the objective by a scalar variable $\theta$ and refines $\theta$ via cuts. The master problem is

$$\min_{\mathbf{x},\theta}\: \mathbf{c}^T\mathbf{x}+\theta \quad \text{s.t.}\: A\mathbf{x}=\mathbf{b},\: \mathbf{x}\geq 0,$$

augmented with optimality and feasibility cuts.

Two consequences of the structure are essential:

1. Decoupled subproblems. For a fixed candidate $\hat{\mathbf{x}},$ each $Q(\hat{\mathbf{x}},\xi_s)$ is its own LP — the only coupling across scenarios is through $\hat{\mathbf{x}}.$

2. Bounds. The optimal master objective $\mathbf{c}^T\hat{\mathbf{x}}+\theta$ is a lower bound on the true optimum. After solving every subproblem at $\hat{\mathbf{x}},$ the quantity $\mathbf{c}^T\hat{\mathbf{x}}+\mathcal{Q}(\hat{\mathbf{x}})$ is an upper bound. The algorithm terminates when these bounds meet.