Two-stage Recourse

330. Two-stage Recourse

The simplest stochastic program: decide $𝑥$ now, observe random $𝜉$ , then adapt with second-stage decision $𝑦$ .

330.1. Formulation

min_{𝑥} 𝑐^{𝑇} 𝑥 + 𝐸_{𝜉} [𝑄 (𝑥, 𝜉)]

where the recourse function:

𝑄 (𝑥, 𝜉) = min_{𝑦} {{𝑞 (𝜉)}^{𝑇} 𝑦 : 𝑇 (𝜉) 𝑥 + 𝑊 𝑦 = ℎ (𝜉), 𝑦 \geq 0}

$𝑥$ is here-and-now (e.g., build capacity); $𝑦$ is wait-and-see (e.g., produce at each plant once demand is known).

330.2. Deterministic equivalent (scenarios)

For a finite scenario set $𝜉^{1}, \dots, 𝜉^{𝑆}$ with probabilities $𝑝^{𝑠}$ :

min_{𝑥, 𝑦^{1}, \dots, 𝑦^{𝑆}} 𝑐^{𝑇} 𝑥 + \sum_{𝑠} 𝑝^{𝑠} {𝑞 (𝜉^{𝑠})}^{𝑇} 𝑦^{𝑠}

s.t.: $𝑇 (𝜉^{𝑠}) 𝑥 + 𝑊 𝑦^{𝑠} = ℎ (𝜉^{𝑠})$ , $𝑦^{𝑠} \geq 0$ , $\forall 𝑠$ .

A single large LP with $| 𝑥 | + | 𝑦 | \cdot 𝑆$ variables. Can be solved with simplex / interior-point. Problematic when $𝑆$ is large.

330.3. Decomposition methods

For large $𝑆$ :

L-shaped method (Benders decomposition): alternate between a master problem on $𝑥$ and recourse subproblems for each scenario
Stochastic dual dynamic programming (SDDP): for multi-stage problems, builds piecewise-linear approximations of cost-to-go
Progressive hedging: bundle scenarios and enforce non-anticipativity via Lagrangian relaxation

330.4. Worked example

You can install solar capacity $𝑥$ now (cost $𝑐$ per unit). Tomorrow, demand $𝐷$ is realized — uncertain, two scenarios:

High demand ( $𝑝 = 0.6$ ): $𝐷 = 100$ , recourse buys grid power at $0.20$ per unit shortage
Low demand ( $𝑝 = 0.4$ ): $𝐷 = 40$ , recourse sells excess at $0.10$ per unit

Decision: how much $𝑥$ to install? Two-stage SP:

min_{𝑥} 𝑐 𝑥 + 0.6 [0.20 max (0, 100 - 𝑥)] + 0.4 [- 0.10 max (0, 𝑥 - 40)]

(Recourse function is the inner min — here it’s just the cost given the realized demand.)

Optimal $𝑥^{*}$ balances the cost of capacity now against expected shortage/surplus cost later. Different from optimizing for the expected demand $0.6 \cdot 100 + 0.4 \cdot 40 = 76$ .

330.5. Why expected-demand optimization is wrong

Optimizing the expected (deterministic) problem misses the cost asymmetry between scenarios. Shortage at $0.20$ per unit might be much more expensive than surplus at $0.10$ per unit savings. SP captures this directly; deterministic doesn’t.

This gap is the Value of Stochastic Solution (VSS) — see EVPI vs VSS.

330.6. See also

Stochastic Programming
Scenario Trees
EVPI vs VSS
Decision Trees — discrete-decision analog