Operations Research Problems in PowerEngineering
Daniel Bienstock
Columbia University

2016

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

References
Andersson: Modelling and Analysis of Electric Power Systems
Bergen, Vittal: Power Systems Analysis
Glover, Sarma, Overbye: Power System Analysis and Design

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

References
Andersson: Modelling and Analysis of Electric Power Systems
Bergen, Vittal: Power Systems Analysis
Glover, Sarma, Overbye: Power System Analysis and Design
Rebours, Kirschen: What is spinning reserve?

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers
conductor
rotor

steam

statormagneticfieldωenergysourceBienstock
Operations Research Problems in Power Engineering

current, voltage

Columbia UniversityPower engineering for non-power engineers

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

conductor
rotor

steam

statormagneticfieldωenergysourcecurrent, voltage

A generator produces current at a certain voltage.

Bienstock
Operations Research Problems in Power Engineering

Columbia UniversityPower engineering for non-power engineers

conductor
rotor

steam

statormagneticfieldωenergysourcecurrent, voltage

A generator produces current at a certain voltage.
Ohm’s law: power = current x voltage

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Bienstock
Operations Research Problems in Power Engineering

Columbia University

AC Power Flows

Bienstock
Operations Research Problems in Power Engineering

Columbia University

AC Power Flows
Real-time:

Bienstock
Operations Research Problems in Power Engineering

Columbia University

AC Power Flows
Real-time:
i (t)
k

km

m

v (t)
k

Voltage at bus k: vk (t) = Vkmax cos(ωt + θkV )max cos(ωt + θ I ).
Current injected at k into km: ikm (t) = Ikm
km

Bienstock
Operations Research Problems in Power Engineering

Columbia University

AC Power Flows
Real-time:
i (t)
k

km

m

v (t)
k

Voltage at bus k: vk (t) = Vkmax cos(ωt + θkV )max cos(ωt + θ I ).
Current injected at k into km: ikm (t) = Ikm
km

Power injected at k into km: pkm (t) = vk (t)ikm (t).
Averaged over period T :RT.
max cos(θ V − θ I ).
pkm = T1 0 p(t) = 12 Vkmax Ikm
kkm

Bienstock
Operations Research Problems in Power Engineering

Columbia University

i (t)
k

km

m

v (t)
k

.
pkm =

1
T

RT
0

p(t) =

Bienstock
Operations Research Problems in Power Engineering

1 max maxI )Ikm cos(θkV − θkm
2 Vk

Columbia University

i (t)
k

km

m

v (t)
k

.
pkm =

1
T

RT
0

p(t) =

1 max maxI )Ikm cos(θkV − θkm
2 Vk
Vvk (t) = Vkmax Re e j(ωt+θk ) ,Bienstock
Operations Research Problems in Power EngineeringI

max Re e j(ωt+θkm )
ikm (t) = Ikm

Columbia University

i (t)
k

km

m

v (t)
k

.
pkm =

1
T

RT
0

p(t) =

1 max maxI )Ikm cos(θkV − θkm
2 Vk
Vvk (t) = Vkmax Re e j(ωt+θk ) ,. Vkmax jθkV
Vk = √e ,2

Bienstock
Operations Research Problems in Power EngineeringI

max Re e j(ωt+θkm )
ikm (t) = Ikm
max
I
. Ikm
Ikm = √
e jθmk2

Columbia University

i (t)
k

km

m

v (t)
k

.
pkm =

1
T

RT
0

p(t) =

1 max maxI )Ikm cos(θkV − θkm
2 Vk
Vvk (t) = Vkmax Re e j(ωt+θk ) ,. Vkmax jθkV
Vk = √e ,2I

max Re e j(ωt+θkm )
ikm (t) = Ikm
max
I
. Ikm
Ikm = √
e jθmk2I ) = Re(V I ∗ )pkm = |Vk ||Ikm | cos(θkV − θkm
k km

Bienstock
Operations Research Problems in Power Engineering

Columbia University

i (t)
k

km

m

v (t)
k

.
pkm =

1
T

RT
0

p(t) =

1 max maxI )Ikm cos(θkV − θkm
2 Vk
Vvk (t) = Vkmax Re e j(ωt+θk ) ,. Vkmax jθkV
Vk = √e ,2I

max Re e j(ωt+θkm )
ikm (t) = Ikm
max
I
. Ikm
Ikm = √
e jθmk2I ) = Re(V I ∗ )pkm = |Vk ||Ikm | cos(θkV − θkm
k km

.
∗ )
qkm = Im(Vkm Ikm.
and Skm = pkm + jqkm

Bienstock
Operations Research Problems in Power Engineering

Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),

Bienstock
Operations Research Problems in Power Engineering∗qkm = Im(Vkm Ikm)(1)

Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),∗
qkm = Im(Vkm Ikm)(1)

Ikm = y{k,m} (Vk − Vm ),Bienstock
Operations Research Problems in Power Engineering

Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),∗
qkm = Im(Vkm Ikm)(1)

Ikm = y{k,m} (Vk − Vm ), y{k,m} = admittance of km.

Bienstock
Operations Research Problems in Power Engineering(2)

Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),∗
qkm = Im(Vkm Ikm)(1)

Ikm = y{k,m} (Vk − Vm ), y{k,m} = admittance of km.

(2)

Network EquationskBienstock
Operations Research Problems in Power Engineering

Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),∗
qkm = Im(Vkm Ikm)(3)

Ikm = y{k,m} (Vk − Vm ), y{k,m} = admittance of km.

(4)

Network EquationsX

pkm = P̂k ,km∈δ(k)Bienstock
Operations Research Problems in Power EngineeringXqkm = Q̂k∀k

(5)km∈δ(k)Columbia University

. V max V
Vk = √k 2 e jθk ,

max
I
. Ikm
e jθmk (voltage, current)
Ikm = √
2∗
pkm = Re(Vk Ikm),∗
qkm = Im(Vkm Ikm)(3)

Ikm = y{k,m} (Vk − Vm ), y{k,m} = admittance of km.

(4)

Network EquationsX

pkm = P̂k ,km∈δ(k)X

qkm = Q̂k∀k

(5)km∈δ(k)Generator: P̂k , |Vk | given. Other buses: P̂k , Q̂k given.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Bienstock
Operations Research Problems in Power Engineering

Columbia University

What happens when there is a generation/load mismatch
conductor
rotor

steam

statormagneticfieldωenergysourceBienstock
Operations Research Problems in Power Engineering

current, voltage

Columbia University

What happens when there is a generation/load mismatch
conductor
rotor

steam

statormagneticfieldωenergysourcecurrent, voltage

Frequency response:

Bienstock
Operations Research Problems in Power Engineering

Columbia University

What happens when there is a generation/load mismatch
conductor
rotor

steam

statormagneticfieldωenergysourcecurrent, voltage

Frequency response:
mismatch ∆P
Bienstock
Operations Research Problems in Power Engineering

Columbia University

What happens when there is a generation/load mismatch
conductor
rotor

steam

statormagneticfieldωenergysourcecurrent, voltage

Frequency response:
mismatch ∆P ⇒ frequency change ∆ω ≈ −c ∆P
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds. Agent: algorithms, pre-set controls.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds. Agent: algorithms, pre-set controls.

3“Tertiary” control: OPF (Optimal power flow). Manages
longer lasting changes. Run every few minutes. Goal:
economic generation that meets demands while maintaining
feasibility (stability).

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds. Agent: algorithms, pre-set controls.

3“Tertiary” control: OPF (Optimal power flow). Manages
longer lasting changes. Run every few minutes. Goal:
economic generation that meets demands while maintaining
feasibility (stability). Agent: algorithmic computations,humans.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds. Agent: algorithms, pre-set controls.

3“Tertiary” control: OPF (Optimal power flow). Manages
longer lasting changes. Run every few minutes. Goal:
economic generation that meets demands while maintaining
feasibility (stability). Agent: algorithmic computations,humans.

4

Once (?) a day: unit commitment problem. Chooses which
generators will operate in the next day or half-day.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Managing changing demands
1

Primary frequency control. Handles instantaneous (small)changes. Agent: physics.

2

Secondary control. Handles changes that span more than afew seconds. Agent: algorithms, pre-set controls.

3“Tertiary” control: OPF (Optimal power flow). Manages
longer lasting changes. Run every few minutes. Goal:
economic generation that meets demands while maintaining
feasibility (stability). Agent: algorithmic computations,humans.

4

Once (?) a day: unit commitment problem. Chooses which
generators will operate in the next day or half-day. Agent:algorithms, humans.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Bienstock
Operations Research Problems in Power Engineering

Columbia University

CIGRE -International Conference on Large High Voltage
Electric Systems ’09
Large unexpected fluctuations in wind power can cause
additional flows through the transmission system (grid)
Large power deviations in renewables must be balanced byother sources, which may be far away
Flow reversals may be observed – control difficult
A solution – expand transmission capacity! Difficult(expensive), takes a long time
Problems already observed when renewable penetration high

Bienstock
Operations Research Problems in Power Engineering

Columbia University

CIGRE -International Conference on Large High Voltage
Electric Systems ’09“Fluctuations” – 15-minute timespanDue to turbulence (“storm cut-off”)
Variation of the same order of magnitude as mean
Most problematic when renewable penetration starts toexceed 20 − 30%
Many countries are getting into this regime

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Optimal power flow (economic dispatch, tertiary control)

Used periodically to handle the next time window(e.g. 15 minutes, one hour)
Choose generator outputs
Minimize cost (quadratic)
Satisfy demands, meet generator and network constraints
Constant load (demand) estimates for the time window
Bienstock
Operations Research Problems in Power Engineering

Columbia University

OPF:
min c(p)(a quadratic)s.t.
Bθ = p − d|yij (θi − θj )| ≤ uij
Pgmin ≤ pg ≤ Pgmax(6)for each line ij(7)for each bus g(8)Notation:p = vector of generations ∈ Rn ,
n×n

B ∈R
∀i, j :

d = vector of loads ∈ Rn,(bus susceptance matrix)ij ∈ E (set of lines)
 P −yij ,
y
,
i =j
Bij =
kj
k;{k,j}∈E0,otherwise

Bienstock
Operations Research Problems in Power Engineering

Columbia University

min c(p)(a quadratic)s.t.
Bθ = p − d|yij (θi − θj )| ≤ uijmin

Pg

Bienstock
Operations Research Problems in Power Engineeringmax≤ p g ≤ Pg

for each line ij
for each bus g

Columbia University

min c(p)(a quadratic)s.t.
Bθ = p − d|yij (θi − θj )| ≤ uij
min

Pg

max

≤ p g ≤ Pg

for each line ij
for each bus g

How does the grid handle short-term fluctuations in demand (d)?
Secondary frequency control:
Deployed a few seconds after ongoing change – “minute-by-minute”
control
Generator output varies up or down proportionally to aggregatechangeBienstock
Operations Research Problems in Power Engineering

Columbia University

min c(p)(a quadratic)s.t.
Bθ = p − d|yij (θi − θj )| ≤ uij
min

Pg

max

≤ p g ≤ Pg

for each line ij
for each bus g

How does the grid handle short-term fluctuations in demand (d)?
Secondary frequency control:
Deployed a few seconds after ongoing change – “minute-by-minute”
control
Generator output varies up or down proportionally to aggregatechangeHow does the grid handle short-term fluctuations in renewable output?
Answer: Same mechanism, now used to handle aggregate wind powerchangeBienstock
Operations Research Problems in Power Engineering

Columbia University

“Participation factors”
For each generator i, a parameter αi with
Pi αi = 1αi ≥ 0αi > 0 only for selected generators
Assuming real-time generation/demand mismatch ∆, real-time
output of generator i:pi = p i − α i ∆where p i = OPF computed output for generator i.
Note: the αi are precomputed e.g. uniform or based on economic
considerations.
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Experiment
Bonneville Power Administration data, Northwest US
data on wind fluctuations at planned farms
with standard OPF, 7 lines exceed limit ≥ 8% of the time

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Wind model?

Need to model variation in wind power between dispatchesWind at farm attached to bus i of the form µi + wi . Weibull
distribution?

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Wind model

Typical wind farm spans a significant geographical zone withmany turbines

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Wind model

Typical wind farm spans a significant geographical zone withmany turbines
Real-time variations due to turbulence

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Wind model

Typical wind farm spans a significant geographical zone withmany turbines
Real-time variations due to turbulence
Turbulence is local (≈ 50m radius) and arguably local effects
are indepenent

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Wind model

Typical wind farm spans a significant geographical zone withmany turbines
Real-time variations due to turbulence
Turbulence is local (≈ 50m radius) and arguably local effects
are indepenent
Working model: real-time variations in a farm’s output
modeled as a normal variable

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Line limits and line tripping

If power flow in a line exceeds its limit, the line becomes compromised
and may ’trip’. But process is complex and time-averaged:
Thermal limit is most common
Thermal limit may be in terms of terminal equipment, not line itself
Wind strength and wind direction contributes to line temperature
IEEE Standard 738 attempts to account for everything
In 2003 U.S. blackout event, many critical lines tripped due tothermal reasons, but well short of their line limit

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Background

When a power line overheats it becomes exposed to several
risk factors

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Background

When a power line overheats it becomes exposed to several
risk factors
If the line overheats enough, it may sag and experience a
contact/arc, which will cause a trip
If overheating is detected, and is deemed risky, the line will
may be preemptively tripped

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Background

When a power line overheats it becomes exposed to several
risk factors
If the line overheats enough, it may sag and experience a
contact/arc, which will cause a trip
If overheating is detected, and is deemed risky, the line will
may be preemptively tripped
What is risky?

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Background

When a power line overheats it becomes exposed to several
risk factors
If the line overheats enough, it may sag and experience a
contact/arc, which will cause a trip
If overheating is detected, and is deemed risky, the line will
may be preemptively tripped
What is risky? What is a critical temperature?

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Background

When a power line overheats it becomes exposed to several
risk factors
If the line overheats enough, it may sag and experience a
contact/arc, which will cause a trip
If overheating is detected, and is deemed risky, the line will
may be preemptively tripped
What is risky? What is a critical temperature?
2003 event: critical temperatures estimates were sometimes
incorrect.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line,

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for:

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor,

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day),

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day), density andviscosity of air,Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day), density andviscosity of air, several other factors.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day), density andviscosity of air, several other factors.
It also relies on the heat equation for a “static” calculation.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day), density andviscosity of air, several other factors.
It also relies on the heat equation for a “static” calculation.
Note: power lines can be more than 100 miles long.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

IEEE Standard 738
A comprehensive method for determining the temperature ofa power line, as a function of current and pause physicalproperties of the conductor .
It attempts to account for: wind, and ambient temperature,
day of the year, latitude and longitude, angle between windand conductor, altitude of sun (and time of day), density andviscosity of air, several other factors.
It also relies on the heat equation for a “static” calculation.
Note: power lines can be more than 100 miles long.
How can we account for data uncertainty, errors,
unavailability?
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Line trip modelsummary: exceeding limit for too long is bad, but complicatedwant: ”fraction time a line exceeds its limit is small”
proxy: prob(violation on line i) <  for each line i

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Goalssimple control
aware of limits
not too conservative
computationally practicable with a simple algorithm

Bienstock
Operations Research Problems in Power Engineering

Columbia University

ControlFor each generator i, two parameters:pi = risk-aware mean output
αi = risk-aware participation factor
Real-time output of generator i:pi = p i − α i

X

∆ωj

j

where ∆ωj = change in output of renewable j (from mean).
Xαi = 1iBienstock
Operations Research Problems in Power Engineering

Columbia University

Set up
control

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Computing line flows

wind power at bus i: µi + wi
DC approximationBθ = p − d P+(µ + w − α i∈G wi )
θ = B + (p̄ − d + µ) + B + (I − αe T )w
flow is a linear combination of bus power injections:fij = yij (θi − θj )Bienstock
Operations Research Problems in Power Engineering

Columbia University

Computing line flows
fij = yij(Bi+ − Bj+ )T (p̄ − d + µ) + (Ai − Aj )T w

,

A = B + (I − αe T )Given distribution of wind can calculate moments of line flows:
E fij = yij (Bi+ − Bj+ )T (p̄ − d + µ)P
var (fij ) := sij2 ≥ yij2 k (Aik − Ajk )2 σk2(assuming independence)and higher moments if necessary
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Chance constraints to deterministic constraints

chance constraint: P(fij > fijmax ) < ij and P(fij < −fijmax ) < ijfrom moments of fij , can get conservative approximations using e.g.
Chebyshev’s inequality

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Chance constraints to deterministic constraints

chance constraint: P(fij > fijmax ) < ij and P(fij < −fijmax ) < ijfrom moments of fij , can get conservative approximations using e.g.
Chebyshev’s inequality
for Gaussian wind, can do better, since fij is Gaussian :|E fij | + var (fij )φ−1 (1 − ij ) ≤ fijmax

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Formulation:
Choose mean generator outputs and control to minimize expected cost,with the probability of line overloads kept small.
min E[c(p)]
p,α
X
s.t.
αi = 1, α ≥ 0i∈GBδ = α, δn = 0
X
X
X
pi +
µi =
di
i∈G

i∈W

i∈D

f ij = yij (θi − θj ),Bθ = p + µ − d, θn = 0
X
sij2 ≥ yij2σk2 (Bik+ − Bjk+ − δi + δj )2k∈W|f ij | + sij φ−1 (1 − ij ) ≤ fijmax

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Big cases

Polish 2003-2004 winter peak case2746 buses, 3514 branches, 8 wind sources
5% penetration and σ = .3µ each source
CPLEX: the optimization problem has
36625 variables
38507 constraints, 6242 conic constraints
128538 nonzeros, 87 dense columns

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Big cases

Polish 2003-2004 winter peak case2746 buses, 3514 branches, 8 wind sources
5% penetration and σ = .3µ each source
CPLEX: the optimization problem has
36625 variables
38507 constraints, 6242 conic constraints
128538 nonzeros, 87 dense columns

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Big cases
CPLEX:
total time on 16 threads = 3393 seconds”optimization status 6”
solution is wildly infeasible
Gurobi:time: 31.1 seconds”Numerical trouble encountered”

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Big cases
CPLEX:
total time on 16 threads = 3393 seconds”optimization status 6”
solution is wildly infeasible
Gurobi:time: 31.1 seconds”Numerical trouble encountered”→ basic cutting-plane algorithm works well

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Experiment: Polish grid, 20% wind penetration, 50 farms

Overload
Probability
Overload
Probability

0.001370.50

0.001360.15

0.00135
0.09

Standard OPF

0.06

0.00030

Chance−constrained OPF

0.00006

0.04

0.00003

0.03

0.00002

0.02# of lines# of lines
0

1

2

3

4

5

0

1

2

3

4

5

Bienstock, Chertkov, Harnett, SIAM Review ’15

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Extensions and Ongoing work

Account for errors in estimations of distribution

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Extensions and Ongoing work

Account for errors in estimations of distribution
Account for correlations (spatial and timewise)

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Extensions and Ongoing work

Account for errors in estimations of distribution
Account for correlations (spatial and timewise)
Extension to unit commitment problem

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Extensions and Ongoing work

Account for errors in estimations of distribution
Account for correlations (spatial and timewise)
Extension to unit commitment problem
Better risk model for line temperature
Bienstock, Blanchet and Li ’15

Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Line modeled as one-dimensional object parameterized by x,
0 ≤ x ≤ L.
Time domain: [0, τ ]Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Line modeled as one-dimensional object parameterized by x,
0 ≤ x ≤ L.
Time domain: [0, τ ] (for example: OPF intervals)

Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Line modeled as one-dimensional object parameterized by x,
0 ≤ x ≤ L.
Time domain: [0, τ ] (for example: OPF intervals)
I (t) = current at time t, T (x, t) = temperature at x at time t.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Line modeled as one-dimensional object parameterized by x,
0 ≤ x ≤ L.
Time domain: [0, τ ] (for example: OPF intervals)
I (t) = current at time t, T (x, t) = temperature at x at time t.
Heat equation:∂T (x, t)∂ 2 T (x, t)=κ+ αI 2 (t) − ν(T (x, t) − T ext (x, t)),∂t
∂x 2
where κ ≥ 0, α ≥ 0 and ν ≥ 0 are (line dependent) constants, andT ext (x, t) is the ambient temperature at (x, t)

Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Heat equation:∂T (x, t)∂ 2 T (x, t)=κ+ αI 2 (t) − ν(T (x, t) − T ext (x, t)).
∂t∂x 2

Bienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Heat equation:∂T (x, t)∂ 2 T (x, t)=κ+ αI 2 (t) − ν(T (x, t) − T ext (x, t)).
∂t
∂x 2IEEE 738, other authors:∂T (x, t)= αI 2 (t) − ν(T (x, t) − T ext (x, t)).
∂tUs:

∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂tBienstock
Operations Research Problems in Power Engineering

Columbia University

The heat equation on a 1-dimensional line
Heat equation:∂T (x, t)∂ 2 T (x, t)=κ+ αI 2 (t) − ν(T (x, t) − T ext (x, t)).
∂t
∂x 2IEEE 738, other authors:∂T (x, t)= αI 2 (t) − ν(T (x, t) − T ext (x, t)).
∂tUs:

∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂th(x) = a random variable, at x.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Bienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, get
1
L

Z L
0

∂T (x, t)νdx = αI 2 (t) −∂tLBienstock
Operations Research Problems in Power EngineeringZ L

νT (x, t)dx +L
0Z L
G (h(x))dx.
0Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, get
1
L

Z L
0

∂T (x, t)νdx = αI 2 (t) −
∂t
L
1
L

Z L
0

Z L

ν
T (x, t)dx +L
0Z L
G (h(x))dx.
0∂T (x, t)dx =∂tBienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, get
1
L

Z L
0

∂T (x, t)νdx = αI 2 (t) −
∂t
L
1
L

H(t) ,

Z L
0

1
L

d 1
∂T (x, t)
dx =
dt L
∂t

Z L

ν
T (x, t)dx +L
0Z L
T (x, t)dx =0Z L
G (h(x))dx.
0

dH(t)
.
dt

Z L
T (x, t)dx

(average internal line temperature at t)

0

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, getνdH(t)= αI 2 (t) − νH(t) +
dt
L
1
R,
L

Z L
G (h(x))dx.
0

Z L
G (h(x))dx(average ambient temperature,0

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, getνdH(t)= αI 2 (t) − νH(t) +
dt
L
1
R,
L

Z L
G (h(x))dx.
0

Z L
G (h(x))dx(average ambient temperature, random!)0

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Back to the stochastic heat equation∂T (x, t)= αI 2 (t) − ν(T (x, t) − G (h(x)).
∂t
Recall: x ∈ [0, L], t ∈ [0, τ ]Integrate and divide by L, getνdH(t)= αI 2 (t) − νH(t) +
dt
L
1
R,
L

Z L
G (h(x))dx.
0

Z L
G (h(x))dx(average ambient temperature, random!)

0

dH(t)
= αI 2 (t) − νH(t) + νR.
dt
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Once moredH(t)= αI 2 (t) − νH(t) + νR.
dt
H(t) ,

1

Z L

L

0

T (x, t)dx,

Bienstock
Operations Research Problems in Power Engineering

R ,

1

Z L

L

0

G (h(x))dx,

Columbia University

Once moredH(t)= αI 2 (t) − νH(t) + νR.
dt
H(t) ,

1

Z L

L

0

T (x, t)dx,

R ,

1

Z L

L

0

G (h(x))dx,

Solution:
Z t
H(t)

=

e −ν(t−s) αI 2 (s)ds + R(1 − e −νt ) + Ce −νt ,

0

where
C = H(0) =Bienstock
Operations Research Problems in Power Engineering

1
L

Z L
T (x, 0)dx.
0Columbia University

Once moredH(t)= αI 2 (t) − νH(t) + νR.
dt
H(t) ,

1

Z L

L

0

T (x, t)dx,

R ,

1

Z L

L

0

G (h(x))dx,

Solution:
Z t
H(t)

=

e −ν(t−s) αI 2 (s)ds + R(1 − e −νt ) + Ce −νt ,

0

where
C = H(0) =

1
L

Z L
T (x, 0)dx.
0Control goal: make I (t) “large”,
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Once moredH(t)= αI 2 (t) − νH(t) + νR.
dt
H(t) ,

1

Z L

L

0

T (x, t)dx,

R ,

1

Z L

L

0

G (h(x))dx,

Solution:
Z t
H(t)

=

e −ν(t−s) αI 2 (s)ds + R(1 − e −νt ) + Ce −νt ,

0

where
C = H(0) =

1
L

Z L
T (x, 0)dx.
0Control goal: make I (t) “large”, but with P maxt∈[0,τ ] H(t) > k ≤ Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νtBienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νt
So, H 0 (t) > 0 for I¯ large enough,Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νt
So, H 0 (t) > 0 for I¯ large enough, (and of constant sign for any I¯).

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νt
So, H 0 (t) > 0 for I¯ large enough, (and of constant sign for any I¯).

So, P maxt∈[0,τ ] H(t) > k ≤  equivalent to P(H(τ ) > k) ≤ .

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νt
So, H 0 (t) > 0 for I¯ large enough, (and of constant sign for any I¯).

So, P maxt∈[0,τ ] H(t) > k ≤  equivalent to P(H(τ ) > k) ≤ .
Solution:I¯2≤

ν k − Ce −ντ − ρ (1 − e −ντ )α
1 − e −ντ

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Constant control: I (t) = I¯, for all t ∈ [0, τ ]
Z t
H(t)

=

e

−ν(t−s)2αI¯ (s)ds + R(1 − e−νt) + Ce

−νt

,

0

where
C = H(0) =

1

Z L

L

0

T (x, 0)dx.

Constant current ⇒ H(t) = ( αν I¯2 + R)(1 − e −νt ) + Ce −νt
So, H 0 (t) > 0 for I¯ large enough, (and of constant sign for any I¯).

So, P maxt∈[0,τ ] H(t) > k ≤  equivalent to P(H(τ ) > k) ≤ .
Solution:I¯2≤

ν k − Ce −ντ − ρ (1 − e −ντ )= L(τ, k)α
1 − e −ντ

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:
2. For all t ∈ [0, τ /2], we set I (t) = I1 .

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:
2. For all t ∈ [0, τ /2], we set I (t) = I1 .
3. At time τ /2, we observe the value of R. Assuming R = ri , thenfor all t ∈ [τ /2, τ ], we set I (t) = I2,i .
Goals:(a) P(H(τ ) > k) < .

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:
2. For all t ∈ [0, τ /2], we set I (t) = I1 .
3. At time τ /2, we observe the value of R. Assuming R = ri , thenfor all t ∈ [τ /2, τ ], we set I (t) = I2,i .
Goals:(a) P(H(τ ) > k) < .

k smaller than critical temperature(b) I1 ≤ L(τ /2).

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:
2. For all t ∈ [0, τ /2], we set I (t) = I1 .
3. At time τ /2, we observe the value of R. Assuming R = ri , thenfor all t ∈ [τ /2, τ ], we set I (t) = I2,i .
Goals:(a) P(H(τ ) > k) < .

k smaller than critical temperature(b) I1 ≤ L(τ /2).
(c) What about performance?
Bienstock
Operations Research Problems in Power Engineering

Columbia University

We want to maximize:“Total” current:τ
2 I1

Bienstock
Operations Research Problems in Power Engineering+ τ2 I2,i?

Columbia University

We want to maximize:“Total” current:τ2 I1+ τ2 I2,i?

“Average” current? Square current?

Bienstock
Operations Research Problems in Power Engineering

Columbia University

We want to maximize:“Total” current:τ2 I1+ τ2 I2,i?

“Average” current? Square current?
F (I1 , I2 ) : a monotonely increasing function of I1 , I2

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Adaptive control
Simplification:
R is a discrete random variable. P(R = ri ) = pi , i = 1, 2, . . . , n (known).
1. At time τ = 0, we compute values I1 , and I2,i for i = 1, 2, . . . , n.
These values are used as follows:
2. For all t ∈ [0, τ /2], we set I (t) = I1 .
3. At time τ /2, we observe the value of R. Assuming R = ri , thenfor all t ∈ [τ /2, τ ], we set I (t) = I2,i .
Goals:(a) P(H(τ ) > k) < .

k smaller than critical temperature(b) I1 ≤ L(τ /2).
(c) Maximize:nX

F (I1 , I2,i )pi

i=1
Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ 

Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u

Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u

Bienstock
Operations Research Problems in Power Engineering(k < u < critical temp)

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)

Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)other constraints.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)other constraints.
Recall:
Z τ
H(τ )

=

e −ν(τ −s) αI 2 (s)ds + R(1 − e −ντ ) + Ce −ντ ,0Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)other constraints.
Recall:
Z τ
H(τ )

=

e −ν(τ −s) αI 2 (s)ds + R(1 − e −ντ ) + Ce −ντ ,0= v1 I12 + v2 I22 (i) + ri (1 − e −ντ ) + Ce −ντBienstock
Operations Research Problems in Power Engineeringin state i

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)other constraints.
Recall:
Z τ
H(τ )

=

e −ν(τ −s) αI 2 (s)ds + R(1 − e −ντ ) + Ce −ντ ,0= v1 I12 + v2 I22 (i) + ri (1 − e −ντ ) + Ce −ντin state i

So chance constraint is of the form:nX
I{v1 I12 + v2 I22 (i) > u − ri (1 − e −ντ ) − Ce −ντ }pi ≤ .
i=1
Bienstock
Operations Research Problems in Power Engineering

Columbia University

max

n
X

F (I1 , I2,i )pi

i=1

s.t.

P(H(τ ) > k) ≤ H(τ ) ≤ u(k < u < critical temp)

I1 ≤ L(τ /2, k)other constraints.
Recall:
Z τ
H(τ )

=

e −ν(τ −s) αI 2 (s)ds + R(1 − e −ντ ) + Ce −ντ ,0= v1 I12 + v2 I22 (i) + ri (1 − e −ντ ) + Ce −ντin state i

So chance constraint s of the form:nX
I{v1 I12 + v2 I22 (i) > u − ri (1 − e −ντ ) − Ce −ντ }pi ≤ .
| {z }| {z } |
{z
}
i=1

z1

z2 (i)

Bienstock
Operations Research Problems in Power Engineeringwi

Columbia University

max
s.t.

n
X
i=1
n
X

F̃ (z1 , z2 (i)) pi
I{z1 + z2 (i) > wi }pi ≤ 

i=1z1 + z2 (i) ≤ ui

(wi < ui )z1 ≤ k̄other constraints.

Bienstock
Operations Research Problems in Power Engineering

Columbia University

max
s.t.

n
X
i=1
n
X

F̃ (z1 , z2 (i)) pi
I{z1 + z2 (i) > wi }pi ≤ 

i=1z1 + z2 (i) ≤ ui

(wi < ui )z1 ≤ k̄other constraints.
Lemma: At optimality,
z1 + z2 (i) = wi or ui ,Bienstock
Operations Research Problems in Power Engineering

all i

Columbia University

max
s.t.

n
X
i=1
n
X

F̃ (z1 , z2 (i)) pi
I{z1 + z2 (i) > wi }pi ≤ 

i=1z1 + z2 (i) ≤ ui

(wi < ui )z1 ≤ k̄other constraints.
Lemma: At optimality,
z1 + z2 (i) = wi or ui ,→ Use binary variable

0
yi =
1
Bienstock
Operations Research Problems in Power Engineering

when
when

all i

z1 + z2 (i) = wi
z1 + z2 (i) = ui
Columbia University

Continuous knapsack problem

max
s.t.

n
X
i=1
n
X

F̃ (z1 , wi − zi )pi (1 − yi ) + F̃ (z1 , ui − zi )pi yi

ui pi yi ≤ 

i=1

0 ≤ z1 ≤ k̄
yi = 0 or 1,

Bienstock
Operations Research Problems in Power Engineering

all i.

Columbia University

Continuous knapsack problem

max M(z1 )z1 ∈[0,k̄]

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Continuous knapsack problem

max M(z1 )z1 ∈[0,k̄]

M(z1 ) ,nXF̃ (z1 , wi − zi )pi (1 − yi ) + F̃ (z1 , ui − zi )pi yi

i=1

s.t.

n
X

ui pi yi ≤ 

i=1

yi = 0 or 1,

Bienstock
Operations Research Problems in Power Engineering

all i.

Columbia University

Continuous knapsack problem

max M(z1 )z1 ∈[0,k̄]

M(z1 ) ,nXF̃ (z1 , wi − zi )pi (1 − yi ) + F̃ (z1 , ui − zi )pi yi

i=1

s.t.

n
X

ui pi yi ≤ 

i=1

yi = 0 or 1,

all i.

Practicable!

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Identifying Risky Contingencies of Transmission Systems(Joint with S. Harnett, T. Kim and S. Wright)

N - 1 criterion widely used. But is it enough?
How about N - K, for K “larger”? Everybody knows that:
It is too slow. A very difficult combinatorial problem.
N
1000
4000
8000
10000

K =2
4995007998000
31996000
49995000

K =3166167000
10658668000
85301336000
166616670000

K =441417124750
10650673999000
170538695998000
416416712497500

It is too conservative. It is not conservative enough.
(T. Boston) during Hurricane Sandy, N - 142 was observed.
Perhaps N - K does not necessarily capture all interesting
events?
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Example: August 14 2003
U.S. - Canada report on blackout:“Because it had been hot for several days in the Cleveland-Akron
area, more air conditioners were running to overcome the persistentheat, and consuming relatively high levels of reactive power –further straining the area’s limited reactive generation capabilities.”
A system-wide condition that impedes the system

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Example: August 14 2003
U.S. - Canada report on blackout:“Because it had been hot for several days in the Cleveland-Akron
area, more air conditioners were running to overcome the persistentheat, and consuming relatively high levels of reactive power –further straining the area’s limited reactive generation capabilities.”
A system-wide condition that impedes the system
Not a cause, but a contributor

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Example: August 14 2003
U.S. - Canada report on blackout:“Because it had been hot for several days in the Cleveland-Akron
area, more air conditioners were running to overcome the persistentheat, and consuming relatively high levels of reactive power –further straining the area’s limited reactive generation capabilities.”
A system-wide condition that impedes the system
Not a cause, but a contributor
Look for events that combine both effects?

Bienstock
Operations Research Problems in Power Engineering

Columbia University

A continuous interdiction model
A fictitious adversary is trying to interdict the transmission
system.
This adversary negatively alters the physical parameters ofequipment, e.g. transmission lines, so as to impede
transmission.
The adversary has a budget available (both system-wide andper-line).
On line km, reactance xkm increased to (1 + λkm )xkm

Bienstock
Operations Research Problems in Power Engineering

Columbia University

A blast from the past: Bienstock and Verma 2007
DC approximation to power flows.
Adversary increases reactances of lines.
Limit on total percentage-increase of reactances, and on
per-line increase.
Adversary maximizes the maximum line overload:|θk − θm ||flow on line km|
max
max
= max
x,θ
km
km
ukm xkmlimit of line kms.t.

Bx θ = dx within budget

Continuous, but non-smooth problem.
Bienstock
Operations Research Problems in Power Engineering

Columbia University

A blast from the past: Bienstock and Verma, 2007
DC approximation to power flows.
Adversary increases reactances of lines.
Limit on total percentage-increase of reactances, and on
per-line increase.
Adversary maximizes the maximum line overload:X+− (θk − θm )
max
(αkm
− αkm
)
x,θ,α
ukm xkmkm

s.t.

Bx θ = dx within budget
X
+
−
(αkm
+ αkm
) = 1,

α+ , α− ≥ 0.

km

Continuous, smooth, nonconvex.
Bienstock
Operations Research Problems in Power Engineering

Columbia University

And what happens?
Efficient computation of gradient and Hessian of objective
Local optimization algorithm implemented using LOQO
Algorithm scales well (2007): CPU times of ∼ 1 hour forstudying systems with thousands of lines.
Optimal * attack concentrated on a handful of lines
Plus system-wide attack impacting many lines

Bienstock
Operations Research Problems in Power Engineering

Columbia University

single = 20

total = 60

single = 10

total = 30

Range

[ 1, 1 ]( 1, 2 ]( 2, 3 ]( 5, 6 ]( 6, 7 ]( 7, 8 ]( 8, 20 ]single = 10

total = 40

Count

Range

8
72
4
1
1
4
0

[ 1, 1 ]( 1, 2 ]( 2, 9 ]( 9, 10 ]

Count

Range

Count

1
405
0
3

[ 1, 1 ]( 1, 2 ]( 2, 5 ]( 5, 6 ]( 6, 7 ]( 7, 9 ]( 9, 10 ]

14
970
3
0
1
0
2

“single” = max multiplicative increase of a line’s reactance“total” = max total multiplicative increase of line reactances

Bienstock
Operations Research Problems in Power Engineering

Columbia University

Today: the AC power flows setting
Adversary increases impedances, so as to maximize:
Phase angle differences across ends of a lines
Voltage deviations (loss)
Lost load following recourse actions
Generically:
max

F (x)

s.t.

x ∈B

x = impedances, B = budget constraints
F (x)= meausure of phase angle differences, voltage loss, load
loss
Challenge: F (x) is implicitly defined (bilevel optimization
problem)
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Voltage attack on 2383-bus Polish“Double the reactance of at most three lines”
Voltage Magnitude
1.1

p.u.

1.0
0.9
0.8
0.7

After Attack
Before Attack
300

600

900

1,200 1,500 1,800 2,100

Bus Index (reordered)→ Primarily 4 lines interdicted
Bienstock
Operations Research Problems in Power Engineering

Columbia University

Sat.Feb.20.102859.2016@rockadoodle

Bienstock
Operations Research Problems in Power Engineering

Columbia University