# Presentation: 346619

## Robust Optimization Formulations for Sensor Placement inWater Distribution Systems

- William Hart
- Sandia National Laboratories
- wehart@sandia.gov
- Robert Carr (SNL)
- Harvey Greenberg (UC Denver)
- Todd Morrison (UC Denver)
- Regan Murray (USEPA)
- Jean-Paul Watson (SNL)

## Overview

- What type of robust optimization techniques can be used with general MILP formulations?
- Driver application: sensor placement in water distribution networks
- Key issue: how can we bound risk while maximizing performance?

## Water Security

- National Water Security Goals
- Protect long-term availability of national water resources
- Protect the operation of water utility distribution systems
- Protect water resources and infrastructure from improper use
- Universal Vulnerabilities in Water Systems
- Plant access
- Source Water
- Water storage
- Water distribution

## What is a water distribution network?

- _Drinking Water_
- Water source
- Treatment facilities
- Transmission systems
- Distribution systems

- _Wastewater_
- Wastewater source
- Collection system
- Treatment facility
- Receiving water body

## A Motivating Threat Scenario

**A Motivating Threat Scenario**

**Contaminant Injection**
- Risk: moderate-high
- Technically difficult to accomplish
- Potential terrorists fascinated by this prospect
- Impact: public health impacts, network contamination impacts
- Mitigation:
- Use of detection equipment
- Response:
- Coordination with public health institutions
- Proactive identification of contaminant source
- Decontamination procedures

## Designing a Contaminant Warning System (CWS)

- Technical Goal: placement of sensors for the CWS within a budget
- Possible objectives:
- Minimize response time
- Minimize health impacts
- Minimize extent of contamination
- Minimize volume of water that enters the water network
- Minimize number of failed detections
- Minimize cost
- Minimize political risk...

## What data do we need for sensor placement?

- Population consumption
- Location and time
- Individual characteristics: health, age
- Contamination risks
- Location and time
- Contaminant type
- Duration of impact
- Network model
- Physical topology
- Demand characteristics through time
- Variability in demands
- Note: there are major uncertainties in many of this data!

## Integer Programming for Sensor Placement

- IPs can be used to model sensor placement for water security
- Berry et al (2003, 2006); Watson et al (2004)
- Objective:
-  – contamination likelihood
-  *w* – contamination impact
-  *x* – witness variable
-  *s* – sensor placement variable
- IP model:
-  Can capture different objectives/networks
-  Can be solved with COTS software
- We need a 64-bit workstation to solve large instances

## Two RO Approaches

- Interval Uncertainties
- Data lies within a specified interval about an estimated value
- Formulate models that find the best solution for all possible uncertain values within the interval
- Consider side-constraints that exploit additional knowledge about the uncertainties
- Contamination Location Uncertainties
- Contamination impact varies with contamination location
- Formulate models that minimize or constrain the risk of a *catastrophic* contamination
- Consider different notions of risk: worst-case, VaR, CVaR
- Note: Our focus is on developing robust MILP models

## Interval Uncertainties

- Idea: consider uncertainties as simple errors on given numerical estimates
- where
- Note: This RO problem can be trivially reformulated as an IP model!

## Bounded Interval Uncertainties

- Example: population estimates
- The total population is probably well-known
- The estimated population at any given site may have considerable error
- Modeling interval uncertainties as a sum-restricted ball
- Note: this model of uncertainty works for various model parameters
- contamination probabilities, consumption demands, etc.

## Optimization with Bounded Uncertainties

- Idea: minimize the worst case value with bounded uncertainty
- where
- We consider proportional uncertainty intervals to simplify our discussion ...

## Example: Minimizing EC

- Extent of contamination (EC)
- Objective:
*w**ai* is the pipe length contaminated, which is well-known
***a* is uncertain
- RO formulation with bounded interval uncertainty
- Idea: reformulate this RO formulation using the dual of this subproblem

## Experiments With Bounded Uncertainties

- Network A: 97 junctions, 234 pipes	Network B: 470 junctions, 1198 pipes

**Notes:**
Note: this is data on an “old” IP formulation (Not the formulation presented earlier)

## Contamination Location Uncertainties

- Idea: consider the risk of a catastrophic contamination event
- Goal: limit the risk that the worst impacts have a big effect

## The Pitfall of Expected-Case Risk Minimization

- Note: minimizing expected impact can allow for high-consequence impacts, which could be exploited by an adversary

- no sensors

- 20 sensors

- Mean Impact

- Heavy tail “mass”

## Risk Measures of Interest

- Worst-Case
- The value of the worst impact
- Value-at-Risk (VaR)
- VaR(*x*,) is the value of the  quantile of the impact distribution
- Conditional Value at Risk
- Tail Conditional Expectation (TCE) is the average loss in worst 100 percent of the impact distribution
- CVaR(*x*,) is an approximation to TCE

## Examples of Risk Measures

- VaR(*x*,) - the tail has probability 

- TCE(*x*,) - the expectation of this tail

- The worst impact

## MILPs for These Risk Measures

- Worst-case MILPs are easy to formulate
- These are equivalent to the p-Center problem from facility location theory
- VaR-constrained formulations
- Standard risk metric in the financial community
- Can formulate with a simple quadratic constraint
- Can use binary indicator variables in a MILP formulation, but this can lead to a large formulation
- TCE/CVaR-constrained formulation
- More costly to evaluate than VaR
- Avoids some worst-case behavior of VaR

## Worst-Case versus Expected-Case Minimization

- Minimal expected case 20 sensors

- Minimal worst case    20 sensors

- Key observation
- You *can* trade off expected-case for worst-case impact in sensor placement

- Mean Impact

- Mean Impact

## Experience with Robust IPs

|  | Run-Time |  |  |
| --- | --- | --- | --- |
| Objective | Network 1 | Network 2 | Network 3 |
| Mean | 0.70s | 3m2s | 47m31s |
| Worst | 8ms20s | > 24 hrs | > 48 hrs |
| TCE (CVaR) | 3m18s | > 24 hrs | > 96 hrs |

-  Robust optimization models are *MUCH* more difficult to solve than expected case models
- One to two orders of magnitude more run-time for MIP models
-  MIP models are in effective unsolvable, requiring days to weeks of run-time
- With CPLEX 10 on 64GB RAM, 64-bit architectures

## Runtime vs. Optimal CVaR

- Time (seconds)

- CVaR

## Experience with Robust Heuristics

|  | Run-Time per Local Optimum |  |  |
| --- | --- | --- | --- |
| Objective | Network 1 | Network 2 | Network 3 |
| Mean | 0.01s | 0.81s | 6.5s |
| Worst | 0.02s | 97s | 4.4hrs |
| VaR | 0.05s | 643s | 20.4hrs |
| TCE | 0.06s | 810s | 26.0hrs |

-  We use a GRASP heuristic (multistart local search)
- Heuristics  are obtaining optimal solutions where verifiable
- Heuristics are currently the only practical option

## Qualitative Observations on Robust Optimization Models

- For moderate sensor budgets
-  We observe that you can typically obtain a 30-50% reduction in worst-case impact for a 50-100% increase in expected-case impact
- Key motivation in continued exploration of robust optimization models
- Unexpectedly, the various solutions to the robust optimization models are _*not*_ strongly correlated
- E.g., optimal worst-case solutions tend to yield sub-optimal (and often highly sub-optimal) VaR and TCE performance
- Emphasizes the importance of the optimization objective in system design

## Acknowledgements

- Robert Carr (SNL)
- Harvey Greenberg (SNL)
- Goren Konjevod (ASU)
- Eric Lauer (UNM)
- Henry Lin (Berkeley)
- Tod Morrison (CU Denver)
- Cindy Phillips (SNL)

## Experience with CVaR MILPs

- Considered Performance/CVaR trade-off for Network B

- Expected Impact

- CVaR

## Defining CVaR

## CVaR-Constrained Formulation

- Let  be a bound on CVaR
- The following formulation bounds CVaR
- Note: we can include CVaR in both the objective as well!
- Note: v is VaR when the CVaR constraint is binding