Two-Stage Stochastic Programming
The two-stage model makes a here-and-now decision, observes the random outcome, then takes a recourse action to correct for it, minimizing total expected cost.
The two stages
The two-stage model is the canonical form of stochastic programming. In the first stage a decision x is fixed before any uncertainty is known, incurring a deterministic cost. Then a random outcome is observed. In the second stage a recourse decision y is chosen, allowed to depend on the observed outcome, to respond optimally to what happened. The objective is the first-stage cost plus the expected second-stage cost.
The recourse function
Formally the problem is minimize c^T x + E[ Q(x, xi) ], where Q(x, xi) is the value of the optimal second-stage decision given first-stage choice x and realized scenario xi. Q is itself an optimization: for each scenario, choose the cheapest feasible recourse. When the second stage is always feasible for any x, the problem has complete recourse, which simplifies analysis and guarantees the model never gets stuck.
Deterministic equivalent
With finitely many scenarios s of probability p_s, the expectation becomes a sum, and the whole problem is one large linear or mixed-integer program: minimize c^T x + sum p_s (q_s^T y_s) with separate recourse variables y_s per scenario, all tied to the single x. This is the deterministic equivalent. Its size grows with the number of scenarios, which motivates decomposition.
# schematic two-stage LP structure
# variables: x (first stage), y_s (recourse per scenario s)
# minimize c^T x + sum_s p_s * q_s^T y_s
# s.t. A x = b (first-stage)
# T_s x + W y_s = h_s for all s (links x to each scenario)
# x >= 0, y_s >= 0Solving at scale
The L-shaped method (Benders decomposition) exploits the structure: it solves a master problem over x, then for each scenario solves the recourse subproblem and returns an optimality cut that approximates the expected recourse cost, iterating until the cuts are tight. This avoids ever forming the full deterministic equivalent. The value of the stochastic solution, compared with optimizing against the mean scenario alone, quantifies what modeling uncertainty explicitly is worth.