Identifying and Controlling Risky Contingencies ofTransmission Systems
Daniel Bienstock and Sean Harnett, Columbia University
Taedong Kim and Steve Wright, U. of Wisconsin
FERC Software conference, 2015-> Thu.Jun.11.205236.2015@littleboyN - K criterion revisited

Previous work: Salmeron and Wood, Donde et al, Turitsyin, Hines

N - K criterion revisited• N - 1 criterion widely used.

N - K criterion revisited• 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 - K criterion revisited• 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.
Table 1:
N
1000
4000
8000
10000

K=2
4995007998000
31996000
49995000

N
K



K=3
166167000
10658668000
85301336000
166616670000

K=441417124750
10650673999000
170538695998000
416416712497500

N - K criterion revisited• 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.
Table 2:
N
1000
4000
8000
10000

K=2
4995007998000
31996000
49995000

N
K



K=3
166167000
10658668000
85301336000
166616670000

K=441417124750
10650673999000
170538695998000
416416712497500– It is too conservative. It is not conservative enough.

N - K criterion revisited• 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.
Table 3:
N
1000
4000
8000
10000

K=2
4995007998000
31996000
49995000

N
K



K=3
166167000
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.

N - K criterion revisited• 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.
Table 4:
N
1000
4000
8000
10000

K=2
4995007998000
31996000
49995000

N
K



K=3
166167000
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?

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 persistent heat, andconsuming relatively high levels of reactive power – further straining thearea’s limited reactive generation capabilities.”→ A system-wide condition that impedes the system→ Not a cause, but a contributor→ Look for combined events ?

N - K criterion revisited• 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.
Table 5:
N
1000
4000
8000
10000

K=2
4995007998000
31996000
49995000

N
K



K=3
166167000
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?
• How can we deal with both types of problems?

A continuous interdiction model• A fictitious adversary is trying to interdict the transmission system.

• This adversary negatively alters the physical parameters of equipment,
e.g. transmission lines, so as to impede transmission.
• The adversary has a budget available (both system-wide and per-line).
– On line km, reactance xkm increased to (1 + λkm)xkm

A continuous interdiction model• A fictitious adversary is trying to interdict the transmission system.

• This adversary negatively alters the physical parameters of equipment,
e.g. transmission lines, so as to impede transmission.
• The adversary has a budget available (both system-wide and per-line).
– On line km, reactance xkm increased to (1 + λkm)xkm,– 0 ≤ λkm ≤ λmax
km (per line limit)

A continuous interdiction model• A fictitious adversary is trying to interdict the transmission system.

• This adversary negatively alters the physical parameters of equipment,
e.g. transmission lines, so as to impede transmission.
• The adversary has a budget available (both system-wide and per-line).
– On line km, reactance xkm increased to (1 + λkm)xkm,– 0 ≤ λkm ≤ λmax
km (per line limit)P– km λkm ≤ Λ (global limit)

A continuous interdiction model• A fictitious adversary is trying to interdict the transmission system.

• This adversary negatively alters the physical parameters of equipment,
e.g. transmission lines, so as to impede transmission.
• The adversary has a budget available (both system-wide and per-line).

• Adversary maximizes the impact (e.g. voltage loss) over the available
budget.
• A continuous, non-convex optimization problem with simple constraints.
No emumeration!

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|
max maxx,θ
km
ukm xkms.t.

Bx θ = dx within budget– Variables: reactances x, phase angles π– xkm = reactance of km, ukm = limit of km, Bx = bus susceptance matrix,
d = net injections (given)• Continuous, but non-smooth problem.

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
) = 1,(αkm
km

α+, α− ≥ 0.

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
) = 1,(αkm
km• Continuous, smooth, nonconvex.

α+, α− ≥ 0.

Technical point
max
x,θ,α

s.t.

X
+
− (θk − θm )
(αkm
− αkm
)
ukm xkmkm

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

α+ , α− ≥ 0.

. X +− (θk −θm ))u xFunction to maximize: F (x, α) =(αkm − αkm
km km

km

Technical point
max
x,α

s.t.

X
+
− (θk − θm )
(αkm
− αkm
)
ukm xkmkm

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

α+ , α− ≥ 0.

. X +− (θk −θm ))u xFunction to maximize: F (x, α) =(αkm − αkm
km km

km

• Fact: The gradient and the Hessian of F (x, α) can be efficiently computed• Optimization problem solved using LOQO ( IPOPT an option)

And what happens?
• Algorithm scales well (2007): CPU times of ∼ 1 hour for studying systems
with thousands of lines.

And what happens?
• Algorithm scales well (2007): CPU times of ∼ 1 hour for studying systems
with thousands of lines.
• Optimal * attack concentrated on a handful of lines

And what happens?
• Algorithm scales well (2007): CPU times of ∼ 1 hour for studying systems
with thousands of lines.
• Optimal * attack concentrated on a handful of lines• Significant part of the budget expended on many lines, with visible impact
Table 6: Attack patterns

single = 20 total = 60 single = 10 total = 30 single = 10 total = 40
Range
Count
Range
Count
Range
Count
[ 1, 1 ]8[ 1, 1 ]1[ 1, 1 ]14( 1, 2 ]72( 1, 2 ]405( 1, 2 ]970( 2, 3 ]4( 2, 9 ]0( 2, 5 ]3( 5, 6 ]1( 9, 10 ]3( 5, 6 ]0( 6, 7 ]1( 6, 7 ]1( 7, 8 ]4( 7, 9 ]0( 8, 20 ]0( 9, 10 ]2“single” = max multiplicative increase of a line’s reactance“total” = max total multiplicative increase of line reactancesToday: the AC power flows setting
As before, adversary increases impedances, subject to budgets
Adversary wants to maximize:• Phase angle differences across ends of a lines• Voltage deviations (loss)
Alternative version:• There is a recourse action: shed load so as to maintain feasibility of all
power flow constraints (limits)• Adversary wants to maximize the amount of lost load

Generically:

max
s.t.

F (x)
x∈B

• x = impedances, B = budget constraints• F (x)= meausure of phase angle differences, voltage loss, load loss

• Challenge 1: F (x) is implicitly definedBasic methodology: Frank-Wolfe
max
s.t.

F (x)
x∈B

(within budget)BBasic methodology: Frank-Wolfe
max
s.t.

x

F (x)
x∈B

(within budget)kB(an iterative algorithm)

Basic methodology: Frank-Wolfe
max
s.t.

F (x)
x∈B

(within budget)kF( x )xk

B(an iterative algorithm)

Basic methodology: Frank-Wolfe
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)

Basic methodology: Frank-Wolfe
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)

y k solves

max
s.t.

[∇F (xk )]T y
xk + y ∈ B(within budget)Basic methodology: Frank-Wolfe
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)

y k solves

max
s.t.

[∇F (xk )]T y
xk + y ∈ B(within budget)

Final step is a line search: xk+1 = xk + αy k , where 0 ≤ α ≤ 1 is the stepsize.

Line searches
0.91

0.9205
ls3.1

ls3.2
0.92

0.9
0.91950.919
0.89
0.91850.88

0.918
0.91750.87
0.917
0.9165
0.86
0.916
0.85

0.9155
0

10

20

0.55
ls4.2

0.5

0.45

0.4

0.35

0.3

0.25
0

10

20

30

40

50

60

70

80

30

40

50

60

70

80

90

100

0

10

20

30

40

50

60

70

80

90

100

Challenge 2
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• Recall: F (x) measures e.g. the largest phase angle difference using
reactances x• Q: exactly how do we get ∇F (x)?

Challenge 2
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• Recall: F (x) measures e.g. the largest phase angle difference using
reactances x• Q: exactly how do we get ∇F (x)?

• A: We estimate ∇F (x) using finite differences

Challenge 2
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• Recall: F (x) measures e.g. the largest phase angle difference using
reactances x• Q: exactly how do we get ∇F (x)?

• A: We estimate ∇F (x) using finite differences• But ∇F (x) is a vector with an entry for each line of the transmission
system – it is a big vector

Challenge 2
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• Recall: F (x) measures e.g. the largest phase angle difference using
reactances x• Q: exactly how do we get ∇F (x)?

• A: We estimate ∇F (x) using finite differences• But ∇F (x) is a vector with an entry for each line of the transmission
system – it is a big vector• “Solution”: Estimate ∇F (x) in parallel over several cores

Challenge 2
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• Recall: F (x) measures e.g. the largest phase angle difference using
reactances x• Q: exactly how do we get ∇F (x)?

• A: We estimate ∇F (x) using finite differences• But ∇F (x) is a vector with an entry for each line of the transmission
system – it is a big vector• “Solution”: Estimate ∇F (x) in parallel over several cores• Alternative: only estimate some of the components of ∇F (x):– Random subset of small size
– Most promising subset

Challenge 3
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• F (x) measures e.g. the sum of voltage losses with reactances x• And we estimate ∇F (x) using finite differences• Q: How do we compute F (x), for given reactances x?

Challenge 3
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• F (x) measures e.g. the sum of voltage losses with reactances x• And we estimate ∇F (x) using finite differences• Q: How do we compute F (x), for given reactances x?
• A: Ideally, a PF (load flow) calculation

Challenge 3
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• F (x) measures e.g. the sum of voltage losses with reactances x• And we estimate ∇F (x) using finite differences• Q: How do we compute F (x), for given reactances x?
• A: Ideally, a PF (load flow) calculation• Challenge! PF often does not converge for interesting x

Challenge 3
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• F (x) measures e.g. the sum of voltage losses with reactances x• And we estimate ∇F (x) using finite differences• Q: How do we compute F (x), for given reactances x?
• A: Ideally, a PF (load flow) calculation• Challenge! PF often does not converge for interesting x• solution: solution OPF-like problem:
minimize sum of square of all violations (load mismatch, line limits, etc)

Challenge 3
max
s.t.

F (x)
x∈B

(within budget)kF( x )

x

k

yk

B

(an iterative algorithm)• F (x) measures e.g. the sum of voltage losses with reactances x• And we estimate ∇F (x) using finite differences• Q: How do we compute F (x), for given reactances x?
• A: Ideally, a PF (load flow) calculation• Challenge! PF often does not converge for interesting x• solution: solution OPF-like problem:
minimize sum of square of all violations (load mismatch, line limits, etc)
• solution? violations still observed• solution? Add to definition of F (x) sum of weighted square violations→ Currently using IPOPT within Matpower (fastest for our purposes)→ Infeasible cases verified using SDP relaxation

Example: phase angle attack on Polish grid (from Matpower)
1 obj=2620.72 step=1.00 [ 263 8.00; 300 8.00; 728 8.00; ]2 obj=2641.52 step=1.00 [ 305 8.00; 306 8.00; 309 8.00; ]3 obj=2649.34 step=1.00 [ 168 8.00; 263 8.00; 321 8.00; ]5 obj=2765.47 step=0.50 [ 51 4.00; 261 4.00; 263 4.00; 300 4.00; 321 4.00; 322 4.00; ]13 obj=2944.01 step=0.12 [ 305 2.60; 168 2.32; 322 2.17; 169 1.90; 321 1.85; 263 1.57; 309
1.50; 32 1.15; 51 1.08; 261 1.08; 170 1.00; 171 1.00; 306 0.85; 39 0.75; 281 0.75; 166 0.57;
310 0.57; 8 0.43; 264 0.43; 300 0.42; ]20 obj=2950.54 step=0.03 [ 169 2.53; 305 2.38; 168 1.88; 322 1.77; 321 1.76; 309 1.74; 166
1.44; 170 1.28; 263 1.28; 261 1.14; 32 0.93; 51 0.88; 171 0.81; 306 0.69; 39 0.61; 281 0.61;
264 0.59; 260 0.51; 310 0.46; 8 0.35; 300 0.34; ]27 obj=2958.08 step=0.00 [ 169 2.80; 305 2.53; 321 2.00; 309 1.97; 168 1.63; 263 1.58; 322
1.53; 166 1.38; 261 1.11; 170 1.11; 32 0.81; 51 0.76; 264 0.76; 281 0.75; 171 0.71; 306 0.60;
39 0.53; 260 0.44; 310 0.40; 8 0.30; 300 0.30; ]Example: phase angle attack on 118-bus
Three top-attacked lines in red:Fact: phase angle attack cannot be isolated to a few lines

Fact: phase angle attack cannot be isolated to a few lines
Experiment on 118-bus case:(1) Take line most heavily interdicted: line 38(2) Let the reactance of this line increase to infinity(3) What happens? Phase angle difference → π/2 ?

Fact: phase angle attack cannot be isolated to a few lines
Experiment on 118-bus case:(1) Take line most heavily interdicted: line 38(2) Let the reactance of this line increase to infinity(3) What happens? Phase angle difference → π/2 ? No.

Fact: phase angle attack cannot be isolated to a few lines
Experiment on 118-bus case:(1) Take line most heavily interdicted: line 38(2) Let the reactance of this line increase to infinity(3) What happens? Phase angle difference → π/2 ? No.
From ≈ 10 to ≈ 40.

Fact: phase angle attack cannot be isolated to a few lines
Experiment on 118-bus case:(1) Take line most heavily interdicted: line 38(2) Let the reactance of this line increase to infinity(3) What happens? Phase angle difference → π/2 ? No.
From ≈ 10 to ≈ 40.

heavily interdicted line

lightly nor not interdicted

Voltage attack on 118-bus“Triple the reactance of at most three lines”
Voltage Magnitude

p.u.

1.1

1.0

After Attack
Before Attack

0.9
20

40
60
80
Bus Index (reordered)

100

Changes in Voltage Magnitude

p.u.

0.00
−0.02
−0.04
−0.06
0

20

40
60
80
Bus Index (original)

100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)

Changes in Voltage Magnitude

p.u.

0.0

−0.1

−0.2

300

600

900

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

Bus Index (original)→ Primarily 4 lines interdicted