000172512 001__ 172512
000172512 005__ 20180913061019.0
000172512 0247_ $$2doi$$a10.1007/s10107-010-0368-4
000172512 02470 $$2ISI$$a000280154400008
000172512 037__ $$aARTICLE
000172512 245__ $$aLocating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
000172512 260__ $$c2010
000172512 269__ $$a2010
000172512 336__ $$aJournal Articles
000172512 520__ $$aWe 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.
000172512 6531_ $$aPrize-collecting Steiner problem
000172512 6531_ $$aBranch and cut
000172512 6531_ $$aNetwork leakage detection
000172512 6531_ $$aOptimization
000172512 6531_ $$aCommunity
000172512 6531_ $$aSoftware
000172512 700__ $$aProdon, Alain$$uEPFL SB IMA ROSO, Stn 8, CH-1015 Lausanne, Switzerland
000172512 700__ $$aDeNegre, Scott$$uLehigh Univ, Bethlehem, PA 18015 USA
000172512 700__ $$0241744$$aLiebling, Thomas M.$$g105665$$uEPFL SB IMA ROSO, Stn 8, CH-1015 Lausanne, Switzerland
000172512 773__ $$j124$$q119-141$$tMathematical Programming
000172512 909C0 $$0252055$$pROSO
000172512 909CO $$ooai:infoscience.tind.io:172512$$particle
000172512 937__ $$aEPFL-ARTICLE-172512
000172512 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000172512 980__ $$aARTICLE