of 11
2554
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
Branch Flow Model: Relaxations
and Convexi
fi
cation—Part I
Masoud Farivar and Steven H. Low
, Fellow, IEEE
Abstract—
We propose a branch
fl
ow model for the analysis and
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 eliminates t
he 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 relaxation st
eps 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 to det
ermine 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
cient
ly 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 power
fl
o
ws, 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 describes co
nvexi
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
A. Motivation
T
HE bus injection model is the standard model for power
fl
ow analysis and optimization. It focuses on nodal vari-
ables such as voltages, current and power injections and does
not directly deal with power
fl
ows on individual branches. In-
stead of nodal variables, the branch
fl
ow model focuses on cur-
rents and powers on the branches. It has been used mainly for
modeling distribution circuits which tend to be radial, but has
received far less attention. In this paper, we advocate the use
of branch
fl
ow model for
both
radial and mesh networks, and
demonstrate how it can be used for optimizing the design and
operation of power systems.
One of the motivations for our work is the optimal power
fl
ow
(OPF) problem. OPF seeks to op
timize a certain objective func-
tion, such as power loss, generat
ion cost and/or user utilities,
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. This work
was supported by NSF through NetSE grant CNS 0911041, 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, SCE, the Resnick Institute of Cal-
tech, Cisco, and the Okawa Foundation. A preliminary and abridged version has
appeared in [1]. Paper no. TPWRS-00424-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.2255317
subject to Kirchhoff’s laws, power balance as well as capac
ity,
stability and contingency constraints on the voltages an
d power
fl
ows. There has been a great deal of research on OPF since C
ar-
pentier’s
fi
rst formulation in 1962 [2]; surveys can be f
ound in,
e.g., [3]–[7]. OPF is generally nonconvex and NP
-hard, and a
large number of optimization algorithms and re
laxations have
been proposed. A popular approximation is the
DC power
fl
ow
problem, which is a linearization and theref
oreeasytosolve,
e.g., [8]–[11]. An important observation w
as made in [12] and
[13] that the full AC OPF can be formulated as
a quadratically
constrained quadratic program and th
erefore can be approxi-
matedbyasemide
fi
nite program. Whil
e this approach is illus-
trated in [12] and [13] on several IEE
Etestsystemsusingan
interior-point method, whether or
when the semide
fi
nite relax-
ation will turn out to be exact is no
t studied. Instead of solving
the OPF problem directly, [14] pr
oposes to solve its convex La-
grangian dual problem and gives
asuf
fi
cient condition that must
be satis
fi
ed by a dual solutio
nforanoptimalOPFsolutiontobe
recoverable. This result i
s extended in [15] to include other vari-
ables and constraints and i
n [16] to exploit network sparsity. In
[17] and [18], it is proved
that the suf
fi
cient condition of [14]
always holds for a radial
(tree) network, provided the bounds
on the power
fl
ows satisfy
a simple pattern. See also [19] for
a generalization. Th
ese results con
fi
rm that radial networks are
computationally muc
h simpler. This is important as most distri-
bution systems are r
adial.
The limitation of sem
ide
fi
nite relaxation for OPF is studied in
[20]usingmeshnetw
orks with 3, 5, and 7 buses: as a line-
fl
ow
constraint is tigh
tened, the duality gap becomes nonzero and
the solutions prod
uced by the semide
fi
nite relaxation becomes
physically mean
ingless. Indeed, examples of nonconvexity
have long been d
iscussed in the literature, e.g., [21]–[23]. See,
e.g., [24] for b
ranch-and-bound algorithms for solving OPF
when convex re
laxation fails.
The papers abov
e are all based on the bus injection model.
In this paper,
we introduce a branch
fl
ow model on which OPF
and its relax
ations can also be de
fi
ned. Our model is motivated
by a model
fi
r
st proposed by Baran and Wu in [25] and [26] for
the optima
l placement and sizing of switched capacitors in dis-
tribution
circuits for Volt/VAR control. One of the insights we
highligh
t here is that the Baran-Wu model of [25] and [26] can
be treate
d as a particular relaxation of our branch
fl
ow model
where th
e phase angles of the voltages and currents are ignored.
By reca
sting their model as a set of linear and quadratic equality
constr
aints, [27] and [28] observe that relaxing the quadratic
equal
ity constraints to inequality constraints yields a second-
order
cone program (SOCP). It proves that the SOCP relaxation
is ex
act for radial networks, when there are no upper bounds on
the
loads. This result is extende
dheretomeshnetworkswith
0885-8950/$31.00 © 2013 IEEE
FARIVAR AND LOW: BRANCH FLOW MODEL: RELAXATIONS AND CONVEXIFICATION—PART I
2555
line limits, and convex, as opposed to linear, objective func-
tions (Theorem 1). See also [29] and [30] for various convex
relaxations of approximations of the Baran-Wu model for ra-
dial networks.
Other branch
fl
ow models have also been studied, e.g., in
[31]–[33], all for radial networks. Indeed [31] studies a sim-
ilar model to that in [25] and [2
6], using receiving-end branch
powers as variables instead of sending-end branch powers as
in [25] and [26]. Both [32] and [33] eliminate voltage angles
by de
fi
ning real and imaginary parts of
as new variables
and de
fi
ning bus power injections in terms of these new vari-
ables. This results in a system of linear quadratic equations in
power injections and the new variables. While [32] develops a
Newton-Raphson algorithm to solve the bus power injections,
[33] solves for the branch
fl
ows through an SOCP relaxation for
radial networks, though no pro
of of optimality is provided.
This set of papers [25]–[33] all exploit the fact that power
fl
ows can be speci
fi
ed by a simple set of linear and quadratic
equalities if voltage angles can be eliminated. Phase angles can
be relaxed only for radial networks and generally not for mesh
networks, as [34] points out for their branch
fl
ow model, be-
cause cycles in a mesh network im
pose nonconvex constraints
on the optimization variables (similar to the angle recovery con-
dition in our model; see Theorem 2 below). For mesh networks,
[34] proposes a sequence of SOCP where the nononvex con-
straints are replaced by their lin
ear approximations and demon-
strates the effectiveness of thi
s approach using seven network
examples. In this paper we extend the Baran-Wu model from
radial to mesh networks and use it to develop a solution strategy
for OPF.
B. Summary
Our purpose is to develop a formal theory of branch
fl
ow
model for the analysis and optimization of mesh as well as ra-
dial networks. As an illustration
, we formulate OPF within this
alternative model, propose rela
xations, characterize when a re-
laxed solution is exact, prove that our relaxations are always
exact for radial networks when there are no upper bounds on
loads but may not be exact for mesh networks, and show how to
use phase shifters to convexify
a mesh network so that a relaxed
solution is always optimal for the convexi
fi
ed network.
Speci
fi
cally we formulate in Sec
tion II the OPF problem
using branch
fl
ow equations involving complex bus voltages
and complex branch current and power
fl
ows. In Section III we
describe our solution approach th
at consists of two relaxation
steps (see Fig. 1):
Angle relaxation
: relax OPF by eliminating voltage and
current angles from the branch
fl
ow equations. This yields
the (extended) Baran-Wu model and a relaxed problem
OPF-ar which is still nonconvex due to a quadratic equality
constraint.
Conic relaxation
: relax OPF-ar by changing the quadratic
equality into an inequality constraint. This yields a convex
problem OPF-cr (which is an
SOCP when the objective
function is linear).
In Section IV we prove that the conic relaxation OPF-cr is al-
ways exact
even for
mesh networks, provided there are no upper
bounds on real and reactive loads, i.e.,
any
optimal solution of
Fig. 1. Proposed solution strategy for solving OPF.
Fig. 2. Proposed algorithm for solving OPF (11)–(12) without phase shifters.
The details are explained in Sections II–V.
OPF-cr is also optimal for OPF-ar
. Given an optimal solution of
OPF-ar, whether we can derive an optimal solution of the orig-
inal OPF depends on whether we can recover the voltage and
current angles from the given OPF-ar solution. In Section V we
characterize the exact condition (
the angle recovery condition)
under which this is possible, and present two angle recovery al-
gorithms. The angle recovery condition has a simple interpreta-
tion: any solution of OPF-ar implies an angle difference across
a line, and the condition says that the implied angle differences
sum to zero
around each cycle. For a radial network,
this condition holds trivially an
d hence solving the conic relax-
ation OPF-cr always produces an optimal solution for OPF. For
a mesh network, the angle recove
ry condition corresponds to
the requirement that the implied
phase angle differences sum to
zero around every loop. The given OPF-ar solution may not sat-
isfy this condition, but our char
acterization can be used to check
if it yields an optimal solution for OPF. These results suggest an
algorithm for solving OPF as summarized in Fig. 2.
If a relaxed solution for a mesh network does not satisfy the
angle recovery condition, then it is infeasible for OPF. In Part II
of this paper, we propose a simple way to convexify a mesh net-
work using phase shifters so that
any
relaxed solution of OPF-ar
can be mapped to an optimal solution of OPF for the convexi-
fi
ed network, with an optimal cost that is lower than or equal to
that of the original network.
2556
IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 28, NO. 3, AUGUST 2013
C. Extensions: Radial Networks and Equivalence
In [35] and [36], we prove a variety of suf
fi
cient conditions
under which the conic relaxation proposed here is exact for ra-
dial networks. The main difference from Theorem 1 below is
that [35] and [36] allow upper bounds on the loads but relax
upper bounds on voltage magnitudes. Unlike the proof for The-
orem 1 here, those in [35] and [36] exploit the duality theory.
The bus injection model and the branch
fl
ow model are de-
fi
ned by different sets of equations in terms of their own vari-
ables. Each model is self-contai
ned: one can formulate and ana-
lyze power
fl
ow problems within each model, using only nodal
variables or only branch variables. Both models (i.e., the sets of
equations in their respective var
iables), however, are descrip-
tions of the Kirchhoff’s laws. In [37] we prove formally the
equivalence of these models, in the sense that given a power
fl
ow solution in one model, one can derive a corresponding
power
fl
ow solution in the other model. Although the semide
fi
-
nite relaxation in the bus injection model is very different from
the convex relaxation proposed here, [37] also establishes the
precise relationship between the various relaxations in these two
models.
This is useful because some results are easier to formulate
and prove in one model than in the other. For instance, it is
hard to see how the upper bounds on voltage magnitudes and
the technical conditions on the line impedances in [35] and [36]
for exactness in the branch
fl
ow model affect the rank of the
semide
fi
nite matrix variable in the bus injection model, although
[37] clari
fi
es conditions that guarant
ee their equivalence.
II. B
RANCH
F
LOW
M
ODEL
Let
denote the set of real numbers,
complex numbers, and
integers. A variable without a subscript denotes a vector with
appropriate components, e.g.,
. For a vector
denotes
. For a scalar, vector, or matrix
denotes its transpose and
its complex conjugate transpose.
Given a directed graph
, denote a link in
by
or
if it points from node
to node
.Wewilluse
,or
interchangeably to refer to a link in
.We
write
if
and
are connected, i.e., if either
or
(but not both). We write
if
,
and
if
, for some integer
.
For a
-dimensional vector
denotes its projection onto
by taking modulo
componentwise.
A. Branch Flow Model
Let
be a connected graph representing a power
network, where each node in
represents a bus and each link
in
represents a line (condition A1). We index the nodes by
. The power network is called
radial
if its graph
is a tree. For a distribution netwo
rk, which is typically radial,
the root of the tree (node 0) represents the substation bus. For a
(generally meshed) transmissio
n network, node 0 represents the
slack bus.
We regard
as a directed graph and adopt the following ori-
entation for convenience (only). Pick
any
spanning tree
of
rooted at node 0, i.e.,
is connected and
has
links. All links in
point away from the root. For any
link in
that is not in the spanning tree
, pick an arbitrary
direction. Denote a link by
or
if it points from node
to node
. Henceforth we will assume without loss of generality
that
and
are directed graphs as described above.
1
For each
link
,let
be the complex impedance
on the line, and
be the corresponding
admittance. For each node
,let
be the shunt
impedance from
to ground, and
.
2
For each
,let
be the complex current from buses
to
and
be the
sending-end
complex power
from buses
to
. For each node
,let
be the complex
voltage on bus
.Let
be the net complex power injection,
which is generation minus load on bus
.Weuse
to denote
both the complex number
and the pair
depending
on the context.
As customary, we assume that the complex voltage
is
given and the complex net generation
is a variable. For power
fl
ow analysis, we assume other power injections
are given. For optimal power
fl
ow, VAR control, or
demand response,
are control variables as well.
Given
and bus power
injections
,thevariables
satisfy the Ohm’s law:
(1)
the de
fi
nition of branch power
fl
ow:
(2)
and power balance at each bus: for all
,
(3)
We will refer to (1)–(3) as the
branch
fl
ow model/equations
.
Recall that the cardinality
and let
.The
branch
fl
ow equations (1)–(3) specify
nonlinear
equations in
complex variables
,when
other bus power injections
are speci
fi
ed.
We will call a solution of (1)–(3) a
branch
fl
ow solution
with
respect to a given
, and denote it by
.Let
be the set of all branch
fl
ow solutions with
respect to a given
:
solves (1)-(3) given
(4)
and let
be the set of all branch
fl
ow solutions:
(5)
For simplicity of exposition, we will often abuse notation and
use
to denote either the set de
fi
nedin(4)orthatin(5),de-
1
The orientation of
and
are different for different spanning trees
,but
we often ignore this subtlety in this paper.
2
The shunt admittance
represents capacitive devices on bus
only and a
line is modeled by a series admittance
without shunt elements. If a shunt
admittance
is included on each end of line
in the
-model, then
the line
fl
ow should be
.