An Overview of Decomposition-Coordination Methods in Multistage Stochastic Optimization

Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties (scenarios). Quite often, solutions are also indexed by decision units, like nodes in a graph (space), or agents in a team. Hence, their large scale nature makes decomposition methods appealing. We present, in an unified framework, three main approaches and methods to decompose multistage stochastic optimization problems for numerical resolution: time decomposition (and state-based resolution methods, like Stochastic Dynamic Programming, in Stochastic Optimal Control); scenario decomposition (like Progressive Hedging in Stochastic Programming); spatial decomposition (price or resource decompositions). We show how writing a dynamic programming equation on the increasing sets of histories paves the way for state reduction at specified stages; this makes it possible to develop what we call time block decomposition. We also show how price or resource decompositions quite naturally provide decomposed lower and upper bounds for minimization problems. Finally, we point to some mathematical questions raised by the mixing (blending) of different decompositions methods to tackle large scale problems. We hint at the potential of blending for the management of new energy systems (smart grids), as they will be developed in the next two talks.Non UBCUnreviewedAuthor affiliation: Ecole des Ponts ParisTechFacult