Verification of Branch and Bound Algorithms Applied to Water Distribution Network Design - Brossura

Hailer, Angelika

Brossura

ISBN 10: 3832513167 ISBN 13: 9783832513160

Casa editrice: Logos Verlag Berlin, 2006

Riassunto

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

Dettagli dell?edizione

• Editore: Logos Verlag Berlin
• Data di pubblicazione: 2006
• Lingua: Inglese
• ISBN 10: 3832513167
• ISBN 13: 9783832513160
• Rilegatura: Copertina flessibile
• Numero di pagine: 350
• Contatto del produttore: non disponibile
• Persona responsabile: non disponibile