Stochastic Programming

Stochastic programming, introduced independently by Dantzig (1955) and Beale (1955), is the branch of mathematical optimization in which uncertainty is modelled by a known probability distribution. The canonical formulation is two-stage: first-stage here-and-now decisions (capacity, location, ordering) are made before uncertainty is revealed; second-stage recourse decisions (corrective actions — overtime, emergency procurement, penalty acceptance) are made after a scenario realises. The objective is first-stage cost plus expected second-stage recourse cost. The multi-stage extension is defined on a scenario tree where non-anticipativity constraints couple decisions at each node. Risk-averse variants replace risk-neutral expectation with CVaR or expected utility. Solution methods include scenario-based deterministic equivalent LP, Benders decomposition (L-shaped method, Van Slyke and Wets 1969), stage-wise Lagrangian relaxation, progressive hedging (Rockafellar and Wets 1991), and Sample Average Approximation (SAA, Shapiro and Homem-de-Mello 1998). Scenario count grows quickly; scenario reduction and clustering are practical necessities. Stochastic programming is preferred over robust optimization when probability distributions are credible. References: Birge and Louveaux (2011), Shapiro Dentcheva Ruszczynski (2009).