Scenario Reduction Techniques in Stochastic Programming
(invited lecture for SAGA 2009)

Author: Werner Römisch

Affiliation: Institut für Mathematik
Humboldt University, Berlin, Germany

Abstract. Two- and multi-stage stochastic programming problems appear as mathematical models for optimization problems under stochastic uncertainty. Most computational approaches for solving such models are based on approximating the underlying probability distribution by a probability measure with finite support. Since the computational complexity for solving stochastic programs gets worse with increasing the number of atoms (or scenarios), it is sometimes necessary to reduce their number. Another motivation for scenario reduction goes back to the need of generating scenario trees to model decision processes based on recursive observation and decision. Scenario reduction techniques often require fast heuristics for solving combinatorial subproblems. Available techniques are reviewed and open problems are discussed.