Abstract
This paper proposes a multi-stage stochastic programming formulation based on affine decision rules for the reservoir management problem. Our approach seeks to find a release schedule that balances flood control and power generation objectives while considering realistic operating conditions as well as variable water head. To deal with the non-convexity introduced by the variable water head, we implement a simple, yet effective, successive linear programming algorithm. We also introduce a novel non-linear inflow representation that captures serial correlation of arbitrary order. We test our method on a small real river system and discuss policy implications. Our results namely show that our method can decrease flood risk and increase production compared to the historical decisions, albeit at the cost of reduced final storages.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Although the intersections of the two sets is not a polyhedron, it is can be represented by a polyhedron using the decomposition \(\varrho _t= \varrho _t^+ - \varrho _t^-\) and \(|\varrho _t| = \varrho _t^+ + \varrho _t^-\) with \(\varrho _t^+, \varrho _t^- \geqslant 0, \, \forall t\).
References
Bana e Costa CA, Vansnick JC (1997) A theoretical framework for measuring attractiveness by a categorical based evaluation technique (MACBETH). Springer, New York
Ben-Tal A, Goryashko E, Guslitzer A, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math Program 99:351–378
Bezerra B, Veiga Á, Barroso LA, Pereira M (2017) Stochastic long-term hydrothermal scheduling with parameter uncertainty in autoregressive streamflow models. IEEE Trans Power Syst 32(2):999–1006
Billingsley P (1995) Probability and measure, 3rd edn. Wiley, New York
Borghetti A, D’Ambrosio C, Lodi A, Martello S (2008) An milp approach for short-term hydro scheduling and unit commitment with head-dependent reservoir. IEEE Trans Power Syst 23(3):1115–1124
Box GEP, Cox DR (1964) An analysis of transformations. J Roy Stat Soc 2:211–252
Box GEP, Jenkins GM, Reinsel GC (2008) Time series analysis: forecasting and control, 4th edn. Wiley, Hoboken
Braaten SV, Gjonnes O, Hjertvik K, Fleten SE (2016) Linear decision rules for seasonal hydropower planning: modelling considerations. Energy Procedia 87:28–35. 5th International Workshop on Hydro Scheduling in Competitive Electricity Markets
Brockwell PJ, Davis RA (1987) Time series: theory and methods. Springer, New York
Carpentier PL, Gendreau M, Bastin F (2013) Long-term management of a hydroelectric multireservoir system under uncertainty using the progressive hedging algorithm. Water Resour Res 49:2812–2827
Castelletti A, Pianosi F, Soncini-Sessa R (2008) Water reservoir control under economic, social and environmental constraints. Automatica 44(6):1595–1607
Castelletti A, Galetti S, Restelli M, Soncini-Sessa R (2010) Tree-based reinforcement learning for optimal water reservoir operation. Water Resour Res 46(W09):507
Cerisola S, Latorre JM, Ramos A (2012) Stochastic dual dynamic programming applied to nonconvex hydrothermal models. Eur J Oper Res 218(3):687–697. https://doi.org/10.1016/j.ejor.2011.11.040
De Ladurantaye D, Gendreau M, Potvin JY (2007) Strategic bidding for price-taker hydroelectricity producers. IEEE Trans Power Syst 22(4):2187–2203
De Ladurantaye D, Gendreau M, Potvin JY (2009) Optimizing profits from hydroelectricity production. Comput Oper Res 36:499–529
Diniz AL, Maceira MEP (2000) A four-dimensional model of hydro generation for the shortterm hydrothermal dispatch problem considering head and spillage effects. IEEE Trans Power Syst 23(3):1298–1308
Diniz AL, Souza TM (2014) Short-term hydrothermal dispatch with river-level and routing constraints. IEEE Trans Power Syst 29(5):2427–2435
dos Santos TN, Diniz AL (2009) A new multiperiod stage definition for the multistage benders decomposition approach applied to hydrothermal scheduling. IEEE Trans Power Syst 24(3):1383–1392
Egging R, Fleten SE, Grønvik I, Hadziomerovic A, Ingvoldstad N (2017) Linear decision rules for hydropower scheduling under uncertainty. IEEE Trans Power Syst 32(1):103–113
Ehrgott M (2005) Multicriteria optimization, 2nd edn. Springer, New York
Gauvin C, Delage E, Gendreau M (2017) Decision rule approximations for the risk averse reservoir management problem. Eur J Oper Res 261:317–336
Gauvin C, Delage E, Gendreau M (2016) A stochastic program with tractable time series and affine decision rules for the reservoir management problem. Technical report. G-2016-24, Les cahiers du GERAD
Gauvin C, Delage E, Gendreau M (2017) A successive linear programming algorithm with non-linear time series for the reservoir management problem. Technical report
Gjelsvik A, Mo B, Haugstad A (2010) Long- and medium-term operations planning and stochastic modelling in hydro-dominated power systems based on stochastic dual dynamic programming. Springer Berlin Heidelberg, Berlin, pp 33–55. https://doi.org/10.1007/978-3-642-02493-1_2
Hamann A, Hug G, Rosinski S (2017) Real-time optimization of the mid-columbia hydropower system. IEEE Trans Power Syst 32(1):157–165
Klöckl B, Papaefthymiou G (2010) Multivariate time series models for studies on stochastic generators in power systems. Electr Power Syst Res 80:265–276
Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math Program Ser A 130:177–209
Labadie J (2004) Optimal operation of multireservoir systems: state-of-the-art review. J Water Resour Plan Manag 130:93–111
Li X, Guo S, Liu P, Chen G (2010) Dynamic control of flood limited water level for reservoir operation by considering inflow uncertainty. J Hydrol 391(1):124–132
Lohmann T, Hering AS, Rebennack S (2016) Spatio-temporal hydro forecasting of multireservoir inflows for hydro-thermal scheduling. Eur J Oper Res 255(1):243–258. https://doi.org/10.1016/j.ejor.2016.05.011
Lorca Á, Sun XA, Litvinov E, Zheng T (2016) Multistage adaptive robust optimization for the unit commitment problem. Oper Res 64(1):32–51. https://doi.org/10.1287/opre.2015.1456
Lorca A, Sun XA (2015) Adaptive robust optimization with dynamic uncertainty sets for multi-period economic dispatch under significant wind. IEEE Trans Power Syst 30:1702–1713
Maceira M, Damázio J (2004) The use of par(p) model in the stochastic dual dynamic programming optimization scheme used in the operation planning of the Brazilian hydropower system. In: 8th International conference on probabilistic methods applied to power systems, Iowa State University, pp 397–402
Maceira M, Duarte V, Penna D, Moraes L, Melo A (2008) Ten years of application of stochastic dual dynamic programming in official and agent studies in brazil—description of the newave program. In: 16th PSCC, Glasgow, Scotland
Needham JT, Watkins DW, Lund JR, Nanda SK (2000) Linear programming for flood control in the iowa and des moines rivers. J Water Resour Plan Manag 126(3):118–127
Nocedal J, Wright SJ (2006) Numerical optimization. Springer Series in Operations Research, 2nd edn. Springer, New York
Pan L, Housh M, Liu P, Cai X, Chen X (2015) Robust stochastic optimization for reservoir operation. Water Resour Res 51(1):409–429. https://doi.org/10.1002/2014WR015380
Phillpott A, Wahid F, Bonnans F (2016) Midas: a mixed integer dynamic approximation scheme. Technical report. http://www.optimization-online.org/DB_FILE/2016/05/5431.pdf
Pianosi F, Soncini-Sessa R (2009) Real-time management of a multipurpose water reservoir with a heteroscedastic inflow model. Water Resour Res 45(10):1–12. https://doi.org/10.1029/2008WR007335.W10430
Poorsepahy-Samian H, Espanmanesh V, Zahraie B (2016) Improved inflow modeling in stochastic dual dynamic programming. J Water Resour Plan Manag 142(12):04016065
ReVelle CS, Kirby W (1970) Linear decision rule in reservoir management and design, 2, performance optimization. Water Resour Res 6:1033–1044
Séguin S, Côté P, Audet C (2016) Self-scheduling short-term unit commitment and loading problem. IEEE Trans Power Syst 31(1):133–142
Séguin S, Côté P, Audet C (2014) Short-term unit commitment and loading problem. Tech. rep, Les cahiers du GERAD
Shapiro A (2011) Analysis of stochastic dual dynamic programming method. Eur J Oper Res 209:63–72
Shapiro A, Tekaya W, da Costa JP, Soares MP (2013) Risk neutral and risk averse stochastic dual dynamic programming method. Eur J Oper Res 224(2):375–391. https://doi.org/10.1016/j.ejor.2012.08.022
Shapiro A, Tekaya W, da Costa JP, Soares MP (2012) Final report for technical cooperation between georgia institute of technology and ons - operador nacional do sistema eletrico. Tech. rep., Georgia Institute of Technology and Operador Nacional do Sistema Eletrico
Stedinger JR, Faber BA (2001) Reservoir optimization using sampling sdp with ensemble streamflow prediction (esp) forecast. J Hydrol 249:113–133
Steeger G, Rebennack S (2017) Dynamic convexification within nested benders decomposition using lagrangian relaxation: an application to the strategic bidding problem. Eur J Oper Res 257(2):669–686
Thome F, Pereira M, Granville S, Fampa M (2013) Non-convexities representation on hydrothermal operation planning using sddp (unpublished technical report)
Tilmant A, Kelman R (2007) A stochastic approach to analyze trade-offs and risk associated with large-scale water resources systems. Water Resour Res 43(W06):425
Tsay RS (2005) Analysis of financial time series, 2nd edn. Wiley, Hoboken
Turgeon A (2005) Solving a stochastic reservoir management problem with multilag autocorrelated inflows. Water Resour Res 41(W12):414
Turgeon A, Charbonneau R (1998) An aggregation-disaggregation approach to long-term reservoir management. Water Resour Res 34:3585–3594
Wei CC, Hsu NS (2009) Optimal tree-based release rules for real-time flood control operations on a multipurpose multireservoir system. J Hydrol 365(3):213–224
Acknowledgements
The authors would like to thank Grégory Émiel, Louis Delorme, Pierre-Marc Rondeau, Sara Séguin, Jasson Pina and Pierre-Luc Carpentier. This research was supported by NSERC/Hydro-Québec through the Industrial Research Chair on the Stochastic Optimization of Electricity Generation and Grant 386416-2010.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix
1.1 Counterexample showing that \(\varXi _t\) is generally non-convex
We show that in general, \(\varXi _t\) is not convex for an arbitrary \(t \in {\mathbb {T}}\). Consider the following instance:
Figure 10 displays \(\varXi _t=\{ \xi \in {\mathbb {R}}^L : \exists \varrho \in P, \xi _l = \exp ( V_l^{\top } \varrho ), \forall l=1,\ldots ,L\}\) and illustrates that \(\varXi _t\) is in general not convex.
Non convex uncertainty set
For a slightly more formal demonstration, it is possible to show that given the two points \({\hat{\varrho }}_1=(1-\sqrt{2},1)^{\top } \in P\) and \({\hat{\varrho }}_2=(\sqrt{2}-1,1)^{\top }\in P\) illustrated in Fig. 10 as well as \(\lambda =\frac{1}{2}\), there exists no \( \varrho \in P \) such that:
Equivalently, we can show that \(\forall \varrho \in P\),
This can be shown by solving the following linear program and observing that its optimal value is strictly larger than 0:
where \(l_{i}^{\lambda } = ln(\lambda e^{V_i^{\top }{\hat{\varrho }}_1 } + (1-\lambda ) e^{V_i^{\top }{\hat{\varrho }}_2} )\) is a known constant.
First order Taylor approximation of the composite risk
We first fix \({\text {E} \left[ {\mathcal {P}}_{i,t+l}(\xi ) {\mathcal {H}}_{i,t+l}(\xi ) |\mathcal {G}_{t-1} \right] } \equiv F_{i,t+l}({\mathcal {H}}_{i,t+l},{\mathcal {P}}_{i,t+l}) \) where \({\mathcal {H}}_{i,t+l}=({\mathcal {H}}^0_{i,t+l},{\mathcal {H}}^{t+1}_{i,t+l},\ldots ,{\mathcal {H}}^{t+L-1}_{i,t+l})^{\top } \in {\mathbb {R}}^L\) and \({\mathcal {P}}_{i,t+l}=({\mathcal {P}}^0_{i,t+l},{\mathcal {P}}^{t+1}_{i,t+l},\ldots ,{\mathcal {P}}^{t+L-1}_{i,t+l})^{\top }\in {\mathbb {R}}^L\). Given the point \((\hat{{\mathcal {H}}}_{i,t+l}^{\top } ,\hat{{\mathcal {P}}}_{i,t+l}^{\top } )^{\top } \in {\mathbb {R}}^{2L }\), we then obtain:
Rights and permissions
About this article
Cite this article
Gauvin, C., Delage, E. & Gendreau, M. A successive linear programming algorithm with non-linear time series for the reservoir management problem. Comput Manag Sci 15, 55–86 (2018). https://doi.org/10.1007/s10287-017-0295-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10287-017-0295-4