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 Loganathan 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.