Multistage stochastic integer programs: An introduction

Werner Römisch, Rüdiger Schultz

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC 2000

90C15 Stochastic programming

We consider linear multistage stochastic integer programs and study their functional and dynamic programming formulations as well as conditions for optimality and stability of solutions. Furthermore, we study the application of the Rockafellar-Wets dualization approach as well as the structure and algorithmic potential of corresponding dual problems. For discrete underlying probability distributions we discuss possible large scale mixed-integer linear programming formulations and three dual decomposition approaches, namely, scenario, component and nodal decomposition.

Keywords: stochastic programming, multistage, mixed-integer, dynamic programming, dualization, decomposition