Multistage Stochastic Integer Programs

Abstract

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.