327. Two-stage Recourse
The simplest stochastic program: decide now, observe random , then adapt with second-stage decision .
327.1. Formulation
where the recourse function:
is here-and-now (e.g., build capacity); is wait-and-see (e.g., produce at each plant once demand is known).
327.2. Deterministic equivalent (scenarios)
For a finite scenario set with probabilities :
s.t.: , , .
A single large LP with variables. Can be solved with simplex / interior-point. Problematic when is large.
327.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
327.4. Worked example
You can install solar capacity now (cost per unit). Tomorrow, demand is realized — uncertain, two scenarios:
- High demand (): , recourse buys grid power at per unit shortage
- Low demand (): , recourse sells excess at per unit
Decision: how much to install? Two-stage SP:
(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 .
327.5. Why expected-demand optimization is wrong
Optimizing the expected (deterministic) problem misses the cost asymmetry between scenarios. Shortage at per unit might be much more expensive than surplus at per unit savings. SP captures this directly; deterministic doesn’t.
This gap is the Value of Stochastic Solution (VSS) — see EVPI vs VSS.
327.6. See also
- Stochastic Programming
- Scenario Trees
- EVPI vs VSS
- Decision Trees — discrete-decision analog