Efficient Implementation of Sampling Stochastic Dynamic Programming Algorithm for Multireservoir Management in the Hydropower Sector
Publication: Journal of Water Resources Planning and Management
Volume 145, Issue 4
Abstract
Despite decades of operational use, stochastic dynamic programming (SDP) is still a popular method for solving hydropower management optimization problems. From an operational perspective, there are many advantages to using this type of method: it provides a feedback operating policy that can be used for simulation purposes, marginal values of water stored in reservoirs are easy to compute, and it is relatively simple and easy to understand. However, for systems with more than two or three reservoirs, some issues arise that must be resolved in order to create efficient and fast operational software. This paper presents a case study which solved a problem of four reservoirs by sampling SDP (SSDP). Several improvements were proposed, such as using parallelization techniques, efficient discretization of the state space, and piecewise linear approximation of the water value function utilizing a strategy similar to Benders cuts as in stochastic dual dynamic programming, to build fast, efficient, and robust SSDP operational software. Program implementation details and numerical results were presented for a real hydropower system owned by Rio Tinto in Canada.
Get full access to this article
View all available purchase options and get full access to this article.
References
Anaconda. 2018. “Anaconda python distribution.” Accessed January 20, 2018. https://www.anaconda.com/.
Archibald, T. W., K. I. McKinnon, and L. C. Thomas. 1997. “An aggregate stochastic dynamic programming model of multireservoir systems.” Water Resour. Res. 33 (2): 333–340. https://doi.org/10.1029/96WR02859.
Arsenault, R., T. Latraverse, and T. Duchesne. 2016. “An efficient method to correct under-dispersion in ensemble streamflow prediction of inflow volumes for reservoir optimization.” Water Resour. Manage. 30 (12): 4363–4380. https://doi.org/10.1007/s11269-016-1425-4.
Carpentier, P. L., M. Gendreau, and F. Bastin. 2015. “Managing hydroelectric reservoirs over an extended horizon using benders decomposition with a memory loss assumption.” IEEE Trans. Power Syst. 30 (2): 563–572. https://doi.org/10.1109/TPWRS.2014.2332402.
Charbonneau, R., J.-P. Fortin, and G. Morin. 1977. “The CEQUEAU model: Description and examples of its use in problems related to water resource management/Le modèle CEQUEAU: Description et exemples d’utilisation dans le cadre de problèmes reliés à l’aménagement.” Hydrol. Sci. J. 22 (1): 193–202. https://doi.org/10.1080/02626667709491704.
Côté, P., D. Haguma, R. Leconte, and S. Krau. 2011. “Stochastic optimisation of Hydro-Quebec hydropower installations: A statistical comparison between SDP and SSDP methods.” Can. J. Civ. Eng. 38 (12): 1427–1434. https://doi.org/10.1139/l11-101.
Côté, P., and R. Leconte. 2016. “Comparison of stochastic optimization algorithms for hydropower reservoir operation with ensemble streamflow prediction.” J. Water Resour. Plann. Manage. 142 (2): 4015046. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000575.
Davidsen, C., S. J. Pereira-Cardenal, S. Liu, X. Mo, D. Rosbjerg, and P. Bauer-Gottwein. 2015. “Using stochastic dynamic programming to support water resources management in the Ziya River Basin, China.” J. Water Resour. Plann. Manage. 141 (7): 04014086. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000482.
Desreumaux, Q., P. Côté, and R. Leconte. 2014. “Role of hydrologic information in stochastic dynamic programming: A case study of the Kemano hydropower system in British Columbia.” Can. J. Civ. Eng. 41 (9): 839–844. https://doi.org/10.1139/cjce-2013-0370.
Desreumaux, Q., P. Côté, and R. Leconte. 2018. “Comparing model-based and model-free streamflow simulation approaches to improve hydropower reservoir operations.” J. Water Resour. Plann. Manage. 144 (3): 5018002. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000860.
Etkin, D., P. Kirshen, and D. Watkins. 2013. “Stochastic programming for improved multiuse reservoir operation in Burkina Faso, West Africa.” Water Resour. Plann. Manage. 141 (3): 1–12. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000396.
Faber, B. A. 2000. “Reservoir optimization using sampling stochastic dynamic programming (SSDP) with ensemble streamflow prediction (ESP).” Ph.D. thesis, Dept. of Civil Engineering, Cornell Univ.
Faber, B. A., and J. R. Stedinger. 2001. “Reservoir optimization using sampling SDP with ensemble streamflow prediction (ESP) forecasts.” J. Hydrol. 249 (1–4): 113–133. https://doi.org/10.1016/S0022-1694(01)00419-X.
Giuliani, M., A. Castelletti, F. Pianosi, E. Mason, and M. Reed Patrick. 2016. “Curses, tradeoffs, and scalable management: Advancing evolutionary multiobjective direct policy search to improve water reservoir operations.” J. Water Resour. Plann. Manage. 142 (2): 4015050. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000570.
Goor, Q., R. Kelman, and A. Tilmant. 2011. “Optimal multipurpose-multireservoir operation model with variable productivity of hydropower plants.” J. Water Resour. Plann. Manage. 137 (3): 258–267. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000117.
Hjelmeland, M. N., J. Zou, A. Helseth, and S. Ahmed. 2019. “Nonconvex medium-term hydropower scheduling by stochastic dual dynamic integer programming.” IEEE Trans. Sustainable Energy 10 (1): 481–490. https://doi.org/10.1109/TSTE.2018.2805164.
Kelman, J., J. R. Stedinger, L. A. Cooper, E. Hsu, and S.-Q. Yuan. 1990. “Sampling stochastic dynamic programming applied to reservoir operation.” Water Resour. Res. 26 (3): 447–454. https://doi.org/10.1029/WR026i003p00447.
Kim, Y.-O., H.-I. Eum, E.-G. Lee, and I. H. Ko. 2007. “Optimizing operational policies of a Korean multireservoir system using sampling stochastic dynamic programming with ensemble streamflow prediction.” J. Water Resour. Plann. Manage. 133 (1): 4–14. https://doi.org/10.1061/(ASCE)0733-9496(2007)133:1(4).
Kuo, H., and J. Huang. 2005. “Building a concept hierarchy from a distance matrix.” Vol. 31 of Intelligent information processing and web mining: Advances in soft computing, edited by M. A. Kłopotek, S. T. Wierzchoń, and K. Trojanowski. Berlin: Springer.
Magnani, A., and S. P. Boyd. 2009. “Convex piecewise-linear fitting.” Optim. Eng. 10 (1): 1–17. https://doi.org/10.1007/s11081-008-9045-3.
Neboh, N., J. Adeyemo, A. Enitan, and O. Olugbara. 2015. “A review on applications of evolutionary algorithms to reservoir operation for hydropower production.” Int. J. Environ. Chem. Ecol. Geol. Geophys. Eng. 9 (9): 1115–1121. https://doi.org/10.5281/zenodo.1109762.
Omer, J., M. Towhidi, and F. Soumis. 2015. “The positive edge pricing rule for the dual simplex.” Comput. Oper. Res. 61: 135–142. https://doi.org/10.1016/j.cor.2015.03.009.
Pedregosa, F., et al. 2011. “Scikit-learn: Machine learning in Python.” J. Mach. Learn. Res. 12: 2825–2830.
Pereira, M. V. F., and L. Pinto. 1991. “Multi-stage stochastic optimization applied to energy planning.” Math. Program. 52 (1–3): 359–375. https://doi.org/10.1007/BF01582895.
Philpott, A., A. Dallagi, and E. Gallet. 2013. “On cutting plane algorithms and dynamic programming for hydroelectricity generation BT.” In Handbook of risk management in energy production and trading, edited by R. M. Kovacevic, G. C. Pflug, and M. T. Vespucci, 105–127. Boston: Springer.
Pina, J., A. Tilmant, and P. Côté. 2017. “Optimizing multireservoir system operating policies using exogenous hydrologic variables.” Water Resour. Res. 53 (11): 9845–9859. https://doi.org/10.1002/2017WR021701.
Raman, H., and V. Chandramouli. 1996. “Deriving a general operating policy for reservoirs using neural network.” J. Water Resour. Plann. Manage. 122 (5): 342–347. https://doi.org/10.1061/(ASCE)0733-9496(1996)122:5(342).
Rego, E. E., C. de Oliveira Ribeiro, O. L. do Valle Costa, and L. L. Ho. 2017. “Thermoelectric dispatch: From utopian planning to reality.” Energy Policy 106: 266–277. https://doi.org/10.1016/j.enpol.2017.03.065.
Tilmant, A., and R. Kelman. 2007. “A stochastic approach to analyze trade-offs and risks associated with large-scale water resources systems.” Water Resour. Res. 43 (6): 1–11. https://doi.org/10.1029/2006WR005094.
Toriello, A., and J. Pablo. 2012. “Fitting piecewise linear continuous functions.” Eur. J. Oper. Res. 219 (1): 86–95. https://doi.org/10.1016/j.ejor.2011.12.030.
Xu, W., C. Zhang, Y. Peng, G. Fu, and H. Zhou. 2014. “A two stage Bayesian stochastic optimization model for cascaded hydropower systems considering varying uncertainty of flow forecasts.” Water Resour. Res. 50 (12): 9267–9286. https://doi.org/10.1002/2013WR015181.
Ziming, G., S. Ziad, and A. Alaa. 2018. “Using SDDP to develop water-value functions for a multireservoir system with international treaties.” J. Water Resour. Plann. Manage. 144 (2): 5017021. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000858.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 145 • Issue 4 • April 2019
Copyright
©2019 American Society of Civil Engineers.
History
Received: May 16, 2018
Accepted: Sep 26, 2018
Published online: Jan 26, 2019
Published in print: Apr 1, 2019
Discussion open until: Jun 26, 2019
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.