Mixed Spatial and Temporal Decompositions for Large-Scale Multistage Stochastic Optimization Problems
- PDF / 466,634 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 180 Views
Mixed Spatial and Temporal Decompositions for Large-Scale Multistage Stochastic Optimization Problems Pierre Carpentier1 François Pacaud2
· Jean-Philippe Chancelier2 · Michel De Lara2 ·
Received: 19 December 2019 / Accepted: 28 July 2020 / Published online: 10 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider multistage stochastic optimization problems involving multiple units. Each unit is a (small) control system. Static constraints couple units at each stage. We present a mix of spatial and temporal decompositions to tackle such large scale problems. More precisely, we obtain theoretical bounds and policies by means of two methods, depending on whether the coupling constraints are handled by prices or by resources. We study both centralized and decentralized information structures. We report the results of numerical experiments on the management of urban microgrids. It appears that decomposition methods are much faster and give better results than the standard stochastic dual dynamic programming method, both in terms of bounds and of policy performance. Keywords Discrete time stochastic optimal control · Decomposition methods · Dynamic programming Mathematics Subject Classification 93A15 · 93E20 · 49M27 · 49L20
Communicated by Francesco Zirilli.
B
Pierre Carpentier [email protected] Jean-Philippe Chancelier [email protected] Michel De Lara [email protected] François Pacaud [email protected]
1
UMA, ENSTA Paris, IP Paris, Palaiseau, France
2
CERMICS, Ecole des Ponts, Marne-la-Vallée, France
123
986
Journal of Optimization Theory and Applications (2020) 186:985–1005
1 Introduction Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties (scenarios). Another layer of complexity can come from spatial structure. The large-scale nature of such problems makes decomposition methods appealing (we refer to [1,2] for a broad description of decomposition methods in stochastic optimization problems). We sketch decomposition methods along three dimensions: temporal decomposition methods like dynamic programming break the multistage problem into a sequence of interconnected static subproblems [3,4]; scenario decomposition methods split large-scale stochastic optimization problems scenario by scenario, yielding deterministic subproblems [5–7]; spatial decomposition methods break possible spatial couplings in a global problem to obtain local decoupled subproblems [8]. These decomposition schemes have been applied in many fields, especially in energy management: Dynamic programming methods have been used for example in dam management [9], and scenario decomposition has been successfully applied to the resolution of unit-commitment problems [10], among others. Recent developments have mixed spatial decomposition methods with dynamic programming to solve large-scale multistage stochastic optimization problems. This work led to the introductio
Data Loading...
