Reformulated Co-Tree Flows Method Competitive with the Global Gradient Algorithm for Solving Water Distribution System Equations

Abstract

Many different methods have been devised to solve the nonlinear systems of equations that model water distribution networks. Probably the most popular is Todini and Pilati’s global gradient algorithm (GGA). Given the GGA’s success, alternative methods have not aroused much interest. One example is the co-tree method, which requires some cumbersome steps in its implementation. In this paper, a reformulated co-trees method (RCTM) is presented that simplifies the procedure by manipulating the incidence matrix into trapezoidal form: a lower triangular block at the top representing a spanning tree and rectangular block below it representing the corresponding co-tree. This reordering leads to significant efficiencies that make the RCTM competitive with the GGA in certain settings. The new method has some similarities to the loop flows corrections formulation, and it is shown, by application to a set of eight case study networks with between 932 and 19,647 pipes and between 848 and 17,971 nodes, to be between 15 and 82% faster than the GGA in a setting, such as optimization using evolutionary algorithms, where the methods are applied hundreds of thousands, or even millions, of times to networks with the same topology. It is shown that the key matrix for the RCTM can require as little as 7% of the storage requirements of the corresponding matrix for the GGA. This can allow for the solution of larger problems by the RCTM than might be possible for the GGA in the same computing environment. Unlike some alternatives to the GGA, the following features make the RCTM attractive: (1) it does not require a set of initial flows that satisfy continuity; (2) there is no need to identify independent loops or the loops incidence matrix; (3) a spanning tree and co-tree can be found from the incidence matrix without the addition of virtual loops, particularly when multiple reservoirs are present; and (4) it does not require the addition of a ground node and pseudoloops for each demand node and does not require the determination of cut sets. In contrast with the GGA, the RCTM does not require special techniques to handle zero flow problems that can occur when the head loss is modeled by the Hazen-Williams formula (a sufficient condition is given). The paper also (1) reports a comparison of the sparsity of the key RCTM and GGA matrices for the case study networks; (2) shows mathematically why the RCTM and GGA always take the same number of iterations and produce precisely the same iterates; and (3) establishes that the loop flows corrections and the nullspace methods (previously shown by Nielsen to be equivalent) are actually identical to the RCTM.