Design Heuristic for Globally Minimum Cost Water-Distribution Systems

Two standard test problems that are nonconvex with multiple local minima are considered. An outer flow search–inner optimization procedure is proposed for choosing better local minima. Each pipe network is judiciously subjected to the outer-search scheme that chooses alternative flow configurations to find an optimal flow division among pipes. An inner linear program is used for the design of least-cost diameters. The algorithm can also be used for the optimal design of parallel expansion of existing networks. Because the problem is nonconvex, two global-search schemes, MULTISTART and ANNEALING, are used to permit a local-optimum-seeking method to migrate among various local minima. MULTISTART selectively saturates portions of the feasible region to identify the local minima. ANNEALING iteratively improves the objective function by finding successive better points, and, to escape out of a local minimum, it exercises the metropolis step, which requires an occasional acceptance of a worse point. The optimal solutions thus found have significantly smaller costs than the ones reported previously by other researchers.