Abstract
The practical utility of optimization technologies is often impacted by factors that reflect how these tools are used in practice, including whether various real-world constraints can be adequately modeled, the sophistication of the analysts applying the optimizer, and related environmental factors (e.g. whether a company is willing to trust predictions from computational models). Other features are less appreciated, but of equal importance in terms of dictating the successful use of optimization. These include the scale of problem instances, which in practice drives the development of approximate solution techniques, and constraints imposed by the target computing platforms. End-users often lack state-of-the-art computers, and thus runtime and memory limitations are often a significant, limiting factor in algorithm design. When coupled with large problem scale, the result is a significant technological challenge. We describe our experience developing and deploying both exact and heuristic algorithms for placing sensors in water distribution networks to mitigate against damage due intentional or accidental introduction of contaminants. The target computing platforms for this application have motivated limited-memory techniques that can optimize large-scale sensor placement problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hart, W.E., Berry, J., Murray, R., Phillips, C.A., Riesen, L.A., Watson, J.P.: SPOT: A sensor placement optimization toolkit for drinking water contaminant warning system design. Technical Report SAND2007-4393 C, Sandia National Laboratories (2007)
Morley, K., Janke, R., Murray, R., Fox, K.: Drinking water contamination warning systems: Water utilities driving water research. Journal AWWA, 40–46 (2007)
USEPA: WaterSentinel System Architecture. Technical report, U.S. Environmental Protection Agency (2005)
Berry, J., Hart, W.E., Phillips, C.A., Uber, J.: A general integer-programming-based framework for sensor placement in municipal water networks. In: Proc. World Water and Environment Resources Conference (2004)
Berry, J., Fleischer, L., Hart, W.E., Phillips, C.A., Watson, J.P.: Sensor placement in municipal water networks. J. Water Planning and Resources Management 131(3), 237–243 (2005)
Lee, B.H., Deininger, R.A., Clark, R.M.: Locating monitoring stations in water distribution systems. Journal, Am. Water Works Assoc., 60–66 (1991)
Lee, B.H., Deininger, R.A.: Optimal locations of monitoring stations in water distribution system. Journal of Environmental Engineering 118(1), 4–16 (1992)
Propato, M., Piller, O., Uber, J.: A sensor location model to detect contaminations in water distribution networks. In: Proc. World Water and Environmental Resources Congress, American Society of Civil Engineers (2005)
Watson, J.P., Greenberg, H.J., Hart, W.E.: A multiple-objective analysis of sensor placement optimization in water networks. In: Proc. World Water and Environment Resources Conference (2004)
Kessler, A., Ostfeld, A., Sinai, G.: Detecting accidental contaminations in municipal water networks. Journal of Water Resources Planning and Management 124(4), 192–198 (1998)
Kumar, A., Kansal, M.L., Arora, G.: Discussion of ‘detecting accidental contaminations in municipal water networks’. Journal of Water Resources Planning and Management 125(4), 308–310 (1999)
Ostfeld, A., Salomons, E.: Optimal layout of early warning detection stations for water distribution systems security. Journal of Water Resources Planning and Management 130(5), 377–385 (2004)
Rossman, L.A.: The EPANET programmer’s toolkit for analysis of water distribution systems. In: Proceedings of the Annual Water Resources Planning and Management Conference (1999), http://www.epanet.gov/ORD/NRMRL/wswrd/epanet.html
Berry, J., Hart, W.E., Phillips, C.E., Uber, J.G., Watson, J.P.: Sensor placement in municiple water networks with temporal integer prog ramming models. J. Water Resources Planning and Management 132(4), 218–224 (2006)
Mirchandani, P., Francis, R. (eds.): Discrete Location Theory. John Wiley and Sons, Chichester (1990)
Berry, J., Carr, R.D., Hart, W.E., Phillips, C.A.: Scalable water sensor placement via aggregation. In: Proc. Water Distribution System Symposium (2007)
Resende, M., Werneck, R.: A hybrid heuristic for the p-median problem. Journal of Heuristics 10(1), 59–88 (2004)
Ostfeld, A., Uber, J.G., Salomons, E., Berry, J.W., Hart, W.E., Phillips, C.A., Watson, J.P., Dorini, G., Jonkergouw, P., Kapelan, Z., di Pierro, F., Khu, S.T., Savic, D., Eliades, D., Polycarpou, M., Ghimire, S.R., Barkdoll, B.D., Gueli, R., Huang, J.J., McBean, E.A., James, W., Krause, A., Leskovec, J., Isovitsch, S., Xu, J., Guestrin, C., VanBriesen, J., Small, M., Fischbeck, P., Preis, A., Propato, M., Piller, O., Trachtman, G.B., Wu, Z.Y., Walski, T.: The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms. J. Water Resource Planning and Management (submitted, 2007)
Berry, J.W., Boman, E., Phillips, C.A., Riesen, L.A.: Low-memory Lagrangian relaxation methods for sensor placement in municipal water networks. In: Proc. EWRI (to appear, 2008)
Avella, P., Sassano, A., Vasil’ev, I.: Computational study of large-scale p-median problems. Mathematical Programming 109(1), 89–114 (2007)
Barahona, F., Chudak, F.: Near-optimal solutions to large-scale facility location problems. Discrete Optimization 2, 35–50 (2005)
Barahona, F., Anbil, R.: The volume algorithm: producing primal solutions with a subgradient method. Mathematical Programming 87(3), 385–399 (2000)
Berry, J., Phillips, C.: Randomized rounding for sensor placement problems (preparation) (submitted, 2007)
Computational INfrastructure for Operations Research home page (2008), http://www.coin-or.org/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hart, W.E., Berry, J.W., Boman, E., Phillips, C.A., Riesen, L.A., Watson, JP. (2008). Limited-Memory Techniques for Sensor Placement in Water Distribution Networks. In: Maniezzo, V., Battiti, R., Watson, JP. (eds) Learning and Intelligent Optimization. LION 2007. Lecture Notes in Computer Science, vol 5313. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92695-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-92695-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92694-8
Online ISBN: 978-3-540-92695-5
eBook Packages: Computer ScienceComputer Science (R0)