A municipal water distribution system is a network of underground pipes, usually mirroring the city street network, that connects water supply sources such as reservoirs and water towers with demand points such as residential homes, industrial sites and fire hydrants. These systems are extremely expensive to install, with costs typically in the tens of millions of dollars. Existing pipes wear out, leak and break due to various factors including corrosion and cold weather ruptures, each requiring inconvenient and expensive repairs. Therefore, over time, these pipes need to be considered for replacement. Meanwhile, increasing urban development and water use rates dictate the need for larger and larger pipes to handle increased flow rates, while keeping water pressure within an acceptable range. However, larger pipes cost considerably more to install and maintain, causing the pipe sizing decision to be a critical task.

We develop an optimal network design and replacement strategy that meets hydraulic requirements under all likely demand and failure scenarios. Two submodels are used in a hierarchical fashion to integrate the reliability and cost analysis, and the network optimization process, within the overall network design process. The pipe reliability and cost submodel uses statistical methodologies based on historical records of pipe breaks to estimate future maintenance costs, and to recommend replacing relatively expensive-to-maintain or undercapacitated pipes. The pipe network optimization submodel provides a least cost construction and replacement plan along with optimal flows and energy heads for each fixed network configuration and demand pattern.

Traditional approaches isolate the above two types of models, assuming away the required interaction of inputs and outputs between them. We use a hierarchical design approach that integrates the foregoing two submodels by designing the network in a sequential fashion over a number of stages. The models are tied in a feedback loop that reprocesses the information until a stable design is attained. The result is a comprehensive reduced cost network design that meets all pressure and flow requirements for realistic problems, even under a wide variety of pipe failure modes.

For the optimization model, we develop two new algorithms that exploit the special network structure of the problem. In the first approach, the problem is restructured in a manner that facilitates its decomposition into a master control program, and an easy-to-solve convex cost network flow programming subproblem. The master program operates in the space of the structural design variables, while the subproblem determines flows as well as heads via its primal and dual optimal solutions. The coordination between the master program and the subproblems is effected via a suitable penalty term. The theoretical validity of the decomposition scheme is established, and efficient algorithmic implementation strategies are developed. On a standard popular test problem in the literature, this procedure is shown to recover a solution that significantly improves upon a previously best known solution.

The second optimization approach is one that guarantees a global optimal solution, and contrasts with previous approaches that at best produce local optimal solutions. This procedure is based on a Reformulation-Linearization Technique that constructs tight linear programming relaxations for the nonlinear problem, and embeds these in a branch-and-bound algorithm. A suitable partitioning strategy is coordinated with this scheme to provably ensure infinite convergence to a global optimum. When this method is applied to the aforementioned test problem, a further improved solution is obtained.

It is hoped that with additional enhancements and refinements, our proposed methodologies will serve to provide a useful tool for practitioners to design reliable pipe network water distribution systems.