Forest-Core Partitioning Algorithm for Speeding Up Analysis of Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 140, Issue 4
Abstract
Commonly, water distribution networks have many treed or branched subgraphs. The equations for these systems are often solved for the steady-state flows and heads with a fast implementation of Newton’s method such as the global gradient algorithm (GGA). Applying the GGA to the whole of a network that has a treed portion means using a nonlinear solver on a problem that has separable linear and nonlinear parts. This is not optimal, and the flows and heads of treed networks can be found more quickly if the flows and heads of the treed portions are first solved explicitly by a linear process and then only the flows and heads of the smaller looped part of the network are found using the nonlinear GGA solver. The main contributions in this paper are the following: (1) development of a forest-core partitioning algorithm (FCPA), which separates the linear treed part of the network (the forest) from the nonlinear looped part (the core) by inspecting the incidence matrix; this allows the linear and nonlinear parts of the problem to be solved separately by linear and nonlinear methods, respectively; (2) explaining the mathematical basis for the adjustment of the network as the forest is identified and relating the mathematics to adjusting the graph of the network; (3) demonstration of flop count savings of between approximately 40 and 70% achievable in the linear phase of the GGA with forest-core partitioning on eight realistic case study water distribution networks ranging in size from 932 to 19,647 pipes; these savings lead, in turn, to savings in total CPU times of between 11 and 31% on the same networks; and (4) removing the need to use special techniques to deal with zero flows in forest pipes that have head loss modeled by the Hazen-Williams formulation. Where zero flows occur in the core, as a result of equal heads at the two ends of a pipe, special techniques will still need to be used.
Get full access to this article
View all available purchase options and get full access to this article.
References
Alperovits, E., and Shamir, U. (1977). “Design of optimal water distribution systems.” Water Resour. Res., 13(6), 885–900.
Amestoy, P. R., Davis, T. A., and Duff, I. (2004). “Algorithm 837: AMD, an approximate minimum degree ordering algorithm.” ACM Trans. Math. Software, 30(3), 381–388.
Bhave, P., and Sonak, V. (1992). “A critical study of the linear programming gradient method of optimal design of water supply networks.” Water Resour. Res., 28(6), 1577–1584.
Cross, H. (1936). “Analysis of flow in networks of conduits or conductors.” Bulletin 286, Univ. of Illinois Engineering Experiment Station, Urbana, IL.
Dandy, G., Simpson, A., and Murphy, L. (1996). “An improved genetic algorithm for pipe network optimization.” Water Resour. Res., 32(2), 449–457.
Deuerlein, J. W. (2008). “Decomposition model of a general water supply network graph.” J. Hydraul. Eng., 822–832.
Diestel, R. (2010). “Graph theory.” Graduate texts in mathematics, Vol. 173, 4th Ed., Spriger, Heidelberg, Germany.
Elhay, S., and Simpson, A. (2011). “Dealing with zero flows in solving the nonlinear equations for water distribution systems.” J. Hydraul. Eng., 1216–1224.
Epp, R., and Fowler, A. (1970). “Efficient code for steady-state flows in networks.” J. Hydr. Div., Proc. ASCE, 96(HY1), 43–56.
Giustolisi, O., and Todini, E. (2009). “Pipe hydraulic resistance correction in WDN analysis.” Urban Water J., 6(1), 39–52.
Gupta, R., and Prasad, T. (2000). “Extended use of linear graph theory for analysis of pipe networks.” J. Hydraul. Eng., 56–62.
Lippai, I. (2005). “Colorado Springs utilities case study: Water system calibration/optimization.” Proc., Pipeline Conf., ASCE, Reston, VA.
Matlab 7.14 [Computer software]. Mathworks, Natick, MA.
Ostfeld, A., et al. (2008). “The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms.” J. Water Resour. Plann. Manage., 556–568.
Perelman, L., Ostfeld, A., and Salomons, E. (2008). “Cross entropy multiobjective optimization for water distribution systems design.” Water Resour. Res., 44(9), W09413.
Rahal, H. (1995). “A co-tree formulation for steady state in water distribution networks.” Adv. Eng. Softw., 22(3), 169–178.
Reca, J., and Martnez, J. (2006). “Genetic algorithms for the design of looped irrigation water distribution networks.” Water Resour. Res., 42(5), W05416.
Rossman, L. (2000). EPANET 2 users manual, Water Supply and Water Resources Div., National Risk Management Research Laboratory, Cincinnati, OH.
Saldarriaga, J., Ochoa, S., Rodriguez, D., and Arbelez, J. (2008). “Water distribution network skeletonization using the resilience concept.” Proc., Water Distribution Systems Analysis 2008, ASCE, Reston, VA.
Shacham, M. (1984). “Decomposition of systems of non-linear algebraic equations.” AICHE J., 30(1), 92–99.
Simpson, A., and Elhay, S. (2011). “The Jacobian for solving water distribution system equations with the Darcy-Weisbach head loss model.” J. Hydraul. Eng., 696–700.
Todini, E., and Pilati, S. (1988). A gradient algorithm for the analysis of pipe networks, B. Coulbeck and O. Chun-Hou, eds., John Wiley and Sons, London, 1–20.
Tolson, B., Asadzadeh, M., Maier, H. R., and Zecchin, A. C. (2009). “Hybrid discrete dynamically dimensioned search (HD-DDS) algorithm for water distribution system design optimization.” Water Resour. Res., 45(12), W12416.
van Zyl, J., Savic, D., and Walters, G. (2004). “Operational optimization of water distribution systems using a hybrid genetic algorithm.” J. Water Resour. Plann. Manage., 160–170.
Zheng, F., Simpson, A., and Zecchin, A. (2011). “A combined NLP-differential evolution algorithm approach for the optimization of looped water distribution systems.” Water Resour. Res., 47(8), W08531.
Information & Authors
Information
Published In
Copyright
© 2012 American Society of Civil Engineers.
History
Received: Mar 5, 2012
Accepted: Nov 19, 2012
Published online: Nov 21, 2012
Discussion open until: Apr 21, 2013
Published in print: Apr 1, 2014
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.