When the probability distributions for the random parameters (events) are discrete, there are only a finite number of outcomes in each stage. With each random parameter fixed to one of its possible outcomes, one can create a scenario representing one possible realization of the future. Enumeration of all possible combinations of outcomes allows us to represent all scenarios in a tree, with each scenario being a path from the root of the tree to one of its leaves. The nodes visited by each path correspond to values assumed by random parameters in the model.

We illustrate the construction of a scenario tree with a stochastic version of the well-known Newsvendor inventory problem.  In this problem, we must decide how much to order initially and then later, how much of any unsold product to return before the end of the planning horizon.  There is a shortage penalty when there are lost sales and a carrying cost for left over units.  The decision process takes place under uncertain demand and uncertain price per returned item:

1.In stage 0, the order quantity has to be decided (under uncertain demand).
2.In stage 1, at the beginning, the demand is revealed.  A recourse decision, at the end of stage 1, is the number of units to be returned to the publisher (for an uncertain refund price)
3.In stage 2 at the beginning, the refund price is announced by the publisher. The price per returned item can be either
•Positive (i.e. publisher accepts them at a high price which covers the cost of shipping and handling)  or
•Negative (i.e. publisher accepts them at a low price which doesn’t cover the cost of shipping and handling).  
4.The objective is to maximize the total expected profit at the end of planning horizon (stage 2).

 

 

In the scenario tree above, x0 represents the initial decision, or order size to be determined before seeing any of the random outcomes. x1 represents the quantity to return to the publisher of any portion of the unsold units. Profit2 represents the total profit collected at the end of planning horizon. The notation Ω1 represents the event space for the unknown demand, for which there are three different possible outcomes Ω1 = {Low, Medium, and High} with probabilities {0.4, 0.3, 0.3}, respectively.  Once we observe the demand ω1 ∈ Ω1, we make a recourse decision x1 based upon which ω1 nature chose and our previous decision x0.  The notation Ω2 represents the event space for refund price per unsold newspapers if returned to the publisher in stage 2.  This event has two different outcomes Ω2 = {Positive, Negative} with probabilities {0.7, 0.3}.  Once the refund price ω2 ∈ Ω2 in stage 2 is observed, the total profit would be computed by the model as the final decision Profit2.

It should be clear from the scenario tree that,

•There are as many distinct scenarios in the SP as there are leaf-nodes.
•Each root-leaf path defines a scenario, induced by a full observation of all random events.
•There is a one-to-one correspondence between the scenarios and the leaf-nodes in the tree.
•The unconditional probability of a node is computed by multiplying the conditional probabilities of the nodes positioned on the path, which starts from the root and terminates at that node.
•The unconditional probability of each leaf-node corresponds to the probability of the associated scenario.
•Each node in the tree corresponds to a vector of random parameter with a particular history up to that node in some scenario.
•The branches out of each node enumerate all possible outcomes associated with random parameters associated with it in order to construct the history of random parameters that belong to the next stage.