Motivation

Model

Robust Optimization

Robust Models of Epidemics, and Emergency
Resource Allocation
Daniel Bienstock, joint with A. Cecilia Zenteno
Columbia University
USC Epstein, February 2013

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic
How to combat its impact?

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic
How to combat its impact?
Mortality and morbidity →Public health interventions:

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic
How to combat its impact?
Mortality and morbidity →Public health interventions:
Vaccine and antivirals

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic
How to combat its impact?
Mortality and morbidity →Public health interventions:
Vaccine and antivirals
Non-pharmaceutical interventions

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Virus mutates continuously → epidemic
How to combat its impact?
Mortality and morbidity →Public health interventions:
Vaccine and antivirals
Non-pharmaceutical interventions

Workforce absenteeism

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Objective: Counteract impact of epidemic-related
absenteeism on operation of critical infrastructure

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Motivation

Objective: Counteract impact of epidemic-related
absenteeism on operation of critical infrastructure
Energy plants
Water plants
Supply chains
Hospitals and clinics

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisrecommendationsof national pandemic influenza
preparedness plans
JANUARY 2011

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB
Students (health services)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB
Students (health services)
Recent retirees

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB
Students (health services)
Recent retirees

Planning horizon

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB
Students (health services)
Recent retirees

Planning horizon - fully preplanned

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

What to do?
WHO, CDC, HHS - preparedness

Comparative
analysisof national pandemic influenza
preparedness plans

recommendations
Absenteeism → surge staff

JANUARY 2011

Volunteer networks and DB
Students (health services)
Recent retirees

Planning horizon - fully preplanned
When and how many?

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Agenda1 Disease Modeling1.

2. Hiring Restrictions
2& Implementation

3. System Utilization
MeasureBienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Robust Optimization

Results

Motivation

Model

Robust Optimization

Agenda1 Disease Modeling1.

2. Hiring Restrictions
2& Implementation

3. System Utilization
MeasureBienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Robust Optimization
Algorithm

Results

Motivation

Model

Robust Optimization

1. A model for influenza
SEIR model
Deterministic
Spread of the disease in large populations

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

1. A model for influenza
SEIR model
Deterministic
Spread of the disease in large populations

Individuals → compartments

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

1. A model for influenza
SEIR model
Deterministic
Spread of the disease in large populations

Individuals → compartments
S Susceptible
E Exposed or latent
I Infectious
R Removed
?>=<
89:;
S

λβp

* ?>=<
89:;
E

µE

)?>=<
89:;
I

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

µRR

* ?>=<
89:;
R

Results

Motivation

Model

Robust Optimization

1. A model for influenza
SEIR model
Deterministic
Spread of the disease in large populations

Individuals → compartments
λ
β
p
µE
µRR

S Susceptible
E Exposed or latent
I Infectious

avg contacts
P{contact I}
P{contagion}
Incubation rate
Removal rate

R Removed
?>=<
89:;
S

λβp

* ?>=<
89:;
E

µE

)?>=<
89:;
I

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

µRR

* ?>=<
89:;
R

Results

Motivation

Model

Robust Optimization

1. A model for influenza
SEIR model
Deterministic
Spread of the disease in large populations

Individuals → compartments
λ
β
p
µE
µRR

S Susceptible
E Exposed or latent
I Infectious

avg contacts
P{contact I} = I /N
P{contagion}
Incubation rate
Removal rate

R Removed
?>=<
89:;
S

λβp

* ?>=<
89:;
E

µE

)?>=<
89:;
I

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

µRR

* ?>=<
89:;
R

Results

Motivation

Model

Robust Optimization

Workers

Keep track of absenteeism → separate accounting of workers.

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Workers

Keep track of absenteeism → separate accounting of workers.
@ABC
GFED
S1

λ1 βp

@ABC
GFED
S2

λ2 βp

+ @ABC
GFEDµE1+ @ABC
GFED

µE2

E1
E2

*
GFED
@ABC
I1

µRR1

*
GFED
@ABC
I2

µRR2

+ GFED@ABC

R1→ General population+ GFED@ABC→ Workers

R2

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Workers

Keep track of absenteeism → separate accounting of workers.
@ABC
GFED
S1

λ1 βp

@ABC
GFED
S2

λ2 βp

+ @ABC
GFEDµE1+ @ABC
GFED

µE2

E1
E2

*
GFED
@ABC
I1

µRR1

+ GFED@ABC

R1→ General population

*
GFED
@ABC
I2

µRR2

+ GFED@ABC→ Workersβ=

λ1 I 1 + λ2 I 2
λ1 N 1 + λ2 N 2

R2

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Discrete time SEIR model

Model for subgroup j transition t → t + 1:j
St+1
= Stj e −λj ∗βt ∗pj
Et+1= Etj e−µEj

j
= Itj eIt+1

+ Stj (1 − e −λj ∗βt ∗p )−µRRj

+ Etj (1 − ej
Rt+1= Rtj + Itj (1 − e[LJS Allen et al, 1991; Larson, 2007]
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

−µRRj

).

−µEj

)

Results

Motivation

Model

Robust Optimization

Discrete time SEIR model

Model for subgroup j transition t → t + 1:j
St+1
= Stj e −λj ∗βt ∗pj
Et+1= Etj e−µEj

j
= Itj fj e
It+1

+ Stj (1 − e −λj ∗βt ∗p )−µRRj

+ Etj (1 − ej
Rt+1= Rtj + Itj (1 − e[LJS Allen et al, 1991; Larson, 2007]
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

−µRRj

).

−µEj

)

Results

Motivation

Model

Robust Optimization

Non-homogeneous contact

It is likely that social contacts will change during epidemic

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Non-homogeneous contact

It is likely that social contacts will change during epidemic↑ Severity ⇒ Average # contacts ↓jjjjj St + Et + Rt
λt = Λ
Ntj[LJS Allen et al, 1991]

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

An inconvenient fact

SEIR models → uncertain many parameters

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

An inconvenient fact

SEIR models → uncertain many parameters
New mutation - at best, noisy estimations

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

An inconvenient fact

SEIR models → uncertain many parameters
New mutation - at best, noisy estimations
Incubation and recovery rates (µE , µRR ) are “easy”

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

An inconvenient fact

SEIR models → uncertain many parameters
New mutation - at best, noisy estimations
Incubation and recovery rates (µE , µRR ) are “easy”
Contagion rate λβp ?

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

An inconvenient fact

SEIR models → uncertain many parameters
New mutation - at best, noisy estimations
Incubation and recovery rates (µE , µRR ) are “easy”
Contagion rate λβp ?
Focus uncertainty on probability of contagion p

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Planning under uncertainty
Leave SEIR parameters fixed, except probability of contagion, p.
0.35
p = 0.03
p = 0.02
0.3

workforce shortage (%)

0.25

0.2

0.15

0.1

0.05

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Planning under uncertainty
Leave SEIR parameters fixed, except probability of contagion, p.
0.35
p = 0.015

0.3

workforce shortage (%)

0.25

0.2

0.15

0.1

0.05

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Planning under uncertainty
Leave SEIR parameters fixed, except probability of contagion, p.
0.35
p = 0.015
p = 0.015, 2*lambda at t = 10
0.3

workforce shortage (%)

0.25

0.2

0.15

0.1

0.05

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions
Limited availability

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions
Limited availability
Quantity

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions
Limited availability
QuantityTime

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions
Limited availability
QuantityTime

Can also get sick

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

2. Implementing a strategy

Bringing in surge staff - restrictions
Limited availability
QuantityTime

Can also get sickWhen is the surge strategy rolled out?

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

When does the surge commence?

Epidemic declared when growth rate of infectious > threshold

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

When does the surge commence?

Epidemic declared when growth rate of infectious > threshold

Assumption: Deploy strategy only after epidemic is declared

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

When does the surge commence?

Epidemic declared when growth rate of infectious > threshold

Assumption: Deploy strategy only after epidemic is declared

Assumption: Epidemic is correctly declared

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

A technical detail
Epidemics with different “p” declared at different times
0.35
p = 0.015
p = 0.02
p = 0.03
0.3

workforce shortage (%)

0.25

0.2

0.15

0.1

0.05

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

A technical detailthe planner’s perspective:

0.35
p = 0.015
p = 0.02
p = 0.03
0.3

workforce shortage (%)

0.25

0.2

0.15

0.1

0.05

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Results

A technical detailthe planner’s perspective:

0.35

0.35

p = 0.015
p = 0.02
p = 0.03

0.3

0.3

0.25

0.25
workforce shortage (%)

workforce shortage (%)

p = 0.015
p = 0.02
p = 0.03

0.2

0.15

0.2

0.15

0.1

0.1

0.05

0.05

0

0
0

2

4

6

8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50
time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

0

2

4

6

8

10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42
timeMotivation

Model

Robust Optimization

3. Quantifying the impact - Utilization measures
Total “social” cost: sum of per day costs
Two specific settings:

zt

Min workforce level to operatem - threshold

1

m

N

Cost =

1X% av. workforce at tztt
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Results

3. Quantifying the impact - Utilization measures
Total “social” cost: sum of per day costs
Two specific settings:
Queueing theory
System utilization ρtzt

exp(ρt)

Min workforce level to operatem - threshold

1

m

N

Cost =

1X% av. workforce at tztt
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

av. workforce at t

Cost =Xt+e K (ρt −1) − 1

Motivation

Model

Robust Optimization

Results

3. Quantifying the impact - Utilization measures
Total “social” cost: sum of per day costs
Two specific settings:
Queueing theory
System utilization ρt
cost

zt

Min workforce level to operatem - threshold

1

m

N

1

% av. workforce at t

Convex piecewise-linear functions
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

av. workforce at t

Motivation

Model

Robust Optimization

F First Optimization Model

Assumption: Size of surge staff corps is small relative topopulation; so staff deployment does not alter epidemic
Key modeling variables:∀ time periods t 0 > t, the quantities of surge staff thatare first deployed at time t, andare susceptible, or exposed, or infected at time t 0

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F First Optimization ModelV (h|p) := impact of epidemic under strategy h, given prob ofcontagion p

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F First Optimization ModelV (h|p) := impact of epidemic under strategy h, given prob ofcontagion p
Robust Optimization Problem
V ∗ = min max V (h|p)
h∈H p∈P

Objective: Strategy resilient against all scenariosH ← set of feasible surge strategies
P ← uncertainty set

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Some formulation details

at time t, variable at = total number of available staff= original staff, non-infective at time t (known from SEIR model)+ surge staff, non-infective at time t

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Some formulation details

at time t, variable at = total number of available staff= original staff, non-infective at time t (known from SEIR model)+ surge staff, non-infective at time t
use SEIR equations to keep track of the latter: linear for fixed p

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Discrete time SEIR model applied to surge staff
For each given time t 0 , track of condition of staff deployed at t 0 :ht0 : quantity deployed at t 0
sst,t0 : quantity deployed at t 0 and susceptible at t,
est,t0 : quantity deployed at t 0 and exposed at t,
sts0 ,t 0= ht 0and for all t 0 ≤ t < t 0 + K ,sst+1,t0s−λs ∗βt ∗p= st,t0eset+1,t0s−µss−λj ∗βt ∗p= et,t+ st,t)0e
0 (1 − eBienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Some formulation details

at time t, variable at = total number of available staff= original staff, non-infective at time t (known from SEIR model)+ surge staff, non-infective at time t
use SEIR equations to keep track of the latter: linear for fixed p

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Some formulation details

at time t, variable at = total number of available staff= original staff, non-infective at time t (known from SEIR model)+ surge staff, non-infective at time t
use SEIR equations to keep track of the latter: linear for fixed p
Likewise, constraints to keep track of (convex) costs are linear

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example:f (z) = piecewise-linear increasing function of z

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example:f (z) = piecewise-linear increasing function of z
we pay for shortage of staff below threshold θt

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example:f (z) = piecewise-linear increasing function of z
we pay for shortage of staff below threshold θt
So cost = κt = f ((θt − at )+ )Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example:f (z) = piecewise-linear increasing function of z
we pay for shortage of staff below threshold θt
So cost = κt = f ((θt − at )+ )So: constraint: Γt ≥ θt − at , variable Γt ≥ 0,

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example:f (z) = piecewise-linear increasing function of z
we pay for shortage of staff below threshold θt
So cost = κt = f ((θt − at )+ )So: constraint: Γt ≥ θt − at , variable Γt ≥ 0,and constraint: κt ≥ si Γt + bi ,for 1 ≤ i ≤ It (si ≥ 0 for all i)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) :Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP
p fixed → we know trajectory of epidemic

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP
p fixed → we know trajectory of epidemic
SEIR equations linear for fixed p

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP
p fixed → we know trajectory of epidemic
SEIR equations linear for fixed p
So constraints that keep track of available staff and cost are linear

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP
p fixed → we know trajectory of epidemic
SEIR equations linear for fixed p
So constraints that keep track of available staff and cost are linear

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

F Summary: First Optimization model
V (h|p) : (given p) can be formulated as an LP
p fixed → we know trajectory of epidemic
SEIR equations linear for fixed p
So constraints that keep track of available staff and cost are linear

V (h|p) := min
s.t.

cT x
Ap x = h(SEIR eqs)

Cp x ≥ dp(piecewise-linear approx)x ≥ 0,x ∈ H

x ← groups SE (IR) + objective function aux. variables
H ← set of feasible strategies

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Solving the problem
Our problem:
V ∗ = min max V (h|p)
h∈H p∈P(An infinite LP.) How to solve?

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Solving the problem
Our problem:
V ∗ = min max V (h|p)
h∈H p∈P(An infinite LP.) How to solve?
(Today) Approximate model: use finite Q ⊂ P
V ∗ ≈ min
s.t.

cT x
Ap x = h,∀p ∈ QCp x ≥ dp , ∀p ∈ Qh∈H
x ≥0Example: P = [0.01, 0.013],
Q = subset of P at integral multiples of 0.0001
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Theoretical justification

Suppose we know that p ≥ p0 > 0.
For each epsilon > 0 small enough there is a δ = O() s.t.:
If |p − p0 | < δ then V(h|p0 ) ≤ (1 + )V(h|p) for any hBienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Benders’ Decomposition
Generalized Benders’ Decomposition

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Benders’ Decomposition
Generalized Benders’ Decomposition
Optimization problemV∗==

min max V (h|p)
h∈H p∈P

min z

z,h∈H

s.t.

z ≥ V (h|p) ∀ p ∈ P

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Benders’ Decomposition
Generalized Benders’ Decomposition
Idea: replace V (h|p) by cuts obtained from the dual
Optimization problemV∗==

min max V (h|p)
h∈H p∈P

min z

z,h∈H

s.t.

z ≥ αpT h + πpT dp , (dual ∀p ∈ P)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Benders’ Decomposition
Generalized Benders’ Decomposition
Idea: replace V (h|p) by cuts obtained from the dual
ApproximationV∗≈ min max V (h|p)
h∈H p∈P

=

min z

z,h∈H

s.t.

z ≥ αpT h + πpT dp , (dual ∀p ∈ Q)

Q is a relatively small subset of P - so separation problem is fast

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Basic Algorithm

Iterate:1

Solve Master Problem; let ĥ be the computed surge and ẑ
be the estimate of its worst-case cost.

2

Sample: compute the worst-case data realization for ĥ.

3

If the cost of ĥ under this resolution is at most ẑ, STOP.

4

Otherwise, add to the master a duality cut violated by ĥ, ẑ,and goto 1.

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Algorithmic enhancements“Powers of two” approximation to finite grid

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Algorithmic enhancements“Powers of two” approximation to finite grid“Pre-Benders”’ cuts

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Alternative Optimization Problem 1

Intervals or tranches I1 , . . . I1 of [0, 1]; a time period J
At time = 1, it is known that p ∈ I1 .
At time J there is a switch. For t ≥ J, p ∈ Ih (known at t = J)
Decision maker:
Rolls out a surge at t = 1 that covers periods 1 ≤ t < J,
At t = 1 announces m surge plans to cover periods J ≤ t ≤ T
At time = J, switches to one of the announced plans

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Alternative Optimization Problem 2

There is a known interval I such that pt ∈ I for all t J
At time = t, pt = µ + δt , and is observed
Here µ = midpoint of I , and δt = zero mean stochastic, small
Decision maker:
At time 1, announces “expected” surge quantities ht for all t, and amultiplier λ ≥ 0PAt time t, corrects ht by λj<t (pt −µ)t(up to a maximum allowable)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

More general uncertainty sets
Flexible algorithm - more general uncertainty sets

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

More general uncertainty sets
Flexible algorithm - more general uncertainty sets
Sudden weather changes [Lowen et al, 2007]
Public Health measures could change course of epidemic
Daily cumulative incidence
Flu epidemic ‐ San Francisco
100%
90%

Cumulative Inciidence

80%
70%
60%
50%
40%
30%
20%
10%
0%
1

4

7

10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61
Time (days)

SanFranpcont = 0.18

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

pcont = 0.2

pcont = 0.194

Results

Motivation

Model

Robust Optimization

More general uncertainty sets
Flexible algorithm - more general uncertainty sets
Sudden weather changes [Lowen et al, 2007]
Public Health measures could change course of epidemic
Analyze the impact of multiple values of p during 1 epidemic
Daily cumulative incidence
Flu epidemic ‐ San Francisco
100%
90%

Cumulative Inciidence

80%
70%
60%
50%
40%
30%
20%
10%
0%
1

4

7

10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61
Time (days)

SanFranpcont = 0.18

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

pcont = 0.2

pcont = 0.194

Results

Motivation

Model

Robust Optimization

Numerical example
Demography
Size
Initial infected
Contact rates (per day)Incubation rate (µE)
Removal rate (µR)
Survival prob (f)General Population

High Risk Population

900,000
5
30
10/19
10/41
1

20,000
0
35
10/19
10/41
1

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Numerical example
Demography
Size
Initial infected
Contact rates (per day)Incubation rate (µE)
Removal rate (µR)
Survival prob (f)General Population

High Risk Population

900,000
5
30
10/19
10/41
1

20,000
0
35
10/19
10/41
1

Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Numerical example
Demography
Size
Initial infected
Contact rates (per day)Incubation rate (µE)
Removal rate (µR)
Survival prob (f)General Population

High Risk Population

900,000
5
30
10/19
10/41
1

20,000
0
35
10/19
10/41
1

Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}

Pool of surge staff
Up to 3,000 staff
Stay up to 1 week

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Numerical example
Demography
Size
Initial infected
Contact rates (per day)Incubation rate (µE)
Removal rate (µR)
Survival prob (f)General Population

High Risk Population

900,000
5
30
10/19
10/41
1

20,000
0
35
10/19
10/41
1

Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}

Pool of surge staff
Up to 3,000 staff
Stay up to 1 week

Social Contact Model
Non-homogeneous contact
Contact rate decreases 30% when epidemic is declared
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Comparisons:

Do nothing at all (how bad is the “worst” epidemic?)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Comparisons:

Do nothing at all (how bad is the “worst” epidemic?)

Naı̈ve Worst-Case planning: prepare for the data realizationthat is most expensive in the “do nothing” case

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Comparisons:

Do nothing at all (how bad is the “worst” epidemic?)

Naı̈ve Worst-Case planning: prepare for the data realizationthat is most expensive in the “do nothing” case

The robust strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

No surge staff deployment
Most costly data realization: (p1 , p2 , d) = (0.0109, 0.0135, 140)
Cost: 4.58
1.05
1

ρ

0.95
0.9
0.85
0.8

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0.75
Time from declaration of epidemicρ (No Interv); Cost = 4.58

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

ρ*Results

Motivation

Model

Robust Optimization

Results

Same data realization, but using Robust Strategy(p1 , p2 , d) = (0.0109, 0.0135, 140)
Cost: 0.0495
1.05
600
500
400

0.9

300

0.85

200

0.8

100

0.75

0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

ρ

0.95

Time from declaration of epidemicρ (Robust); Cost = 0.0495

ρ (No Interv); Cost = 4.58

ρ*Robust Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Procurement Strategy

1Motivation

Model

Robust Optimization.. and using Naı̈ve Worst-Case Strategy(p1 , p2 , d) = (0.0109, 0.0135, 140),

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Results.. and using Naı̈ve Worst-Case Strategy(p1 , p2 , d) = (0.0109, 0.0135, 140), Cost: 0
1.05
600
500
400

0.9

300

0.85

200

0.8

100

0.75

0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

ρ

0.95

Time from declaration of epidemicρ (Worst‐Scen); Cost = 0

ρ (No Interv); Cost = 4.58

ρ*

Worst‐case Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Procurement Strategy

1Motivation

Model

Robust Optimization

Worst scenario, when played against the robust strategy:(p1 , p2 , d) = (0.01168, 0.0135, 140)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Worst scenario, when played against the robust strategy:(p1 , p2 , d) = (0.01168, 0.0135, 140)
Using this data realization, “do nothing” cost: 1.69
1.05
1

ρ

0.95
0.9
0.85
0.8

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0.75

Time from declaration of epidemicρ (No Interv); Cost =1.6938

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

ρ*Results

Motivation

Model

Robust Optimization

Results

Same data: (p1 , p2 , d) = (0.01168, 0.0135, 140)... against the Robust Strategy, Cost: 0.05
1.05

500
400

ρ

0.95

300
0.9
200
0.85

100
0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0.8
Time from declaration of epidemicρ (Robust); Cost = 0.05

ρ (No Interv); Cost = 1.43

ρ*Robust Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Procurement Strategy

6001Motivation

Model

Robust Optimization

Results

Same data: (p1 , p2 , d) = (0.01168, 0.0135, 140)... against “Naı̈ve Worst-Case” Strategy
Cost: 0.69
1.05

500
400

ρ

0.95

300
0.9
200
0.85

100
0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0.8
Time from declaration of epidemicρ (Worst‐Scen); Cost = 0.69

ρ (No Interv); Cost = 1.43

ρ*

Worst‐case Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Procurement Strategy

6001Motivation

Model

Robust Optimization

Results

Example - Comparing strategies

Scenario I
1.05

1.05

600

600

0.9

300

500
0.95
ρ

400

400

0.9

300

0.85

0.85

200

0.8

100

0.8

100

0.75

0

0.75

0

200

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

ρ

0.95

Procurement Strategy

500Time from declaration of epidemic

Time from declaration of epidemicρ (Robust); Cost = 0.0495

ρ (No Interv); Cost = 4.58

ρ (Worst‐Scen); Cost = 0

ρ (No Interv); Cost = 4.58

ρ*Robust Strategy

ρ*Worst‐case Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Procurement Strategy

11Motivation

Model

Robust Optimization

Results

Example - Comparing strategies

Scenario II
1.05

1.05

400

ρ

0.95

300
0.9
200
0.85

500
400

0.95
ρ

500

Procurement Strategy

1

1

300
0.9
200
0.85

100

100

0.8

0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0
1
7
13
19
25
31
37
43
49
55
61
67
73
79
85
91
97
103
109
115
121
127
133
139
145

0.8

Time from declaration of epidemic

Time from declaration of epidemicρ (Robust); Cost = 0.05

ρ (No Interv); Cost = 1.43

ρ*Robust Strategy

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

ρ (Worst‐Scen); Cost = 0.69

ρ (No Interv); Cost = 1.43

ρ*

Worst‐case Strategy

Procurement Strategy

600

600

Motivation

Model

Robust Optimization

Results

Example - Comparing strategies

No Intervention
No intervention:
worst tuple(0.01092, 0.0135, 140)
Robust Strategy:
worst tuple(0.01168, 0.0135, 140)
Worst‐case Strategy:
worst tuple(0.01172, 0.0135, 140)

Cost
Maximum ρ
Critical days ( ρ > 1)
Cost
Maximum ρ
Critical days ( ρ > 1)
Cost
Maximum ρ
Critical days ( ρ > 1)

4.581
1.002
28
1.694
1.024
21
1.430
1.021
20

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

RobustStrategy
0.050
1.048
8
0.052
1.003
7
0.050
1.002
8

Worst‐Case
Strategy
0.000
1.000
0
0.686
1.017
12
0.710
1.018
13

Motivation

Model

Robust Optimization

Results

Example - Comparing strategies
Take-away: Planning against most expensive scenario is notenough!

No Intervention
No intervention:
worst tuple(0.01092, 0.0135, 140)
Robust Strategy:
worst tuple(0.01168, 0.0135, 140)
Worst‐case Strategy:
worst tuple(0.01172, 0.0135, 140)

Cost
Maximum ρ
Critical days ( ρ > 1)
Cost
Maximum ρ
Critical days ( ρ > 1)
Cost
Maximum ρ
Critical days ( ρ > 1)

4.581
1.002
28
1.694
1.024
21
1.430
1.021
20

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

RobustStrategy
0.050
1.048
8
0.052
1.003
7
0.050
1.002
8

Worst‐Case
Strategy
0.000
1.000
0
0.686
1.017
12
0.710
1.018
13

Motivation

Model

Robust Optimization

Results

Example - Out-of-sample Analysis
Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}

p changes
timeepidemicdeclaredsurge staff
comes in

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Motivation

Model

Robust Optimization

Results

Example - Out-of-sample Analysis
Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}

p changes

p changes
timeepidemicdeclaredsurge staff
comes in

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Motivation

Model

Robust Optimization

Results

Example - Out-of-sample Analysis
Uncertainty set
P = [0.01, 0.012] × [0.0125, 0.0135]
p can change in days {140, ..., 160}
Worst case:(p1 , p2 , d) = (0.01168, 0.0135, 140)

Scenarios
p_1
p_2
day epidemic is declared
day deployment starts
day p changes

Original
0.01168
0.0135113
140
140

cost Robust Policy
cost No Intervention

0.0508
4.58

150

Worst case given Robust Policy
Hypothetical 1
0.01168
0.014
113
140
155
160
165‐
150

0.3268 0.07295
1.609
0.762

0
0.087

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013002.1737
4.133

Hypothetical 2
0.01168
0.015
113
140
155
160

1.40682.669

0.62821.243

165

0.02940.146

Motivation

Model

Robust Optimization

Example - Numeric Performance

350 days
max-cost tuple : grid search
VBA (UI) + C (SEIR) + AMPL (Gurobi solver)

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example - Numeric Performance

350 days
max-cost tuple : grid search
VBA (UI) + C (SEIR) + AMPL (Gurobi solver)∼ 175 iterations
5% duality gap∼ 15min CPU time

Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results

Motivation

Model

Robust Optimization

Example - Numeric Performance

350 days
max-cost tuple : grid search
VBA (UI) + C (SEIR) + AMPL (Gurobi solver)
Enhancement:
8 pre-Benders’ iterations + 1 Benders’ cut
Duality gap 0.0052%< 1 min CPU time
Bienstock, Zenteno | Robust Models of Epidemics | USC, 2013

Results