Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming

Chapter 3 Recombining Trees for Multistage Stochastic Programs (p. 32-33)

In order to solve multistage stochastic optimization problems by numerical methods, the underlying stochastic process is usually approximated by a process that takes only a ?nite number of values. Consequently, the approximating process can be represented by a scenario tree, where the nodes of the tree correspond to the possible realizations of the process and the tree structure is induced by the ?ltration generated by the process. Unfortunately, the number of nodes can grow exponentially as the number of time stages increases, and the corresponding optimization problem thus becomes quickly intractable. Hence, many problems of practical interest are represented by stochastic programming models that include only either a small number of time stages or a small number of scenarios.

Thereby, models with a small number of time stages either take only a short time horizon into account or they allow only for a very limited branching scheme of the scenario tree. Thus, such models may appear too simpli?ed to represent dynamic decision problems. In order to construct scenario trees that approximate the initial underlying stochastic process as best as possible by a small number of scenarios, certain approximation and scenario reduction techniques have been developed by P?ug (2001), Gröwe-Kuska et al. (2003), Heitsch and Römisch (2003), and Dupacová et al. (2003). Considering only few scenarios allows to solve problems with several thousands of time stages, see, e.g., the recent case study of Eichhorn et al. (2008). However, this reduction requires some compromise with regard to the representation of the underlying stochastic process.

An approach often used in practice, aiming to ?nd acceptable decisions along a concrete observation process, is to optimize with a rolling time horizon (cf., e.g., Sethi and Sorger (1991)). Thereby, a solution is constructed by solving a sequence of subproblems on small overlapping time intervals. However, decisions made by considering only a short time horizon will be myopic and thus generally not optimal whenever the optimization problem includes time-coupling constraints. The situation can be somewhat improved by ?nding suitable (shadow-) prices for those decision variables that a?ect the future costs.

A further approach to handle problems of larger dimensionality relies on recombining scenario trees. The probably best-known example is the Binomial Model of Stock Price Behaviour due to Cox, Ross, and Rubinstein (1979), where the node number of a binary scenario tree with T time stages decreases from 2T -1 to T(T +1)/2 by the recombination of scenarios. However, in a recombined node no information about the history of the parameter and the decision processes is available. Consequently, recombining scenario trees seem at ?rst sight not appropriate to solve optimization problems including time-coupling constraints.