Journal of Water Resources Planning and Management · 2008 · 421 citations · 27 references
Natural SciencesMathematicsWater Resources ManagementDistributed SystemsOptimizationWater Resources EngineeringCombinatorial OptimizationInteger ProgrammingNetwork OptimizationSensor NetworksWater Distribution SystemsWireless Sensor NetworksBenchmark NetworksMixed-integer ProgrammingOptimization Of Distribution NetworksPlacement AlgorithmsPlacement OptimizationSensor PlacementSensor Placement OptimizationWater Distribution System Optimization
The paper seeks to deploy sensors in large water distribution networks to detect malicious contaminants by exploiting submodularity for efficient placement with provable guarantees. The authors design submodular‑based algorithms that extend to multicriteria optimization, robust to sensor failures, and minimax criteria. The algorithms scale to networks 72 times larger than previous work, avoid mixed‑integer programming, and empirical tests on two benchmarks and a 21,000‑node system demonstrate their effectiveness.
The problem of deploying sensors in a large water distribution network is considered, in order to detect the malicious introduction of contaminants. It is shown that a large class of realistic objective functions—such as reduction of detection time and the population protected from consuming contaminated water—exhibits an important diminishing returns effect called submodularity. The submodularity of these objectives is exploited in order to design efficient placement algorithms with provable performance guarantees. The algorithms presented in this paper do not rely on mixed integer programming, and scale well to networks of arbitrary size. The problem instances considered in the approach presented in this paper are orders of magnitude (a factor of 72) larger than the largest problems solved in the literature. It is shown how the method presented here can be extended to multicriteria optimization, selecting placements robust to sensor failures and optimizing minimax criteria. Extensive empirical evidence on the effectiveness of the method presented in this paper on two benchmark distribution networks, and an actual drinking water distribution system of greater than 21,000 nodes, is presented.
27
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7