ENHANCED LOWER BOUNDS FOR THE GLOBAL OPTIMIZATION OF WATER DISTRIBUTION NETWORKS

In this paper we address a global optimization approach to the problem of designing a water distribution network that satisfies specified fl ow demands at stated pressure head requirements. The nonlinear, noncon vex network problem is transformed into the space of certain design va riables. By relaxing the nonlinear constraints in the transformed spac e via suitable polyhedral outer approximations, we derive a linear low er bounding problem. This problem provides an enhancement of Eiger et al.'s [1994] lower bounding scheme and takes advantage of the monotone concave-convex nature of the nonlinear constraints. Upper bounds are computed by solving a projected linear program that uses the flow cons erving solution generated by the lower bounding problem. These boundin g strategies are embedded within a branch-and-bound algorithm. The par titioning scheme employed reduces the gap from optimality, inducing a convergent process to a feasible solution that lies within any prescri bed accuracy tolerance of global optimality. The approach is illustrat ed using two standard test problems from the literature. For the large r (Hanoi network) problem a better incumbent than previously reported in the literature is obtained and is proven to be within 0.486% of opt imality over the specified feasible domain used for this problem.