Stability, Approximation, and Decomposition in Two- and Multistage Stochastic Programming / Stochastic Programming (PDF)

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

Dr. Christian Küchler completed his doctoral thesis at the Humboldt University, Berlin. He currently works as a quantitative analyst at Landesbank Berlin AG.