Optimization of a large-scale water reservoir network by stochastic dynamic programming with efficient state space discretization. (English) Zbl 1116.90123

Summary: A numerical solution to a 30-dimensional water reservoir network optimization problem, based on stochastic dynamic programming, is presented. In such problems the amount of water to be released from each reservoir is chosen to minimize a nonlinear cost (or maximize benefit) function while satisfying proper constraints. Experimental results show how dimensionality issues, given by the large number of basins and realistic modeling of the stochastic inflows, can be mitigated by employing neural approximators for the value functions, and efficient discretizations of the state space, such as orthogonal arrays, Latin hypercube designs and low-discrepancy sequences.


90C90 Applications of mathematical programming
90C39 Dynamic programming
90C06 Large-scale problems in mathematical programming
90C15 Stochastic programming
Full Text: DOI


[1] Archibald, T. W.; McKinnon, K. I.M.; Thomas, L. C., An aggregate stochastic dynamic programming model of multireservoir systems, Water Resources Research, 33, 333-340 (1997)
[2] Barron, A. R., Approximation and estimation bounds for artificial neural networks, Machine Learning, 14, 115-133 (1994) · Zbl 0818.68127
[3] Bellman, R., Dynamic Programming (1957), Princeton University Press: Princeton University Press Princeton · Zbl 0077.13605
[4] Bertsekas, D., Dynamic Programming and Optimal Control, vol. 1 (2000), Athena Scientific: Athena Scientific Belmont
[5] Bertsekas, D. P.; Tsitsiklis, J. N., Neuro-dynamic Programming (1996), Athena Scientific: Athena Scientific Belmont · Zbl 0924.68163
[6] Cervellera, C.; Muselli, M., Deterministic design for neural network learning: an approach based on discrepancy, IEEE Transactions on Neural Networks, 15, 533-544 (2004)
[7] Chen, V. C.P., Application of MARS and orthogonal arrays to inventory forecasting stochastic dynamic programs, Computational statistics and data analysis, 30, 317-341 (1999) · Zbl 1042.62606
[8] Chen, V. C.P., Measuring the goodness of orthogonal array discretizations for stochastic programming and stochastic dynamic programming, SIAM Journal of Optimization, 12, 322-344 (2001) · Zbl 1017.90067
[9] Chen, V. C.P.; Ruppert, D.; Shoemaker, C. A., Applying experimental design and regression splines to high-dimensional continuous-state stochastic dynamic programming, Operations Research, 47, 38-53 (1999) · Zbl 0979.90094
[10] Chen, V. C.P.; Tsui, K.-L.; Barton, R. R.; Allen, J. K., A review of design and modeling in computer experiments, (Rao, C. R.; Khattree, R., Handbook in Industrial Statistics, vol. 22 (2003), Elsevier Science: Elsevier Science Amsterdam), 231-261
[11] Fang, K.-T.; Wang, Y., Number-theoretic Methods in Statistics (1994), Chapman and Hall: Chapman and Hall London
[12] Foufoula-Georgiou, E.; Kitanidis, P. K., Gradient dynamic programming for stochastic optimal control of multidimensional water resources systems, Water Resources Research, 24, 1345-1359 (1988)
[13] Gal, S., Optimal management of a multireservoir water supply system, Water Resources Research, 15, 737-749 (1979)
[14] Georgakakos, A. P., Extended linear quadratic Gaussian control for the real time operation of reservoir systems, (Esogbue, A. O., Dynamic Programming for Optimal Water Resources Systems Analysis (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 329-360
[15] Hagan, M. T.; Menhaj, M., Training feedforward networks with the marquardt algorithm, IEEE Transactions on Neural Networks, 5, 989-993 (1994)
[16] Haykin, S., Neural Networks: A Comprehensive Foundation (1999), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0934.68076
[17] Hoeffding, W., Probability inequalities for sum of bounded random variables, Journal of the American Statistical Association, 58, 13-30 (1963) · Zbl 0127.10602
[18] Hua, L. K.; Wang, Y., Applications of Number Theory to Numerical Analysis (1981), Springer-Verlag: Springer-Verlag Berlin · Zbl 0465.10045
[19] Jacobson, D.; Mayne, D., Differential Dynamic Programming (1970), Academic: Academic New York
[20] Johnson, S. A.; Stedinger, J. R.; Shoemaker, C.; Li, Y.; Tejada-Guibert, J. A., Numerical solution of continuous-state dynamic programs using linear and spline interpolation, Operations Research, 41, 484-500 (1993) · Zbl 0777.90074
[21] Lamond, B. F.; Sobel, M. J., Exact and approximate solutions of affine reservoirs models, Operations Research, 43, 771-780 (1995) · Zbl 0842.90032
[22] Morokoff, W. J.; Caflisch, R. E., A Monte Carlo technique with quasirandom points for the stochastic shortest path problem, American Journal of Mathematics and Management Sciences, 7, 325-358 (1987)
[23] Morokoff, W. J.; Caflisch, R. E., A quasi-Monte Carlo approach to particle simulation of the heat equation, SIAM Journal of Numerical Analysis, 30, 1558-1573 (1993) · Zbl 0796.65141
[24] Niederreiter, H., Random Number Generation and Quasi-Monte Carlo Methods (1992), SIAM: SIAM Philadelphia · Zbl 0761.65002
[25] Niederreiter, H.; Xing, C. P., Low-discrepancy sequences obtained from algebraic function fields over finite fields, Acta Arithmetica, 72, 281-298 (1995) · Zbl 0833.11035
[26] Niederreiter, H.; Xing, C. P., Low-discrepancy sequences and global function fields with many rational places, Finite Fields and Their Application, 2, 241-273 (1996) · Zbl 0893.11029
[27] Philbrick, C. R.; Kitanidis, P. K., Improved dynamic programming methods for optimal control of lumped-parameter stochastic systems, Operations Research, 49, 398-412 (2001) · Zbl 1163.90783
[28] Puterman, M., Markov Decision Processes (1994), Wiley: Wiley New York
[29] Rust, J., Using randomization to break the curse of dimensionality, Econometrica, 65, 487-516 (1997) · Zbl 0872.90107
[30] Salas, J. D.; Tabios, G. Q.; Bartolini, P., Approaches to multivariate modeling of water resources time series, Water Resources Bullettin, 21, 683-708 (1985)
[31] Sharma, V.; Jha, R.; Naresh, R., Optimal multi-reservoir network control by two-phase neural network, Electric Power Systems Research, 68, 221-228 (2004)
[32] Sobol’, I. M., The distribution of points in a cube and the approximate evaluation of integrals, USSR Computational Mathematics and Mathematical Physics, 7, 784-802 (1967)
[33] Tang, B., Orthogonal array-based latin hypercubes, Journal of the American Statistical Association, 88, 1392-1397 (1993) · Zbl 0792.62066
[34] Turgeon, A., A decomposition method for the long-term scheduling of reservoirs in series, Water Resources Research, 17, 1565-1570 (1981)
[35] Weyl, H., Über die gleichverteilung von zahlen mod, Eins Mathematische Annalen, 77, 313-352 (1916) · JFM 46.0278.06
[36] Weyl, H., Selecta Hermann Weyl (1956), Birkhäuser: Birkhäuser Basel, Switzerland
[37] Yakowitz, S., Dynamic programming applications in water resources, Water Resources Research, 18, 673-696 (1982)
[38] M. Baglietto, C. Cervellera, T. Parisini, M. Sanguineti, R. Zoppoli, Approximating networks for the solution of T-stage stochastic optimal control problems, in: S. Bittanti (Ed.), Proceedings of the IFAC Workshop on Adaptation and Learning in Control and Signal Processing, Cernobbio-Como, Italy, 29-31 August 2001, Elsevier, Oxford.; M. Baglietto, C. Cervellera, T. Parisini, M. Sanguineti, R. Zoppoli, Approximating networks for the solution of T-stage stochastic optimal control problems, in: S. Bittanti (Ed.), Proceedings of the IFAC Workshop on Adaptation and Learning in Control and Signal Processing, Cernobbio-Como, Italy, 29-31 August 2001, Elsevier, Oxford.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.