Hd. Sherali et al., ENHANCED LOWER BOUNDS FOR THE GLOBAL OPTIMIZATION OF WATER DISTRIBUTION NETWORKS, Water resources research, 34(7), 1998, pp. 1831-1841
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.