A global optimization approach to a water distribution network design problem

In this paper, we address a global optimization approach to a water distribution network design problem. Traditionally a variety of local optimization schemes have been developed for such problems, each new method discovering improved solutions for some standard test problems, with no known lower bound to test the quality of the solutions obtained. A notable exception is a recent paper by Eiger et al. (1994) who present a first global optimization approach for a loop and path-based formulation of this problem, using a semi-infinite linear program to derive lower bounds. In contrast, we employ an are-based formulation that is linear except for certain complicating head-loss constraints and develop a first global optimization scheme for this model. Our lower bounds are derived through the design of a suitable ReformuIation-Linearization Technique (RLT) that constructs a tight linear programming relaxation for the given problem, and this is embedded within a branch-and-bound algorithm. Convergence to an optimal solution is induced by coordinating this process with an appropriate partitioning scheme. Some preliminary computational experience is provided on two versions of a particular standard test problem for the literature for which an even further improved solution is discovered, but one that is verified for the first time to be an optimum (within $1 of cost), without any assumed a priori bounds on the flows. Two other variants of this problem are also solved exactly for illustrative purposes and to provide researchers with additional test cases having known optimal solutions. Suggestions on a more elaborate study involving several algorithmic enhancements are presented for future research.