Water networks security: A two-stage mixed-integer stochastic program for sensor placement under uncertainty

This work describes a stochastic approach for the optimal placement of sensors in municipal water networks to detect maliciously injected contaminants. The model minimizes the expected fraction of the population at risk and the cost of the sensors. Our work explicitly includes uncertainties in the attack risk and population density, so that the resulting problem involves optimization under uncertainty. In our formulation, we include the location of a number of sensors as first stage decision variables of a two-stage mixed-integer stochastic linear problem; the second stage evaluates the population at risk for the scenario obtained in the first stage and that information is then used to modify the first stage decisions for the next iteration. Since the model is integer in the first stage, a generalized framework based on the stochastic decomposition algorithm allows us to solve the problem in a reasonable computational time. The paper describes the mixed-integer stochastic model and the algorithmic framework, and compares the deterministic and stochastic optimal solutions. The network used as our case study has been derived through the water network simulator EPANET 1.0; four acyclic water flow patterns are considered. Results show a significant effect of uncertainty in sensor placement and total cost.