Improving the performance of the stochastic dual dynamic programming algorithm using Chebyshev centers
- PDF / 2,096,138 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 206 Views
Improving the performance of the stochastic dual dynamic programming algorithm using Chebyshev centers Felipe Beltrán1 · Erlon C. Finardi1,2 · Guilherme M. Fredo1 · Welington de Oliveira3 Received: 4 February 2020 / Revised: 26 August 2020 / Accepted: 29 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In hydro predominant systems, the long-term hydrothermal scheduling problem (LTHS) is formulated as a multistage stochastic programming model. A classical optimization technique to obtain an operational policy is the stochastic dual dynamic programming (SDDP), which employs a forward step, for generating trial state variables, and a backward step to construct Benders-like cuts. To assess the quality of the obtained policy (the cuts obtained over the iterations), a confidence interval is computed on the optimality gap. As the SDDP is a cutting-plane based method, it exhibits slow convergence in large-scale problems. To improve computational efficiency, we explore different regions in which the cuts are usually constructed by the classical algorithm. For that, the cuts in the forward step are translated using ideas related to the definition of Chebyshev centers of certain polyhedrons. Essentially, the cuts are lifted by a parameter that vanishes along with iterations without harming the convergence analysis. The proposed technique is assessed on an instance of the Brazilian LTHS problem with individualized monthly decisions per plant, indicating a higher policy quality in comparison with the classical approach, since it computes lower optimality gaps throughout the iterative process. Keywords Hydrothermal scheduling problem · Multi-stage stochastic programming · Stochastic dynamic dual programming · Chebyshev centers
* Felipe Beltrán [email protected] 1
Federal University of Santa Catarina/LabPlan, Florianópolis, Brazil
2
INESC P&D, Santos, Brazil
3
CMA‑Centre de Mathématiques Appliquées, MINES ParisTech, PSL-Research University, Sophia Antipolis, France
13
Vol.:(0123456789)
F. Beltrán et al.
1 Introduction The Long-Term Hydrothermal Scheduling (LTHS) problem aims at obtaining a generation policy that minimizes a cost function (with some risk-measure) associated with the thermal generation and deficit over a multi-year planning horizon. Since inflow is uncertain, determining an economical generation scheduling in hydro predominant systems is a difficult task (Philpott and de Matos 2012; Carpentier et al. 2015; Gjerden et al. 2015; Hernandez et al. 1991; Tilmant and Kelman 2007; Maceira et al. 2018). The LTHS problem is modeled as a multistage stochastic linear program (MSLP), as is the case with other real-life applications (Goel and Grossmann 2004; Hochreiter and Pflug 2007; Dupacová 2009). In this problem, the uncertainty is handled by a scenario tree with finite realizations of inflows per stage. However, even with a finite number of realizations, the size of the tree grows exponentially according to the number of stages. In this context, the
Data Loading...
