(545g) Solution of Optimal Placement Problems in Water Networks with Intractably Large Scenario Spaces

Design of contaminant detection and response systems in municipal water networks is crucial for protecting consumers from malicious or accidental contamination events. In order to minimize the health risks to the public, these systems must incorporate early warning detection systems to allow for adequate response measures in the event a contaminant is detected. Cleanup and control strategies should also be implemented to return the water system to an operational state with minimal disruption to service. The installation of chlorine booster stations for activation immediately following contaminant detection is one method to help reduce the impact of potential contamination scenarios. Optimal placement of sensors and booster stations within these municipal systems is an active area of research where a large number of methods have been proposed that employ linear or mixed-integer linear programming techniques.

We formulate these placement problems as mixed-integer linear stochastic programming problems. These problems must consider uncertainty in the location and time of these contamination events. Assuming contamination can occur from any node in the network and at any number of discrete time points can produce an intractably large scenario space when studying water networks with tens of thousands of nodes. In order to apply these solution techniques to actual city-scale design problems, the issue of finding representative scenario sets of a tractable size needs to be addressed. 

We propose a method for finding provably good placements using random sampling from the entire scenario space. Using the method of Mak, Morton, and Wood (1999), we employ a sampling procedure that generates confidence intervals on the optimality gap when optimal placements are determined with a limited number of scenarios. In addition to variability in the objective function, we examine variability in the optimal placements. Using a number of distance metrics for comparing placements, we demonstrate near optimal placements using significantly smaller representative subsamples of the entire scenario space.

Sandia National Laboratories is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-AC04-94AL85000.