Batch Learning SDDP for Long-Term Hydrothermal Planning

Dynamic programming; hydroelectric-thermal power generation; parallel algorithms; SDDP; stochastic optimal control; Batch learning; Convergence; Dynamic programming algorithm; Heuristics algorithm; Hydroelectric-thermal power generation; Parallel processing; Programming; Reinforcement learnings; Stochastic dual dynamic programming; Stochastic optimal control; Energy Engineering and Power Technology; Electrical and Electronic Engineering

Abstract :

[en] We consider the stochastic dual dynamic programming (SDDP) algorithm - a widely employed algorithm applied to multistage stochastic programming - and propose a variant using experience replay - a batch learning technique from reinforcement learning. To connect SDDP with reinforcement learning, we cast SDDP as a Q-learning algorithm and describe its application in both risk-neutral and risk-averse settings. We demonstrate the superiority of the algorithm over conventional SDDP by benchmarking it against PSR's SDDP software using a large-scale instance of the long-term planning problem of inter-connected hydropower plants in Colombia. We find that SDDP with batch learning is able to produce tighter optimality gaps in a shorter amount of time than conventional SDDP. We also find that batch learning improves the parallel efficiency of SDDP backward passes.

Disciplines :

Electrical & electronics engineering

Author, co-author :

Avila, Daniel ; Université Catholique de Louvain, Core, Louvain-la-Neuve, Belgium

Papavasiliou, Anthony ; National Technical University of Athens, Electrical and Computer Engineering, Zografou, Greece

LÖHNDORF, Nils ; University of Luxembourg

External co-authors :

yes

Language :

English

Title :

Batch Learning SDDP for Long-Term Hydrothermal Planning

Publication date :

2024

Journal title :

IEEE Transactions on Power Systems

ISSN :

0885-8950

Publisher :

Institute of Electrical and Electronics Engineers Inc.

Volume :

Issue :

Pages :

614 - 627

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

http://xplorestaging.ieee.org/ielx7/59/10375287/10049084.pdf?arnumber=10049084

Funders :

European Research Council
European Union Horizon 2020 Research and Innovation Program

Available on ORBilu :

since 13 December 2024

Statistics

Number of views

60 (1 by Unilu)

Number of downloads

29 (1 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

WoS citations^™

Bibliography

M. V. Pereira and L. M. Pinto, “Multi-stage stochastic optimization applied to energy planning,” Math. Program., vol. 52, no. 1–3, pp. 359–375, 1991.
B. Flach, L. Barroso, and M. Pereira, “Long-term optimal allocation of hydro generation for a price-maker company in a competitive market: Latest developments and a stochastic dual dynamic programming approach,” IET Gener., Transmiss., Distrib., vol. 4, no. 2, pp. 299–314, 2010.
V. L. de Matos, A. B. Philpott, E. C. Finardi, and Z. Guan, “Solving long-term hydro-thermal scheduling problems,” in Proc. Power Syst. Comput. Conf., Stockholm, Sweden, 2007.
R. J. Pinto, C. T. Borges, and M. E. P. Maceira, “An efficient parallel algorithm for large scale hydrothermal system operation planning,” IEEE Trans. Power Syst., vol. 28, no. 4, pp. 4888–4896, Nov. 2013.
N. Löhndorf, D. Wozabal, and S. Minner, “Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming,” Oper. Res., vol. 61, no. 4, pp. 810–823, 2013.
B. G. Gorenstin, N. M. Campodonico, J. P. da Costa, and M. V. F. Pereira, “Stochastic optimization of a hydro-thermal system including network constraints,” IEEE Trans. Power Syst., vol. 7, no. 2, pp. 791–797, May 1992.
T. A. Rotting and A. Gjelsvik, “Stochastic dual dynamic programming for seasonal scheduling in the norwegian power system,” IEEE Trans. Power Syst., vol. 7, no. 1, pp. 273–279, Feb. 1992.
B. Mo, A. Gjelsvik, and A. Grundt, “Integrated risk management of hydro power scheduling and contract management,” IEEE Trans. Power Syst., vol. 16, no. 2, pp. 216–221, May 2001.
S. Rebennack, B. Flach, M. V. F. Pereira, and P. M. Pardalos, “Stochastic hydro-thermal scheduling under CO2 emissions constraints,” IEEE Trans. Power Syst., vol. 27, no. 1, pp. 58–68, Feb. 2012.
A. Papavasiliou, Y. Mou, L. Cambier, and D. Scieur, “Application of stochastic dual dynamic programming to the real-time dispatch of storage under renewable supply uncertainty,” IEEE Trans. Sustain. Energy, vol. 9, no. 2, pp. 547–558, Apr. 2018.
C. Gérard, D. Ávila, Y. Mou, A. Papavasiliou, and P. Chevalier, “Comparison of priority service with multilevel demand subscription,” IEEE Trans. Smart Grid, vol. 13, no. 3, pp. 2026–2037, May 2022.
A. Kiszka and D. Wozabal, “Stochastic dual dynamic programming for optimal power flow problems under uncertainty,” Technische Universität München, Munich, Germany, Tech. Rep., 2022. [Online]. Available: https://mediatum.ub.tum.de/1648358
N. Löhndorf and D. Wozabal, “Gas storage valuation in incomplete markets,” Eur. J. Oper. Res., vol. 288, no. 1, pp. 318–330, Jan. 2022.
S. Rebennack, “Generation expansion planning under uncertainty with emissions quotas,” Electric Power Syst. Res., vol. 114, pp. 78–85, 2014.
O. Dowson, A. Philpott, A. Mason, and A. Downward, “A multi-stage stochastic optimization model of a pastoral dairy farm,” Eur. J. Oper. Res., vol. 274, no. 3, pp. 1077–1089, 2019.
A. Shapiro, W. Tekaya, J. P. da Costa, and M. P. Soares, “Risk neutral and risk averse stochastic dual dynamic programming method,” Eur. J. Oper. Res., vol. 224, no. 2, pp. 375–391, 2013.
A. B. Philpott and Z. Guan, “On the convergence of stochastic dual dynamic programming and related methods,” Oper. Res. Lett., vol. 36, no. 4, pp. 450–455, 2008.
E. L. da Silva and E. C. Finardi, “Parallel processing applied to the planning of hydrothermal systems,” IEEE Trans. Parallel Distrib. Syst., vol. 14, no. 8, pp. 721–729, Aug. 2003.
A. Helseth and H. Braaten, “Efficient parallelization of the stochastic dual dynamic programming algorithm applied to hydropower scheduling,” Energies, vol. 8, no. 12, pp. 14287–14297, 2015.
F. D. Machado, A. L. Diniz, C. L. Borges, and L. C. Brandão, “Asynchronous parallel stochastic dual dynamic programming applied to hydrothermal generation planning,” Electric Power Syst. Res., vol. 191, 2021, Art. no. 106907.
I. Aravena and A. Papavasiliou, “Asynchronous Lagrangian scenario decomposition,” Math. Program. Comput., vol. 13, pp. 1–50, 2021.
D. Ávila, A. Papavasiliou, and N. Löhndorf, “Parallel and distributed computing for stochastic dual dynamic programming,” Comput. Manage. Sci., vol. 19, pp. 199–226, 2021.
V. L. De Matos, A. B. Philpott, and E. C. Finardi, “Improving the performance of stochastic dual dynamic programming,” J. Comput. Appl. Math., vol. 290, pp. 196–208, 2015.
V. Guigues, “Dual dynamic programing with cut selection: Convergence proof and numerical experiments,” Eur. J. Oper. Res., vol. 258, no. 1, pp. 47–57, 2017.
V. Guigues and M. Bandarra, “Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: Convergence proof and numerical experiments,” Comput. Manage. Sci., vol. 18, pp. 125–148, 2021.
T. Asamov and W. B. Powell, “Regularized decomposition of high-dimensional multistage stochastic programs with Markov uncertainty,” SIAM J. Optim., vol. 28, no. 1, pp. 575–595, 2018.
C. Donohue and J. Birge, “The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse,” Algorithmic Oper. Res., vol. 1, no. 1, pp. 20–30, 2006.
M. Hindsberger and A. Philpott, “ReSa: A method for solving multistage stochastic linear programs,” J. Appl. Oper. Res., vol. 6, no. 1, pp. 2–15, 2014.
PSR, “SDDP - stochastic hydrothermal dispatch with network restrictions,” 2020. [Online]. Available: https://www.psr-inc.com/softwares-en/?current=p4028
O. Dowson and L. Kapelevich, “SDDP.jl: A Julia package for stochastic dual dynamic programming,” 2017. [Online]. Available: http://www.optimization-online.org/DB_HTML/2017/12/6388.html
S. Kalyanakrishnan and P. Stone, “Batch reinforcement learning in a complex domain,” in Proc. 6th Int. Joint Conf. Auton. Agents Multiagent Syst., 2007, pp. 1–8.
L.-J. Lin, “Self-improving reactive agents based on reinforcement learning, planning and teaching,” Mach. Learn., vol. 8, no. 3/4, pp. 293–321, 1992.
S. Lange, T. Gabel, and M. Riedmiller, “Batch reinforcement learning,” in Reinforcement Learning. Berlin, Germany:Springer, 2012, pp. 45–73.
V. Mnih, K. Kavukcuoglu, and E. A. Silver, “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
W. B. Powell, Approximate Dynamic Programming: Solving the Curses of Dimensionality, vol. 703. Hoboken, NJ, USA:Wiley, 2007.
R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction. Cambridge, MA, USA:MIT Press, 2018.
M.L.Puterman,MarkovDecisionProcesses:DiscreteStochasticDynamic Programming. Hoboken, NJ, USA:Wiley, 2014.
M. Pieters and M. A. Wiering, “Q-learning with experience replay in a dynamic environment,” in Proc. IEEE Symp. Ser. Comput. Intell., 2016, pp. 1–8.
N. Löhndorf and A. Shapiro, “Modeling time-dependent randomness in stochastic dual dynamic programming,” Eur. J. Oper. Res., vol. 273, no. 2, pp. 650–661, 2019.
N. V. Arvanitidits and J. Rosing, “Composite representation of a multireservoir hydroelectric power system,” IEEE Trans. Power App. Syst., vol. PAS-89, no. 2, pp. 319–326, Feb. 1970.
J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, “Julia: A fresh approach to numerical computing,” SIAM Rev., vol. 59, no. 1, pp. 65–98, 2017, doi: 10.1137/141000671.
I. Dunning, J. Huchette, and M. Lubin, “JuMP: A modeling language for mathematical optimization,” SIAM Rev., vol. 59, no. 2, pp. 295–320, 2017.
“European resource adequacy assessment 2021,” 2021. Accessed: Jan. 18, 2023. [Online]. Available: https://www.entsoe.eu/outlooks/eraa/2021
“European resource adequacy assessment. 2021 edition. annex 1 assumptions,” 2021. Accessed: Jan. 18, 2023. [Online]. Available: https://eepublicdownloads.azureedge.net/clean-documents/sdcdocuments/ERAA/ERAA_Annex_1_Assumptions.pdf
D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, vol. 23. Englewood Cliffs, NJ, USA: Prentice-Hall, 1989.