# Presentation: 548089

## The TEVA-SPOT Toolkit

- _William E Hart__1_, Jonathan W Berry1,
- Regan Murray2, Cynthia A Phillips1,
- Lee Ann Riesen1, Jean-Paul Watson1
- 1Discrete Algorithms and Mathematics Department, Sandia National Laboratories, Albuquerque, NM
- 2NHSRC, Environmental Protection Agency, Cincinnati, OH

## CWS Design

- Goal: design an online contaminant warning system to protect against contamination events
- Challenge: placement of sensors for the CWS within a budget
- Sensor placement issues...
- How do sensors work?
- What is the design basis threat?
- How does a utility respond to detection events?
- What performance measures are used to evaluate the CWS?
- What are the potential sensor locations?

## SPOT: Sensor Placement Optimization Toolkit

- TEVA-SPOT: A GUI interface for vulnerability assessment and		sensor placement
- Development led by EPA and ANL
- TEVA-SPOT Tookit: The sensor placement library used by TEVA-SPOT
- Development led by EPA and SNL
- Academic collaborators: UC, CU Denver, IBM, PNNL, UNM
- 			**... ****but I’ll just call this SPOT for convenience.**

## Motivations for SPOT

- Flexible solvers that can optimize many different objectives
- Scalable solvers for large-scale problems
- 10,000s junctions and pipes
- Limited-memory problem representations
- Flexible specification of problem formulation
- Flexible specification of performance constraints
- Fast, flexible solvers
- Methods for rigorously evaluating solver performance

**Application Driver:** The EPA needs a robust sensor placement capability for ongoing water security analyses (TEVA Program).

## A Canonical Problem Formulation

- Minimize expected impact of contamination events
- Over a selected set of times and locations
- Cost constraint
- Limit number of sensors
- Limit cost of installation
- Note:
- This is the formulation considered by most of the literature
- This assumes the adversary has no knowledge of how event time/location relates to impact of the event

## An Integer Programming Formulation

- Variables:
-   – event likelihood
-  *w* – event impact
-  *b* – event witness indicator
-  *s* – sensor placement indicator
- IP model:
- Objective is to minimize the expected impact of all events
- Very general formulation
- Can capture different objectives/networks
- Can be solved with COTS  software

## (A) Performance Objectives

- This formulation can capture a wide range of performance objectives:
-  Extent of contamination
-  Population exposed
-  Population Sickened
-  Response time
-  Mass of contaminant in the network
-  Volume of contaminant in the network
-  Number of sensors
-  Total cost (weighted by sensor lcoation)

- _Key Idea:_ These performance objectives are derived from external contaminant transport calculations and impact assessments, which can be arbitrarily complex.

## (B) Scalability

- IP Size:
*n* junctions (10,000’s)
*m* contamination times (100’s)
- Up to *nm* contamination “locations”
- Up to *n**2**m *contamination impact values
- Observations:
- A 64-bit workstation is required to solve applications with 1000s of junctions and many contamination times
- Need: ability to solve applications with 10,000s of junctions

## (B) Scalability Techniques...

- Witness Aggregation
- Combine witness indicator variables (e.g. if they are equal or nearly equal)
- Can compute a bound on the aggregated problem
- Scenario Aggregation
- Combine scenarios that could contaminant sites in the same order
- This allows the optimal sensor placements for multiple types of contaminants
- Representative Sensor Locations
- Select representative or candidate sensor locations
- The problem representation only needs to reflect those locations

## (C) Alternative Problem Formulations

- Minimize Worst-Case Performance
- Mathematically equivalent to the p-mean problem
- Difficult to solve with IP or heuristic solvers
- Robustness Formulations
- Can handle data uncertainties with min-max formulations
- Are solvable as IPs in some cases, but they are harder
- Can handle uncertainty in contamination location/time explicitly
- Risk measures: Value at Risk, Tail-conditioned expectation
- Solving these formulations is still difficult
- Can reduce worst-case impacts while maintaining good expected-case performance

## (D) Performance Constraints

- Observations:
- Different performance objectives need to be considered in practice
- Cannot generally minimize all objectives
- Idea: iteratively optimize different objectives
- SPOT can use side-constraints to constraint secondary objectives
- Solver performance is poor with more than one constraint
- Solvers can cache nearly feasible solutions to illustrate the trade-off between the new objective and the constraint

## (E) Fast, Flexible Solvers

- SPOT Solver Options
- PICO integer programming solver
- CPLEX integer programming solver (commercial)
- GRASP heuristic
- Lagrangian heuristic
- GRASP
- Optimizes with multiple local searches
- Can rapidly solve problems with 10,000s of junctions (minutes)
- Heuristic solutions are often optimal
- Lagrangian
- Optimizes with iterative penalties on constraint violations
- Uses very little memory
- Provides a bound on the value of the final solution

## (F) Confidence Bounds

- Goal: find near-optimal solutions AND quantify how close to optimum they are
- IP Solvers: find a globally optimal solution (but only for modest-scale problems)
- Heuristic:
- Often finds globally optimal solutions
- Can bound the global optimum with a LP-relaxtion of the IP
- Lagrangian:
- Finds near-optimal solutions
- Provides a bound on the value of the global optimum

## How SPOT Works

- TEVA-SPOT performs optimization to find a sensor placement.
- The sensor placement minimizes the potential impact of the ensemble of contamination events defined in Impact files.
- One or more sensor placements are generated.

- TEVA-CAT computes consequences from water quality simulations.
- Consequence analysis varies based on the type of impact being measured. Some analyses use water quality statistics, while others simply use the extent of contamination.
- Impact files are formatted in a generic manner; they summarize how the impact of events can be minimized by placing sensors that can observe them.

- TEVA-Sim executes an ensemble of EPANET simulations.
- This ensemble is defined by characteristics of the contamination events that are relevant for sensor placement (e.g. when and where contamination events might occur.)
- TSO files are formatted in a generic manner to encompass a wide range of water quality statistics about contamination events.

## Future Directions

- Ongoing applications to large-scale water utilities
- Especially within the USEPA’s TEVA Program
- Academic collaborations to integrate other sensor placement techniques
- E.g. include multi-objective optimization capabilities
- Planning public release of TEVA-SPOT Toolkit in 2008
- Some consequence assessment capabilities may be limited to water utilities with a business need
- An upcoming TEVA webpage will include a link to TEVA-SPOT when it is released!

## Questions?