of 8
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
2565
Branch Flow Model: Relaxations and
Convexi
fi
cation—Part II
Masoud Farivar and Steven H. Low
Abstract—
We propose a branch
fl
ow model for the analysi
sand
optimization of mesh as well as radial networks. The model leads
to a new approach to solving optimal power
fl
ow (OPF) that con-
sists of two relaxation steps. The
fi
rst step elimin
ates the voltage
and current angles and the second step approximates the resulting
problem by a conic program that can be solved ef
fi
ciently. For ra-
dial networks, we prove that both relaxati
on steps are always exact,
provided there are no upper boun
ds on loads. For mesh networks,
the conic relaxation is always exact but the angle relaxation may
not be exact, and we provide a simple way t
o determine if a re-
laxed solution is globally optimal. We propose convexi
fi
cation of
mesh networks using phase shi
fters so that OPF for the convexi
fi
ed
network can always be solved ef
fi
ci
ently for an optimal solution.
We prove that convexi
fi
cation requires phase shifters only outside
a spanning tree of the network and their placement depends only
on network topology, not on powe
r
fl
ows, generation, loads, or op-
erating constraints. Par
t I introduces our branch
fl
ow model, ex-
plains the two relaxation steps, and proves the conditions for exact
relaxation. Part II describe
s convexi
fi
cation of mesh networks, and
presents simulation results.
Index Terms—
Convex relaxation, load
fl
ow control, optimal
power
fl
ow, phase control, power system management.
I. I
NTRODUCTION
I
N Part I of this two-part paper [2], we introduce a branch
fl
ow model that focuses on branch variables instead of nodal
variables. We formul
ate optimal power
fl
ow (OPF) within the
branch
fl
ow model and propose two relaxation steps. The
fi
rst
step eliminates phase angles of
voltages and currents. We call
the resulting problem OPF-ar which is still nonconvex. The
second step relaxes the feasible set of OPF-ar to a second-order
cone. We call the resulting problem OPF-cr which is convex, in-
deed a second-order cone program (SOCP) when the objective
function is linear. We prove that the conic relaxation OPF-cr
is always exact
even
for mesh networks, provided there are no
upper bounds on real and reactive l
oads, i.e., any optimal solu-
tion of OPF-cr is also optimal for OPF-ar. Given an optimal so-
lution of OPF-ar, whether we can derive an optimal solution to
Manuscript received May 11, 2012; re
vised July 22, 2012, November 18,
2012, January 04, 2013, and March 01, 2013; accepted March 03, 2013. Date
of publication April 23, 2013; date of current version July 18, 2013. The work
was supported by NSF through NetSE grant CNS 0911041, Resnick Institute
of Caltech through grant DE-AR0000226, the DoE’s ARPA-E through grant
DE-AR0000226, the National Science Council of Taiwan (R. O. C.) through
grant NSC 101-3113-P-008-001, Southern California Edison, the Resnick Insti-
tute of Caltech, Cisco, and the Okawa Foundation. A preliminary and abridged
version has appeared in [1]. Paper no. TPWRS-00425-2012.
The authors are with the Engineering and Applied Science, California Insti-
tute of Technology, Pasadena, CA 91125 USA.
Color versions of one or more of the
fi
gures in this paper are available online
at http://ieeexplore.ieee.org.
Dig
ital Object Identi
fi
er 10.1109/TPWRS.2013.2255318
the original OPF depends on whether we can recover the v
oltage
and current angles correctly from the given OPF-ar so
lution. We
characterize the exact co
ndition (the angle recove
ry condition)
under which this is possible, and present two angle
recovery al-
gorithms. It turns out that the angle recove
ry condition has a
simple interpretation: any solution of OP
F-ar implies a phase
angle difference across a line, and the ang
le recovery
condition
says that the implied phase angle differe
nces sum to zero (mod
) around each cycle. For a radial netwo
rk, this condition holds
trivially and hence solving the conic r
elaxation OPF-cr always
produces an optimal solution for t
he original OPF. For a mesh
network, the angle recovery cond
ition may not hold, and our
characterization can be used to
check if a relaxed solution yields
an optimal solution for OPF.
In this paper, we prove that, by p
lacing phase shifters on some
of the branches,
any
relaxed so
lution of OPF-ar can be mapped
to an optimal solution of OPF fo
r the convexi
fi
ed network, with
an optimal cost that is no hi
gher than that of the original net-
work. Phase shifters thus
convert an NP-hard problem into a
simpler problem. Our res
ult implies that when the angle re-
covery condition holds
for a relaxed branch
fl
ow solution, not
only is the solution opt
imal for the OPF without phase shifters,
but the addition of pha
se shifters cannot further reduce the cost.
On the other hand, wh
en the angle recovery condition is vio-
lated, then the con
vexi
fi
ed network may have a strictly lower
optimal cost. Mor
eover, this bene
fi
t can be attained by placing
phase shifters on
ly outside an
arbitrary
spanning tree of the net-
work graph.
There are in gener
al many ways to choose phase shifter angles
to convexity a ne
twork, depending on the number and location
of the phase sh
ifters. While placing ph
ase shifters on each link
outside a span
ning tree requires the minimum number of phase
shifters to g
uarantee exact relaxation, this strategy might require
relatively l
arge angles at some of these phase shifters. On the
other extre
me, one can choose to minimize (the Euclidean norm
of) the pha
se shifter angles by deploying phase shifters on every
link in th
enetwork.Weprovethatth
is minimization problem is
NP-hard.
Simulations suggest, however, that a simple heuristic
works qu
ite well in practice.
These res
ults lead to an algorithm for solving OPF when there
are phas
e shifters in mesh networks, as summarized in Fig. 1.
Since pow
er networks in practice are very sparse, the number
of lines
not in a spanning tree can be relatively small compared
to the n
umber of buses squared, as demonstrated in simulations
in Sect
ion V using the IEEE test systems with 14, 30, 57, 118,
and 30
0 buses, as well as a 39-bus model of a New England
powe
r system and two models of a Polish power system with
more
than 2000 buses. Moreover, the placement of these phase
shi
fters depends only on network topology, but not on power
0885-8950/$31.00 © 2013 IEEE
2566
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
Fig. 1. Proposed algorithm for solving OPF with phase shifters in mesh net-
works. The details are explained in this two-part paper.
fl
ows, generations, loads, or operating constraints. Therefore
only one-time deployment cost is required to achieve subse-
quent simplicity in network operation. Even when phase shifters
are not installed in the network, the optimal solution of a convex
relaxation is useful in providing a lower bound on the true op-
timal objective value. This lower bound serves as a benchmark
for other heuristic solutions of OPF.
The paper is organized as follows. In Section II, we extend the
branch
fl
ow model of [2] to include phase shifters. In Section III,
we describe methods to compute phase shifter angles to map any
relaxedsolutiontoanbranch
fl
ow solution. In Section IV, we
explain how to use phase shifters to simplify OPF. In Section V,
we present our simulation results.
II. B
RANCH
F
LOW
M
ODEL
W
ITH
P
HASE
S
HIFTERS
We adopt the same notations and assumptions A1–A4 of [2].
A. Review: Model Without Phase Shifters
For ease of reference, we reproduce the
branch
fl
ow model
of
[2] here:
(1)
(2)
(3)
Recall the set
of branch
fl
ow solutions given
de
fi
ned in
[2]:
(4)
and the set
of all branch
fl
ow solutions:
(5)
To simplify notation, we often use
to denote the set de
fi
ned
either in (4) or in (5), depending on the context. In this section
we study power
fl
ow solutions and hence we
fi
xan
. All quan-
tities, such as
, are with respect to the given
,
even though that is not explicit
in the notation. In the next sec-
tion,
is also an optimization variable and the sets
are for any
.
Given a relaxed solution
,de
fi
ne
by
(6)
It is proved in [2, Theorem 2] that a given
can be mapped to a
branch
fl
ow solution in
if and only if there exists a
that
solves
(7)
for some integer vector
. Moreover if (7) has a solution,
then it has a countably in
fi
nite set of solutions
,butthey
are relatively unique, i.e., given
, the solution
is unique, and
given
, the solution
is unique. Hence (7) has a unique solution
with
if and only if
(8)
which is equivalent to the require
ment that the (implied) voltage
angle differences sum to zero around any cycle
:
where
if
and
if
.
B. Model With Phase Shifters
Phase shifters can be traditiona
l transformers or Flexible AC
Transmission Systems (FACTS) devices. They can increase
transmission capacity and impro
ve stability and power quality
[3], [4]. In this paper, we cons
ider an idealized phase shifter
that only shifts the phase angles of the sending-end voltage and
current across a line, and has n
o impedance nor limits on the
shifted angles. Speci
fi
cally, consider an idealized phase shifter
parametrized by
across line
),asshowninFig.2.As
before, let
denote the sending-end voltage. De
fi
ne
to be
the
sending-end
current leaving node
towards node
.Let
be the point between the phase shifter
and line impedance
.Let
and
be the voltage at
and current from
to
,
respectively. Then the effect of
the idealized phase shifter is
summarized by the following modeling assumption:
The power transferred from nodes
to
is still (de
fi
nedtobe)
which, as expected, is equal to the power
from nodes
to
since the phase shifter is assumed to be loss-
less. Applying Ohm’s law across
,wede
fi
ne the
branch
fl
ow
model with phase shifters
as the following set of equations:
(9)
(10)
(11)
FARIVAR AND LOW: BRANCH FLOW MODEL: RELAXATIONS AND CONVEXIFICATION (PART II)
2567
Fig. 2. Model of a phase shifter in line
.
Without phase shifters
, (9)–(11) reduce to the branch
fl
ow model (1)–(3).
The inclusion of phase shifters modi
fi
es the network and en-
largers the solution set of the (new) branch
fl
ow equations. For-
mally, let
(12)
Unless otherwise speci
fi
ed, all angles should be interpreted as
being modulo
and in
. Hence we are primarily in-
terested in
. For any spanning tree
of
,let
”standfor“
for all
”, i.e.,
involves
only phase shifters in branches not in the spanning tree
.De-
fi
ne
(13)
Since (9)–(11) reduce to the branch
fl
ow model when
,
.
III. P
HASE
A
NGLE
S
ETTING
Givenarelaxedsolution
, there are in general many ways
to choose angles
on the phase shifters to recover a feasible
branch
fl
ow solution
from
. They depend on the number
and location of the phase shifters.
A. Computing
For a network with phase shifters, we have from (9) and (10)
leading to
. Hence
for some integer
. This changes the angle recovery
condition in [2, Theorem 2] from whether there exists
that
solves (7) to whether there exists
that solves
(14)
for some integer vector
. The case without
phase shifters corresponds to setting
.
We now describe two ways to compute
:the
fi
rst minimizes
the required number of phase shifters, and the second minimizes
the size of phase angles.
1) Minimize Number of Phase Shifters:
Our
fi
rst key result
implies that, given a relaxed solution
,we
can always recover a branch
fl
ow solution
of the convexi
fi
ed network. Moreover it suf
fi
ces to use phase
shifters in branches only outs
ide a spanning tree. This method
requires the smallest number
of phase shifters.
Given any
-dimensional vector
,let
denote its pro-
jection onto
by taking modulo
componentwise.
Theorem 1:
Let
be
any
spanning tree of
. Consider a
relaxed solution
and the corresponding
de
fi
nedby(6)
in terms of
.
1) There exists a unique
with
such that
, i.e.,
is a branch
fl
ow
solution of the convexi
fi
ed network. Speci
fi
cally
2)
and hence
.
Proof:
For the
fi
rst assertion, write
and set
. Then (14) becomes
(15)
We now argue that there always exists a unique
,with
,
and
, that solves (15)
for some
.
The same argument as in the proof of [2, Theorem 2] shows
that a vector
with
and
is a
solution of (15) if and only if
where
is an integer vector.
Clearly this can always be satis
fi
ed by choosing
(16)
Note that given
,
is uniquely determined since
,but
can be freely chosen to satisfy (16). Hence
we can choose the unique
such that
.
Hencewehaveshownthattherealwaysexistsaunique
,with
,
and
,
that solves (15) for some
. Moreover this unique
vector
is given by the formulae in the theorem.
The second assertion follows from assertion 1.
2) Minimize Phase Angles:
The choice of
in The-
orem 1 has the advantage that it requires the minimum number
of phase shifters (only on links outside an arbitrary spanning
tree
). It might however require relatively large angles
at some links
outside
. On the other extreme, suppose we
have phase shifters on every link. Then one can choose
such that the phase shifter angles are minimized.
Speci
fi
cally we are interested in a solution
of (14)
that minimizes
where
denotes the Euclidean norm
of
after taking mod
componentwise. Hence we are inter-
ested in solving the following problem: given
(17)
(18)
where
are integer vectors.
Theorem 2:
The problem (17), (18) of minimum phase angles
is NP-hard.
2568
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
Fig. 3. Each lattice point corresponds to
for a
. The constrained
optimization (19) is to
fi
nd a lattice point that is closest to the range space
of
. The shaded region around the origin is
and
contains a point
for exactly one
. Our approximate
solution corresponds to solving (20) for this
fi
xed
.
Proof:
Clearly the problem (17), (18) is equivalent to the
following unconstrained minimization [eliminate
from (17),
(18)]:
(19)
It thus solves for a lattice point
that is closest to the
range space
of
, as illustrated in Fig. 3.
Fix any
. Consider
and the inner
minimizationin(19):
(20)
This is the standard linear least-squares estimation where
rep-
resents an observed vector that
istobeestimatedbyanvector
in the range space of
in order to minimize the normed error
squared. The optimal solution is
(21)
(22)
Substituting (22) and (20) into (19), (19) becomes
(23)
where
and
is the
orthogonal complement of the range space of
. But (23) is the
closest lattice vector problem
and is known to be NP-hard [5].
1
Remark 1:
Since the objective function is strictly convex,
the phase angles
at optimality will
lie in
. Moreover, if an optimal solution exists, then
there is always an optimal solution with
in
:if
is optimal for (19) with
,thenbywriting
for integer vectors
,
, the objective
function in (19) becomes
1
We thank Babak Hassibi for pointing out (23) is the closest lattice vector
problem studied in the literature.
i.e., we can always choose
so that
lies
in
and
. Therefore, given an optimal
solution
with
, we can
fi
nd another point
with
that is also optimal.
Many algorithms have been proposed to solve the closest
lattice vector problem. See [6] for state-of-the-art algorithms.
Given
, there is a unique
such that
is in
, as illustrated in the shaded area of Fig. 3. A simple
heuristic that provides an upper bound on (19) is to solve (20)
for this
fi
xed
. From (21)–(22), the heuristic solution is
This approximate solution is ill
ustrated in Section V and seems
to be effective in reducing the phase shifter angles (
in all
our test cases).
B. Arbitrary Network of Phase Shifters
More generally, consider a network with phase shifters on an
arbitrary subset of links. Given a relaxed solution
, under what
condition does there exists a
such that the inverse projection
is a branch
fl
ow solution in
? If there is a spanning
tree
such that all links outside
have phase shifters, then
Theorem 1 says that such a
always exists, with an appropriate
choice of phase shifter angles on non-tree links. Suppose no
such spanning tree exists, i.e., given any spanning tree
,there
is a set
of links that contain no phase shifters.
Let
and
denote the submatrix of
and subvector of
,
respective, corresponding to these links. Then a necessary and
suf
fi
cient condition for angle recove
ry is: there exists a spanning
tree
such that the associated
and
satisfy
(24)
This condition reduces to (8) if there are no phase shifters in
the network
and is always satis
fi
ed if every
link outside any spanning tree has a phase shifter
.
It requires that the angle differences implied by
sum to zero
(mod
) around any loop that contains no phase shifter (c.f. [2,
Theorem 2(1) and Remark 4]). After such a
is identi
fi
ed, the
above two methods can be used to compute the required phase
shifts.
C. Other Properties
We close this section by discussing two properties of
.First,
the voltage angles are
and the angle
recovery condition (8) becomes
(25)
which can always be satis
fi
ed by appropriate (nonunique)
choices of
. A similar argument to the proof of Theorem
2(2) leads to the following interpretation of (25). For any link
, (14) says that the phase angle difference from node
to node
is
and consists of the voltage angle difference
and the phase shifter angle
.Fix
FARIVAR AND LOW: BRANCH FLOW MODEL: RELAXATIONS AND CONVEXIFICATION (PART II)
2569
any link
not in tree
. The left-hand side
of (25) represents the sum of the voltage
angle differences from node
to node
along the unique path
in
,
not
including the phase shifter angles along the path.
This must be equal to the voltage angle difference
across (the non-tree) link
,
not
including the phase shifter
angle across
. Therefore (25) has the same interpretation
as before that the voltage angl
e differences sum to zero (mod
) around any cycle, though, with phase shifters, the voltage
angle differences are now
instead of
.Thisin
particular leads to a relationship between any two solutions
and
of (14).
In particular, let
bethesolutioninTheorem1where
,and
any other solution. Then applying (25) to
both
and
leads to a relation between them on every basis
cycle. Speci
fi
cally, let
be a link not in the spanning tree
,let
be the unique path in
from node 0 to any
node
. Then for each link
in
that is not in
,wehave
(equalities to be interpreted as mod
)
Second, Theorem 1 implies tha
t given any relaxed solution
,
there exists a
such that its inverse projection
is a branch
fl
ow solution, i.e.,
satis
fi
es (9)–(11). We now
give an alternative direct construction of such a solution
from any given branch
fl
ow solution
and phase shifter setting
that may have nonzero angles on some links in
.Itexhibits
how the effect of phase shifters i
n a tree is equivalent to changes
in voltage angles.
Fix any spanning tree
. Given any
, partition
with respect to
.De
fi
ne
by
or
.Thende
fi
ne the mapping
by
(26)
and
if
if
(27)
i.e.,
is nonzero only on non-tree links. It can be veri
fi
ed that
where
is the unique path in
tree
from node
to node
. Note that
,
and
. Hence if
is a relaxed branch
fl
ow solution, so
is
. Moreover, the effect of phase shifters in
is equivalent
to adding
to the phases of
and
.
Theorem 3:
Fix any tree
.If
is a solution of (9)–(11),
so is
de
fi
ned in (26) and (27).
Proof
2
:
Since
,
and
,
satis
fi
es (10) and (11). For any link
in tree
,(26)
2
A less direct proof is to observe that (25) and
imply
which means
satis
fi
es (14).
and (27) imply
where the second equality follows from
.Forany
link
not in
, (26) and (27) imply
But
since
satis
fi
es (9). Therefore
, i.e.,
satis
fi
es (9) on every link.
IV. OPF
IN
C
ONVEXIFIED
N
ETWORK
Theorem 1 suggests using phase shifters to convexify a mesh
network so that
any
solution of OPF-ar can be mapped into an
optimal solution of OPF of the convexi
fi
ed network. Convexi
fi
-
cation thus modi
fi
es an NP-hard problem into a simple problem
without loss in optimality; moreover this requires an one-time
deployment cost for subsequent operational simplicity, as we
now show.
We will compare four OPF problems: the original OPF de-
fi
ned in [2]:
OPF
:
the relaxed OPF-ar de
fi
nedin[2]:
OPF-ar
:
the following problem where there is a phase shifter on every
line
):
OPF-ps
:
and the problem where, given any spanning tree
,thereare
phase shifters only outside
:
OPF-ps(T)
:
Let the optimal values of OPF, OPF-ar, OPF-ps, and OPF-ps(T)
be
,
,
,and
, respectively.
Theorem 1 implies that
for any spanning
tree
. Hence we have
2570
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
TABLE I
L
OSS
M
INIMIZATION
.M
IN
L
OSS
W
ITHOUT
P
HASE
S
HIFTERS
(PS)
WAS
C
OMPUTED
U
SING
SDP R
ELAXATION OF
OPF;
MIN
L
OSS
W
ITH
P
HASE
S
HIFTERS WAS
C
OMPUTED
U
SING
SOCP R
ELAXATIONS
OPF-
CR OF
OPF-
AR
.T
HE
“(%)” I
NDICATES THE
N
UMBER OF
PS
AS A
P
ERCENTAGE OF
#L
INKS
TABLE II
L
OADABILITY
M
AXIMIZATION
.M
AX
L
OADABILITY
W
ITHOUT
P
HASE
S
HIFTERS
(PS)
WAS
C
OMPUTED
U
SING
SDP R
ELAXATION OF
OPF;
MAX
L
OADABILITY
W
ITH
P
HASE
S
HIFTERS WAS
C
OMPUTED
U
SING
SOCP R
ELAXATIONS
OPF-
CR OF
OPF-
AR
.T
HE
“(%)” I
NDICATES THE
N
UMBER OF
PS
AS A
P
ERCENTAGE OF
#L
INKS
Corollary 4:
For any spanning tree
,
, with equality if there is a solution
of OPF-ar that
satis
fi
es (8).
Corollary 4 has several important implications:
1) Theorem 1 in [2] implies that we can solve OPF-ar ef
fi
-
ciently through conic relaxat
ion to obtain a relaxed solu-
tion
. An optimal solution of OPF may or may not
be recoverable from it. If
satis
fi
es the angle recovery
condition (8) with respect to
, then Theorem 2 in [2]
guarantees a unique
such that the inverse
projection
is indeed optimal for OPF.
2) In this case, Corollary 4 implies that adding any phase
shifters to the network cannot further reduce the cost since
.
3) If (8) is not satis
fi
ed, then
and there is no
inverse projection that can r
ecover an optimal solution of
OPF from
. In this case,
.Theorem
1 implies that if we allow phase shifters, we can always
attain
with the relaxed solution
,with
potentially strict improvement over the network without
phase shifters (when
).
4) Moreover, Corollary 4 implies that such bene
fi
t can be
achieved with phase shifters only in branches outside an
arbitrary spanning tree
.
Remark 2:
Thechoiceofthespanningtree
does not af-
fect the conclusion of the theorem. Different choices of
cor-
respond to different choices of
linearly independent rows of
and the resulting decomposition of
and
into
and
.
Therefore
determines the phase angles
and
according to
the formulae in the theorem. Since the objective
of
OPF is independent of the phase angles
, for the same relaxed
solution
, OPF-ps achieves the same objective value regardless
of the choice of
.
V. S
IMULATIONS
For radial networks, results in Part I (Theorem 4) guaran-
tees that both the angle relaxat
ion and the conic relaxation are
exact. For mesh networks, the angle relaxation may be inexact
and phase shifters may be needed to implement a solution of
the conic relaxation. We now explore through numerical exper-
iments the following questions:
• How many phase shifters are typically needed to convexify
a mesh network?
• What are typical phase shifter angles to implement an op-
timal solution for the convexi
fi
ed network?
Test Cases:
We explore these questions using the IEEE
benchmark systems with 14, 30, 57, 118, and 300 buses, as well
as a 39-bus model of a New England power system and two
models of a Polish power system with 2383 and 2737 buses.
The data for all the test cases were extracted from the library of
built in models of the MATPOWER toolbox [7] in Matlab. The
test cases involve constraints on bus voltages as well as limits
on the real and reactive power generation at every generator
bus. The New England and the Polish power systems also
involve MVA limits on branch power
fl
ows. All these systems
are mesh networks, but very sparse.
Objectives:
We solve the test cases for two scenarios:
Loss minimization
. In this scenario, the objective is to min-
imize the total active power loss of the circuit given con-
stant load values, which is equivalent to minimizing the