Research and Application of Multidimensional Dynamic Programming in Cascade Reservoirs Based on Multilayer Nested Structure
Publication: Journal of Water Resources Planning and Management
Volume 141, Issue 7
Abstract
The multidimensional dynamic programming (MDP) algorithm is a traditional method used to solve cascade reservoir operation optimization (CROO) problems, but the high dimensionality called the curse of dimensionalitycannot be ignored. In order to alleviate this problem, this paper proposes a new MDP algorithm named multilayer nested multidimensional dynamic programming (MNDP), which is based on a multilayered, nested structure. MNDP is mainly used to deal with computer memory space and computation complexity problems of MDP in CROO, and its recursive equation of reverse recursion calculation and specific calculation steps are presented in detail. This paper takes the cascade reservoirs of the Li Xianjiang River in China as an example to solve the CROO problem with the proposed MNDP. By comparing with the dynamic programming with successive approximations (DPSA) method, MNDP presents better performance in terms of power generation and the assurance rate in wet, normal, dry, and average years. The global optimality of MNDP is validated by MDP, and the parallel computing results of MNDP are shown in a case study. The MNDP proposed in this paper can reduce not only the programming complexity of MDP, but also the storage of intermediate variables during calculation, thus effectively solving the curse of dimensionality of MDP in CROO and keeping the global convergence feature of MDP.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This study was financially supported by the Natural Science Foundation of China (51279062) and the Central University Basic Scientific Research Business Special Fund Project of North China Electric Power University (13XS23, 13QN22, 13XS22, 2014ZD12). The authors are grateful to anonymous reviewers for their comments and valuable suggestions.
References
Baskar, S., Subbaraj, P., and Rao, M. V. C. (2003). “Hybrid real coded genetic algorithm solution to economic dispatch problem.” Comput. Electr. Eng., 29, 407–419.
Basu, M. (2004). “An interactive fuzzy satisfying method based on evolutionary programming technique for multiobjective, short-term hydrothermal scheduling.” Electr. Power Syst. Res., 69(2–3), 277–285.
Basu, M. (2005). “A simulated annealing-based goal-attainment method for economic emission load dispatch of fixed head hydrothermal power systems.” Int. J. Electr. Power Energy Syst., 27(2), 147–153.
Bellman, R. (1957). Dynamic programming, Princeton University Press, Princeton, NJ.
Cai, X, McKinney, D. C., and Lasdon, L. S. (2001). “Solving nonlinear water management models using a combined genetic algorithm and linear programming approach.” Adv. Water Resour., 24, 667–676.
Chaves, P., and Kojiri, T. (2007). “Stochastic fuzzy neural network: Case study of optimal reservoir operation.” J. Water Resour. Plann. Manage., 133(6), 509–518.
Chen, C. (2007). “Non-convex economic dispatch: A direct search approach.” Energy Convers. Manage., 48, 219–225.
Chen, V. C. P., Ruppert, D., and Shoemaker, C. A. (1999). “Applying experimental design and regression splines to high-dimensional, continuous state stochastic dynamic programming.” Oper. Res., 47(1), 38–53.
Chiang, C. (2007). “Optimal economic emission dispatch of hydrothermal power systems.” Int. J. Electr. Power Energy Syst., 29(6), 462–469.
Deka, P. C., and Chandramouli, V. (2009). “Fuzzy neural network modeling of reservoir operation.” J. Water Resour. Plann. Manage., 135(1), 5–12.
El-Keib, A. A., Ma, H., and Hart, J. L. (1994). “Environmentally constrained economic dispatch using the Lagrangian relaxation method.” IEEE Trans. Power Syst., 9(4), 1723–1727.
El Mouatasim, A. (2012). “Boolean integer nonlinear programming for water multi-reservoir operation.” J. Water Resour. Plann. Manage., 138(2), 176–181.
Eum, H., Kim, Y., and Palmer, R. N. (2010). “Optimal drought management using sampling stochastic dynamic programming with a hedging rule.” J. Water Resour. Plann. Manage., 137(1), 113–122.
Hindi, K., and Ab Ghani, M. R. (1991). “Dynamic economic dispatch for large-scale power systems: A Lagrangian relaxation approach.” Electr. Power Syst. Res., 13, 51–56.
Hordijk, A. (1974). “On the convergence of the average expected return in dynamic programming.” J. Math. Anal. Appl., 46(2), 542–544.
Huang, Q., Zhang, H., Yuan, W., Zhang, S., and Wan, F. (2008). “Study of optimal operation chart of cascade reservoirs based on linking simulation with differential evolution algorithm.” J. Hydroelectr. Eng., 27(6), 13–17.
Huang, W., and Wu, C. M. (1993). “Diagnostic checking in stochastic dynamic programming.” J. Water Resour. Plann. Manage., 119(4), 490–494.
Jabr, R. A., Coonick, A. H., and Cory, B. J. (2000). “A homogeneous linear programming algorithm for the security-constrained economic dispatch problem.” IEEE Trans. Power Syst., 15, 930–936.
Ji, C., Yu, S., Zhou, T., Yang, Z., and Liu, F. (2011). “Application of ant colony algorithm for hydropower dispatching function optimization.” Autom. Electr. Power Syst., 35(20), 103–107.
Johnson, S. A., Stedinger, J. R., Shoemaker, C. A., Li, Y., and Tejada-Guibert, J. A. (1993). “Numerical solution of continuous-state dynamic programs using linear and spline interpolation.” Oper. Res., 41(3), 484–500.
Li, F., Shoemaker, C. A., Wei, J., and Fu, X. (2013). “Estimating maximal annual energy given heterogeneous hydropower generating units with application to the Three Gorges system.” J. Water Resour. Plann. Manage., 139(3), 265–276.
Liang, R., and Hsu, Y. (1995). “A hybrid artificial neural network-differential dynamic programming approach for short-term hydro scheduling.” Electr. Power Syst. Res., 33, 77–86.
Liao, L., and Shoemaker, C. A. (1991). “Convergence in unconstrained discrete-time differential dynamic programming.” IEEE Trans. Autom. Control, 36(6), 692–706.
Liu, D., and Wei, Q. (2013). “Generalized adaptive dynamic programming algorithm for discrete-time nonlinear systems: Convergence and stability analysis.” 2013 IEEE 3rd Int. Conf. on Information Science and Technology, IEEE Computer Society, Piscataway, NJ, 134–141.
Lu, B., Li, K., Zhang, H., Wang, W., and Gu, H. (2013). “Study on the optimal hydropower generation of Zhelin reservoir.” J. Hydroenviron. Res., 7(4), 270–278.
Marino, M. A., and Mohammadi, B. (1983). “Reservoir operation by linear and dynamic programming.” J. Water Resour. Plann. Manage., 109(4), 303–319.
Mathlouthi, M., and Lebdi, F. (2009). “Use of generated time series of dry events for the optimization of small reservoir operation.” Hydrol. Sci. J., 54(5), 841–851.
Momtahen, S. H., and Dariane, A. B. (2007). “Direct search approaches using genetic algorithms for optimization of water reservoir operating policies.” J. Water Resour. Plann. Manage., 133(3), 202–209.
Mousavi, S. J., Karamouz, M., and Menhadj, M. B. (2004). “Fuzzy-state stochastic dynamic programming for reservoir operation.” J. Water Resour. Plann. Manage., 130(6), 460–470.
Nagesh Kumar, D., and Janga Reddy, M. (2007). “Multipurpose reservoir operation using particle swarm optimization.” J. Water Resour. Plann. Manage., 133(3), 192–201.
Nandalal, K. D. W., and Bogardi, J. J. (2007). Dynamic programming based operation of reservoirs: Applicability and limits, Cambridge University Press, Cambridge, U.K.
Papageorgiou, L. G., and Fraga, E. S. (2007). “A mixed-integer quadratic programming formulation for the economic dispatch of generators with prohibited operating zones.” Electr. Power Syst. Res., 77, 1292–1296.
Raman, H., and Chandramouli, V. (1996). “Optimal operation of multi-reservoir system using dynamic programming and neural network.” Applications of Artificial Intelligence in Engineering XI (Full Papers on CD-ROM), Computational Mechanics Publications, Southampton, U.K., 59–60.
Shokri, A., Haddad, O. B., and Marino, M. A. (2013). “Reservoir operation for simultaneously meeting water demand and sediment flushing: Stochastic dynamic programming approach with two uncertainties.” J. Water Resour. Plann. Manage., 139(3), 277–289.
Takriti, S., and Krasenbrink, B. (1999). “A decomposition approach for the fuel-constrained economic power-dispatch problem.” Eur. J. Oper. Res., 112, 460–466.
Travers, D. L., and Kaye, R. J. (1998). “Dynamic dispatch by constructive dynamic programming.” IEEE Trans. Power Syst., 13, 72–78.
Yakowitz, S. (1982). “Dynamic programming applications in water resources.” Water Resour. Res., 18, 673–696.
Yang, C., Chang, L., Yeh, C., and Chen, C. (2007). “Multi-objective planning of surface water resources by multi-objective genetic algorithm with constrained differential dynamic programming.” J. Water Resour. Plann. Manage., 133(6), 499–508.
Yuan, W., Huang, Q., Wan, F., Zhang, S., and Liu, Z. (2008). “Discussion on the application of differential evolution algorithm for optimal operation of cascade reservoirs.” J. Hydroelectr. Eng., 27(5), 23–27.
Yuan, W., and Wu, Z. (2012). “Discussion on application of coopetive coevolution of differential evolution algorithm to optimal operation of cascaded reservoirs.” J. Hydroelectr. Eng., 31(3), 39–43.
Zhang, R., Zhou, J., Zhang, H., Liao, X., and Wang, X. (2014). “Optimal operation of large-scale cascaded hydropower systems in the upper reaches of the Yangtze River, China.” J. Water Resour. Plann. Manage., 140(4), 480–495.
Zhang, X., Zhang, H., Sun, Q., and Luo, Y. (2012). “Adaptive dynamic programming–based optimal control of unknown nonaffine nonlinear discrete-time systems with proof of convergence.” Neurocomputing, 91, 48–55.
Zhang, Z., Zhang, S., Wang, Y., Jiang, Y., and Wang, H. (2013). “Use of parallel deterministic dynamic programming and hierarchical adaptive genetic algorithm for reservoir operation optimization.” Comput. Ind. Eng., 65, 310–321.
Zhao, T., Cai, X., Lei, X., and Wang, H. (2012). “Improved dynamic programming for reservoir operation optimization with a concave objective function.” J. Water Resour. Plann. Manage., 138(6), 590–596.
Zhao, T., Zhao, J., and Yang, D. (2014). “Improved dynamic programming for hydropower reservoir operation.” J. Water Resour. Plann. Manage., 365–374.
Zhou, N., and Ji, C. (2007). “Optimal reservoir rule curve based on ant colony optimization.” J. Wuhan Univ. Technol., 29(5), 61–64.
Zhu-Ge, Y., and Xie, P. (2010). “The application of DDDP method to optimal operation for cascade reservoirs based on state transformation matrix.” Proc., 2010 Int. Conf. on Computational and Information Sciences, ICCIS, IEEE Computer Society, Piscataway, NJ, 76–80.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 141 • Issue 7 • July 2015
Copyright
© 2014 American Society of Civil Engineers.
History
Received: Dec 4, 2013
Accepted: Sep 2, 2014
Published online: Oct 15, 2014
Discussion open until: Mar 15, 2015
Published in print: Jul 1, 2015
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.