TCS -TR-A-14-70

TCS Technical Report

Verifying Distribution Networks for Secure Restoration
by Enumerating All Critical Failures
byTakeru Inoue, Norihito Yasuda, Shunsuke Kawano,
Yuji Takenobu, Shin-ichi Minato, andYasuhiro Hayashi
Division of Computer Science
Report Series A
January 28, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Verifying Distribution Networks for Secure Restoration
by Enumerating All Critical Failures
Takeru Inoue∗†

Norihito Yasuda†‡

Shunsuke Kawano§

Yuji Takenobu§

Shin-ichi Minato‡†

Yasuhiro Hayashi§

January 28, 2014

Abstract
If several feeders are cut in a severe accident, distribution networks should
be restored by reconfiguring switches automatically with smart grid technologies. Although there have been several restoration algorithms developed tofind the new network configuration, they might fail to restore the whole network if the cut critically damaged the network. The networks design has toguarantee that it is restorable under any possible cut for secure power delivery, but it is computationally hard task to examine all possible cuts in alarge-scale network with complex electrical constraints. This paper presents
a novel method to find all the critical (unrestorable) cuts with great efficiency to verify the network design. Our method first runs a fast screening
algorithm based on hitting set enumeration; the algorithm selects suspicious
cuts without naively examining all possible cuts. Next, unrestorable cuts are
identified from the suspicious ones with another algorithm, which strictly tests
the restorability of the network under each suspicious cut without redundantly
repeating heavy power flow calculations. Thorough experiments on two distribution networks reveal that our method can find thousands of unrestorable
cuts from the trillions of possible cuts in a large 432-bus network with nosignificant false negatives. This is the first work to reveal the vulnerability ofa large-scale distribution network extensively.

1

Introduction

Distribution networks consist of several feeders with many switches. The feeder
lines are often cut accidentally by heavy equipment, natural disasters, or intentional attacks, which causes blackouts along the affected feeders. In response to∗takeru.inoue@ieee.org
ERATO MINATO Discrete Structure Manipulation System Project, Japan Science and Technology Agency, Sapporo, Japan.
‡
Graduate School of Information Science and Technology, Hokkaido University, Sapporo,
Japan.
§
Faculty of Science and Engineering, Waseda University, Tokyo, Japan.
†

1

2

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

S/S	
Switch	Section	

Figure 1: Unrestorable cutset found in a distribution network [1]. Given thatline sections indicated by the scissors are cut, the whole network would be still
physically connected but no feasible configuration could be found due to the voltage
drop constraint. We cannot deliver power to some intact sections, though they havepaths to the substation (S/S).
the blackouts, operators attempt to restore the network, providing power to downstream of the affected feeders, by network reconfiguration, that is, by changing
the open/close status of switches. In the restoration process, sections containing
the cut are located, and are isolated by opening neighboring switches. Then, thedownstream sections, which have not been cut but are disconnected from the network by the isolation process, are connected to a neighbor feeder through a tie
switch. The new restored configuration must satisfy operational constraints suchas the radiality of feeders, line capacity, and voltage drop. Secure and automatedrestoration is a key motivation to introduce the smart grid technologies.
The restoration process has been well studied, and several restoration algorithms
have been proposed [11, 16, 10, 9, 15, 14]; given a set of line sections that havebeen cut, the algorithms efficiently find a series of switching operations leading to
a new feasible (constraint-conformant) configuration. These algorithms, however,can fail to restore all the intact sections. This is because no feasible configuration might remain in the affected network whose topology has been changed by
the cuts. Here, we focus on an unrestorable cutset, which is defined as a set ofcuts such that some intact sections cannot be energized after the cuts have been
made due to the absence of feasible configurations. Figure 1 gives an example ofan unrestorable cutset found in the well-known distribution network introducedby Baran and Wu [1]. An unrestorable cutset may cause a long-term blackout on
several intact sections. Unfortunately, restoration algorithms cannot resolve thisVerifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures3

issue, because no feasible configuration exists in the network given the presence ofan unrestorable cutset. Since the root cause of this issue is the absence of feasible configurations, this is an issue of network design at deployment time, not an
issue for the restoration algorithms. If the network were verified not contain anunrestorable cutset, restoration algorithms could identify a new feasible configuration in an emergency. We need to find all unrestorable cutsets and to eliminate
them for secure power delivery before deploying the new distribution network.
Only a few papers have investigated efficient techniques related to finding unrestorable cutsets. The reliability-network-equivalent method [2] calculates theavailability of each load point in a distribution network, but it does not find unrestorable cutsets explicitly since the calculation method depends on probability
propagation. Reference [9] examined feeder lines to be cut for availability calculation, but it checks them one by one naively and so it does not scale to support large
networks. Reference [4] focused on N − 1 security to ensure whether a network
would be feasible under a cutset of any single line, but did not deal with a cutset
of multiple lines.
Finding all unrestorable cutsets is a computationally tough problem, because
the number of possible cutsets increases quite rapidly with network size and cutset
size; i.e., assume there are n line sections ina network and k of the n sections
can be cut at a time, we have to examine nk = O(nk ) combinations of sections
to find all unrestorable cutsets. The naive approach, which examines all possiblecombinations, clearly does not scale well. As will be presented in this paper, lines
separated by 18 switches can form an unrestorable cutset, and so we have to deal
with a network of large n without dividing it into small pieces. In addition, k canbe larger than one, because several lines can be cut in a short time by a large-scaledisaster or a series of terror attacks.
We face another issue; we have to conduct a feasibility test for every cutset
to check whether the network can deliver power to all intact sections under thecutset. Since the search space is non-convex due to the complex constraints of the
distribution network [8], the test is also computationally intractable.
This paper proposes a novel method that efficiently finds (nearly) all unrestorable
cutsets. Our method avoids the computation issues by employing a compresseddata structure named the zero-suppressed binary decision diagram, or ZDD [12],which allows us to represent a huge non-convex space in a compressed manner,and also to execute efficient algebra on the compressed space. ZDDs have beensuccessfully applied to the loss minimization problem of distribution networks [6]; anon-convex space of 1070 configurations were efficiently handled to find an optimal
configuration.
Our method is two-fold.
• First, our method efficiently selects unrestorable cutest candidates (suspicious cutsets), which greatly reduces the number of cutsets to be tested rigorously. We employ the hitting set enumeration with ZDDs [17] for this4

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi(1) Finding all feasible configurations	S/S 1	 S/S 3	
e1	
e2	

e5	

e3	

C1 = {e1,e4 }C2 = { e2, e3}
C3 = {e1,
e5}	

e4	

S/S 2	 S/S 4	
(2) Enumerating all hitting sets	{e1, e2
}
{e1,
e3
}
{ e2,
e4, e5}{e3, e4, e5}	Only minimal sets are shownfor space limits	(3) Testing cutsets only near hitting set switches	

Figure 2: Basic idea to identifying potential unrestorable cutsets. (1) We represent
a feasible configuration by a set of closed switches; e.g, two switches e1 and e4 areclosed in feasible configuration C1 . (2) All hitting sets of the feasible configurations
are enumerated; e.g. switches {e1 , e2 } form a hitting set, since at least one of themis closed in all feasible configurations C1 –C3 . Opening all switches in the hitting
set makes the network infeasible. (3) Cutting all lines near hitting set switches
is also likely to make the network infeasible. We focus only on such cutsets andignore others.
reduction; this approach finds sets of switches that are closed in common
in all feasible configurations (Figure 2). In other words, if all switches inthe set were to be opened, the network would lose all feasible configurations.
This observation leads to our basic idea; cutting lines near the switches of ahitting set is likely to trigger the same consequence, and so we will test only
such suspicious cutsets and can ignore the others. (Section 3.3)
• Second, our method tests the suspicious cutsets rigorously and identifies truly
unrestorable cutsets. In advance, we built two ZDDs, which represent the
topological constraints (radiality) and the electrical constraints (line capacity and voltage drop). After updating just the topological constraints foreach suspicious cutset, we conduct the satisfiability test without re-executing
complex power flow calculations required for the electrical constraints. (Section 3.2)
We conduct comprehensive computer experiments to evaluate our method with

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures

C1 = {e1, e4}	U = {v1, v3}	

v1	
 v4	
e3	
e1	
e5	
v2	
 v5	
e2	
e4	

v1	
 v4	
e3	
e1	
e5	
v2	
 v5	
e2	
e4	

v3	

v6	

v3	

5

v6	

Figure 3: Graph representation of distribution network in Figure 2. In graph
G = (V, E), vertex v ∈ V and edge e ∈ E represent a line section and switch,
respectively, while subgraph C ⊆ E can be a feasible configuration. Our problem
is to find every unrestorable cutset U ⊆ V .
the well-known Baran and Wu network [1] as well as a large-scale network developedby Fukui University and Tokyo Electric Power Company [3]; the large-scale network
closely models a typical Japanese distribution network and includes 432 buses. The
results show a remarkable reduction in the number of tests, five orders of magnitude
lower. Moreover, each test is completed in less than five seconds on average evenin the large-scale network. Finally, thousands of unrestorable cutsets are found in
the large-scale network.
The rest of this paper is organized as follows. Section 2 defines our problem,
and Section 3 describes the algorithms used to find unrestorable cutsets. Section
4 reports our experiments and the results, and Section 5 concludes this paper.

2

Problem statement

We first describe our network model. A distribution network consists of feeders
with switches. Each part of a feeder separated by switches is called a line section, and it has load and impedance. Given the status of all switches, the network
configuration is uniquely determined. A configuration that complies with the topological constraints consists of radial feeders (loop-free), each of which is connected
exclusively to a feeding point at a substation. All line sections must be energized
unless they have not been cut. The electrical constraints including line capacityand voltage drop are also set.
Following our past work [6], we represent the distribution network as a graph,
G = (V, E), as shown in Figure 3. A switch is represented by an edge, e ∈ E,
while a line section is a vertex, v ∈ V . If a switch is open, the correspondingedge is removed. In this graph representation, a configuration is represented bya subset of edges that have not been removed; a subset of edges is simply calleda subgraph in this paper, unless otherwise confusing. A subgraph representing
a feasible configuration is noted by C ⊆ E. The topological constraints requirefeasible subgraph C to be a spanning forest rooted to substations (a forest meansa set of disjoint trees), because each feeder has to be a tree and be rooted on a

6

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

feeding point, and every vertex has to be covered by a tree. Feasible subgraph C
also satisfies the electrical constraints. A set of all feasible subgraphs in graph G
is noted by C(G) and we have,
C(G) = {C ⊆ E : is feasible(C)},where argument G will be omitted when it is obvious from the context.
Our definition of cutset is different from that of the graph theory, though it
shares the flavor of a vertex cutset. A cutset in this paper refers to a set of vertices(line sections) that are being cut at the same time. We give a formal definition ofan unrestorable cutset as follows; given an unrestorable cutset, U ⊆ V , and a setof such cutsets, U 3 U , it is defined as,
U = {U ⊆ V : G0 = (V \ U, E \ edges(U )), |C(G0 )| = 0},
where G0 is a subgraph without vertices U and their edges (i.e., we cut sectionsof U and isolate them by opening neighboring switches), and the last term meansthat G0 has no feasible configuration and cannot deliver power to all intact sections.
An unrestorable cutset might not make the rest of graph physically disconnected,
since it is possible for a configuration to fail to satisfy the electrical constraints
even if the graph can be connected.
Our goal is to find U efficiently. We only consider line failures, since they aremuch more frequent than other failures like capacitor banks and switches.

3

Finding unrestorable cutsets

This section describes our method that finds unrestorable cutsets. Section 3.1
reviews our past work that enumerates all feasible configurations [6]. Section 3.2
describes a test algorithm to identify unrestorable cutsets from suspicious cutsets,
which are selected by the algorithm described in Section 3.3.

3.1

Enumerating all feasible configurations

We briefly describe our past work [6]. We first find a set of all topologicallyfeasible configurations Ct (G), and also find another set of all electrically-feasible
configurations Ce (G),Ct (G) = {C ⊆ E : is topol feasible(C)},(1)

Ce (G) = {C ⊆ E : is elec feasible(C)}.

A set of configurations satisfying all the constraints, C(G), is given as the intersection of both sets,
C(G) = Ct (G) ∩ Ce (G).

(2)

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures

7

These three sets are represented as ZDDs, which are built by algorithms presented
in [6, III.A], [6, III.B], and [12]. The set size, |C(G)|, can be calculated by anotheralgorithm[7]. Finding Ce (G) is the most time-consuming process and it takes morethan 100 times longer than the other calculation processes, since it involves complex
power flow calculations. We assume that Ce (G) and C(G) have been obtained before
the following algorithms.

3.2

Testing network feasibility for suspicious cutsets

Algorithm 1 is unrestorable
Input: G, Ce (G), S
Output: r // indicates S is unrestorable or not
G0 = (V \ S, E \ edges(U ))Ct (G0 ) = {C ⊆ E \ edges(S) : is topol feasible(C)}C(G0 ) = Ct (G0 ) ∩ Ce (G)if |C(G0 )| = 0 then // if G0 has no feasible configurationr = Trueelse
r = Falseend ifWe describe an algorithm to determine whether a given suspicious cutset isunrestorable in Algorithm 1. Given suspicious cutset S by the algorithm of Section 3.3, we isolate vertices of S by removing their neighboring edges (imitating the
opening of the corresponding switches) which yields another graph, G0 . We thenrun the algorithm of (1) that finds topologically-feasible configurations Ct (G0 ) with
G0 . We also run the intersection algorithm of (2) over Ct (G0 ) and Ce (G). Finally,
we count the number of feasible configurations |C(G0 )| to know whether the given
cutset is unrestorable.
This algorithm is very efficient, because it does not involve the time-consuming
power flow calculation required for Ce (G); it is calculated before this algorithm.
Ce (G) includes electrically feasible configurations with and without S, but configurations with S cannot be realized in the modified graph G0 , from which S’s
vertices are removed. These impossible configurations are, however, eliminated byintersection with Ct (G0 ), which does not include configurations that use S.

3.3

Selecting suspicious cutsets

We describe an algorithm to select suspicious cutsets, which will be tested by Algorithm 1. We first consider hypothetical switch failures such that the distribution
network would be infeasible if the switches could not be closed. Figure 2 gives
an example. This network has feasible configurations, but none of them can berealized if switches e1 and e2 are kept open, since at least one of them must bescalable.
such that the distribution network
be mustinfeasible
if the in anyline
one wouldof thembe closed
feasible
configuration.
A as shown in Figure 2 (3). Bas
connected
to the switch,
switches could not be closed. Figure
gives anexample.
Scalability
improvement
techniques
set of2 theseswitchesis Thiscalled D.
a hittingon
this setidea,forwethe
givefeasiblea theoremto1)findunrestorable
Cutallsize
limit: Wec
network has feasible configurations,
but
none
of
them
can
be
configurations. We give a rigorous definition
here.
A As
hittingset
fromhitting
sets.
preparation
forthetheorem,
we definthemethodnumberWe show two techniques thatwhichmake isourmoo
realized if switches e1 and e3forareC kept
open,
least
is a set,
H since✓ E, atsuchthat H function
has non-empty
intersection
from hit thatbased
generates
cuts
from
a
hitti
named cuton the maximum
scalable.
4
one of them must be closed inwith
any every
feasibleconfiguration
configuration.C A2 C. Aset,set of hitting sets, H, isthe number of hitting seby, set for the feasible
set of these switches is calledgiven
a hitting
thislimitation
greatlyre1) Cutlimit:
We 3
putS anupper
limit on8e
thecutsizefromhit(H)= {v
2 vertex(e)2 cutH},siz4
2 findunrestorable
configurations.
give a rigorous
definition
here.a Agiven
hittingAlgorithm
setWe
describe an We
algorithm
to determine
whether
We haveinana effi
isof verticesexamine.
(line sections)cu
H= {H S.✓Kawano,
E : H \Y.
C Takenobu,
6= ;which
8C 2S.
C}.the number
T.inInoue,
Yasuda,and Y. Hayashi
Input: C(G)suspicious
is unrestorable
Algorithm
1.non-empty
Given suspicious
for C iscut
a set,
H8 ✓ E, suchthat HN.has
intersection
where Minato,
the cut consistsof vertices
connected
toorderhitting
setlines
size
[15].
In
to
based
on
the
maximum
number
of
cut
at
a
time.
Sinc
U clueandcutdetermine
S byevery
the whether
algorithmof Section
III-C,
weisolate2hitting
findunrestorable
edges,
it isunrestorable
called a suspicious
cut,examine
S. In otherwor
withconfiguration
C Algorithm
2 C.
A set
of
hittingsets,us
H,Output:The
setvertices
gives
a is
powerful
to findithm toa givenneedwithtohittingsethenumberof hittingsets,
setsSincreases
theirasize
rapidl
U
=
;
of
S
by
removing
theirneighboring
edges(imitating
to
open
a
set
of
suspicious
areprojected
from
set
of
hitti
Input:
C(G)able in Algorithm
1. Given suspicious
cuts. Our basic idea
is like this; a network that opens a maximum vertex degree
given by,0of edges E	
 G . We(subsetsof verticesV)	
 reduces the number of hitting sets
limitation
greatly
HCutsets=thishittingsets(C(G))
the corresponding switches), andOutput:
we Subsets
get anothersets,
by function
U has graphof Section
III-C, we isolate vertices
switcha similar topology with
theH,network
thatcut
cutsfroma hit,
Lemmato(details
for
H
2
H
do
//
for
each
hitting
setalgorithm
cut_from_hit	then runH
the=algorithm
of
(1)
that
finds
topologically-feasible
examine.
We
haveanefficient
restrict are
the discu
hittin
{H
✓
E
:
H
\
C
=
6
;
8C
2
C}.
Uline
= ; connected0 to the switch, as shown in Figure 2 (3). Basedneighboring edges (imitating0 to open
for
S
2
cut
from
hit(H)
do
//
for
each
suspicious
cut
S
=
{S
2
cut
from
hit(H):
8H
2
H},
configurations Ct (G ) withthemodified
graph
G
.
We
also
0
set
size
[15].
In
order
to
identify
unrestorable
cut
U
,
we
on
H = thishittingsets(C(G))es), and we get another graph G . We
theorem(a sketchthenof proof Lemma. An unrestorable
0 we give the following
if isunrestorable(S)run theintersection
algorithm
ofpowerful(2)onover
Cidea,) andCunrestorable
Thehitting
set
gives
us
a
clue
find
t (Gtoe (G).
toexaminehitting4.sets of |H|  |U |(d 1), where d is thforH
2 H indoAppendix).
// for each0 hitting set needf (1) that finds topologically-feasible
asshown
in Figureis
given
of |H|  |U |(d 1).
U=
U [ {S}
Finally,countthefeasible
configurations|C(G opens)|
cuts.weOurbasic
ideaalso
isoflike
this;a2networkthata for maximum
0 numbervertexdegree in the graph, thanks to the followin
for
S
cut
from
hit(H)
do//eachsuspicious
cut
ith thetomodified
graph
G
.
We
end
if
know
whether
the
given
cut
is
unrestorable.
switchhas
topology Theorem.
withnetwork
thatthencuts acutLemma
if istheunrestorable(S)rithm of This
(2)
over
Ct (Ga0 ) similarandCe (G).
Theorem.
Anyareunrestorable
cutAppendix).
is 2)
a suspicious
sho(details
inducedfromatdiscussed
least onein
endis foralgorithm
is very
efficient, because
it Anydoes unrestorable
not inMinimal cut,
cutsasonly0linetheconnectedtotheswitch,as
shown
inFigure
2
(3).
Based
U
=
U
[
{S}
mber ofvolve
feasible
configurations
|C(G
)|
in
Figure4(asketch
of
proof
is
given
in
Appendix).
of calculation
hitting sets,end fortime-consuming power flow
required forrestorable cuts; minimalend
if algorithm.
on thisidea,
givecalculatedthetheorem(a sketchof proof
en cut Cise (G),unrestorable.
Lemma.
An unrestorable
cutwhich
U isany
hittingwhichhaswebeen
thisThis
Figure4: following
A setbeforeof unrestorable
cutsets,
U, is a subset
of suspicious
sets, S,
isinduced
other fromcut, arethat
is, seU
This
theorem
impliesthat all unrestorable
cuts
generaU , 9H
2onH : U 2 cut
fromhit(H),
end for8U 2 thaty efficient,becauseitAppendix).
does
notinis given
Ce (G)
mightininclude
impossible
configurations
rely
of
|H|

|U
|(d
1).
projected from a set of hitting sets, H, by function cut from hit. All unrestorable
cut, any su
fromhittingsets, skip the testsunrestorable
forg powerflow calculation
for theseend
vertices
removed requiredasS, butimpossible
configurations
only,
is nottrue),
we cannot
against suspicious
cutsets
are, therefore,
mappedjustfromhitting
sets.
where function cut
hit(H) generates combinations of unrestorable, and so we
alculated
beforethis algorithm.
Thisintersection,Anyunrestorable
cut is induced
fromareat notleast one
are Theorem.
eliminatedin takingthebecause they
cuts.
only:
only
focus
on minimal
8U 2 U,cuts
9H 2
H : UWe
2 cut
fromhit(H),
minimalhittingsets canunverticesconnected
toedge
e 2 H, 2) Minimal0
possible
configurations
includedin Ctsets,(G that). rely on
We present
the cuts;
completealgorithm
all thatunrestorableofhitting
restorable
minimalcut Utoisfind
a
cut
does
not
includwe testcuts
suspicious
closed in any
feasible
configuration.
switchesisus
calleda hittingbut these impossible configurations
only,
is nottrue),
we hit(H)cannot A
skip
theof
suspicious
cuts
Utheseinagainst
Algorithm
2.
This
algorithm
firstawithout
set of thecuts
anditallowstoignoreunsuspicious
risk
0 setobtains
0
cut
from
3set
{v
2testsvertex(e)8e2H}.
any other cut, that is, U 6 U sets.
8U Reference
2 U. Givenis a[11]Ualso
8Ususpicious
2 U,
9Hare
2
H
: Ucuts.
2 cutfrom hit(H),We give hitting
the intersection,
because
they
not
sets
H
for feasible
configurationsCby [11].
We suspicious
test
for
the
feasible
configurations.
a rigorous
definition
here.
A hittingsettestoverlooking
unrestorable
ones. Weonlyc00 theC. Selecting
cuts
unrestorable
cut,
anysuperset
of
it,
U
U
,
is
clear
selects
minimalhitting se
only intersection
suspicious
cuts
inducedfromthe hitting
sets. Our
methodWe
present
theHcomplete
algorithm
to
find
all
unrestorable
by
Algorithm
1,anddeterminewhethertheyareunrestorab
for
C
is
set
H
⊆
E
where
has
non-empty
with
every
configurationWe
describe
anothertoefficiently
suspi- cut
unrestorable,
anddotests
notcomparedhave to careit. Sincenonwhere
functioncut algorithm
from hit(H)generates
combinations
ofas afirstWe
defineaselect
suspicious
cutinducedfromaofhitting
reducesthenumberoffeasibility
to truea naiveU
in
Algorithm
algorithm
obtains
set
ofso weSincethea opposite
thistheoremMinimalizing
is not(amakeshittingo
Cwill∈ C.
Atestedsetcuts
ofby
hittingsets,
H,2.inisThis
given
by,
cious
cuts,
which
be
the
algorithm
Secminimal
hitting
sets
can
yield
non-minimal
unrestorable
cut
vertices connected to edge ehitting
2 set
H,setsbrute-force
approach,which
performs
a
test
for
every
cut.
by H
cutforfrom
hit.configurations
This theorem
us testto ignorecuts
un-only,introduce
theweriskof ofeasible
C generates
byallows[11]. We
unrestorable
is not true),cannotsk
cuts tion III-B. We first consider hypotheticalswitch failureswe
test
suspicious
cuts
inducedonly
fromminimalhittinsuspicious
cutswithouttheriskofoverlooking
unrestorable
ifnounrestorable
cut
only
suspicious
cuts
inducedfromthehittingsets.
Ourmethod
H
=
{H
⊆
E
:
H
∩
C
=
6
∅
∀C
∈
C}.
the tests.
suchtothat
thefrom
distribution
network
be infeasible
cuthit(H)
3 {v 2would
vertex(e)8e 2 H}.if thealgorithm
efficiently
selectsuspisets.
[11]
also
proposedan algorithm
thatefficient
reducesthebecause
numberof unrestorable
feasibility
testscuts
compared
to a naive
ones,
all
areReference
suspicious
cuts.
We
testalgorithm
unrestorable
can beWe
present
thecompleteto find cuts
all unrestora
switches
could
not
be
closed.
Figure2gives
anexample.
This
D. Scalability
improvement
techniques
be tested by the algorithm in Sec- brute-force approach, which performs
a
test
for
every
cut.
selects
hittingsets.
the suspicious
theforalgorithm
ofinSection
III-B,
set,
whichfirstis notminim
cuts minimal
Uunrestorable
Algorithm
2.andThis Ouralgorithm
obtainsaThehitting onlyset
us thema powerfulcluefinding
cutsets.
has feasible
but gives
noneofcancuts
be bynsidernetwork
hypotheticalswitch configurations,failuresWe showtwo
techniques
that
make
our
methodmore
determinewhethertheyareunrestorable.
Since
the
oppositeofefficiency
andaccuracy.
Wedefineasuspicious
cut
as
a
cut
inducedfromahitting
Minimalizing
makes
our
methodmore
efficient,
but
it
caW
of
hittingsets
Hforfeasible
configurations
C
by
[11].
realizedifswitches
e
and
e
are
kept
open,
since
at
least
basic
opens a switch has a similar topology
1 ifidean network would be infeasible
the 3works as follows; a network thatscalable.
thistheorem
is
not
true
(a
hittingset
inducesunrestorable
cuts
in
the
experiments;
one
one
of
them
must
be
closedinanyfeasible
configuration.
A
test
only
suspicious
cuts
generatedfromthehitting
sets.
set2 bycutan from
hit.theThis
theoremallowsus
to ignore
un- tointroduce
the asriskshownof overlooking
withnetworkthatcuts
a lineconnected
the switch,
in Figure 2some unrestorable cutOosed. Figure
gives
example.
This
D.
Scalability
improvement
techniques
set suspiciousof these switchesiscalledahittingsetforthefeasiblemethodreducesthenumberoflimitfeasibility
comparedtocuts
withoutrisk
of idea,overlooking
iffindnounrestorable
cutan
isupperfoundfroma tests
hittingset, som
(3).
Based
this
we giveunrestorable
a theorem1) toCut
unrestorable
cutsetsfromfigurations, but none ofthem
canbetheonsizeall
limit:
We puton thecut size,
configurations.
Weall
give
a rigorous definition
here.
hittingset
We
show
two Atechniques
thattest
makeunrestorable
our methodcuts
morecan be found from a superset of the hittin
ones,
becauseunrestorable
cuts
aresuspicious
cuts.
Wewhichweisdefine
the numberof vertices(line
in a cut,and e3 are kept open, sinceat least
Ashaspreparation
for the theorem,a suspicious
cutset,S ∈sections)S,
for C is a set, H ✓ hitting
E, such sets.
that Hnon-empty intersection
scalable.
based
on
the
maximum
number
of
lines
cut
at
a
time.
Since
osed in any
feasible
configuration.
A
only
the
suspicious
cuts
by
the
algorithm
ofSection
III-B,
and
set,
which
is
not
minimal.
This
isatradeoff
between thwhich Cis 2
mappeda hittingwith every configuration
C. A setfromof hitting
sets,set
H, by
is a function named cut from hit,thenumberof hitting
sets increases
with evaluate
their sizetwo
rapidly,
calledgiven
a determine
hittingsetforthefeasiblewhethertheyareunrestorable.
Since
the
oppositeofefficiency
andaccuracy.
We
will
our
methodby,1) Cut size limit: We put an upper
limit on the
cut size,
thislimitation
greatly
reducesthenumberofhittingsets
torigorous definition
here.
A
hitting
set
S
=
{S
∈
cut
from
hit(H):∀H∈
H},
this theorem is not true (a hitting
unrestorablecuts(line insections)the experiments;
which setis induces
the numberof vertices
in a cut, one examines minimal hitting sets on

examine. We have an efficient algorithm to restrict the hitting
H non-empty= {H ✓ Eintersection: H \ C 6= ; 8C 2 C}.
ch that H has
based on the maximum number ofsetlines
a time.
Since
size
[15].
In
orderby,to identify unrestorable cut U , we only
shown
hitcutis atdefined
C 2 C. A set of hitting as
sets,
H, is in Figure 4. The function cut fromthe number
hittingsets increases
with
their
size
rapidly,
The hitting set gives us a powerfulclue toof
findunrestorable
need to examine hitting sets of |H|  |U |(d 1), where d is theYcuts. Our basic idea is cut
like fromthis;a network
thatvertices(e)opens
this hit(H)limitation
reducesa themaximum
number ofvertex
hittingsets todegreein the graph, thanks to the following= greatlyswitchhasasimilar
topology
withthe
networkthatcutsaexamine.
We
haveanefficientalgorithm
torestrictthehitting\ C 6= ; 8C 2 C}.
Lemma (details are discussed
in Appendix).
e∈Hline connected to the switch,
shown
Figure2 (3).
size in[15].
In orderto Based
identify unrestorable cut U , we only
Q as sets a powerful
to wefindgive
unrestorable
on thisclue
idea,
the following
theorem(aa sketch
proof
where
Ai needrepresents
Cartesianproductof|(dsetsexampleFigs. 2from hitting setsAn
unrestorable
cut U isofinduced
to examine
hittingofsets
of|H|Lemma.
 |U1),Awhereis thei . In dthe
like isthis;a network
that
opens
a
given
in Appendix).
of
|H|

|U
|(d
1).
maximum
vertexdegreeinthegraph,
thankstothefollowing
and 3, we have,pology with the network that cuts a Lemma (details are discussed in Appendix).
Any unrestorable
inducedfrom e2})
at least=one{v1, v2}2) Minimal
cuts only: We only focus on minimal untch, asTheorem.
shown in Figure
2 (3). Basedcut
cutisfromhit({e1,× {v2, v3}
ofhittingsets,cuts; hitting
minimal cut U is a cut that does not include
following theorem (a sketch of proof Lemma. An unrestorable cut U isrestorable
inducedfrom= {{v1, v2}, {v1, v3}, {v2},sets{v2, v3}}.
any
other
cut,
that
is, U 6 U 0 8U 0 2 U . Given U is anof |H|
 |U|(d 1).
8U 2 U , 9H 2 H : U 2 cut
fromhit(H),
unrestorable cut, any superset of it, U 00
U , is clearly
Suspicious cutset S can also be called a hitting vertex set, since it consists ofunrestorable,
and
so
we
do
not
have
to
care
it.
Since nonfunction
from onehit(H) 2)
generates
combinationsofable cutwhereis induced
fromcut
at least
Minimalcutsofonly:
We only
focus on minimal unto edges
a hittingset.
minimalhitting
sets
can
yield
non-minimal
unrestorable
cuts,
vertices connected vertices
to edge econnected
2 H,
restorable cuts; minimal cut U is a cut that does not include
0 we 0test suspicious cuts induced only from minimal hitting
any other 8ecut,2 that
8U 2 U. Given U is anhit(H) 3 {v 2 vertex(e)H}. is, U 6 U sets.
: U 2 cut cut
fromfromhit(H),
also
proposed cutsets,
an algorithm
Theorem. unrestorable
A set of unrestorable
cutsets,
U,Reference
suspicious
S, that efficiently
cut, any supersetof it,
Uis00 a subset
U ,[11]
isofclearly
selects
minimalhitting
sets.
as
shown
in
Figure4(asketch
of
proof
is
given
in
the
Appendix).
m hit(H) generates combinations of unrestorable, and so we do not have to care it. Since noncut induced
a hittingMinimalizing
makescuts,
our method more efficient, but it canhitting fromsets canyield non-minimal
unrestorable
ge e 2 We
H, define a suspicious cut as aminimal
set by cut from hit. This theorem allows us to ignore un- introduce the risk of overlooking some unrestorable cuts;
wemeans
test suspicious
induced only
fromareminimalhitting
This theorem
that all cuts
unrestorable
cutsets
mappedfrom hitting sets,
cuts
without the risk of overlooking unrestorable if no unrestorable cut is found from a hitting set, some{v 2 suspicious
vertex(e) 8e
2 H}.
sets. Reference [11] also proposed an algorithm that efficiently
ones, because all unrestorable cuts are suspicious cuts. We test unrestorable cuts can be found from a superset of the hittingU ⊆ {U∈ cut
from hit(H): ∀H ∈ H},
selects
minimalhitting sets.
only the suspicious cuts by the algorithm of Section III-B, and set, which is not minimal. This is a tradeoff between the
cut asdetermine
a cut induced
fromtheya hittingMinimalizing
makes
our method
more efficient,
but it canWe will evaluate two our methods
whetherare unrestorable.
Since theoppositeof efficiency
and accuracy.
is theorem
allowsustoignoreunintroduce
the
risk
of
overlooking
someunrestorable
cuts;examines minimal hitting sets only
this theorem is not true (a hitting set induces unrestorable cuts in the experiments; one
the risk of overlooking unrestorable if no unrestorable cut is found from a hitting set, somerable cuts are suspicious cuts. We test unrestorable cuts can be found from a superset of the hittingby the algorithm of Section III-B, and set, which is not minimal. This is a tradeoff between there unrestorable. Since the opposite of efficiency and accuracy. We will evaluate two our methods
a hitting set induces unrestorable cuts in the experiments; one examines minimal hitting sets only

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures9

and it allows us to ignore unsuspicious cutsets without the risk of overlooking unrestorable ones. We test only the suspicious cutsets by Algorithm 1, and determine
whether they are unrestorable. We cannot skip the tests, since the opposite of thistheorem is not true (a hitting set can be mapped to restorable cutsets as well).
This is because loads are reduced given a suspicious cutset due to the blackout of
isolated sections, while it is not reduced for a hitting set that isolates no section.
Algorithm 2 find unrestorable
Input: C(G)Output: UU =∅H = hitting sets(C(G))
for H ∈ H do // for each hitting set
for S ∈ cut from hit(H) do // for each suspicious cutset
if is unrestorable(S) thenU = U ∪ {S}end ifend forend forWe present Algorithm 2 to find all unrestorable cutsets U. This algorithm
first obtains a set of hitting sets H for feasible configurations C by [17]. We test
suspicious cutsets, S’s, mapped from the hitting sets. Our method reduces thenumber of feasibility tests compared to the naive brute-force approach, which tests
each cutset.

3.4

Scalability improvement techniques

We show two techniques that make our method more scalable.

3.4.1

Cutset size limit

We put an upper limit on the cutset size, which is the number of vertices (linesections) in a cutset, based on the maximum number of lines cut at a time. Since
the number of hitting sets rapidly increases with their size, this limitation greatly
reduces the number of hitting sets to be examined. We can efficiently restrict thehitting set size [7]. In order to identify unrestorable cutset U , we only need to
examine hitting sets of |H| ≤ |U |(d − 1), where d is the maximum vertex degree inthe graph, thanks to the following Lemma (details are discussed in the Appendix).
Lemma. Unrestorable cutset U is mapped from hitting sets of |H| ≤ |U |(d − 1).

10

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

3.4.2

Minimal cutsets only

We only focus on minimal unrestorable cutsets; minimal unrestorable cutset U is acutset that does not include any other unrestorable cutset, that is, U 6⊃ U 0 ∀U 0 ∈ U.
Since non-minimal hitting sets can yield non-minimal unrestorable cutsets, wetest suspicious cutsets mapped only from minimal hitting sets; hitting sets which
are supersets of another hitting set are ignored. Reference [17] also proposed analgorithm that efficiently selects minimal hitting sets.
Minimalization makes our method more efficient, but it can introduce the risk ofoverlooking some unrestorable cutsets. Suppose no unrestorable cutset were foundfrom a hitting set, and some unrestorable cutsets were found from a superset ofthe hitting set. This super hitting set would not be minimal and thus would not be
examined, and so this unrestorable cutset could be never found. This is a tradeoff
between efficiency and accuracy, and is evaluated in the experiments.

4

Experiments

Our method is applied to two datasets, a traditional small distribution network in
Section 4.1 and a large-scale network closely modeling a typical Japanese distribution network in Section 4.2. We evaluate our two methods of Algorithm 2 in theexperiments; one examines minimal hitting sets only (minimalization), while theother considers supersets of the minimal hitting sets (no minimalization). Thesemethods are compared against the naive brute-force approach, in which feasibility
tests are performed on every cutset. The tests generated by our methods and thenaive method are executed with Algorithm 1. Our methods were implemented
with the efficient graph library named Graphillion [5]. We performed power flow
calculation based on [13], but our method is not limited to any specific power flow
model. The experiments were conducted using a single core of an Intel Xeon CPU
E7-8837 (2.67GHz).

4.1

32-bus network

The first dataset represents the 32-bus network introduced by Baran and Wu [1].
It has 37 switches and only a single substation. This network is a single-phasealternating current system. The sending line voltage is 12.66 kV, and the maximum
voltage drop must be within 10 % of the sending voltage. This dataset has no line
current constraint. The maximum degree, d, is 3 in the graph representation. The
results include unrestorable cutsets of size four or less, |U | ≤ 4, since we found nominimal unrestorable cutset greater than four.
Figure 5 shows the number of tests performed by each method. Our two methods grew much more slowly than the naive method. Our method with minimalization performed only 88 % fewer tests than the naive method. Many innocent

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures 11

100000# of tests	

10000
1000
100
Naive method
Our method (no minimalization)
Our method (minimalization)

10
1
0

1

2
3
Cut size	

45

Figure 5: The number of tests versus the cutset size in the 32-bus network. The
number of tests is defined as the number of suspicious cutsets |S| in our method
or nk (k is the cutset size) in the naive method. Our methods conducted much
fewer tests than the naive method.
# of minimal hitting sets	

10000
1000
100
10
1
0

5
Set size	

10

Figure 6: The number of minimal hitting sets |H| versus their size, |H|, in the
32-bus network. It is much smaller than the number of tests performed by thenaive method (Figure 5). This is the reason why many unsuspicious cutsets were
filtered out in our method.
cutsets were filtered out without performing feasibility tests by our methods1 . In
order to investigate this great reduction in depth, we plot the number of minimal
hitting sets in Figure 6. Only a couple of thousand sets were found, a lot fewer thanthe possible edge combinations. This result indicates that our method successfully
selected a small number of suspicious cutsets by utilizing the minimal hitting sets.
The number of tests performed by our minimalization method can be greater orsmaller than the number of minimal hitting sets. This is because a single hitting
set can be mapped to multiple suspicious cutsets by function cut from hit, and also
1
Our methods involve nearly the same number of tests as the naive method when the cutset
size is one. This is because every pair of neighboring switches in straight line forms a hitting set,
which generates a suspicious cutset from only the intermediate section. Our focus is, however, on
the scaling of test numbers against the cutset size, and our methods are much more efficient than
the naive method for larger cutsets.

12

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

Probability distribution	

0.3
0.25
0.2
0.15
0.1
0.05
0
0

5

10

Distance between lines in unrestorable cut	Figure 7: Probability distribution of distance between line sections in a minimal
unrestorable cutset, in the 32-bus network. Some minimal unrestorable cutsets
include line sections separated by ten switches, and so we have to address cutsets
across a wide area.
Table 1: The number of minimal unrestorable cutsets found in 32-bus network|U | = 12
3
4

Naive method and our
method (no minimalization)
3
76
69
55

Our method (minimalization)
3
76
69
47

some hitting sets share common suspicious cutsets. We found no minimal hitting
set of greater than six, as shown in the figure. This is because most big hitting
sets include smaller ones, so of course they are not minimal.
The great reduction in the number of tests cannot be achieved just by ignoringline sections far apart. Figure 7 shows distance distribution between line sections
in a minimal unrestorable cutset, where the distance is measured by the number ofswitches between line sections. Line sections in a minimal unrestorable cutset are
separated by up to ten switches; actually, the diameter (the maximum distance)of the network is equal to ten. This result implies that we are not allowed to use
the distance for filtering out innocent cutsets. Sophisticated methods like ours are
required to efficiently find unrestorable cutsets.
Table 1 shows the number of minimal unrestorable cutsets found by each method;an example of unrestorable cutset found is shown in Figure 1. Our method withminimalization overlooked eight unrestorable cutsets (55 − 47 = 8), but it found 96% of them with 88% fewer tests. The probability of finding a minimal unrestorable
cutset per test is 3.8 % in our minimalization method, while it is 0.49 % in the naive
method. Our method found most of the unrestorable cutsets with high efficiency.
This is a good tradeoff between the performance and accuracy.

# of unrestorable cuts	Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures 13

80

Electrical constraints

70

Topological constraints

60
50
40
30
20
10
0
1

2
3
Cut size	

4

Figure 8: Causes of the unrestorable cutsets in the 32-bus network. Unrestorable
cutsets can make the network disconnected topologically, or can make it electricallyinfeasible without disconnection.
Table 2: Computation time for 32-bus network
Algorithm 1 (average per test)
Algorithm 2

10.7 msec
5.55 sec

Figure 8 clarifies the causes of the unrestorable cutsets. The label “topologicalconstraints” means that the network would be disconnected by the cutsets, while
the label “electrical constraints” indicates that the network cannot satisfy theelectrical constraints even though it can be connected. Our method found bothtypes of unrestorable cutsets. The topologically unrestorable cutsets make the
network physically disconnected. We found many small unrestorable cutsets causedby the electrical constraints, unlike the Fukui-TEPCO network as will be shown;
this implies that the network might be so poorly designed that it is likely cause
power supply shortages, which makes the constraints too strict.
We also evaluate the performance of our method (Table 2). Testing a suspicious
cutset by Algorithm 1 requires only 10.7 msec on average, due to our efficientfeasibility test algorithm that involves no power flow calculation. Total CPU timeneeded for Algorithm 2 is 5.55 seconds. The maximum amount of memory usedby our method is 66.7 MB. Calculating feasible configurations, Ce and C, requires
a few hours, as shown in [6].

4.2

Fukui-TEPCO network

We consider the 432-bus network with 468 switches, which was developed in 2006 by
Fukui University and Tokyo Electric Power Company (TEPCO) [3]. The network
is modeled as a three-phase alternating current system, and consists of residential, industrial, and commercial areas. Among the hourly load profiles, we used
the peak load, which imposes the severest electrical constraints on the network.

14

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

Table 3: Specification of Fukui-TEPCO network
Number of buses
Number of switches
Total load
Line capacity
Sending line voltage
Maximum voltage drop
Max degree, d432
468
287 MW
390 A
6.6 kV
0.3 kV3

1E+10# of tests	

100000000
1000000
10000
Naive method
Naive method (18-switch limit)
Our method (minimalization)

100
1
0

1

2
3
Cut size	

45

Figure 9: The number of tests versus cutset size for the Fukui-TEPCO network.
Our method shows a remarkable reduction in test number, several orders of magnitude, even though the naive method took advantage of the distance limit of line
sections.
The specification is given in Table 32 . To the best of our knowledge, there is nobenchmark network that matches this size and specificity. We conducted the experiments with just our method of minimalization, since other methods did notscale to handle this large-scale network. We examined unrestorable cutsets of size
four or less, |U | ≤ 4, due to the scalability limit.

Figure 9 shows the number of tests. The numbers for the naive methods were
just counted without testing. Our method reduced the number of tests by fiveorders of magnitude compared to the naive method, since the number of minimal
hitting sets smaller than nine was 10,539, many fewer than the possible edge combinations. Figure 10 shows the distance distribution of line sections in a minimal
unrestorable cutset. Our method found unrestorable cutsets consisting of line sections separated by up to 18 switches, which implies the naive method can work
more efficiently with this distance limit. However, it still has to examine 226 times
more cutsets than our method, as shown in Figure 9, and so our method outperformed the naive method even with the distance limit. It is worth noting that the2
The dataset of Fukui-TEPCO network is available from http://www.hayashilab.sci.
waseda.ac.jp/RIANT/riant_test_feeder.html

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures 15

Probability distribution	

0.16
0.14
0.12
0.1
0.08
0.06
0.04
0.02
0
0

5

10

15

20

Distance between lines in unrestorable cut	# of unrestorable cuts  

Figure 10: Probability distribution of distance between lines in a minimal unrestorable cutset, in the Fukui-TEPCO network. There are unrestorable cutsets
with lines separated by 18 switches.
1400

Electrical constraints

1200

Topological constraints

1000
800
600
400
200
0
1

2
3
Cut size  

4

Figure 11: The number of minimal unrestorable cutsets |U| found by our method,
versus their size |U |, in the Fukui-TEPCO network. Their causes are also shown.
distance limit has been revealed by our method, and so we could not apply thelimit to the naive method without our method.
The number of minimal unrestorable cutsets found by our method is shown in
Figure 11 together with their causes. In contrast to Fig. 8, we found that the electrical constraints caused only a few small unrestorable cutsets whose sizes are lessthan three. However, the network has relatively many topologically unrestorable
cutsets that are small, which means the network is topologically not robust. Thisis because the network is not tightly connected compared to the 32-bus network;
their average degrees are 2.17 and 2.25, respectively. We evaluated the coverageof our method using random sampling as follows. We selected 4,771,000 cutsets
uniformly and randomly, and found 1,450 minimal unrestorable ones from those
selected. Our method did not overlook any of them, which proves its high accuracy.
Table 4 shows the calculation time. Testing a suspicious cutset by Algorithm 1
required only 4.81 seconds on average. Total CPU time for Algorithm 2 was 98,733
seconds (about a day). The maximum amount of memory used through our method

16

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi

Table 4: Computation time for Fukui-TEPCO network
Algorithm 1 (average per test)
Algorithm 2

4.81 sec
98,733 sec

is 334 GB. This calculation time is long but acceptable, since it would be performed
only once at the design stage (the naive method is, of course, unacceptable, because it takes a year even with the distance limit). Calculating a set of feasible
configurations C requires a few hours as shown in [6].

5Conclusions

In this paper, we have introduced an efficient method to find unrestorable cutsets
exhaustively. Although unrestorable cutsets have not gathered much attention in
the research community, it is a crucial tool with which to guarantee the restorabilityof distribution networks. Finding all unrestorable cutsets is a computationally
tough problem, but we tackled it with efficient algorithms based on hitting sets
and ZDDs; we first select a small number of suspicious cutsets from the many
ones possible by using hitting sets, and performed feasibility tests against the
selected cutsets with ZDD algorithms without complex power flow calculation.
Experiments showed our method reduced the number of tests by five orders ofmagnitude (relative to the naive approach) with no significant false negatives.
Each test was executed in just a few seconds in our method. Our work uncovered
the vulnerability of a large-scale distribution network thoroughly for the first timeever.
In future work, we will consider the significance of each unrestorable cutset;
e.g., the number of intact sections that cannot be restored under the cutset. We
also will develop an optimal strategy to redesign the distribution network basedon the significance of the failure and fixing cost.
We believe that our hitting set approach to vulnerability analysis offers generality to some extent and it can be successfully applied to other complex systems.

Acknowledgement
We would like to thank Takahisa Toda for his energetic support in implementing
his hitting set enumeration algorithm.

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures 17

References[1] M. Baran and F. Wu. Network reconfiguration in distribution systems forloss reduction and load balancing. IEEE Transactions on Power Delivery,
4(2):1401–1407, 1989.
[2] R. Billinton and P. Wang.
Reliability-network-equivalent approach to
distribution-system-reliability evaluation. IEE Proceedings of Generation,
Transmission and Distribution, 145(2):149–153, 1998.
[3] Y. Hayashi, S. Kawasaki, J. Matsuki, H. Matsuda, S. Sakai, T. Miyazaki,
and N. Kobayashi. Establishment of a standard analytical model of distribution network with distributed generators and development of multi evaluation
method for network configuration candidates. IEEJ Transactions on Powerand Energy, 126(10):1013–1022, 2006. in Japanese.
[4] Y. Hayashi and J. Matsuki. Loss minimum configuration of distribution system
considering N-1 security of dispersed generators. IEEE Transactions on Power
Systems, 19(1):636 – 642, 2004.
[5] T. Inoue, H. Iwashita, J. Kawahara, and S. Minato. Graphillion: Software
library designed for very large sets of graphs in Python. Technical report,
Hokkaido University, Division of Computer Science, TCS Technical Reports,
TCS-TR-A-13-65, 2013.
[6] T. Inoue, K. Takano, T. Watanabe, J. Kawahara, R. Yoshinaka, A. Kishimoto,
K. Tsuda, S. Minato, and Y. Hayashi. Distribution loss minimization withguaranteed error bound. IEEE Transactions on Smart Grid, 5(1):102–111,
2014.
[7] D. E. Knuth. The Art of Computer Programming: Combinatorial Algorithms
Part 1, volume 4A. Addison-Wesley, USA, 2011.
[8] J. Lavaei, A. Rantzer, and S. Low. Power flow optimization using positive
quadratic programming. In Proceedings of the 18th IFAC World Congress,
2011.
[9] W. Li, P. Wang, Z. Li, and Y. Liu. Reliability evaluation of complex radial
distribution systems considering restoration sequence and network constraints.
IEEE Transactions on Power Delivery, 19(2):753 – 758, 2004.
[10] W.-M. Lin and H.-C. Chin. A new approach for distribution feeder reconfiguration for loss reduction and service restoration. IEEE Transactions on
Power Delivery, 13(3):870–875, 1998.
[11] C.-C. Liu, S. Lee, and S. Venkata. An expert system operational aid forrestoration and loss reduction of distribution systems. IEEE Transactions on
Power Systems, 3(2):619 –626, 1988.

18

T. Inoue, N. Yasuda, S. Kawano, Y. Takenobu, S. Minato, and Y. Hayashi[12] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of Conference on Design Automation, pages 272–277,
1993.
[13] K. Nara, A. Shiose, M. Kitagawa, and T. Ishihara. Implementation of genetic algorithm for distribution systems loss minimum re-configuration. IEEE
Transactions on Power Systems, 7(3):1044–1051, 1992.
[14] C. Nguyen and A. Flueck. Agent based restoration with distributed energy
storage support in smart grids. IEEE Transactions on Smart Grid, 3(2):1029–
1038, 2012.
[15] R. Perez-Guerrero, G. Heydt, N. Jack, B. Keel, and A. Castelhano. Optimal restoration of distribution systems using dynamic programming. IEEE
Transactions on Power Delivery, 23(3):1589–1596, 2008.
[16] D. Shirmohammadi. Service restoration in distribution networks via network
reconfiguration. IEEE Transactions on Power Delivery, 7(2):952 –958, 1992.
[17] T. Toda. Hypergraph transversal computation with binary decision diagrams.
In Experimental Algorithms, volume 7933 of Lecture Notes in Computer Science, pages 91–102. Springer, 2013.
We give a sketch of proof for Theorem in Section 3.3.
Sketch of proof. We prove it by contradiction. Suppose the Theorem is false; there
exists unrestorable cutset U that cannot be any suspicious cutset, which is mappedfrom a hitting set. This means that any combination of U ’s neighboring edges is
not a hitting set, and so the network must be feasible upon removal of these edges.
We analyze the following two cases; when removing vertices U and their edges, thenetwork is (a) physically disconnected or (b) connected but does not satisfy theelectrical constraint.
• (a) Removing some of U ’s edges, the network can be disconnected, and so
it is infeasible, as shown in Figure 12 (a). This is a contradiction. (Strictly,
let d be the maximum degree of a vertex in U , it is required to remove d − 1edges from each vertex of U at most to make the network disconnected.)• (b) Removing some of U ’s edges, the network does not satisfy the electrical constraint and is infeasible, because it has more load than the network
without U does, as shown in Figure 12 (b). This is a contradiction. (In thiscase, removing just a single edge from each vertex of U is enough to makethe network electrically infeasible.)

We have the Lemma shown in Section 3.4 from the proof, since unrestorable
cutset U is mapped from hitting sets of |U |(d − 1) or less edges.

Verifying Distribution Networks for Secure Restoration by Enumerating All Critical Failures 19(a) Disconnected when removing U	
U	H	Disconnected	

Disconnected	

(b) Electrically infeasible when removing U	
H	

U	Overloaded feeder	

Higher load imposed	

Figure 12: (left) Networks without vertices of U and their edges, and (right) those
without some of U ’s edges (H). If the left networks are infeasible, the right network (a) is disconnected or (b) suffers from higher load, and so they must be also
infeasible and a set of these edges is a hitting set.