# Maximizing electrical power supply using FACTS devices

Karsten Lehmann, Russell Bent and Feng Pan

###### Abstract

Modern society critically depends on the services electric power provides.
Power systems rely on a network of power lines and transformers to deliver
power from sources of power (generators) to the consumers (loads). However,
when power lines fail (for example, through lightning or natural disasters) or
when the system is heavily used, the network is often unable to fulfill all of
the demand for power. While systems are vulnerable to these failures,
increasingly, sophisticated control devices are being deployed to improve the
efficiency of power systems. Such devices can also be used to improve the
resiliency of power systems to failures. In this paper, we focus on using
FACTS devices in this context. A FACTS device allows power grid operators to
adjust the impedance parameters of power lines, thereby redistributing flow in
the network and potentially increasing the amount of power that is supplied.
Here we develop new approaches for determining the optimal parameter settings
for FACTS devices in order to supply the maximal amount of power when networks
are stressed, e.g. power line failures and heavy utilization.

##  I Introduction

One of the challenges facing modern infrastructures is the possibility of
events that cause large-scale damage. These events include hurricanes (i.e.
Superstorm Sandy, Hurricane Katrina, etc.), ice storms, earthquakes, etc.
During these events, significant portions of a society may be without
services, such as electric power, that these systems provide. As a result,
there is considerable interest in developing approaches and methods for
mitigating the effects of these events and restoring these systems as quickly
as possible [1, 2]. One approach for mitigating the effects utilizes controls
in the system to limit the impact of large-scale events. While installing such
controls solely for the purpose of responding to big events may be too
expensive in general, many systems have experienced a rapid rise in deployment
of advanced control technologies to improve efficiency, cost, and reliability
to small-scale events [3]. Here, we focus on how existing adopted technologies
may be used during emergency situations to mitigate the impacts of large-scale
events. In particular, we focus on how Flexible AC Transmission System (FACTS)
[4] improve power throughput when a system is stressed due to damage or
increased utilization of the system.

The flow of electric power in power systems is governed by complicated non-
linear physics. From a practical perspective, this means power flows along
paths of least resistance from sources of power to consumers of power. As a
result, operators have limited ability to direct how power flows in a network.
This lack of control has a number of consequences, but the most important
consequence here is that a network’s capacity may be underutilized. One
solution to this problem is FACTS devices. Using a wide variety of
technologies, FACTS devices allow an operator to modify the resistivity of
power lines, to shift power away or towards portions of a network. As a
result, power systems may use more of their capacity, are more evenly
utilized, and less expensive power generation may be dispatched. While their
primary use is in daily operations to improve efficiency, security, and
economics, FACTS devices, as shown in this paper, are also useful for
improving system response during stressed and adverse conditions.

In general, most recent work of FACTS device related optimization and control
has focused on how FACTS can contribute to the stability [5], [6], [7], [8],
[9] and the maximum load-ability of a network [10], [11], [12], [13]. There is
also work identifying where to place FACTS devices such that the load-ability
of a network is maximized [14], [15], [16]. [17] provides a survey of
different goals and methods that are used in FACTS optimization. All of those
approaches use heuristics (for example genetic algorithms, particle swarm) and
run simulations on small power networks (up to 59 buses). An exception to
these papers is the work [18] that studies the FACTS placement problem on the
2736 bus polish network using the Linear DC model. In this paper we also use
the Linear DC model and in contrast to existing work, we study the maximum
throughput of a network on the big 2736 buses polish network. We also focus on
developing a globally optimal approach as opposed to heuristics.

The key contributions of this paper are as follows:

  * •

An optimization model for maximizing power throughput in power systems when
FACTS devices are available.

  * •

Empirical results demonstrating how FACTS devices increase power throughput in
stressed and damaged systems.

  * •

A discussion of the computational complexity of maximizing power throughput in
power systems with FACTS devices.

  * •

Unlike similar problems, such as transmission switching [19], our empirical
results suggest that, in practice, the problem is often tractable to solve to
small optimality gaps, even for large systems.

  * •

An algorithm for improving the computational performance of commercial solvers
on this problem.

The remainder of this paper is organized as follows. Section II defines the
problem. Section III discusses the complexity of the problem and Section IV
discusses our algorithm for solving the problem. Section V describes the
results of our computational experiments and we conclude with Section VI.

##  II Problem Definition

Power flows in electrical power networks are described by nonlinear, steady-
state electrical power flow equations (Alternating Current Model, AC). In this
paper we use the _Linear DC (LDC) model_ which is an approximation
(linearization) of the AC model [20]. This model ignores reactive power and
resistance and assumes that all voltages magnitudes are one in the per-unit
system. What remains are susceptances (the negative inverse of the reactance),
the capacities and the phase angles of the voltages. The flow on a line is
similar to that of DC currents. The susceptance is the counterpart to the DC
resistance, phase angles are the counterpart to the DC voltages and the power
is the counterpart to the current. FACTS devices are physical devices allowing
the (otherwise constant) susceptance parameter to vary.

###### Definition 1

A _FACTS Linear DC network (FLDC network)_ is a tuple
${\mathcal{N}}=({N},{{N}_{{G}}},{{N}_{{L}}},{E})$ where ${N}$ is the set of
_buses_ ; ${{N}_{{G}}}\subseteq{N}$ is the set of _generators_ ;
${{N}_{{L}}}\subseteq{N}\setminus{{N}_{{G}}}$111W.l.o.g. buses with load and
generation can be split into separate buses. is the set of _loads_ ; and
${E}\subseteq{\mathcal{P}_{2}({N})}\times{{\mathcal{I}({{\mathbb{R}}^{+}})}}\times{{\mathbb{R}}^{+}}$
is the set of _lines_ with their _susceptance limits_ and
_capacity_.222W.l.o.g. we assume that no two lines connect the same pair of
buses.

A _Linear DC network (LDC network)_ network is an FLDC network without FACTS
devices, i.e. all susceptances are fixed. We define functions
${{B^{*}}:{E}\rightarrow{{\mathcal{I}({{\mathbb{R}}^{+}})}}}$ for the
susceptance limits and ${{C}:{E}\rightarrow{{\mathbb{R}}^{+}}}$ for the
capacities of power lines. For a line from $a$ to $b$ with susceptance limit
$[s,t]$ and capacity $p$ we use notation ${{ab}_{p}^{[s,t]}}$. If the
susceptance is fixed, i.e., $t=s$, we write ${{ab}_{p}^{s}}$. We may also
ignore these values and simply refer to the line by ${{ab}}$. While this model
does not explicitly give upper bounds on the generation or load of a bus, such
constraints can be modeled by connecting these buses to the network through a
single line whose capacity is the maximum output/intake of the bus.

We now introduce the notations and equations describing FLDC network power
flows. We assume a fixed FLDC network
${\mathcal{N}}=({N},{{N}_{{G}}},{{N}_{{L}}},{E})$. The _generation_ and _load_
at a bus are given by functions ${{G}:{N}\rightarrow{{\mathbb{R}}^{+}}}$ and
${{L}:{N}\rightarrow{{\mathbb{R}}^{+}}}$ such that $\forall
a\in{N}\setminus{{N}_{{G}}}:{G_{a}}:=0$ and $\forall
a\in{N}\setminus{{N}_{{L}}}:{L_{a}}:=0$. Also, we define functions
${{B}:{E}\rightarrow{{\mathbb{R}}^{+}}}$ and
${{\Theta}:{N}\rightarrow{\mathbb{R}}}$ such that ${B_{e}}$ is the
_susceptance_ of line $e$ and ${\Theta_{a}}$ is the _phase angle_ at bus $a$.
The _flow_ on a line is given by function ${{F}:{E}\rightarrow{\mathbb{R}}}$.
While the lines of FLDC networks are undirected, orientation is needed to
describe flows. However, the concrete orientation we choose does not influence
the theory. To that end, whenever we define a line, we abuse the notation
${{ab}}$ to indicate that ${F_{ab}}\geq 0$ whenever the flow goes from $a$ to
$b$ and ${F_{ab}}\leq 0$ otherwise.

The LDC network model imposes two laws: Kirchhoff’s conservation law and the
LDC network power law.

###### Definition 2

A triple $({F},{G},{L})$ satisfies _Kirchhoff’s conservation law_ if $\forall
a\in{N}:\sum_{{{ab}}\in{E}}{F_{ab}}-\sum_{{{ba}}\in{E}}{F_{ba}}={G_{a}}-{L_{a}}.$

###### Definition 3

A triple $({B},{\Theta},{F})$ satisfies the _LDC network power law_ if
$\forall{{ab}}\in{E}:{F_{ab}}={B_{ab}}({\Theta_{b}}-{\Theta_{a}})$
333Normally, the susceptance is a negative value and the flow equation is
${B_{ab}}({\Theta_{a}}-{\Theta_{b}})$. For notation simplicity, we make the
susceptance a positive value and multiply the flow equation by $-1$..

###### Definition 4

We call a tuple ${({B},{\Theta},{F},{G},{L})}$ a _feasible solution_ if:
$({F},{G},{L})$ satisfies Kirchhoff’s conservation law; $({B},{\Theta},{F})$
satisfies the LDC network power law; $\forall e\in{E}:{B_{e}}\in{B_{e}^{*}}$
and $\forall e\in{E}:|{F_{e}}|\leq{C_{e}}$.
Finally, we use ${\mathcal{T}_{{\mathcal{N}}}}$ for the set of all feasible
solutions of ${\mathcal{N}}$.

The maximum flow ${\mathcal{MF}({\mathcal{N}})}$ of a network ${\mathcal{N}}$
is a triple $({F},{G},{L})$ that maximizes the generation w.r.t. respecting
Kirchhoff’s conservation law; the line capacities and the generation and load
bounds. We now define two variants of this problem for power networks. The
_maximum FACTS flow (MFF)_ additionally has to satisfy the LDC power law. The
_maximum potential flow (MPF)_ is a variant of MFF where susceptance is fixed
(i.e., it applies to an LDC network).

###### Definition 5

The _maximum FACTS flow (MFF)_ of an FLDC network ${\mathcal{N}}$ is defined
as
${\mathcal{MFF}({\mathcal{N}})}:=\max_{{({B},{\Theta},{F},{G},{L})}\in{\mathcal{T}_{{\mathcal{N}}}}}\sum_{g\in{N}}{G_{g}}.$

The _maximum potential flow (MPF)_ of an LDC network ${\mathcal{N}}$ is
defined as
${\mathcal{MPF}({\mathcal{N}})}:=\max_{{({\Theta},{F},{G},{L})}\in{\mathcal{T}_{{\mathcal{N}}}}}\sum_{g\in{N}}{G_{g}}.$

Figure 1(a) shows an LDC network where $g$ is a generator (box), $l$ is a load
(house) and $b$ is a bus (sphere). We omit the susceptance and capacity of a
line when its value is $1$. Here, the MF for this network is $34$ whereas in
the LDC model, we only can supply $16$ as shown in Figure 1(b) because the
congestion of the edge ${{bl}_{4}^{1}}$ constrains the phase angle (written as
$A=$ in the buses) between $g$ and $l$. Figure 1(c) shows a variant of the
network with two FACTS devices. These devices allow the maximum generation to
reach $28$ as shown in Figure 1(d).

(a) An LDC network.  (b) The MPF.  (c) An FLDC network network.  (d) The MFF.

Figure 1: Examples for MFF and MPF.

##  III Computational Complexity

Finding the solution to the MPF is known to be polynomial as it can be
described as a linear program (LP). In our workshop paper [21] we prove that
finding the solution to the MFF is NP-complete even for simple network
structures. For completeness, we discuss the main idea of the proof here. We
also present three special cases where the problem is polynomial: the network
is a tree; all lines ${{ab}_{p}^{[s,t]}}$ have FACTS devices with either $s=0$
or $t=\infty$. In all three cases the MFF is equal to the MF.

###### Lemma III.1

Let ${\mathcal{N}}$ be an FLDC network with a tree structure then
${\mathcal{MFF}({\mathcal{N}})}={\mathcal{MF}({\mathcal{N}})}$.

###### Proof:

This is a consequence of the absence of cycles. Hence there are no cyclic
dependencies on the phase angles which allows us to chose them in a way to
match any optimal solution of the traditional max flow. ∎

###### Lemma III.2

Let ${\mathcal{N}}$ be an FLDC network where for all lines
${{ab}_{p}^{[s,t]}}$: $s=0$ then
${\mathcal{MFF}({\mathcal{N}})}={\mathcal{MF}({\mathcal{N}})}$.

###### Proof:

Let $({F},{G},{L})$ be an acyclic optimal solution of the MF. We have to
define susceptance ${B}\in{B^{*}}$ and phase angles ${\Theta}$ such that the
DC power law is satisfied. First, we define preliminary phase angles
${\Theta}^{\prime}$ using arbitrary positive values with the restriction that
they respect the flow directions, so
$\forall{{ab}}\in{E}:{\Theta_{a}^{{}^{\prime}}}>{\Theta_{b}^{{}^{\prime}}}\text{
if }{F_{ab}}<0;{\Theta_{a}^{{}^{\prime}}}<{\Theta_{b}^{{}^{\prime}}}\text{ if
}{F_{ab}}>0;\text{ and
}{\Theta_{a}^{{}^{\prime}}}={\Theta_{b}^{{}^{\prime}}}\text{ if }{F_{ab}}=0.$
This defines susceptances ${B}^{\prime}$ via the DC power law:
$\forall{{ab}}\in{E}:{B_{ab}^{{}^{\prime}}}:=\frac{{F_{ab}}missing}{{\Theta_{b}^{{}^{\prime}}}-{\Theta_{a}^{{}^{\prime}}}}$.
We now scale these susceptances such that they fit into their limits. Let
$x:=min\\{\frac{s}{{B_{ab}^{{}^{\prime}}}}\mid{{ab}_{p}^{[0,s]}}\in{E}\\}$. By
setting ${B}:=x{B}^{\prime}$ and ${\Theta}:=\frac{1}{x}{\Theta}^{\prime}$ we
obtain
$\forall{{ab}}\in{E}:{F_{ab}}={B_{ab}^{{}^{\prime}}}({\Theta_{b}^{{}^{\prime}}}-{\Theta_{a}^{{}^{\prime}}})=x{B_{ab}^{{}^{\prime}}}(\frac{1}{x}{\Theta_{b}^{{}^{\prime}}}-\frac{1}{x}{\Theta_{a}^{{}^{\prime}}})={B_{ab}}({\Theta_{b}}-{\Theta_{a}})$
and hence $({B},{\Theta},{F})$ satisfies the LDC power law. Also, using the
definition of $x$, for an arbitrary ${{ab}_{p}^{[0,s]}}\in{E}$ we have
$x\leq\frac{s}{{B_{ab}^{{}^{\prime}}}}$ and hence $0\leq{B_{ab}}\leq s$. ∎

###### Lemma III.3

Let ${\mathcal{N}}$ be an FLDC network where for all lines
${{ab}_{p}^{[s,t]}}$ we have $t=\infty$ then
${\mathcal{MFF}({\mathcal{N}})}={\mathcal{MF}({\mathcal{N}})}$.

###### Proof:

Similar to the proof of Lemma III.2.∎

In [21] we prove that deciding whether or not
${\mathcal{MFF}({\mathcal{N}})}\geq x$ for some given $x\in{\mathbb{R}}$ is
strongly NP-complete in general and NP-complete when we restrict the network
structure to cacti. A network is a cactus if every line is part of at most one
cycle. The key element of these proofs are _choice networks_. While the
workshop paper presents the pure mathematical proof of the properties of
choice networks, the reminder of this section presents the underlying idea
that makes these properties possible.

Choice networks are used to encode (discrete) choices that characterize NP-
hard problems. Given an $x\in{{\mathbb{R}}^{+}}$, a choice network can be
regarded as a black box with port $p$ where we have external generation of
either $x$ or $0$ at $p$ in order to achieve the inner maximum generation.
External generation indicates that the black box acts as generator for the
network that is connected to to $p$. Inner generation is the generation
produced inside the black box.

Figure 2:  A choice network with port $p$.

Figure 2 presents our generation-FACTS-choice network ${\mathit{GFCN}_{p,x}}$.

In the following we describe the way the choice network works for the case
$x=1$. In Figure 2, the generator can deliver 1 unit of power. Let the flow to
$p$ be $w$ and the flow to the network $A$ be $r$, so that $w+r=1$. For the
port $p$ we have ${\mathcal{MFF}(p)}=w$. The MFF of port $p$ depends on $w$
according to a linear function of the form $f(z)=n+mz$. Here, $n$ is the _base
generation_ and $m$ is the _generation ratio_. The port $p$ has a base
generation of $0$ and a generation ratio of $1$. In the DC model and in a
network without FACTS device, $n$ and $m$ are independent from the input. The
usage of FACTS devices allows us to construct networks where both values
change if the input exceeds some threshold. As we will show later, network $A$
is constructed in a way that ${\mathcal{MFF}(A)}=5.1+\frac{2}{3}r$ if $r\leq
0.65$ and ${\mathcal{MFF}(A)}=(5.1-\frac{1}{3})+\frac{4}{3}r$ otherwise. Using
the equation $w=1-r$ and assuming $r\leq 0.65$ we have
${\mathcal{MFF}({\mathit{GFCN}_{p,1}})}=1-r+5.1+\frac{2}{3}r=6.1-\frac{1}{3}r$
which has a single maximum of $6.1$ at $r=0$. On the other hand, if $r\geq
0.65$ then we have
${\mathcal{MFF}({\mathit{GFCN}_{p,1}})}=1-r+(5.1-\frac{1}{3})+\frac{4}{3}r=6.1-\frac{1}{3}+\frac{1}{3}r$
which has a single maximum of $6.1$ at $r=1$. This implies that there are
exactly two solutions to achieve a flow of $6.1$ and that port $p$ has $0$ or
$1$ units of power. Looking at the general case, we see that $p$ either
generates $0$ or $x$.

The MFF of $A$ depends on the value of $r$:
${\mathcal{MFF}(A)}=5.1+\frac{2}{3}r$ if $r\leq 0.65$ and
${\mathcal{MFF}(A)}=(5.1-\frac{1}{3})+\frac{4}{3}r$ otherwise. The key feature
to make it possible that there are exactly two solutions for the MFF is that
the generation ratio changes from a value less than one ($\frac{2}{3}$) to a
value greater than one ($\frac{4}{3}$). We now explain why $A$ has two
generation ratios. The network $A$ consists of two networks in sequence: $B$
and $C$. The network $C$ has a fixed generation ratio of $2$. Every unit of
power that enters $d$ has to go to $f$. This increases the phase angle
difference between $d$ and $f$ by one. Hence the phase angle difference
between $e$ and $f$ increases by one and gives us an additional unit of power.
Network $B$ has two generation ratios: $\frac{1}{3}$ for an input less then
$0.65$ and $\frac{2}{3}$ otherwise. Because $B$ and $C$ are in sequence, the
ratios multiply and we get ratios of $\frac{2}{3}$ and $\frac{4}{3}$ for $A$.

Using choice networks, we reduced the exact cover by 3-set problem into the
MFF problem [21]. Figure III.4 presents the idea of the proof.

Figure 3:  Example encoding for
$(M,S)=(\\{a,b,c,d,e,f\\},\allowbreak\\{\\{a,b,c\\},\\{b,c,d\\},\allowbreak\\{d,e,f\\}\\})$.

###### Theorem III.4

Let $x\in{\mathbb{R}}$ and ${\mathcal{N}}$ be an FLDC network. Deciding if
${\mathcal{MFF}({\mathcal{N}})}\geq x$ is strongly NP-complete.

###### Proof:

We prove this by reduction from the _exact cover by 3-set problem_. Given a
set $M$ and a set of subsets $S\subseteq{\mathcal{P}(M)}$ where every element
of $S$ has exactly 3 elements, decide if there exist a set $T\subseteq S$ such
that $\bigcup_{X\in T}X=M$ and $\forall X_{1},X_{2}\in T:X_{1}\neq
X_{2}\implies X_{1}\cap X_{2}=\emptyset$.

For an instance $(M,S)$, we define the FLDC network
${\mathcal{N}_{*}^{M,S}}:=({N},{{N}_{{G}}},{{N}_{{L}}},{E})$ with
${{N}_{{G}}}:=\\{g\\}$, ${{N}_{{L}}}:=\\{l\\}$,
${N}:={{N}_{{G}}}\cup{{N}_{{L}}}\cup\bigcup_{X\in
S}\\{v_{X}\\}\cup\bigcup_{x\in M}\\{x\\}$ and
${E}:=\\{{{gl}_{3}^{1}}\\}\cup\bigcup_{X\in S}\bigcup_{x\in
X}\\{{{v_{X}x}_{1}^{1}}\\})\cup\bigcup_{x\in
M}\\{{{gx}_{1}^{1}},{{xl}_{2}^{1}}\\}.$ We then define
${\mathcal{N}^{M,S}}={\mathcal{N}_{*}^{M,S}}+\sum_{X\in
S}{\mathit{GFCN}_{3,v_{X}}}$ and we have:
${\mathcal{MFF}({\mathcal{N}^{M,S}})}=3+18.3|S|+|M|\iff(M,S)\text{ is
solvable}.$ An example encoding for the exact cover problem
$(M,S)=(\\{a,b,c,d,e,f\\},\allowbreak\\{\\{a,b,c\\},\allowbreak\\{b,c,d\\},\allowbreak\\{d,e,f\\}\\})$
can be found in Figure 3. The choice networks are represented by 3D boxes
where the number $3$ in parenthesis is the value chosen for $x$.

For each $b\in M$ we have a bus $b$. The network is constructed such that
${\mathcal{MFF}({\mathcal{N}^{M,S}})}=3+18.3|S|+|M|$ iff all choice networks
have their inner maximum generation ($3\cdot 6.1$) and all lines from the
generator are congested. This implies a phase angle difference of $3$ between
the generator and the load and a phase angle difference of $1$ between $b$ and
the generator. Hence we have a phase angle difference of $2$ between the load
and $b$. For $b$ to satisfy Kirchhoff’s conservation law, $b$ receives one
unit of flow from a ${\mathit{GFCN}_{3,v_{X}}}$ with $b\in X$. Because
${\mathit{GFCN}_{3,v_{X}}}$ can only generate $3$ if it wants to generate
anything, all $c\in X$ get one. Hence, we can only achieve the proposed MFF
value iff $(M,S)$ is solvable. ∎

##  IV Global Optimization

In this section we present a mixed integer program (MIP) model to find the
solution to the MFF. The main problem in solving the MFF is the right-hand-
side of the DC power law ${F_{ab}}={B_{ab}}({\Theta_{b}}-{\Theta_{a}})$. This
constraint contains the product of two variables which, in general, is a non-
convex quadratic constraint (as implied in the previous section).

However, for solving the MFF, we do not need to know the susceptance values,
we only need to ensure that there exists valid susceptance values such that
the phase angle difference and the line flow are bound together. The solution
region for just the phase angle difference and the flow consists of two convex
regions. There is one region for positive phase angle differences and one
region for negative phase angle differences. Given an edge
${{ab}_{p}^{[s,t]}}$ the positive region is described by
$s({\Theta_{b}}-{\Theta_{a}})\leq{F_{ab}}\leq t({\Theta_{b}}-{\Theta_{a}})$.
To formulate the problem as a MIP, we introduce a binary variable $d_{{{ab}}}$
that represents the choice of phase angle difference direction. Assuming that
$M$ is some upper bound for the phase angle difference, the MIP model can be
found in Model 1.

Model 1:  MIP model to solve the MFF. maximize
$\displaystyle\sum_{a\in{N}}{G_{a}}$ (1) subject to $\displaystyle
d_{{{ab}}}\in\\{0,1\\},\;{{ab}}\in{E}$ (2) $\displaystyle
0\leq{\Delta_{ab}^{+}}\leq d_{{{ab}}}M,\;{{ab}}\in{E}$ (3) $\displaystyle
0\leq{\Delta_{ab}^{-}}\leq(1-d_{{{ab}}})M,\;{{ab}}\in{E}$ (4)
$\displaystyle{\Delta_{ab}^{+}}-{\Delta_{ab}^{-}}={\Theta_{b}}-{\Theta_{a}},\;{{ab}}\in{E}$
(5) $\displaystyle s{\Delta_{ab}^{+}}\leq{F_{ab}^{+}}\leq
t{\Delta_{ab}^{+}},\;{{ab}_{p}^{[s,t]}}\in{E}$ (6) $\displaystyle
s{\Delta_{ab}^{-}}\leq{F_{ab}^{-}}\leq
t{\Delta_{ab}^{-}},\;{{ab}_{p}^{[s,t]}}\in{E}$ (7)
$\displaystyle{F_{ab}}={F_{ab}^{+}}-{F_{ab}^{-}},\;{{ab}}\in{E}$ (8)
$\displaystyle\sum_{{{ab}}\in{E}}{F_{ab}}-\sum_{{{ba}}\in{E}}{F_{ba}}={G_{a}}-{L_{a}},\;a\in{N}$
(9) $\displaystyle-{C_{ab}}\leq{F_{ab}}\leq{C_{ab}},\;{{ab}}\in{E}$ (10)

In this model, Equation 1 describes the objective function that maximize the
amount of flow in the system by maximizing the total generation. Equation 2
constrains the flow direction variables as binary. Then, equations 3 and 4
force either the positive or negative phase angle difference of $ab$ to be 0
depending on the choice of $d$. Equation 5 states that the difference in phase
angles (right hand side), as stated by $\Theta$, is equal to the sum of the
negative and positive phase angle differences as stated by $\Delta$. This
constraint couples the flow direction (edge based variables) with the phase
angles (node based variables). Equations 6 and 7 state that the flow in the
positive or negative direction can be any value that is consistent with the
phase angle differences and the bounds on the susceptances. Equation 8 states
the flow on $ab$ is the sum of the negative and positive flows. Equation 9
states that flow must be balanced at each node. Finally, equation 10
constrains the flow on $ab$ to be smaller than its capacity. After this
problem is solved, the susceptance of $ab$ is calculated as
${B_{ab}}=\frac{{F_{ab}}missing}{{\Theta_{b}}-{\Theta_{a}}missing}$.

During our experimental testing, we observed cases where commerical solvers
such as Gurobi and Cplex were unable to find provably good solutions on large
problems. After one CPU hour the optimality gap was larger than 400%, in some
cases. Based on these observations, we developed an approach to boost the
performance of the solvers by providing high quality initial solutions. We
refer to this approach as the _iterative method (IM)_.The IM is based on two
observations. First, finding the MPF is polynomial. That means that finding
the maximum flow in a network with fixed susceptances is easy. Second, if we
fix the binary variables in the MIP model, we are left with an LP. Fixing the
binary variables is equivalent to fixing the phase angle difference for all
lines. We refer to the maximum possible flow possible when the sign of the
phase angle differences fixed as the maximum variable flow (MVF). The IM works
as follows, given some random valid susceptances (${B}$) we find the MPF. Then
we take the sign of the phase angle differences ($D$) from this solution, fix
them and solve the MVF problem. From this solution we take the susceptances
(${B}$) and put them into the MPF model to start the next iteration. This
process is described in Algorithm 1. We continue iterating until we converge
to a solution.

Data: susceptances ${B}$

Result: phase angle difference directions $D$

MPF = -1;

MVF = 0;

while _MPF $<$ MVF_ do

MPF, $D$ = $solveMPF({B}$);

MVF, ${B}$ = $solveMVF(D)$;

end while

Algorithm 1 The iterative method (IM).

##  V Experimental Results

For our experimental results we focused on evaluating the computation required
for solving the MPF, both with and without the IM. We also compared the
solutions obtained by the MPF with the solutions of MFF in order to provide
some evidence of the types of solution improvement one might expect when FACTS
devices are used. We used the IEEE test problems provided with Matpower [22]
to test our approach. In general, on smaller networks, the MFF is
computationally easy to solve (under 1 CPU minutes) and the differences
between MPF and MFF are small. Thus, we focus on presenting results produced
on the IEEE 2736 bus system (based on Poland’s power grid) due to its large
size and computational challenges. The results were obtained on a computer
with an Intel Core i7-4702HQ Quad Core processor using Gurobi 5.5 [23].

We used two approaches to create variants of the IEEE problems that mimic
damage and heavy utilization. Our first method removes random lines to
simulate line failures.

Figure 4:  IEEE 2736 damage scenarios that remove randomly selected lines (x
axis). The y-axis shows the maximum throughput for MPF and MFF.

Figure 4 shows results on IEEE 2736 for 60 scenarios where random sets of
lines are removed from the power network. The graphs compare the quality of
the solution for MPF with MFF. MFF was initialized with IM and was allowed to
run for 10 CPU minutes. In each case we selected a random set of lines that
have FACTS devices according to a uniform distribution. Each device was
allowed to vary the suceptances $30\%$. With these results, we see that as the
amount of damage increases, the benefits provided by MFF increase (up to
$5\%$).

TABLE I: A comparison of MFF and MPF on IEEE2736 for different congestion factors. $30\%$ of the lines have FACTS devices Generation | 1.5 | 2.0 | 2.5 | 3.0
---|---|---|---|---
Load | MPF | MFF | Improv. | MPF | MFF | Improv. | MPF | MFF | Improv. | MPF | MFF | Improv.
1.5 | 270.56 | 271.0 | 0.16 | 271.12 | 271.12 | 0.0 | 271.12 | 271.12 | 0.0 | 271.12 | 271.12 | 0.0
2.0 | 303.05 | 303.13 | 0.03 | 347.8 | 353.47 | 1.63 | 354.99 | 358.68 | 1.04 | 358.17 | 360.33 | 0.6
3.0 | 303.13 | 303.13 | 0.0 | 392.83 | 401.49 | 2.2 | 433.85 | 445.88 | 2.77 | 450.15 | 462.18 | 2.67
4.0 | 303.13 | 303.13 | 0.0 | 401.26 | 403.12 | 0.46 | 461.17 | 473.41 | 2.66 | 490.41 | 502.01 | 2.36
TABLE II: Results comparing MFF with IM on problem IEEE2736 with different FACTS devices. The MPF of the network is $419.19$. IM significantly improves the quality of solutions. Net | MFF (1h time limit) | 3-IM | 3-IM + MFF (10min time limit) | Improv.
---|---|---|---|---
FACTS% | Interval% | Obj | RT | MIPgap | Obj | RT | Calls | Obj | RT | MIPgap | to MPF in %
30 | 40 | 405.32 | 3600 | 15.69 | 463.83 | 306 | 83.00 | 463.86 | 600 | 1.29 | 10.66
60 | 70 | 455.22 | 3600 | 3.07 | 466.87 | 320 | 91.00 | 466.98 | 600 | 0.71 | 11.4
60 | 10 | 91.47 | 3600 | 398.14 | 445.78 | 191 | 45.00 | 445.80 | 600 | 2.34 | 6.35
10 | 40 | 449.72 | 3602 | 4.25 | 458.21 | 188 | 23.00 | 460.21 | 600 | 2.13 | 9.79
30 | 10 | 88.85 | 3600 | 424.37 | 457.66 | 224 | 41.00 | 457.69 | 600 | 1.80 | 9.18
60 | 40 | 343.99 | 3603 | 35.85 | 460.12 | 218 | 41.00 | 460.15 | 600 | 1.62 | 9.77
90 | 40 | 376.41 | 3600 | 23.58 | 451.43 | 176 | 21.00 | 454.08 | 600 | 2.52 | 8.32
90 | 70 | 455.22 | 3600 | 3.07 | 466.87 | 320 | 91.00 | 466.98 | 600 | 0.71 | 11.4
10 | 10 | 385.63 | 3600 | 21.42 | 463.98 | 304 | 73.00 | 464.04 | 600 | 1.07 | 10.7
10 | 70 | 455.22 | 3600 | 3.07 | 466.65 | 230 | 67.00 | 466.73 | 600 | 0.55 | 11.34
30 | 70 | 455.22 | 3600 | 3.07 | 466.87 | 254 | 65.00 | 466.98 | 600 | 0.71 | 11.4

Our second method scales the upper bound of load and generation to model
increased utilization. We refer to the scaling factors as generation and load
_congestion factors_ , respectively. Table I presents the solutions for MPF,
MFF and their improvement percentage for different congestion factors when
$30\%$ of the lines (randomly chosen) have FACTS devices that are allowed to
vary from their initial susceptance by $30\%$. MFF was initialized with IM and
was allowed to run for 10 CPU minutes. The first row and column of this table
note the generation and load congestion factors. In this table, the results
indicate that as the congestion factors increase, the benefit of MPF over MFF
increases by up to $3\%$.

In most of the results discussed in this section, Gurobi is able to find
solutions with a gap of $0.1\%$ in under an hour of CPU time without the need
for IM. As part of our study, we generated a large number of random cases for
different levels of FACTS penetration and different capabilities of FACTS to
vary susceptances. In some of these cases, even with 1 CPU hour available,
Gurobi was unable to find reasonable solutions. In general, we observed this
behavior when the gap between MPF and MFF was large (between 6 and 11%). We
show some results for one case when the generation congestion factor was
$2.375$ and the load congestion factor was $2.75$ in II. The MPF of this
network is $419.9$. The first two columns of this table show the percentage of
lines with FACTS devices and the allowed interval of susceptance (as a
percentage of the original suspectance). The MFF column shows the results of
MFF without IM. The columns labeled Obj, RT, and MIPGap present the solution,
run time in CPU seconds, and optimality gap, respectively. The column 3-IM
presents the results of the iterative method in terms of solution quality
(IM), run time in CPU seconds (RT), and iterations (Calls). Here, IM is
executed 3 times with different starting solutions (susceptance upper bound,
sucsceptance lower bound, and suscepatance mid point), and the best result is
reported. As seen in these results, the IM method produces a high quality
solution in a short amount of time. In the 3-IM + MFF column, we show the
results after 10 CPU minutes when IM is used as an initial solution for MFF.
Though the MIP solver is unable to improve the solutions much, it is able to
show that the IM method (in most casess) produces solutions with substantially
small optimality gaps and that are significantly better than MPF.

##  VI Conclusion

In this paper we discussed an optimization model for maximizing the throughput
of a network utilizing FACTS devices and an algorithm that improves the
computational performance of commercial solvers on this problem. In general,
even for large scale problems, our approach is able to solve the problem to
near optimality in under 10 CPU minutes. On large scale problems, using FACTS
devices when the network is over utilized or damaged is able to improve the
throughput between 2 and $5\%$ (on occasion, higher). While this appears to be
a modest improvement, when discussing damage scenarios that result in millions
of people without power (such as Hurricane Sandy), a $5\%$ improvement
corresponds to a significant number of people. We also provided a discussion
that illustrates that the problem is NP-complete in general.

There remain a number of interesting future directions in FACTS device
optimization for maximum throughput. It will be interesting to include other
types of controls, such as switching, to determine if the combined control
further improves system response. It will also be interesting to consider
problems that are of larger scale than the IEEE Polish systems. Finally,
future work should also conduct an in-depth study of problem structure that
results in solutions with large gaps between MPF and MFF in order to guide the
placement of FACTS devices.

## Acknowledgment

This work was partially supported by the Los Alamos National Laboratory LDRD
project Optimization and Control Theory for Smart Grids and the Department of
Energy Advanced Grid Science Program.

## References

  * [1] P. Van Hentenryck, C. Coffrin, and R. Bent, “Vehicle Routing for the Last Mile of Power System Restoration,” in _17th Power Systems Computation Conference_ , Stockholm, Sweden, 2011.
  * [2] M. M. Adibi and L. H. Fink, “Power System Restoration Planning,” _IEEE Transactions on Power Systems_ , vol. 9, no. 1, pp. 22–28, 1994.
  * [3] United States Department of Energy, “2010 Smart Grid System Report,” Washington, DC, Tech. Rep., 2012.
  * [4] N. G. Hingorani, L. Gyugyi, and M. El-Hawary, _Understanding FACTS: concepts and technology of flexible AC transmission systems_. IEEE press New York, 2000, vol. 1.
  * [5] A. Oudalov, R. Cherkaoui, and A. Germond, “Application of fuzzy logic techniques for the coordinated power flow control by multiple series facts devices,” in _Power Industry Computer Applications, 2001. PICA 2001. Innovative Computing for Power - Electric Energy Meets the Market. 22nd IEEE Power Engineering Society International Conference on_ , 2001, pp. 74–80.
  * [6] W. Wu and C. Wong, “Facts applications in preventing loop flows in interconnected systems,” in _Power Engineering Society General Meeting, 2003, IEEE_ , vol. 1, July 2003, pp. –174 Vol. 1.
  * [7] G. Glanzmann and G. Andersson, “Using facts devices to resolve congestions in transmission grids,” in _CIGRE/IEEE PES, 2005. International Symposium_ , Oct 2005, pp. 347–354.
  * [8] C. Rehtanz and U. Hager, “Coordinated wide area control of facts for congestion management,” in _Electric Utility Deregulation and Restructuring and Power Technologies, 2008. DRPT 2008. Third International Conference on_ , April 2008, pp. 130–135.
  * [9] H. Sauvain, M. Lalou, Z. Styczynski, and P. Komarnicki, “Optimal and secure transmission of stochastic load controlled by wacs swiss case,” in _Power and Energy Society General Meeting - Conversion and Delivery of Electrical Energy in the 21st Century, 2008 IEEE_ , July 2008, pp. 1–5.
  * [10] T. Orfanogianni and R. Bacher, “Steady-state optimization in power systems with series facts devices,” _Power Systems, IEEE Transactions on_ , vol. 18, no. 1, pp. 19–26, Feb 2003.
  * [11] W. Feng and G. Shrestha, “Allocation of tcsc devices to optimize total transmission capacity in a competitive power market,” in _Power Engineering Society Winter Meeting, 2001. IEEE_ , vol. 2, 2001, pp. 587–593 vol.2.
  * [12] D. Gotham and G. Heydt, “Power flow control and power flow studies for systems with facts devices,” _Power Systems, IEEE Transactions on_ , vol. 13, no. 1, pp. 60–65, Feb 1998.
  * [13] M. Santiago-Luna and J. Cedeno-Maldonado, “Optimal placement of facts controllers in power systems via evolution strategies,” in _Transmission Distribution Conference and Exposition: Latin America, 2006\. TDC ’06. IEEE/PES_ , Aug 2006, pp. 1–6.
  * [14] S. Gerbex, R. Cherkaoui, and A. Germond, “Optimal location of multi-type facts devices in a power system by means of genetic algorithms,” _Power Systems, IEEE Transactions on_ , vol. 16, no. 3, pp. 537–544, Aug 2001.
  * [15] K. Lee, M. Farsangi, and H. Nezamabadi-pour, “Hybrid of analytical and heuristic techniques for facts devices in transmission systems,” in _Power Engineering Society General Meeting, 2007. IEEE_ , June 2007, pp. 1–8.
  * [16] Q. Wu, Z. Lu, M. Li, and T. Y. Ji, “Optimal placement of facts devices by a group search optimizer with multiple producer,” in _Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on_ , June 2008, pp. 1033–1039.
  * [17] A. Jordehi and J. Jasni, “Approaches for facts optimization problem in power systems,” in _Power Engineering and Optimization Conference (PEDCO) Melaka, Malaysia, 2012 Ieee International_ , June 2012, pp. 355–360.
  * [18] V. Frolov, S. Backhaus, and M. Chertkov, “Reinforcing power grid transmission with facts devices,” _arXiv:1307.1940, preprint_ , 2013.
  * [19] E. Fisher, R. O’Neill, and M. Ferris, “Optimal Transmission Switching,” _IEEE Transactions on Power Systems_ , vol. 23, no. 3, pp. 1346–1355, 2008\.
  * [20] F. Schweppe and D. Rom, “Power system static-state estimation, part ii: Approximate model,” _power apparatus and systems, IEEE transactions on_ , no. 1, pp. 125–130, 1970.
  * [21] K. Lehmann, A. Grastien, and P. Van Hentenryck, “The complexity of switching and facts maximum-potential-flow problems,” in _40th International Workshop on Graph-Theoretic Concepts in Computer Science_ , under review.
  * [22] R. D. Zimmerman, C. E. Murillo-Sanchez, and R. J. Thomas, “MATPOWER: Steady-State Operations, Planning, and Analysis Tools for Power Systems Research and Education,” _IEEE Transactions on Power Systems_ , vol. 26, no. 1, pp. 12–19, 2011. [Online]. Available: ¡Go to ISI¿://000286516100002
  * [23] I. Gurobi Optimization, “Gurobi optimizer reference manual,” 2014. [Online]. Available: http://www.gurobi.com

Karsten Lehmann received Master degrees in Computer Science and Mathematics
from Technische Universität Dresden and is currently a PhD student at NICTA in
the Optimisation Research Group and the Australian National University. He did
a 3 month internship at LANL.
Russell Bent received his PhD in Computer Science from Brown University in
2005 and is currently a staff scientist at LANL in the Energy and
Infrastructure Analysis Group. His publications include deterministic
optimization, optimization under uncertainty, infrastructure modeling and
simulation, constraint programming, algorithms, and simulation. Russell has
published 1 book and over 40 articles in peer-reviewed journals and
conferences in artificial intelligence and operations research.
Feng Pan received his Ph.D. degree in Operations Research from the University
of Texas, Austin, in 2005. His research areas include combinatorial
optimization, stochastic programming, and network modeling. He is a Research
Scientist at Los Alamos National Laboratory, Los Alamos, NM. He has worked on
various projects in transportation security and infrastructure modeling. He is
currently working on optimization and control models in smart grids and is
leading several basic research projects in the areas of developing network
interdiction models and designing robust and resilient infrastructure
networks.

---