The Computational Complexity of the Problem of Determining Least Capital Cost Designs for Water Supply Networks

Pipes for water supply are manufactured in a set of discrete-sized diameters. This situation introduces significant difficulties to the problem of devising an algorithm for selecting pipe diameters to constitute a water supply network of least capital cost. In this paper, it is shown that, even for the very simplest type of branching network, the problem is one of a mathematical class known as NP-hard; a result which, by implication, applies to the more complex type of network containing loops. This result suggests that research aimed at devising such an algorithm is likely to be unsuccessful, and would be better directed towards developing good approximate solution methods.