Prodon, Alain
DeNegre, Scott
Liebling, Thomas M.
Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
Mathematical Programming
Mathematical Programming
Mathematical Programming
Mathematical Programming
124
Prize-collecting Steiner problem
Branch and cut
Network leakage detection
Optimization
Community
Software
2010
2010
We consider the problem of optimizing a novel acoustic leakage detection system for urban water distribution networks. The system is composed of a number of detectors and transponders to be placed in a choice of hydrants such as to provide a desired coverage under given budget restrictions. The problem is modeled as a particular Prize-Collecting Steiner Arborescence Problem. We present a branch-and-cut-and-bound approach taking advantage of the special structure at hand which performs well when compared to other approaches. Furthermore, using a suitable stopping criterion, we obtain approximations of provably excellent quality (in most cases actually optimal solutions). The test bed includes the real water distribution network from the Lausanne region, as well as carefully randomly generated realistic instances.
Mathematical Programming
Journal Articles
10.1007/s10107-010-0368-4