A General Integer-Programming-Based Framework for Sensor Placement in Municipal Water Networks

We present a new integer-programming formulation for sensor placement in municipal water systems. Berry, Fleischer, Hart, and Phillips introduced a time-independent sensor-placement model. To avoid explicit references to time, this model assumed consumers are protected only if every path from a contaminant introduction site is guarded by a sensor. The model also assumed flow within the pipes was reasonably swift, if not quantified, so that flow patterns will not shift before a contaminant is detected. We decouple contaminant transportation from sensor placement decisions and explicitly consider time. We use discrete-event simulation, using velocity information derived from EPANET, to calculate contamination timing in the network for each of an enumerable number of attack scenarios. We use an integer program to select a set of sensor locations that minimizes the expected amount of contaminant delivered to consumers across all these attack scenarios. Initial computational experience on two real networks shows that the discrete-event simulator is very fast and the resulting integer programs are tractable for moderate-sized attack sets.