Global optimization of water distribution networks through a reduced space branch-and-bound search

A branch-and-bound approach to the problem of optimal design of water distribution networks is presented. Global optimum is reached through the generation of convergent sequences of upper and lower bounds. The relaxations responsible for the lower bounds correspond to linear programming problems formulated through the enlargement of the original feasible region by outer approximations of the constraints. Although formulated within an are-based framework, the proposed scheme does not apply the branching process to all flow variables; by utilizing the mass conservation principle, only a reduced set of variables is assigned for branching. The algorithm was applied to three variants of a classical problem from the literature. Comparisons with previous results indicates a faster convergence to the optimum (fewer linear programming problems solved) in several situations.