Low-Memory Lagrangian Relaxation Methods for Sensor Placement in Municipal Water Networks
Publication: World Environmental and Water Resources Congress 2008: Ahupua'A
Abstract
Placing sensors in municipal water networks to protect against a set of contamination events is a classic p-median problem for most objectives when we assume that sensors are perfect. Many researchers have proposed exact and approximate solution methods for this p-median formulation. For full-scale networks with large contamination event suites, one must generally rely on heuristic methods to generate solutions. These heuristics provide feasible solutions, but give no quality guarantee relative to the optimal placement. In this paper we apply a Lagrangian relaxation method in order to compute lower bounds on the expected impact of suites of contamination events. In all of our experiments with single objectives, these lower bounds establish that the GRASP local search method generates solutions that are provably optimal to to within a fraction of a percentage point. Our Lagrangian heuristic also provides good solutions itself and requires only a fraction of the memory of GRASP. We conclude by describing two variations of the Lagrangian heuristic: an aggregated version that trades off solution quality for further memory savings, and a multi-objective version which balances objectives with additional goals.
Get full access to this chapter
View all available purchase options and get full access to this chapter.
Information & Authors
Information
Published In
Copyright
© 2008 American Society of Civil Engineers.
History
Published online: Apr 26, 2012
ASCE Technical Topics:
- Algorithms
- Computing in civil engineering
- Engineering fundamentals
- Environmental engineering
- Lagrangian functions
- Mathematical functions
- Mathematics
- Measurement (by type)
- Municipal water
- Pollution
- Relaxation (mechanics)
- Sensors and sensing
- Stress (by type)
- Structural analysis
- Structural engineering
- Water (by type)
- Water and water resources
- Water management
- Water pollution
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.