| Affiliation: | (1) Discrete Algorithms and Math Department, Sandia National Laboratories, USA;(2) Mathematics Department, University of Colorado at Denver, USA;(3) Discrete Algorithms and Math Department, Sandia National Laboratories, USA;(4) Computer Science Department, Arizona State University, USA;(5) Electrical and Computer Engineering Department, University of New Mexicó, USA;(6) University of California at Berkeley, USA;(7) Mathematics Department, University of Colorado at Denver, USA;(8) Discrete Algorithms and Math Department, Sandia National Laboratories, USA |
| Abstract: | We present a series of related robust optimization models for placing sensors in municipal water networks to detect contaminants that are maliciously or accidentally injected. We formulate sensor placement problems as mixed-integer programs, for which the objective coefficients are not known with certainty. We consider a restricted absolute robustness criteria that is motivated by natural restrictions on the uncertain data, and we define three robust optimization models that differ in how the coefficients in the objective vary. Under one set of assumptions there exists a sensor placement that is optimal for all admissible realizations of the coefficients. Under other assumptions, we can apply sorting to solve each worst-case realization efficiently, or we can apply duality to integrate the worst-case outcome and have one integer program. The most difficult case is where the objective parameters are bilinear, and we prove its complexity is NP-hard even under simplifying assumptions. We consider a relaxation that provides an approximation, giving an overall guarantee of near-optimality when used with branch-and-bound search. We present preliminary computational experiments that illustrate the computational complexity of solving these robust formulations on sensor placement applications. |
