Skip to content

Distinguished Lecture Series Featuring Dr. Cynthia Phillips

“Sensor Placement For Municipal Water Networks”

Monday, March 27, 2017


We consider the problem of placing a limited number of sensors in a municipal water distribution network to minimize the expected impact over a given suite of contamination incidents. In its simplest form, the sensor placement problem is a p-median problem (essentially a simplified facility placement problem) that has structure extremely amenable to exact and heuristic solution methods. As the models become more realistic, the optimization problems become more complex. Yet many more complex forms can still be transformed to exploit the simplified, tractable p-median formulation.

We will describe research from a long-term collaboration with the US Environmental Protection Agency that began in 2003, covering some work through 2014. Specifically, we will consider the following topics in varying degrees of detail: objective function considerations, handling sensor failures which makes the problem nonlinear, and special considerations to compute practical solutions on low-memory PCs. We will give some (not particularly new) computational results on real data. Time-permitting, we will discuss lessons learned (technical and otherwise) from the 2006 “Battle of the Water Sensor Networks” competition and describe how this long-term research began with an idea, some risks, and some luck.

Many of these algorithms are incorporated into the TEVA-SPOT toolkit, a software suite that the US Environmental Protection Agency has used and is using to design contamination-warning systems for US municipal water systems.

This is joint work with many colleagues at the EPA and at Sandia National Laboratories, covering material reported in over 20 papers in water systems journals and conferences. Some of this work lead to our Edelman-Award-finalist submission: “U.S. Environmental Protection Agency uses operations research to reduce drinking water contamination risks.”


Cynthia Phillips is a senior scientist in the Center for Computing Research at Sandia National Laboratories. She received a PhD in computer science from MIT in 1990. In her 27 years at Sandia National Laboratories, she has conducted research in combinatorial optimization, algorithm design and analysis, and parallel computation with applications to many areas including scheduling, network and infrastructure surety, wireless network management, integer programming, cybersecurity, graph algorithms, and streaming algorithms.

Return to Distinguished Lecture Series

The flagship campus of the University of Tennessee System and partner in the Tennessee Transfer Pathway.