328. 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.

328.1. Structure

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.

328.2. Example: 3-stage tree

Stage 1 (root): uncertain demand Stage 2: uncertain interest rate 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.

328.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: if A and B agree up to stage .

Implementation:

328.4. Curse of dimensionality

Number of leaves = of branching factors. A 5-stage tree with 5 outcomes per stage has leaves; with 10 outcomes, leaves.

Mitigations:

328.5. Where it shows up

328.6. See also