Open Collections

An Overview of Decomposition-Coordination Methods in Multistage Stochastic Optimization

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Probability theory and stochastic processes; Operations research, mathematical programming; Control/Optimization/Operation Research

video/mp4

Author affiliation: Ecole des Ponts ParisTech

2020-03-23

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73781

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/