TCS -TR-A-12-59

TCS Technical Report

Loss Minimization of Power Distribution Networks
with Guaranteed Error Boundby

Takeru Inoue, Keiji Takano, Takayuki Watanabe,
Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto,Koji Tsuda, Shin-ichi Minato, Yasuhiro Hayashi

Division of Computer Science
Report Series A
August 21, 2012

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Loss Minimization of Power Distribution Networks
with Guaranteed Error Bound
Takeru Inoue ∗Keiji Takano †Takayuki Watanabe ‡Jun Kawahara ∗Ryo Yoshinaka §Akihiro Kishimoto †Koji Tsuda ¶ ∗Shin-ichi Minato k ∗Yasuhiro Hayashi ‡August 21, 2012

Abstract
Determining loss minimum configuration in a distribution network is a
hard discrete optimization problem involving many variables. Since more andmore dispersed generators are installed on the demand side of power systems and they are reconfigured frequently, developing automatic approaches
is indispensable for effectively managing a large-scale distribution network.
Existing fast methods employ local updates that gradually improve the loss
to solve such an optimization problem. However, they finally get stuck at local
minima, resulting in arbitrarily poor results. In contrast, this paper presents
a novel optimization method that provides an error bound on the solution
quality. Thus, the obtained solution quality can be evaluated in comparison
to the global optimal solution. Instead of using local updates, we construct
a highly compressed search space using a binary decision diagram and reduce
the optimization problem to a shortest path-finding problem. Our method wasshown to be not only accurate but also remarkably efficient; Optimization ofa large-scale model network with 468 switches was solved in three hours with1.56% relative error bound.
∗

T. Inoue, J. Kawahara, K. Tsuda, and S. Minato are with Minato Discrete Structure Manipulation System Project, ERATO, Japan Science and Technology Agency, Sapporo, Japan.
†
K. Takano and A. Kishimoto are with Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Tokyo, Japan.
‡
T. Watanabe and Y. Hayashi are with Faculty of Science and Engineering, Waseda University,
Tokyo, Japan.
§
R. Yoshinaka is with Graduate School of Informatics, Kyoto University, Kyoto, Japan.
¶
K. Tsuda is with Computational Biology Research Center, National Institute of Advanced
Industrial Science and Technology, Tokyo, Japan.
k
S. Minato is with Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.

1

2

Takeru Inoue et al.
Component 1

Component 2

Substation
Open switch
Closed switch

Component 3

Figure 1: Distribution network. By configuring switches appropriately, sections
are partitioned to several feeders, each of which is connected to a substation. Eachfeeder is distinguished by color.

1

Introduction

Distribution networks consist of several feeders and many switches. They areoperated to minimize resistive line losses while satisfying operational constraints
on line capacity and voltage drop. As more and more dispersed generators suchas fuel cells and solar cells are installed, the reconfiguration of switches would
be more frequently needed to avoid violating constraints and to preserve resistive
loss within an admissible range. Figure 1 shows a typical distribution network.
Reconfiguration amounts to optimizing the configuration of switches such that thepower loss is minimized. Since each switch configuration is represented as a binary
variable (open/closed), this task is formulated as a discrete optimization problem
with a set of binary variables. As a result of optimization, the network is divided toseveral feeders, where a feeder represents a set of sections connected to a substation.
Usable configurations must satisfy both topological and electrical constraints. The
topological constraint ensures that each section is connected to only one substation,and there is no loop in any feeder. The electrical constraint keeps line current andvoltage drop within admissible ranges. The loss minimization is a highly complex
combinatorial, nondifferentiable, and nonconvex optimization problem with a large
number of variables [18, 3].
Several optimization methods have been recently presented to solve this problem. Most of them rely on approximate techniques such as heuristics [6, 1, 18, 13]
and metaheuristics [5, 17, 10, 8]. Although these methods scale well with large
distribution networks, they provide no guarantee on the quality of the solution.
That is, because the solution can be arbitrarily worse than the optimal solution,these approaches may fail to reduce the running cost for managing the network.
Although the brute force method presented in [16] guarantees optimality, its scalability is currently limited to a network with at most one hundred switches. In
contrast, practical networks usually include several hundred switches [18, 14, 11].
Heuristics and metaheuristics employ local update rules of configuration that
gradually lead to a smaller loss. Since the search space is discrete and non-convex,

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound
x1

x2

x3
1

-3
2

-3

3

x4
-2

1
1

-2

Figure 2: Binary decision diagram (BDD) corresponding to a set of bit vectors
satisfying the constraints (2). Each bit vector is represented as a path from theroot node to the terminal. The nodes in a BDD are organized in several levels.
Solid and dotted arrows from level i to i+1 indicate xi = 1 and xi = 0, respectively.
For example, the path that consists of dotted, solid, solid, and dotted arrows inthis order corresponds to x = 0110 and its cost is 0 − 3 + 1 + 0 = −2. Note that
this is the shortest path from the root to the terminal in the BDD.
they eventually get stuck at local minima. The local minima problem can besolved, however, by organizing the search space in an appropriate way as in our
approach. Consider the following example problem with four binary variables,
min 2x1 − 3x2 + x3 − 2x4x(1)

subject to the constraints
HamDist(x, 0000) ≤ 2, HamDist(x, 0101) ≥ 2,(2)

where HamDist denotes the Hamming distance. The optimal solution is achieved
at x = 0110 with optimal value −2, but it also has local minima at x = 1100 and
x = 0011 with suboptimal value −1. This problem can be reduced to a simple
shortest path-finding problem by means of a binary decision diagram (BDD) [15],which is a compact data structure that represents a set of bit vectors. The BDD
corresponding to the constraints is shown in Figure 2, where each bit vector satisfying the constraints is represented as a path from the root node to the terminal
node. The nodes in a BDD are organized in several levels. Solid and dotted arrows
from level i to i + 1 indicate xi = 1 and xi = 0, respectively. The main advantage
of BDD is that, in certain settings, the BDD size grows only polynomially even
if the number of represented bit vectors grows exponentially [15]. Let us assign
the coefficients in the objective function (1) to solid arrows as edge weights. Zeroweights are assigned to dotted arrows. Now, the optimal solution corresponds tothe shortest path from the root node to the terminal and can easily be obtainedby invoking search algorithms such as Dijkstra’s algorithm.
If BDD is used to solve the loss minimization problem, we must overcome thefollowing two difficulties. First, BDDs representing topological and electrical constraints have to be constructed efficiently. We present novel algorithms for BDD
construction specifically designed for electrical networks. Second, since the power

4

Takeru Inoue et al.

loss is not a linear function, more measures are necessary to reduce it to the shortest
path-finding problem. To this aim, the distribution network is divided into several
components where the total loss is tightly approximated as the sum of those of individual components. The BDD is transformed into a component-level diagram byaggregating binary variables into categorical variables. Notably, an error boundof our solution can be derived, thus one can always evaluate the quality of oursolution in comparison to the global optimal solution. So far, such a guarantee is
not available in the other methods except brute-force.
The construction of BDD is performed under a full-blown support of a collection of algorithms implemented in BDD software packages such as CUDD1 andBuddy2 . They usually support reduction, reordering of variables and all kinds ofbinary operations. They are highly optimized via extensive use of cache to prevent
unnecessary computation.
In experiments, we use the model network developed in 2006 by Fukui University and Tokyo Electric Power Company (TEPCO) [9]. It closely models a typicalJapanese distribution network including 72 feeders and 468 switches. The network
consists of residential, industrial, and commercial areas. Each section has a different time-course load profile that is deliberately determined by expert curators. To
our best knowledge, there are no benchmark networks that compare to this sizeand specificity. For example, the benchmark networks by IEEE power and energy
society3 have at most 12 switches, and those by North Dakota State University4
have at most 27 switches. The benchmark network used in our experiments has
not been disclosed outside Japan, but we will make it publicly available upon acceptance of this paper. Our experimental results showed remarkable efficiency andreliability of the algorithm; by representing 1.5 × 1070 feasible configurations as acompact BDD, the solution was obtained in less than three hours using one CPU
core and the relative error bound was about 1-2%. It implies that our novel BDDbased approach to global optimization can be successfully applied to solve generalcomplex problems.
The rest of this paper is organized as follows. Section 2 introduces the loss minimization problem. Section 3 describes algorithms to construct BDDs for topological and electrical constraints. Section 4 explains the variable aggregation method
for reducing the problem to a shortest path-finding problem. Section 5 reports our
experimental results and Section 6 concludes the paper.

2

Loss Minimization Problem

This section formulates the loss minimization problem. The distribution network
is an undirected graph where vertices are either substations, switches or junctions
1

http://vlsi.colorado.edu/~fabio/CUDD/
http://buddy.sourceforge.net/manual/main.html
3
http://www.ewh.ieee.org/soc/pes/dsacom/testfeeders/4
http://venus.ece.ndsu.nodak.edu/~kavasseri/reds.html
2

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound5

and links are sections. For simplicity, we assume that each substation provides
single feeder. An open switch can cut the line. The configuration of switches iscontrolled to minimize the power loss. A junction has more than two links attachedwith no switching function. Each section i ∈ {1, . . . , m} has load Ii , impedance Zi
and resistance Ri . Notice that section load is represented as constant current [10]and uniformly distributed on the section.
The configuration of n switches is described as an n-dimensional binary vectorx ∈ {0, 1}n , where closed switches are denoted as one. Given ` substations, a valid
configuration of switches partitions the set of sections into ` feeders, each of whichis connected exclusively to a substation. Additionally, each feeder must be loopfree. Once the partition is fixed, the set of upstream sections Ciup can be definedas the sections on the path from the substation to section i (including i). The setof downstream sections is defined as the sections farther from the substation thansection i (excluding i). The line current Ji at section i is determined asX
Ji (x) =Ij + Ii(3)
j∈Cidown

via the backward sweep [4]. The voltage drop at the end of section i is described
as
#
"
X
X
Ij
Di (x) =
Zj
(4)
+
Ik .
2
up
down
j∈Ci

k∈Cj

Finally, the loss minimization problem is formulated as follows,
min
x

s.t.

m
X

Ri Ji2 (x),

(5)

i=1

Configuration x provides valid feeders
Ji (x) ≤ J

max, Di (x) ≤ D

max, i = 1, . . . , m.

(6)
(7)

Constraints (6) and (7) will be referred to as the topological constraint and theelectric constraint later on. The electric constraint ensures that the current andvoltage are within admissible limits everywhere.

3

Binary Decision Diagrams

A BDD, such as depicted in Figure 2, is a loopless directed graph with one root
node and one terminal node. Each non-terminal node has solid and dotted arrows
called one-arc and zero-arc, respectively. A path from the root to the terminal
corresponds to a bit vector. An advantage of BDD is that binary operations for two
BDDs, such as union and intersection, can be performed without transforming the
BDDs into any other data structures. For example, given two BDDs representing

6

Takeru Inoue et al.

Substation node
Closed switch
Open switch

Figure 3: Dual representation of the distribution network in Figure 1. Basically,each switch corresponds to an edge and a section is represented as a node. Exceptionally, a set of sections connected with a junction is also represented as a node.
A substation and adjacent sections are represented as a substation node.
{x | F (x) = 1} and {x | G(x) = 1}, a new BDD representing {x | F (x) =1} ∧ {x | G(x) = 1} can be constructed efficiently and directly by the intersection
operation [15].
As mentioned in Section 1, we reduce the optimization problem to the shortest
path-finding problem. As the first step, all bit vectors satisfying the topologicalconstraint are represented as a BDD. All bit vectors satisfying each electrical constraint are also represented as a BDD. The final BDD that contains all bit vectors
satisfying all constraints is created via taking an intersection of multiple BDDs
using a BDD package.
This section employs a dual representation of the distribution network (Figure 3). Basically, a switch corresponds to an edge and a section is represented asa node. A set of sections connected by a junction is also represented as a node.
A substation with all neighboring sections is described as a special node called
substation node. If a switch is open, the corresponding edge is removed. Oncea configuration of switches is defined, its corresponding subgraph of the originalgraph is uniquely determined. Since each feeder has to be a tree rooted on thesubstation node, the topological constraint requires the subgraph to be a rooted
spanning forest.

3.1

Topological Constraint

Let us consider a small graph with two root nodes such as depicted upper left
in Figure 4, and assume the order of edges is determined as shown. All rooted
spanning forests of this graph can be represented with the inclusion-exclusion tree
in Figure 4. One-arcs at level i indicate that the i-th edge is included in thesubgraph and zero-arcs indicate exclusion. By looking at the conditions of theedges on a path from the root of a leaf, its corresponding subgraph is determined.
The inclusion-exclusion tree can be constructed level-by-level. Given the subtree
up to level i − 1, all candidate subgraphs for level i are created and those withpaths between substation nodes (i.e., shortcuts), loops or unreachable nodes are
removed.

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound

7

4

1
7

5

3
2

6

Figure 4: Inclusion-exclusion tree representing all rooted spanning forests. The
solid line (1-arc) at the i-th level indicates the i-th edge is included and the dottedline (0-arc) indicates exclusion. The leaf nodes correspond to all rooted spanning
forests of the graph shown above.
Let h(x) denote the Boolean function that returns one if switch configuration x
leads to a rooted spanning forest and zero otherwise. The inclusion-exclusion tree isan uncompressed representation of all configurations satisfying h(x) = 1. This tree
can be compressed to the form of a BDD by merging tree nodes with “equivalent”
downstream subtrees into one node. For example, the three nodes highlighted witharrows in Figure 4 are equivalent and can thus be merged. Internal nodes a and b
corresponding to decision paths a1 , . . . , as and b1 , . . . , bs , respectively, are defined
to be equivalent iff{(xs+1 , . . . , xn ) | h(x) = 1, x1 = a1 , . . . , xs = as }= {(xs+1 , . . . , xn ) | h(x) = 1, x1 = b1 , . . . , xs = bs }.
This indicates that a and b has the the same set of downstream decisions after
taking paths a1 , . . . , as and b1 . . . , bs , respectively.
Due to excessive time and memory cost, it is not desirable to construct thewhole tree before compression. Thus we need to merge the tree nodes on the fly
when new candidates are created at each level. Our approach identifies equivalentsubgraphs by looking at the color profile of “frontier nodes”. At the i-th level, edges
i, . . . , n are not yet processed. Frontier nodes refer to the nodes adjacent to at least
one unprocessed edge. As shown in Figure 4, the nodes connected to a substation
node via processed edges are distinguished by color. The nodes not yet connected
to any substation node are left uncolored. Interestingly, two subgraphs with thesame set of frontier nodes are equivalent if they have the same color profile. Whencandidate subgraphs for a new level are created, those with shortcuts, loops andunreachable nodes are removed. This removal decision depends only on the color
profile of frontier nodes, hence the whole downstream subtree depends only on the
profile. By merging equivalent nodes on the fly, a compact BDD is produced in a
top-down manner with remarkable efficiency.
Historically, Coudert was the first to construct a BDD representing substructures of a graph [7]. This algorithm was inefficient, because it employed a bottom-

8

Takeru Inoue et al.

up procedure of aggregating small BDDs by binary operations. Recently, Knuth
presented a revolutionary top-down path enumeration algorithm, simpath, basedon a similar frontier property [12]. Our algorithm can be seen as an extension of
simpath for rooted spanning forests. To our best knowledge, this extension is noveland plays an indispensable role for the success of loss minimization.

3.2

Electrical Constraints

The electrical constraint with respect to a substation specifies the limit on line
current at the substation and voltage drop at the leaves of the corresponding
feeder. These values depend only on the corresponding feeder and are irrelevantto the other feeders. Due to this property, a BDD representing each electricalconstraint includes only a small number of variables and is much smaller than thatof the topological constraint.
In constructing the BDD for a substation, edges (i.e., switches) are ordered ina breadth-first manner starting from the corresponding substation node. Then,
we start to construct an inclusion-exclusion tree. Given the tree up to the i −1-th level, candidates for new nodes are created. The candidates violating any
electrical constraint are removed at this point. This procedure is valid due to themonotonicity of line current and voltage drop; they only increase when the feeder
expands. After the whole tree is generated, it is reduced to a BDD using the BDD
package.

4

Variable Aggregation

Since the resistive loss is a nonlinear function of the switch configuration x, we needto transform the final BDD into the search space by aggregating the variables in acomponent of the distribution network. As shown in Figure 1, network components
are defined as the connected components of the distribution network after removing
the root sections (i.e., sections adjacent to substations) and the first junctions(i.e., junctions adjacent to root sections). Switches 1, . . . , n are divided to subsets
M1 , . . . , Mq for q components. Similarly, the configuration vector x is divided tosubvectors x1 , . . . , xq . Non-root sections of each component are represented as
N1 , . . . , Nq , and the set of root sections is represented as U . Using this notation,
the objective function (5) is rewritten as
f (x) =Xi∈U

Ri Ji2 (x) +q X
XRi Ji2 (xk ).

k=1 i∈Nk

Importantly, the loss at a non-root node depends only on the configuration ofswitches in its component, because the line current at a section depends only on
downstream sections of that section.

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound

BDD

9Component-level
DiagramComponent 1

Component 2

Component 3

Figure 5: Variable aggregation. Boundary nodes are shown as bold circles. In thecomponent-level diagram, two nodes are connected if there is a path between themin the BDD.

4.1

Approximation

Minimizing f (x) is extremely difficult due to global dependencies of Ji at root
sections. However, when root section are ignored as below;f ∗ (x) =q X
XRi Ji2 (xk ),(8)

k=1 i∈Nk

the global optimal solution x∗ minimizing (8) under the topological and electric
constraints can be obtained by the following procedure of variable aggregation.
Let us define the aggregated categorical variable for xk as vk ∈ {0, . . . , 2|Mk | − 1}.
Although vk might take 2|Mk | different values in the worst scenario, the domain ismuch smaller in most cases due to topological and electric constraints.
A component-level diagram is created as follows. First, the BDD is rearranged
such that the variables in a component are aligned next to each other. The set ofnodes located at the top level in each component is called boundary nodes (Figure 5). As the first step, only the boundary nodes are copied to the componentlevel diagram. Edges between these nodes are then created by enumerating all
BDD paths between the boundary nodes. More specifically, if there is a path in
BDD, an edge is created in the component-level diagram. A BDD path from component k to k + 1 specifies a configuration of switches for vk in the k-th component.
We compute the total loss in the component corresponding to the BDD path andassign it as the weight of the new edge in the component-level diagram. If there
are multiple BDD paths, the minimum loss is taken as the weight. Finally, theoptimal solution to (8) is obtained as the shortest path from the root node to theterminal in the component-level diagram.

10

4.2

Takeru Inoue et al.

Error Bound

Since the above solution is merely the global optimal solution to an approximatedproblem (8), the achieved loss for the original problem is suboptimal, i.e., f (x∗ ) ≥fopt . Nevertheless, an error bound f (x∗ ) − fopt ≤  can be derived theoretically.
Let us revise the original optimization problem as follows: Minimize (5) subject to(6), (7) and a new constraintX

Ji (x) =

n
X

Ii .

(9)

i=1

i∈U

It indicates that the sum of line current at the root sections is equal to the sum ofload of all non-root sections. Since this constraint holds for any x satisfying the
topological constraint, the optimal solution remains unchanged even after introducing the new constraint. Now, assume that Ji (x) is not a function of x and isregarded as a new free variable Ji ,frelax =Xminx,{Ji | i∈U }Ri Ji2 +

i∈U

q X
X

Ri Ji2 (xk ),k=1 i∈Nk

subject to (6), (7) and (9). Here the optimal solution to frelax is x∗ and
Ji∗ =

m
X
j=1

Ij /(Ri

X 1
j∈U

Rj

).

It always holds frelax ≤ fopt because frelax relaxes the original problem. The error
bound is therefore finally obtained as  = f (x∗ ) − frelax . Similarly, the relative
error of x∗ is bounded asf (x∗ ) − foptf (x∗ ) − frelax≤.
f (x∗ )f (x∗ )

5

(10)

Experiments

As mentioned in Section 1, we employ the Fukui-TEPCO network including 72
feeders and 468 switches (Table 1). The network has 63 components. The numberof switches in a component is 7.43 on average, while the minimum and maximum
are 3 and 20, respectively. We also generated subsampled versions of the network
containing 20, 39, 59, 78, 99, 118, 235, and 352 switches. Among hourly load
profiles, the peak load at 2 p.m. and the baseline load at 4 a.m. were used in theexperiments. The experiments were conducted using a single core in Intel Xeon
CPU E31290 (3.60 GHz).
Figure 7 shows the computation time of our method and that of the brute force
method for networks of different sizes and two time points (2 p.m. and 4 a.m.).
Figure 8, left, plots the relative error bound (10) of our solutions. Our solution forLoss Minimization of Power Distribution Networks with Guaranteed Error Bound

11

Table 1: Specification of the Fukui-TEPCO network.
Number of feeders
Number of switches
Number of sections
P
Total load, ni=1 Ii
Line capacity, J max
Sending line voltage
Maximum voltage drop, Dmax

72
468
648
287 MW at 2 p.m., and 113 MW at 4 a.m.
300 A
6.6 kV
0.3 kV

Figure 6: Switch configuration of the Fukui-TEPCO network determined by our
method for the load profile at 4 a.m.
4 a.m. is partly visualized in Figure 6. Our method finished the whole optimization
procedure in less than three hours for the full network with 468 switches and therelative error bound was 1.56% at most. As expected, the computational time of
the brute-force approach exploded quickly. With a time limit of 10,000 seconds,
the global optimal solution was obtained only up to 78 switches. Figure 8, right,
shows the true relative error of our solutions up to 78 switches. In many cases,
our solution was indeed optimal (i.e., the relative error was zero). The maximum
relative error was about 0.0225%; much smaller than the theoretical bound.
Figure 9 shows the computation time required by each process. The construction of BDDs for electrical constraints takes the largest fraction of the computation
time. This is because large inclusion-exclusion trees are produced without on-thefly merging, and computing voltage drop for each subgraph is time-consuming. In
contrast, the construction for the topological constraint finished in less than one
second even for up to 468 switches, clearly indicating the significant importance ofon-the-fly merging. The BDD construction for electrical constraints took signifi-

12

Takeru Inoue et al.

Computation time [sec.]

10000

Proposed method (2 p.m.)
Proposed method (4 a.m.)Brute force (2 p.m.)
Brute force (4 a.m.)

1000

100

10

1
0

100

200
300
# of switches

400

500

Figure 7: Computation time of the proposed method and the brute force method.
f(x*) - frelaxf(x*)f(x*) - fopt
f(x*)

0.02

0.0003

Relative error

2 p.m.
4 a.m.

0.00025

2 p.m.
4 a.m.

0.015
0.00020.01

0.000150.0001

0.005
5e-05
0
0

100

200

300

400

0
500
0
# of switches

10 20 30 40 50 60 70 80

Figure 8: (Left) Relative error bound of the solutions. (Right) True relative errorof the solutions up to 78 switches.
cantly more time for the 4 a.m. time point; Since the section loads were smaller atnight, a larger inclusion-exclusion tree had to be explored to reach the line current
capacity.
The number of nodes in the BDDs for the constraints are shown in Figure 10.
Since a single BDD node requires about 32 bytes, this figure indicates that theamount of memory required to store the BDD was about 100 MB and 100 KB for2 p.m. and 4 a.m., respectively. Given a BDD, it is easy to count the number ofrepresented bit vectors by a recursive algorithm [2]. We therefore computed thenumber of feasible configurations for the topological constraint and all constraints
combined. The results are shown in Figure 11 and Table 2. Interestingly, sucha large number of feasible configurations is compressed to a small BDD. Larger
BDDs do not necessarily represent larger numbers of bit vectors. Intuitively, theBDD size gets smaller if the set of bit vectors has some kind of regularity. In
general, however, it is hard to predict the size of BDDs in advance for a given
problem.

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound

13

Topological constraint
Electrical constraints
Intersection
Component-level diagram
Shortest path search
4 a.m.

2 p.m.
10000
Computation time [sec.]

1000
100
10
1
0.1
0.01
0

100

200

300

400

500 0
# of switches

100

200

300

400

500

Figure 9: Computation time of each process in the proposed method.
1e+07

All constraints (2 p.m.)
All constraints (4 a.m.)
Topological constraint

1e+06

BDD size

100000
10000
1000
100
10
0

100

200
300
# of switches

400

500

Figure 10: BDD size for the constraints.

6

Conclusion

In this paper, we have developed an efficient network reconfiguration method thatyields an error bound. In the real-world settings, ad-hoc algorithms without solution quality guarantee are unlikely to be used because of the danger of returning
solutions incurring an excessive running cost for managing the network. It may bepossible to reduce the probability of such a catastrophic failure caused by localupdate-based methods, e.g. by using multiple starting points. However, since
distribution networks are fundamental infrastructure, failures cannot be allowed
even with the smallest probability. In contrast, our method is the first reliable
method with solution quality guarantee, hence we believe that this is an important
step towards automated network reconfiguration.

Acknowledgement
We would like to thank Takashi Horiyama, Takeaki Uno, Hirotaka Takano, Masakazu
Ishihata and David duVerle for their valuable comments.

14

Takeru Inoue et al.

# of feasible configurations

1e+80

All constraints (2 p.m.)
All constraints (4 a.m.)
Topological constraint

1e+70
1e+60
1e+50
1e+40
1e+30
1e+20
1e+10
1

0

100

200
300
# of switches

400

500

Figure 11: Number of feasible configurations.
Table 2: Numbers of feasible configurations in a network of 468 switches.
Condition
All constraints, loads at 2 p.m.
All constraints, loads at 4 a.m.
Topological constraint

Number of feasible configurations
56549012847446003723757714431732193815091620755492933270200
15052768726188994695810341375588783632354554002783638970270450179200000
218646889093444243387855355581579747968214496454992053728787429330078125

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. Bryant. Graph-based algorithms for boolean function manipulation. IEEE
Transactions on Computers, C-35(8):677–691, 1986.
[3] E. Carreno, R. Romero, and A. Padilha-Feltrin. An efficient codification tosolve distribution network reconfiguration for loss reduction problem. IEEE
Transactions on Power Systems, 23(4):1542–1551, 2008.
[4] C. Cheng and D. Shirmohammadi. A three-phase power flow method for realtime distribution system analysis. IEEE Transactions on Power Systems,
10(2):671–679, 1995.
[5] H.-D. Chiang and R. Jean-Jumeau. Optimal network reconfigurations in distribution systems. i. a new formulation and a solution methodology. IEEE
Transactions on Power Delivery, 5(4):1902–1909, 1990.
[6] S. Civanlar, J. Grainger, H. Yin, and S. Lee. Distribution feeder reconfiguration for loss reduction. IEEE Transactions on Power Delivery, 3(3):1217–1223,
1988.
[7] O. Coudert. Solving graph optimization problems with ZBDDs. In Proceedingsof European Design and Test Conference, pages 224–228, 1997.

BDD size
32239853171
1554

Loss Minimization of Power Distribution Networks with Guaranteed Error Bound

15[8] B. Enacheanu, B. Raison, R. Caire, O. Devaux, W. Bienia, and N. HadjSaid.
Radial network reconfiguration using genetic algorithm based on the matroid
theory. IEEE Transactions on Power Systems, 23(1):186–195, 2008.
[9] 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.
[10] 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.
[11] Y.-J. Jeon, J.-C. Kim, J.-O. Kim, J.-R. Shin, and K. Lee. An efficient simulated annealing algorithm for network reconfiguration in large-scale distribution systems. IEEE Transactions on Power Delivery, 17(4):1070–1078, 2002.
[12] D. Knuth. The Art of Computer Programming, volume 4, Fascicle 1: Bitwise
Tricks and Techniques; Binary Decision Diagrams. Addison-Wesley, USA,2009.
[13] 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.
[14] T. McDermott, I. Drezga, and R. Broadwater. A heuristic nonlinear constructive method for distribution system reconfiguration. IEEE Transactions on
Power Systems, 14(2):478–483, 1999.
[15] S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of Conference on Design Automation, pages 272–277,
1993.
[16] A. Morton and I. Mareels. An efficient brute-force solution to the network
reconfiguration problem. IEEE Transactions on Power Delivery, 15(3):996–
1000, 2000.
[17] 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.
[18] D. Shirmohammadi and H. Hong. Reconfiguration of electric distribution
networks for resistive line losses reduction. IEEE Transactions on Power
Delivery, 4(2):1492 –1498, 1989.