329. Stochastic Programming

Optimization with uncertain parameters whose probability distribution is known. Distinguishes:

• Here-and-now decisions made before the random data is revealed
• Wait-and-see / recourse decisions made after observing the random outcome

329.1. Two-stage stochastic LP

where:

• $𝑥$: first-stage (here-and-now) decision — fixed before $𝜉$ is observed
• $𝜉$: random parameter
• $𝑦=𝑦\left(𝜉\right)$: second-stage (recourse) decision — chosen after observing $𝜉$
• $𝑄\left(𝑥,𝜉\right)$: optimal recourse cost given $𝑥$ and $𝜉$

The expectation ${𝐸}_{𝜉}$ aggregates over the distribution of $𝜉$.

329.2. Subtopics

• Two-stage recourse — the core model
• Scenario trees — multi-stage extension
• Chance constraints — probabilistic feasibility
• Sample average approximation — solve via Monte Carlo
• EVPI vs VSS — value of information / value of stochastic modeling

329.3. When to use

• Decisions must be made before uncertainty resolves — capacity planning, network design, hiring
• Some adjustments are possible later — production levels, shipping, hiring temps
• You want explicit risk management not just nominal expected-value optimization

329.4. Alternatives

• Dynamic programming: same as stochastic programming for sequential decisions, but explodes with state-space dimension. SP scales better in continuous variables.
• Robust optimization: hedges against worst-case uncertainty instead of expected case. Less data-hungry; more conservative.
• Scenario analysis: pick a few representative scenarios; solve each deterministically. Crude but easy.

329.5. See also

• Two-stage Recourse
• Scenario Trees
• Chance Constraints
• Sample Average Approximation
• EVPI vs VSS
• Dynamic Programming