Scenario Trees and the Extensive Form

Represent multistage uncertainty as a scenario tree and write the deterministic-equivalent extensive-form optimization problem for a two-stage stochastic program. Compute scenario probabilities by multiplying along tree branches, and evaluate expected total cost using the extensive-form objective.

Step 1 of 157%

Tutorial

Scenario Trees

A scenario tree represents how uncertainty unfolds over multiple decision stages. The tree has:

  • A single root node, representing the current state before any uncertainty has been resolved.
  • Each non-leaf node has one branch per possible outcome of the next random event. The conditional probabilities on the branches leaving any node sum to 1.1.
  • Each leaf corresponds to one scenario -- a complete root-to-leaf path describing one possible history of random outcomes.
  • The probability of a scenario is the product of the conditional probabilities along the branches in its path.

For example, in a two-stage program with a single random outcome taking values ω1,ω2,ω3\omega_1, \omega_2, \omega_3 with probabilities 0.3,0.5,0.2,0.3, 0.5, 0.2, the tree has three scenarios with probabilities p1=0.3,p_1 = 0.3, p2=0.5,p_2 = 0.5, p3=0.2.p_3 = 0.2. The scenario probabilities sum to 1.1.

In a multistage tree, scenario probabilities multiply along the path. For instance, if the root branches with probabilities 0.60.6 and 0.4,0.4, and from the 0.60.6 child we branch with probabilities 0.50.5 and 0.5,0.5, each of the two scenarios passing through that child has probability

0.6⋅0.5=0.30.0.6 \cdot 0.5 = 0.30.
↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle