Verification of Branch and Bound Algorithms applied to Water Distribution Network Design

The design of distribution networks is an integral factor in the planning process of water supply systems.
Models concerning this design process contain the problem of selecting pipe diameters for a given layout
of the network. Assuming the demand to be estimated for a certain point of time and the costs for
pipes of different diameters to be known, this stationary problem can be formulated as a nonlinear global
optimization problem. Restrictions to the pressure head and the calculations of head-loss due to friction
in the pipes imply nonlinear constraints.
Heuristic as well as deterministic algorithms have been developed during the last 30 years to solve this
problem. Their implementation is based on floating point arithmetic. In a branch and bound algorithm
the decision for every branch depends on numerical results. Therefore even small errors may have farreaching
consequences. In the context of this thesis the software package WaTerInt has been developed
which contains the first verified algorithm for water distribution design optimization to avoid this problem.
WaTerInt is based on the branch and bound algorithm developed by Sherali, Subramanian and Loganathan1
and results from interval analysis, allowing rigorous bounds together with a guarantee of
existence and uniqueness. Furthermore, a new additional constraint propagation technique is introduced
which decreases the computational time for expansion networks by approximately one third to one half.
The computational results using non-verified floating point calculations are found to show numerical
artifacts. For example, it is possible that a problem is identified as infeasible that in reality does have a
solution, or that the lower bound for the optimal solution is larger than the upper bound. Using verified
calculations, these artifacts are avoided, the obtained results are always reliable. Nevertheless for this
improved quality, in the current implementation the computational time for verified calculations takes on
average fifteen times the time needed for the calculation without error analysis when relying just on pure
floating point arithmetic. This factor could probably be decreased when not depending on interpretation
overhead of MATLAB, especially for object orientation.
In addition to the model based on Hazen-Williams formula as used by Sherali, Subramanian and Loganathan,
the optimization problem is reformulated to contain Darcy-Weisbach and Colebrook-White
equations. The algorithm has been expanded to be able to solve this more accurate problem as well,
and again a verified version is presented. Essentially, detailed investigation of the nonlinearity of the
implicitly defined Colebrook-White equation was necessary to retain certain monotonicity and convexity
arguments. The adjacency property is proved for this new problem as well. However, the computational
effort is around forty times higher than for the Hazen-Williams problem. To combine the advantages of
the Darcy-Weisbach optimization problem with the more simple structure and lower computational times
of Hazen-Williams, the coefficients of this formula are adjusted to obtain a closer approximation.
Finally, verified results have been used to compare results obtained for different head loss formulae and
hydraulic parameters for known test networks. When regarding the whole life span of a pipe network it
occurs that energy costs form a significant part of the overall costs, except when water is mainly delivered
by gravity.
In summary, recently developed verification techniques are combined with a branch and bound algorithm
to investigate the practicability of obtaining error estimates along with the calculation of the optimal
solution of a nonlinear optimization problem. They are applied to water network distribution design,
both to the known branch and bound algorithm of Sherali, Subramanian and Loganathan and to the one
for the more realistic network model based on the Darcy-Weisbach equation.