Power Grid Decomposition Based on Vertex Cut Sets and Its Applications to
Topology Control and Power Trading
Shuai Wang & John Baillieul

arXiv:1803.05860v2 [] 18 Mar 2018

Abstract
It is well known that the reserves/redundancies built into the transmission grid in order to address a variety of contingencies
over a long planning horizon may, in the short run, cause economic dispatch inefficiency. Accordingly, power grid optimization
by means of short term line switching has been proposed and is typically formulated as a mixed integer programming problem
by treating the state of the transmission lines as a binary decision variable, i.e. in-service or out-of-service, in the optimal
power flow problem. To handle the combinatorial explosion, a number of heuristic approaches to grid topology reconfiguration
have been proposed in the literature. This paper extends our recent results on the iterative heuristics and proposes a fast grid
decomposition algorithm based on vertex cut sets with the purpose of further reducing the computational cost. The paper
concludes with a discussion of the possible relationship between vertex cut sets in transmission networks and power trading.

I. I NTRODUCTION
Siting and maintaining massive power infrastructure is not cheap [1] and therefore makes the optimal use of existing
network a priority. Because of the fast time constants in changing the system state and the very low costs, corrective
switching operations, including transmission line switching, bus-bar switching, and shunt element switching, etc., are often
the first post-contingency corrective action to be considered and implemented [2].
The focus of corrective switching has been mainly on handling line overload [3], [4] and voltage violations [5], [6],
and most recently, on co-optimizing the generation along with the network topology [7], [8], [9]. Based on the DC optimal
power flow (OPF) problem, such co-optimization is typically formulated as a mixed integer programming problem (MIP) with
some binary variables denoting the choices of transmission line switches. There are a number of challenges in implementing
effective transmission topology control, including understanding and avoiding voltage problems, transient instability, reactive
power problems [10] and, most importantly, the ability to find a good solution within a time that is short enough to be of
practical use.
Due to the combinatorial nature of the problem and the nonlinearities inherent to networks, the approaches proposed in
the literature focus on the reduction of the search space of possible switching actions [11]. Accordingly, a set of fast line
switching heuristics have been proposed, and the running time records have been consistently set and then shattered [7],
[8], [9]. In all of these studies, simulations show that significant savings are indeed possible from transmission switching.
While optimality for this NP-hard problems is ever elusive, theorems together with simulation results on a set of iterative
heuristics in [12], nevertheless, offer some justification that, with similar searching space, the locally optimal switching at
each stage of an iterative heuristic has the best chance in reducing generation cost while enforcing connectivity.
The present paper examines possible grid decomposition approaches that are able to further reduce the search space of
possible switching operations while at the same time retain the locally optimal switchings to the maximum degree. The
paper is organized as follows. In Section II, we first discuss the typical limitations with respect to the composability and
composationality of real transmission grids, showing the challenges in grid decomposition. A series of trade-off is then
proposed, and this forms the main thread of the paper. Section III proposes a decomposition method based on vertex
cut sets and pseudo biconnected components. Rather than intuitively using line outage distribution factor to quantify the
decomposition quality, Section IV makes a further trade-off by justifying the usage of locational marginal price range to
quantify the potential of a pseudo biconnected component in reducing generation cost. The useful properties of the vertex
cut set in LMP partitioning and power/FTR trading are discussed in great detail in Section V. A fast grid decomposition
algorithm is then proposed in Section VI, and its efficiency is tested in Section VII. The paper ends with concluding remarks
in Section VIII.
II. C OMPOSABILITY AND C OMPOSITIONALITY
When proposing heuristics to deal with the “largest machine in the world”, the transmission network, one natural idea
is a divide-and-conquer strategy. We ask whether this large and complex system can be usefully decomposed into smaller,
more tractable subsystems, thereby reducing the search space of line switching. Here, we refer the ease of building a system
out of subsystems as composability, and the ease of validation of system properties by using the related subsystems as
composationality [13].
Shuai Wang is with the Division of Systems Engineering and John Baillieul is with the Departments of Mechanical Engineering; Electrical and
Computer Engineering, and the Division of Systems Engineering at Boston University, Boston, MA 02115. Corresponding author is John Baillieul (Email:
johnb@bu.edu).
The authors gratefully acknowledge support of NSF EFRI grant number 1038230.

1

A transmission network can be modeled as a graph G = (V, E) such each node in V is either a substation bus, or
simply a bus connecting several transmission lines. There is an edge ei,j = (vi , vj ) ∈ E between two nodes if there is a
physical line connecting directly the elements represented by vi and vj . Note that the terms vertex/node/bus, link/line/edge
and grid/graph/network will be used interchangeably.
In graph theory, a biconnected component in a graph is one where if any node is removed (with its boundary edges),
the component will still be connected [14]. Reference [15] proves that the impact of topology control is strictly confined
within the biconnected component in which the line switching is applied in a transmission network. The decomposition of
a transmission network based on biconnected components is thus “clean” in the sense that if the sizes of all its biconnected
components are relatively small, the network will have high level composability and composationality.
Also proved in [15], the event occurs with probability 1 that disconnecting a transmission line will change every line flow
within the biconnected component that contained the disconnected line. The N-1 reliability standard of today’s transmission
network, requiring the system to move to a satisfactory state for any single line outage event, significantly increases
the likelihood of the whole network or a large portion of the network being biconnected. Despite of the desirability of
maintaining N-1 connectivity, the downside of large biconnected components is a significantly decreased level of the network
composability and composationality.
While we should not neglect that every switchable line has the potential to alleviate the congestion in a biconnected
component of a grid, simulation results in [8] showed that a fairly large portion of the switchable lines remained not
operated in most samples, and thereby might well go unnoticed. Such observations suggest the possibility that a biconnected
component of a grid may still be effectively further decomposed even if the interactions between the sub-grids of the
biconnected component are not zero.
Our work thus aims to find an optimal trade off between the size of sub-grids of the biconnected component and the
realized composability/composationality by the grid decomposition. The desired outcome should help us focus attention on
a relatively small set of promising switchable lines such that both the computational efforts and the attainable savings can
be reasonably controlled.
III. V ERTEX C UT S ETS & P SEUDO B ICONNECTED C OMPONENTS
The initially “clean” decomposition of a transmission grid involves a graph theory term called the cut vertex [14] which
is any single vertex/node whose removal increases the number of connected components of a graph and, by definition, is
the only element shared by two or more biconnected components of a graph.
Apparently, further decomposing a biconnected component needs something beyond the cut vertex, and we propose the
following:
Definition 1: A vertex cut set is a set of vertices of a graph which, if removed together with any incident edges, disconnects
the graph. The sub-graphs of a biconnected graph obtained by one or several vertex cut sets are called pseudo biconnected
components. The vertices in the vertex cut sets are the only elements shared by two or more pseudo biconnected components.
In addition, the union of several vertex cut sets for a given graph is also a vertex cut set.
Using the concept of vertex cut sets, a two-step construction of pseudo biconnected components can be carried out. Given
a graph and a vertex cut set, the disconnected subgraphs remaining when the vertex cut set, together with any incident
edges, is removed are called the pre pseudo biconnected components. From these, the pseudo biconnected components are
obtained by adjoining the vertex cut set to each pre pseudo biconnected component the entire vertex cut set along with the
incident edges that have been removed. Fig. 1 shows an example of the decomposition of a biconnected graph where the
three red nodes in the middle of graph form the vertex cut set. Note that the decomposition based on one vertex cut set may
not be unique. For example, the horizontal black edge in Fig. 1(a) can be either assigned to the black-edge sub-graph (Fig.
1(c1)) or to the blue-edge sub-graph (Fig. 1(c2)). Thus we do have some degree of discretion in decomposing the grid. To
reduce the search space of line switching, we will use the convention throughout this paper that, whenever possible, any
incident edges of the vertex cut set subject to our discretion will be assigned to a pseudo biconnected component that is
free
of congested
lines.
Ideally,
we would
expect the decomposition in Fig 1 to satisfy the following criteria:
(1) The interactions between any two lines belonging to two different pseudo biconnected components are insignificant;
(2) The size of the targeting pseudo biconnected component is large enough to contain all promising switchings;
(3) The size of the targeting pseudo biconnected components is small enough to be efficiently searched.
IV. Q UANTIFYING D ECOMPOSITION Q UALITY
So far, the interactions mentioned in Criterion (1) at the end of Section III are imprecisely specified, and hence we look
for some metrics to quantify the effects of line outages.
(j)
We introduce the well-known sensitivity, line outage distribution factor or LODF, denoted by ζi , of the line flow i with
(j)
respect to the removal of line j. In short, ζi denotes the percentage of line flow on line j that will show up on line i after
(i)
the outage of line j. Similarly, we can compute the LODF, denoted by ζj , of the power flowing through line j with respect

2

Fig. 1.

One example of the decomposition based on a vertex cut set formed by the three red nodes in the middle.

(j)

(i)

to the removal of line i. The pair of LODFs, ζi and ζj , are usually different. The interactions between the line pair
(j)
(i)
{i, j} are said to be insignificant if ζi and ζj are both small. Similarly, the interactions between two pseudo biconnected
components are said to be insignificant if the pair of LODFs for any two lines belonging to two different pseudo biconnected
components are small.
To quantify the quality of grid decomposition based on vertex cut set, we need to recalculate the LODFs for each possible
line switching which could be computationally intensive for large scale grids.
The computational overhead pushes us to make another trade off between the computational costs and the preciseness of
the metrics measuring the interactions in a grid. Such trade off is achieved by introducing another well-know sensitivity,
power transfer distribution factor or PTDF, which gives the sensitivity of the flow on one line with respect to a power
transfer between a pair of buses.
The PTDF, by definition, is essentially the difference between a pair of shift factors. In the DC power flow model, the
transmission sensitivity matrix Ψ, also known as the injection shift factor matrix, gives the sensitivities in line flows due
to changes in the nodal injections, with the reference bus assumed to ensure the power balance. Suppose Ψi,j1 denotes the
sensitivity in power flowing through line i due to one unit increase in the power injection at bus j1 and one unit decrease
in power injection at the reference bus, i.e.
Ψi,j1 =

∆f low in line i
,
∆injection at bus j1

then the shift factor difference |Ψi,j1 − Ψi,j2 | gives the PTDF of power flowing through line i with respect to one unit power
transfer between bus j1 and j2 .
The network LODFs, mathematically, are equivalent to the post-outage network PTDFs. While the pre- and post-outage
PTDFs are rarely equivalent, there usually exists a strong correlation between their values. Therefore, although the estimations
of the decomposition quality based on pre-outage PTDFs maybe different from those based on LODFs, such differences are
reasonably expected to be small.
Here, we would like to remark that the introduction of PTDF does reduce the computation cost associated with the
estimations of decomposition quality, but such computation effort is still relatively small compared with solving the updated
DCOPFs. The value of the following PTDF analysis, in fact, is more towards a fundamental understanding of some structural
properties of the grid decomposition, thus reducing the computational effort spent on finding the optimal vertex cut sets.
We now need to deal with the most challenging step of the decomposition, i.e. minimizing the interactions (PTDFs)
between pseudo biconnected components. Though highly desired, such decomposition quality is usually not achievable by
just using vertex cut sets as the cushion zones between pseudo biconnected components, due to the unavoidable strong
LODFs between those edges belonging to different pseudo biconnected components but incident to same nodes in the vertex
cut sets. Instead of complicating the decomposition by expanding the cushion zones to some sub-graphs containing both
vertex cut sets and the associated incident edges, we would like to stick to the vertex cut sets, indicating a necessity to modify
the criteria. Rather than struggling with the nominal PTDFs between pseudo biconnected components, our decomposition
instead aims to minimize the potentially “useful” portion of those PTDFs, i.e. the portion associated with the congestion
effect.
When talking about the congestion effect, it is natural to wonder about the the locational marginal price (LMP). In a
lossless DC power flow model, the LMP at a given bus, say bus i, is equal to the sum of the LMP at the reference bus and
the congestion cost which can be calculated using the following equation:
X
λi = λref −
(µj × Ψj,i )
(1)
j

3

where

Ψj,i

λi = LM P at bus i
λref = LM P at the ref erence bus
µj = Shadow price of line constraint j
= Shif t f actor f or real load at bus i on line f low j.

The sensitivity analysis of DCOPF model suggests that power transfer between buses with close LMPs usually can’t
change the generation cost as much as that between buses with significantly different LMPs, and similarly line switches in
areas with low range LMPs are typically of little use in reducing overall generation costs. Therefore, the goal of the partition
problem based on vertex cuts is to decompose the grid into two sub-grids with one being of high range LMPs and the other
being of low range LMPs.
V. T HE O PTIMALITY OF V ERTEX C UT S ETS
In this section, we will show a set of useful properties of vertex cut sets with respect to the decomposition based on
LMPs. The discussion starts with the following definition.
Definition 2: Suppose there is one line congestion in a transmission network and we are able to control certain number
of nodal injections, then the smallest set (i.e. of smallest cardinality) of buses that is able to fully alleviate the given line
congestion by changing least amount of nodal power injections is defined as the optimal set of buses for that congested
line.
Remark 1: The optimal set of buses for a given congested line may not be unique.
We first show that for a given congestion in one pseudo biconnected component, the optimal set of buses in another pseudo
biconnected component must be a subset of the vertex cut set. The complete proof involves two lemmas, one theorem, and
one proposition.
We start the proof by introducing the well established correspondence between power grids and electric circuits.
Mathematically, the DC power flow model is equivalent to a current driven network (an electric circuit comprised purely by
resistors and current sources) [15], where power injections are equivalent to current sources; power flowing through lines is
equivalent to current through edges, etc. See Table 1. Thus part of the following discussion will be focusing on resistance
networks with nodal current injections controlled by a set of current sources.
network potential injection
admittance
equation
circuit voltage V current I conductance G I = GV
grid
phase θ power P susceptance B P = Bθ
Table 1: The equivalence between current driven circuits and DC power flow models of transmission grids.
Lemma 1: If we are allowed to alter all controllable nodal power injections by arbitrary amount and all uncongested lines
have enough line capacity, then the cardinality of the optimal set of buses for a given congested line must be 2, i.e. the
optimal set of buses is a bus pair.
Proof: Shift factors do not change when the injection/withdrawal amount increases for any set of buses. Suppose line
i is overloaded by ∆i units of power and the power injections at bus j1 and j2 are controllable. In order to alleviate the
congestion of line i, the power injections at bus j1 and j2 need to be changed by
∆j1 &j2 =

∆i
.
|Ψi,j1 − Ψi,j2 |

Thus the pair of controllable buses with the largest shift factor difference associated with the congested line must be the
optimal set of buses for that congested line.
Theorem 1: ([16]) Any n-terminal connected resistance network is electrically equivalent to a circuit whose graph is a
complete graph consisting of n(n-1)/2 resistances. Such n-terminal equivalent graph can be obtained by using Kron Reduction
to eliminate all interior (non-terminal) nodes.
Remark 2: The above theorem can be easily extended to any disconnected graph by adding some trivial lines of infinite
resistance to make the equivalent graph connected and complete. The current flowing through those trivial lines must always
be zero no matter how the nodal current injections are changed.
Lemma 2: Suppose line i is connected to bus pair {i1 , i2 } and line j is connected to bus pair {j1 , j2 } in a connected
transmission network, and the reference directions of the power flowing through line i and line j are defined as from bus
i2 to bus i1 and from bus j2 to bus j1 , respectively. Then the shift factor differences Ψi,j2 − Ψi,j1 and Ψj,i2 − Ψj,i1 must
be of the same sign.
Proof: By keeping applying Kron reduction [16] to the original transmission network (shown in the right side of
Fig. 2) until all nodes but {i1 , i2 , j1 , j2 } are eliminated, we can create a 4-terminal equivalent grid with only four buses
{i1 , i2 , j1 , j2 } which is shown in the left side of Fig. 2. Note that the two red lines in Fig. 2 may be of different susceptance

4

Fig. 2.

The 4-terminal equivalent network of the original network.

but the direction of power flowing the lines, Pj and Pj 0 , must be the same. The same is true of the two blue lines. Thus
we focus our attention on the 4-terminal equivalent grid.
By the equivalence in Table 1, we can actually treat the 4-terminal equivalent grid as a 4-terminal resistance network and
discuss the problem in a circuit environment. Under the circuit environment, we denote the line resistances of the four black
lines in the left side of Fig. 2 as α, β, γ and δ, respectively, and suppose there is no current injections and withdrawals in
the network except one unit nodal injection at node i2 and one unit nodal withdrawal at node i1 . If the direction of red line
flow in the left figure is from node j2 to node j1 , we know Ψj,i2 − Ψj,i1 > 0, indicating
β
δ
< ,
γ
α
that we must have Ψi,j2 − Ψi,j1 > 0. If the direction of red line flow in the left figure is from node j1 to node j2 , we know
Ψj,i2 − Ψj,i1 < 0, indicating
δ
β
> ,
γ
α
that we must have Ψi,j2 − Ψi,j1 < 0.
Proposition 1: Suppose we use a vertex cut set to decompose a connected transmission network into n (n ≥ 2) subgraphs. Assume that we can arbitrarily change the power injection at all buses in the j-th sub-graph to alleviate a given
congested line in the i-th sub-graph (i 6= j), then one optimal pair of buses must be a subset of the vertex cut set.
Proof: Although the value of each entry in the injection shift factor matrix varies as the reference bus changes, the
PTDF or the difference between a pair of shift factors is independent of the choice of the reference bus. Suppose line i is
congested and is connected to bus i1 and i2 , and we pick up i1 as the reference bus and assuming the direction from i2 to
i1 as the positive power direction, we can get an injection shift factor matrix with all i-th row entries being non-negative.
Suppose there are M buses {n1 , ..., nM } that are shared by the j-th sub-graph and the rest of the graph. Clearly,
{n1 , ..., nM } is a subset of the vertex cut set. Then in order to prove the proposition, we just need to show that the shift
factor differences {Ψi,p −Ψi,n1 , ..., Ψi,p −Ψi,nM } cannot be all positive or all negative for any bus p that is owned exclusively
by the j-th sub-graph, i.e.
min{Ψi,n1 , ..., Ψi,nM } ≤ Ψi,p ≤ max{Ψi,n1 , ..., Ψi,nM }.
We first create two sub-networks to simplify the proof. The first sub-network (shown at the bottom middle of Fig. 3) is
created from the original network by removing all lines in the j-th sub-graph, and it is called the nearby sub-network. The
second sub-network (shown at the top middle of Fig. 3) is just the j-th sub-graph, and it is called the remote sub-network.
It is easy to see that the two sub-networks share nothing except the buses {n1 , ..., nM }. Buses {i1 , i2 } are interior buses of
the nearby sub-network, and bus p is interior bus of the remote sub-network.
Then an equivalent sub-network of the remote sub-network can be created by applying Kron reduction to the remote
sub-network until all nodes but {n1 , ..., nM , p} are removed. The equivalent sub-network obtained in this way is a KM +1
complete graph as shown at the top right corner of Fig. 3. An equivalent network of the original network can then be
created by putting together the nearby sub-network and the KM +1 equivalent sub-network. The process described above is
visualized in Fig. 3.
Suppose the reference direction of the power flowing through the line connecting bus p and nm (m = 1, ..., M ) in the
equivalent network (shown at the bottom right corner of Fig. 3) is defined as from bus p to bus nm . Then by Lemma 2, we
know that the change of power flowing through the line connecting bus p and nm (m = 1, ..., M ) in the equivalent network
due to one unit increase in nodal injections at bus i2 and one unit decrease in nodal injections at bus i1 is of the same sign
as that of the shift factor difference Ψi,p − Ψi,nm .
Finally, we denote the power flowing through the lines connecting node p and node nm (m = 1, ..., M ) as {Ip,n1 , ..., Ip,nM }

5

p
p
p

n1

...

nm

i1

n1

...n

...

nm

...

nM

nM

...

...

nm

KM+1
p

M

n1

i2

...
i1

Fig. 3.

n1

nm

...

nM

i2

n1

...
i1

...

nM

nm

i2

The network simplification process.

due to one unit nodal injection at bus i2 and one unit nodal withdrawal at bus i1 . By Kirchhoff’s current law, we must have
M
X

Ip,nm = 0

m=1

meaning
M
X

cm (Ψi,p − Ψi,nm ) = 0

m=1

where Ip,nm = cm Ψi,nm and cm are some positive coefficient by Lemma 2. Thus {Ψi,p − Ψi,n1 , ..., Ψi,p − Ψi,nM } cannot
be all positive or all negative.
Rather than limiting the discussion to single line congestion, we’d like to know if phenomena similar to Proposition 1 can
be found for scenarios with multiple congestions. Things become a little complicated here as the changes of line flows of
the congested lines due to the nodal injection regulations may not be all favorable, i.e. the alleviation of some congestions
may come inevitably at the expense of worsening other congestions, requiring all congestions being assigned proper weights
to evaluate the overall benefit of the nodal injection regulations. Since our main consideration is to reduce generation cost,
the shadow prices of line constraints are naturally used as the weights in the following discussion.
We will show that for multiple given congestions in one pseudo biconnected component, the optimal set of buses in another
pseudo biconnected component must also be a subset of the vertex cut sets. The complete proof involves one proposition
and two corollaries.
Proposition 2: Suppose we use a vertex cut set to decompose a connected transmission network into n (n ≥ 2) subgraphs. Assume that we can arbitrarily change the power injections at buses in the j-th sub-graph to alter the line flows in
the i-th sub-graph (i 6= j), then such impact on the i-th sub-graph can be precisely replicated/canceled by regulating the
power injections of the buses in the vertex cut set.
Proof: By the superposition principle in the DC power flow model, we just need to prove that all line flows in the
i-th sub-graph can always be set to zero if the net power injections at all interior buses of the i-th sub-graph are strictly
zero and if we can arbitrarily regulate the power injections at the buses in the vertex cut set.
We first show that the reduced nodal susceptance matrix B of any transmission network is positive definite. Since any
resistance network is a passive system that consumes energy, and the absorbed power is given by
P = v T Gv

(2)

where v is the nodal voltage vector and G is the reduced conductance matrix of the resistance network. It follows that the
energy consumption will always be positive only if all eigenvalues of G are positive. Thus, a criterion for passivity is that
G be positive definite. Since the DC model of power flow is equivalent to a current driven network as shown in Table 1, we
know the reduced susceptance matrix B in the DC power flow model is positive definite, meaning its inverse matrix B −1
is also positive definite.
Suppose, in the bus vector, the first l buses are owned exclusively by the i-th sub-graph, the middle m buses are owned
by the vertex cut set, and the last n + 1 buses containing the reference bus are owned exclusively by other sub-graphs,
respectively, we then have the DC power flow equation
θ = B −1 p

(3)

6

where p is the net nodal power injection vector, and θ is the nodal voltage angel vector. Based on the classification of the
buses, the reduced voltage angle vector θ can be decomposed into 3 sub-vectors
T
θT = [θlT θm
θnT ],

and the positive definite matrix B −1 can be decomposed into 9 sub-matrices
in
↓


B −1

Al×l
= Dm×l
Gn×l

at

out

↓

↓

Cl×n ← in
Fm×n  ← at
In×n ←out

Bl×m
Em×m
Hn×m

(4)

and we know the sub-matrix Em×m must have full rank and be positive definite. Thus we have


θm = Dm×l Em×m Fm×n p.
It follows that we can always set the voltage angles of the vertex cut set θm to be equal if we can arbitrarily regulate the
power injections of the buses in the vertex cut set.
Next we are going to prove that the line flows in the i-th sub-graph must be all zero if we set the voltage angles θm of
the vertex cut set to be equal and if the net power injections at the interior buses of the i-th sub-graph are all zero. If under
such scenario there still exist some non-zero line flows in the i-th sub-graph, then we know that the voltage angles of the
interior buses of the i-th sub-graph can not be equal, meaning at least one of the interior buses is of non-zero net power
injection. This contradicts our assumption.
Corollary 1: Suppose we use a vertex cut set to decompose a connected transmission network into n (n ≥ 2) connected
sub-graphs. We first classify the columns of the injection shift factor matrix into 3 sets with the first set being associated
with the buses owned exclusively by the i-th sub-graph, and the second set being associated with the buses in the vertex
cut set, and the third set being associated with the buses owned exclusively by other sub-graphs. Assume their cardinalities
are l, m, and n, respectively. We then classify the rows of the injection shift factor matrix into 2 sets with the first set
being associated with the lines owned exclusively by the i-th sub-graph, and the second set being associated with the lines
owned exclusively by other sub-graphs, and assume their cardinalities are x, and y, respectively. A visualization of the
decomposition is shown below.
in

at

out

↓

↓

Ax×l
Dy×l

Bx×m
Ey×m

↓



Ψ=

Cx×n ← in
Fy×n ←out

(5)

Then the ranks of the sub-matrix

Bx×m

Cx×n


Dy×l

Ey×m



and


must both be ≤ m.
Proof: By Proposition 2, we know that the effect of one unit net power injection at a bus in the j-th sub-graph on
lines in the i-th sub-graph is a linear combination of the effects of one unit net power injections at the buses in the vertex
cut set on lines in the i-th sub-graph. Thus we know each column of the sub-matrix [Cx×n ] is a linear combination of the
columns of the sub-matrix [Bx×m ], meaning the rank the sub-matrix [Bx×m Cx×n ] is ≤ m. Similarly, we can prove that
each column of the sub-matrix [Dy×l ] is a linear combination of the columns of the sub-matrix [Ey×m ], meaning the rank
the sub-matrix [Dy×l Ey×m ] is ≤ m .
Corollary 2: Suppose we use a vertex cut set to decompose a connected transmission network into n (n ≥ 2) sub-graphs
and all congested lines are contained in the i-th sub-graph (which may be unconnected), then one pair of buses with maximum
LMP difference in the j-th sub-graph (i 6= j) must be in the vertex cut set.
Proof: Here, we just need to show that the LMP at any bus in the j-th sub-graph is a convex combination of the LMPs
at the buses in the vertex cut set.
Suppose there are m buses in the vertex cut set and their LMPs are {λ1 , ..., λm }, and we randomly pick a bus, say bus j1
with LMP being λj1 , from the j-th sub-graph. By Proposition 2, we know that the effect of one unit net power injection at a
bus j1 on lines in the i-th sub-graph is a linear combination of the effect of one unit net power injections at the m buses in
the vertex cut set on lines in the i-th sub-graph, and we assume the coefficients of the linear combination are {a1 , ..., am },
where the power balance equation ensures that a1 + a2 + ... + am = 1. Thus we have
~ i,j1 = [Ψ
~ i,v , ..., Ψ
~ i,v ][a1 , ..., am ]T ,
Ψ
1
m

7

~ i,j1 denotes the shift factor vector for read power at bus j1 on lines in the i-th sub-graph, Ψ
~ i,v (k = 1, ..., m)
where Ψ
k
denotes the shift factor vector for read power at the k-th vertex cut set bus on lines in the i-th sub-graph.
Since we assume all congestions are in the i-th sub-graph, we know the shadow prices for line constraints that are not in
the i-th sub-graph are all zero. Denoting the shadow price vector for all line constraints in the i-th sub-graph by [µi ], we
have
~ i,j1
λj1 = λref − [µi ]T Ψ
~ i,v , ..., Ψ
~ i,v ][a1 , ..., am ]T
= λref − [µi ]T [Ψ
1
m

(6)

= a1 λ1 + a2 λ2 + ... + am λm
Next we will show that ai ≥ 0 (i = 1, ..., m), i.e. to cancel the effect of one unit net power injection at bus j1 on lines
in the i-th sub-graph requires a non-negative net power withdrawn at each bus in the vertex cut set. Suppose we only inject
and withdraw power at bus j1 (which has one unit net power injection) and the buses in the vertex cut set, and their effects
on the i-th sub-graph precisely offset each other. Then the bus with the lowest voltage angle must be one of the buses with
positive net power withdrawn (or negative net power injection) and its voltage angle must be strictly lower than any bus
with positive net power injection. Apparently, the bus with lowest voltage angle must be in the vertex cut set. If one of the
buses in the vertex cut set has positive net power injection, meaning its voltage angle is different from the lowest nodal
voltage angle, then there exists a nodal voltage angle difference in the vertex cut set. In such case, the absorbed power in
the i-th sub-graph
T
T T
Pi = [θiT θm
]Bi [θiT θm
]
must be positive where θi is the voltage angle vector of all interior buses in the i-th sub-graph, θm is the voltage angle
vector of all bus in the vertex cut set and Bi is the reduced susceptance matrix of the i-th sub-graph. This means some line
power flows in the i-th sub-graph must be non-zero, indicating a contradiction to the assumption that the effects of power
injections/withdrawals at bus j1 and at the buses in the vertex cut set on the i-th sub-graph precisely offset each other.
Remark 3: Corollary 2 points out an useful property of vertex cut set in the trading of power or financial transmission
rights (FTRs). Essentially, the main task in power trading is to find those pairs of buses between which the LMP differences
are significant. If a vertex cut set can decompose the grid such that all congestions are isolated to one or several sub-grids,
then the range of the LMPs of buses in the vertex cut that form the boundary of the congested sub-grid(s) will dominate the
LMP range of all buses in the non-congested sub-grids. Loosely speaking, the closer the vertex cut gets to the congestions,
the higher trading values of the buses in the vertex cut set. Or in other words, if the congested sub-grid(s) defined by one
given vertex cut set is a subset of the congested sub-grid(s) defined by another vertex cut set, then the buses in the given
vertex cut must be of higher or at least equal trading value than that in the other one, suggesting an arbitrage opportunity
if violates.
VI. G RID D ECOMPOSITION H EURISTIC
This section presents a general algorithm structure for grid decomposition heuristics. The objective of the algorithm is
eliminating the portion(s) of the grid with relatively small range of LMPs from the consideration of topology control with
little computational effort. The algorithm is specified in Fig. 4. This simple algorithm structure first solves an OPF and,
given the OPF results, if the OPF is feasible, finds an appropriate vertex cut set to decompose the grid into two parts: one
with relatively high range of LMPs and the other with relatively low range of LMPs.
The initial vertex cut set that includes the ending buses of all congested lines forms the boundary of the smallest sub-grid
containing all congestions. The algorithm then calculates the LMP absolute deviation for each bus in the initial vertex cut
set and locates the bus, say bus i, with the largest LMP absolute deviation. It then “pushes out” the initial vertex cut from
bus i by swapping out bus i (and therefore bus i becomes an interior bus of the congested sub-grid) and bringing bus i’s
neighboring buses into the vertex cut set.
A pre-set LMP range threshold is the characterizing element for the stopping criteria which determines the number of
iterations applied, and can include a number of conditions. The algorithm terminates if the range of the LMP of the vertex
cut set falls below the pre-set threshold or if all buses have been brought into the congested sub-grid. Additionally, the
algorithm may have a pre-set maximum number of iterations.
VII. S IMULATION R ESULTS
To test the validity of the grid decomposition based on vertex cut set, a new topology control heuristic was proposed and
tested on the IEEE 118-bus test systems. The so called Local Greedy Heuristic is the same as the Standard Greedy Heuristic
in [12] except that the switchable lines are limited to the neighboring area of the congested line, i.e the congested sub-grid
obtained by the grid decomposition algorithm shown in Fig. 4.

8

Step 0
Solve the initial OPF and locate all line
congestions.

Step 1
Initialize the vertex cut set as the set of all
terminal buses of the congested lines.

Step 2
Select the bus of maximum LMP
difference from the mean LMP of the
vertex cut set and (1) remove it from the
vertex cut set, (2) bring its neighboring
buses that were not included in the subgraphs containing congestions into the
vertex cut set.

Step 3
Stopping criteria?
No
Yes
Step 4
Store solution.

Fig. 4.

Flow chart describing general algorithm structure of grid decomposition based on vertex cut set.

A. Test Network Overview
The heuristics were tested on the IEEE 118-bus test system. This test system represents a portion of the Midwestern US
Power System as of December, 1962. The data of the test system employed is downloaded from the website of UW1 . The
generator cost information used in the IEEE 118 network is extracted from [17]. The test system consists of 118 buses, 54
generators, and 194 lines, all of which are assumed to be connected in the initial topology.
B. Standard Greedy Heuristic Overview
The algorithm is specified in Fig. 5. The Standard Greedy Heuristic redoes the DCOPFs for each allowable line outage
and then select the single line outage that leads to maximum savings in each iteration. Please refer [12] for more details.
Clearly, optimality is not guaranteed, since the transmission topology is not co-optimized with power dispatch.
C. Simulation Results and Analysis
To generate the test scenarios for the heuristics, a fixed load is maintained and we perform a Monte Carlo simulation
where the generator costs are randomly varied. The sample size used for the Monte Carlo simulation is 50. For the Local
Greedy Heuristic based on vertex cut set, the LMP range threshold is set to be 10% of the maximum LMP difference across
the grid.
The percent savings rather than the dollar value are the focus of the paper. Two benchmark cases are used to evaluate
the savings of the heuristic: 1) the one with initial topology and line constraints whose DCOPF sets an upper bound of the
total generation costs, and 2) the unconstrained case whose DCOPF provides a lower bound of the generation costs. The
cost difference between the two benchmark cases is called the maximum attainable savings (MAS).
The two heuristics are implemented in Matlab, using MATPOWER [18] as the DCOPF solver. The performance comparison
between the two heuristic is detailed in Table 2.
Heuristic Saving/MAS Lines removed Mean effort
Local
0.653 ± 0.055 12.910 ± 4.312
0.216
Standard 0.672 ± 0.051 10.18 ± 3.98
1
Table 2: Performance comparison.
In the worst case, the two heuristics are of the same level computational complexity if the grid decomposition algorithm
brings all buses into the congested sub-grid. In general, the Standard Greedy Heuristic costs much more computational effort
especially for a large scale networks. Though the computational costs of the two heuristics differ by almost five times, their
attainable savings are quite close, showing the promise in applying grid decomposition to topology control.
1 https://www2.ee.washington.edu/research/pstca/pf118/pg

tca118bus.htm

9

Step 0
Solve the initial OPF and store solutions.
Initialize the switchable line set.

Step 1
Calculate the savings for each switchable
line by redoing the DCOPF for each
switchable line.

Step 2
Select the line of maximum savings from
the switchable set and change its status.

Reconnect the disconnected
line and remove it from the
switchable set.

No

Step 3
Solve the updated DCOPF (with one new
line removed) problem.

Store solution and remove
the disconnected line from
the switchable set.

Step 4
Improved
Solution?
Yes

Step 5
Stopping criteria?

No

Yes
Step 6
Store solution.

Fig. 5.

Flow chart describing general algorithm structure of the Standard Greedy Heuristic.

VIII. C ONCLUSION
In spite of the seemingly promising simulation results of the heuristic approaches pursued by the research community and a
certain level of proven predictability [19], [15], [20] of topology control, satisfactory grid-scale solutions are not guaranteed.
While optimality for this NP-hard problem is no obtained, our approach based on a general spatial grid decomposition
nevertheless offers some hope that it is possible to design algorithms that isolate congestion effects to a relatively small part
of the network. By only focusing attention to the neighboring area of the congestions, the search space of possible switching
operations and the computational cost is significantly reduced, and the locally optimal switchings at each iteration are still
retained to a large degree.
R EFERENCES
[1] Vajjhala, S.P. and Fischbeck, P.S., 2007. Quantifying siting difficulty: A case study of US transmission line siting. Energy Policy, 35(1), pp.650-671.
[2] Glavitsch, H., 1993, September. Power system security enhanced by post-contingency switching and rescheduling. In Athens Power Tech, 1993. APT
93. Proceedings. Joint International Power Conference (Vol. 1, pp. 16-21). IEEE.
[3] Mazi, A.A., Wollenberg, B.F. and Hesse, M.H., 1986. Corrective control of power system flows by line and bus-bar switching. IEEE Transactions on
Power Systems, 1(3), pp.258-264.
[4] Granelli, G., Montagna, M., Zanellini, F., Bresesti, P., Vailati, R. and Innorta, M., 2006. Optimal network reconfiguration for congestion management
by deterministic and genetic algorithms. Electric power systems research, 76(6-7), pp.549-556.
[5] Bakirtzis, A.G. and Meliopoulos, A.S., 1987. Incorporation of switching operations in power system corrective control computations. IEEE Transactions
on Power Systems, 2(3), pp.669-675.
[6] Rolim, J.G. and Machado, L.J.B., 1999. A study of the use of corrective switching in transmission systems. IEEE Transactions on Power Systems,
14(1), pp.336-341.
[7] Fisher, E. B., ONeill, R. P., and Ferris, M. C. (2008). Optimal transmission switching. IEEE Transactions on Power Systems, 23(3):13461355
[8] Ruiz, P. A., Foster, J. M., Rudkevich, A., and Caramanis, M. C. (2011). On fast transmission topology control heuristics. In 2011 IEEE Power and
Energy Society General Meeting, pp. 18. IEEE.
[9] Fuller, J. D., Ramasra, R., and Cha, A. (2012). Fast heuristics for transmission-line switching. IEEE Transactions on Power Systems, 27(3):1377-1386
[10] Hedman, K.W., ONeill, R.P., Fisher, E.B. and Oren, S.S., 2009. Optimal transmission switching with contingency analysis. IEEE Transactions on
Power Systems, 24(3), pp.1577-1586.
[11] Hedman, K.W., Oren, S.S. and O’Neill, R.P., 2011, July. A review of transmission switching and network topology optimization. In Power and Energy
Society General Meeting, 2011 IEEE (pp. 1-7). IEEE.
[12] Wang, S. and Baillieul, J., 2018. Paradigm and Paradox in Topology Control of Power Grids. arXiv preprint, arXiv:1803.05852.
[13] Kammerer, R., Frmel, B., Obermaisser, R. and Milbredt, P., 2013, July. Composability and compositionality in can-based automotive systems based
on bus and star topologies. In Industrial Informatics (INDIN), 2013 11th IEEE International Conference on (pp. 116-122). IEEE.
[14] Chartrand, G. (1985) Cut-vertices and bridges. introductory graph theory. New York: Dover, pp. 4549.
[15] Wang, S., and Baillieul, J. (2016). Kirchhoff-Braess phenomena in DC electric networks. In Decision and Control (CDC), 2016 IEEE 55th Conference
on, pp. 3286-3293. IEEE.
[16] Dorfler, F. and Bullo, F., 2013. Kron reduction of graphs with applications to electrical networks. IEEE Transactions on Circuits and Systems I:
Regular Papers, 60(1), pp.150-163.

10

[17] Blumsack, S. A., 2006, Network topologies and transmission investment under electric-industry restructuring, Ph.D. dissertation, Eng. Public Pol.,
Carnegie Mellon Univ., Pittsburgh, PA.
[18] Zimmerman, R.D., Murillo-Snchez, C.E. and Thomas, R.J., 2011. MATPOWER: Steady-state operations, planning, and analysis tools for power
systems research and education. IEEE Transactions on power systems, 26(1), pp.12-19.
[19] Baillieul, J., Zhang, B., and Wang, S. (2015). The Kirchhoff-Braess paradox and its implications for smart microgrids. In Decision and Control
(CDC), 2015 IEEE 54th Annual Conference on, pp. 6556-6563. IEEE.
[20] Wang, S. and Baillieul, J., 2017. A Novel Decomposition for Control of DC Circuits and Grid Models with Heterogeneous Energy Sources. arXiv
preprint arXiv:1709.07569, accepted to the American Control Conference (ACC), 2018.

