Limitations of Network Flow Algorithms in River Basin Modeling
Publication: Journal of Water Resources Planning and Management
Volume 135, Issue 1
Abstract
A number of computer models for river basin planning and management have been developed by various agencies and used extensively since the mid-1970s. Most of the early developments have been based on the use of heuristic weight factors to represent priorities of allocation, and specialized optimization algorithms that were based on the use of network flow algorithms (NFAs). While these algorithms were at first considerably faster than the standard Simplex solvers, their handling of flow constraints was simplistic, which eventually led to the use of iterative schemes for handling nonnetwork constraints. This paper critically examines the notion that iterations applied in combination with NFA are a good vehicle for handling nonnetwork constraints. The failures are demonstrated on several variants of a simple problem with two reservoirs in series.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The Water Resources Management Model (WRMM) used as the benchmark NFA-based model is a public domain modeling tool owned and maintained by Alberta Environment in Canada. Sincere thanks go to George Kuczera who independently verified the results of the test problems presented here, and also to an anonymous reviewer and the journal editor for their useful suggestions.
References
Andrews, E. S., Chung, F. I., and Orlin, J. B. (1993). “Multilayers, priority-based simulation of conjunctive facilities.” J. Water Resour. Plann. Manage., 118(1), 32–53.
Barr, R. S., Glover, F., and Klingman, D. (1974). “An improved version of the out-of-kilter method and comparative study of computer codes.” Mathematical programming 7, North Holland Publishing, Amsterdam, The Netherlands, 60–86.
Bertsekas, D. P., and Tseng, P. (1988). “Relaxation methods for minimum cost ordinary and generalized network flow problems.” Oper. Res., 36(1), 93–114.
Brendecke, C. M. (1989). “Network models of water rights and system operations.” J. Water Resour. Plann. Manage., 115(5), 684–696.
Chung, F. I., Archer, M. C., and DeVries, J. J. (1989). “Network flow algorithm applied to California aqueduct simulation.” J. Water Resour. Plann. Manage., 115(2), 131–147.
Dean, R., Cleland, L., Kuehne, C., Buzz, L., George, W., and Sheer, D. (1998). “Water supply planning simulation model using mixed-integer linear programming ‘engine.’” J. Water Resour. Plann. Manage., 123(2), 116–124.
Draper, A. J., et al. (2004). “CalSim: Generalized model for reservoir system analyses.” J. Water Resour. Plann. Manage., 130(6), 480–489.
Evanson, D. E., and Moseley, J. C. (1970). “Simulation/optimization techniques for multi-basin water resources planning.” Water Resour. Bull., 6(5), 725–736.
Fulkerson, D. R. (1961). “An out-of-kilter method for minimal cost flow problems.” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal., 9(1), 18–27.
Ilich, N. (1993). “Improvement of the return flow allocation in the water resources management model (WRMM) of Alberta environment.” Can. J. Civ. Eng., 20(4), 613–621.
Ilich, N. (2008). “Shortcomings of linear programming in optimizing river basin allocation.” Water Resour. Res., 44, W02426).
Ilich, N., Simonovic, S. P., and Amron, M. (2000). “The benefits of computerized real-time river basin management in the Malahayu reservoir system.” Can. J. Civ. Eng., 27(1), 55–64.
Kennington, J. L., and Helgason, R. V. (1980). Algorithms for network programming, Wiley-Interscience, New York.
Kuczera, G. (1992). “Water supply simulation using network linear programming.” Adv. Eng. Software, 14, 55–60.
Kuczera, G., and Diment, G. (1988). “General water supply system simulation model: WASP.” J. Water Resour. Plann. Manage., 114(4), 365–382.
Labadie, J. W. (2004). “Optimal operation of multireservoir systems: A state-of-the-art review.” J. Water Resour. Plann. Manage., 130(2), 93–111.
Labadie, J. W., Bode, D. A., and Pineda, A. M. (1986). “Network model for decision-support in municipal raw water supply.” Water Resour. Bull., 22(6), 927–940.
Lund, J. R. (1996). “Developing seasonal and long-term reservoir system operation plans using HEC-PRM.” Hydrologic Engineering Center, Davis, Calif., ⟨http://handle.dtic.mil/100.2/ADA315845⟩.
Lund, J. R., and Guzman, J. (1999). “Derived operating rules for reservoirs in series or in parallel.” J. Water Resour. Plann. Manage., 125(3), 143–153.
Needham, J. T., Watkins, D. W., Jr., and Lund, J. (2000). “Linear programming for flood control in the Iowa and Des Moines Rivers.” J. Water Resour. Plann. Manage., 126(3), 118–127.
Perera, B. J. C., and James, B. (2003). “A generalised water supply simulation computer software package.” Hydrology J., Inst. Engineers (India), 26(1–2), 67–83.
Perera, B. J. C., James, B., and Kularathna, M. D. U. (2005). “Computer software tool for sustainable water allocation and management—REALM.” J. Environ. Manage., 77(4), 291–300.
Sigvaldason, O. T. (1976). “A simulation model for operating a multi- purpose multireservoir system.” Water Resour. Res., 12(2), 263–278.
Sun, Y. H., Yeh, W., Hsu, N. S., and Louie, P. W. F. (1995). “Generalized network algorithm for water supply system optimization.” J. Water Resour. Plann. Manage., 121(5), 392–398.
Wurbs, R. (1993). “Reservoir system simulation and optimization models.” J. Water Resour. Plann. Manage., 119(4), 455–471.
Zagona, E. A., Fulp, T. J., Shane, R., Magee, T., and Goranflo, H. M. (2001). “RiverWare: A generalized tool for complex reservoir system modeling.” J. Am. Water Resour. Assoc., 37(4), 913–929.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 135 • Issue 1 • January 2009
Pages: 48 - 55
Copyright
© 2009 ASCE.
History
Received: May 29, 2007
Accepted: May 20, 2008
Published online: Jan 1, 2009
Published in print: Jan 2009
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.