331. Scenario Trees

The data structure that represents multi-stage uncertainty in stochastic programming. A branching tree where each node represents a state of information at a point in time.

331.1. Structure

• Root: initial state, $𝑡=0$, all decisions ahead
• Internal nodes: information realized so far at time $𝑡$
• Branches: random outcomes from each node
• Leaves: complete realization paths from root to leaf

Each path from root to leaf is a scenario. The tree assigns probabilities to outcomes; each leaf’s path-probability is the product of branch probabilities.

331.2. Example: 3-stage tree

Stage 1 (root): uncertain demand ${𝐷}_1\in \left\{\text{high},\text{low}\right\}$ Stage 2: uncertain interest rate ${𝑅}_2\in \left\{\text{up},\text{down}\right\}$ Stage 3: terminal payoff depending on both

                       ┌── high R → leaf (D=high, R=up)
       ┌── D high (.6)─┤
       │              └── low R → leaf (D=high, R=down)
root ──┤
       │              ┌── high R → leaf (D=low, R=up)
       └── D low (.4)─┤
                      └── low R → leaf (D=low, R=down)

4 scenarios. Decisions at each node, conditional on the information available at that point.

331.3. Non-anticipativity

A critical constraint: decisions at a node can depend only on information realized up to that node. Two scenarios sharing a prefix must have identical decisions for that prefix.

Formally: ${𝑥}_{𝑡}^{\text{scenario A}}={𝑥}_{𝑡}^{\text{scenario B}}$ if A and B agree up to stage $𝑡$.

Implementation:

• Per-node variables (vs per-scenario): naturally encodes non-anticipativity
• Per-scenario variables with explicit constraints: ${𝑥}_{𝑡}^{𝑠}={𝑥}_{𝑡}^{\text{s'}}$ for $𝑠,{𝑠}^{\prime }$ in the same subtree
• Progressive hedging: dualize the non-anticipativity to decompose

331.4. Curse of dimensionality

Number of leaves = $\prod$ of branching factors. A 5-stage tree with 5 outcomes per stage has $5^5=3,125$ leaves; with 10 outcomes, ${10}^5=100,000$ leaves.

Mitigations:

• Scenario reduction — cluster similar scenarios, pick representative ones (Heitsch-Römisch)
• Sampling — Monte Carlo-style — see SAA
• Decomposition — solve subproblems per scenario, coordinate via Lagrangian (PH, SDDP)
• Approximate dynamic programming

331.5. Where it shows up

• Investment planning — multi-year capital allocation under uncertain returns
• Power systems — unit commitment under stochastic demand & renewables
• Supply chain network design — multi-year facility planning
• Financial planning — asset-liability matching for pensions / insurance
• Inventory — multi-period stochastic inventory

331.6. See also

• Stochastic Programming — broader framework
• Two-stage Recourse — simplest case
• SAA — Monte Carlo approximation
• Dynamic Programming — alternative view