Loading...
Please wait, while we are loading the content...
Similar Documents
Low-memory Lagrangian Relaxation Methods for Sensor Placment in Municipal Water Networks
| Content Provider | Semantic Scholar |
|---|---|
| Author | Riesen, Lee Ann |
| 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 multiobjective version which balances objectives with additional goals. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.sandia.gov/~egboman/papers/BerryBomanPhillipsRiesen-EWRI08.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation algorithm Augmented Lagrangian method Experiment Full scale GRASP gene Heuristics Lagrangian relaxation Linear programming relaxation Local search (optimization) Relaxation (approximation) Solutions sensor (device) |
| Content Type | Text |
| Resource Type | Article |
