Effective relaxations and partitioning schemes for solving water distribution network design problems to global optimality

In this paper, we address the development of a global optimization procedur e for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach signif icantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning st rategies in concert with a maximal spanning tree-based branching variable s election procedure. Computational experience on three standard test problem s from the literature is provided to evaluate the proposed procedure. For a ll these problems, proven global optimal solutions within a tolerance of 10 (-4)% and/or within 1$ of optimality are obtained. In particular, the two l arger instances of the Hanoi and the New York test networks are solved to g lobal optimality for the very first time in the literature. A new real netw ork design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test case s, and related computational results are presented.