DESIGN HEURISTIC FOR GLOBALLY MINIMUM-COST WATER-DISTRIBUTION SYSTEMS

Two standard test problems that are nonconvex with multiple local mini ma are considered. An outer flow search-inner optimization procedure i s proposed for choosing better local minima. Each pipe network is judi ciously subjected to the outer-search scheme that chooses alternative flow configurations to find an optimal flow division among pipes. An i nner linear program is used for the design of least-cost diameters. Th e algorithm can also be used for the optimal design of parallel expans ion 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. MULTISTA RT selectively saturates portions of the feasible region to identify t he local minima. ANNEALING iteratively improves the objective function by finding successive better points, and, to escape out of a local mi nimum, it exercises the metropolis step, which requires an occasional acceptance of a worse point. The optimal solutions thus found have sig nificantly smaller costs than the ones reported previously by other re searchers.