Contamination Warning in Water Networks: General Mixed-Integer Linear Models for Sensor Location Design

A mixed-integer linear program is proposed to identify optimal sensor locations for early warning against accidental and intentional contaminations in drinking water distribution systems. The general model can be applied to unsteady hydraulic conditions. Furthermore, it may accommodate different design objectives whose problem formulations vary only by the cost function coefficients while decision variables and linear constraints remain identical. Such a feature is very important since several requirements may be factors for practical design of warning systems. Linear constraint matrix properties show that the solution may often be found at the root (no branching). If not, a procedure is proposed to identify a significant set of discrete decision variables whose integrality constraints can be always relaxed. This result is coupled with good data preprocessing to minimize auxiliary continuous variables and constraints, allowing for efficient computation and increasing model applicability to large problems. The methodology is illustrated on a small and a midsize network.