From Electrical Power Flows to Unsplittabe Flows: A QPTAS for
OPF with Discrete Demands in Line Distribution Networks

arXiv:1709.05876v1 [cs.DS] 18 Sep 2017

Khaled Elbassioni, Chi-Kin Chau, Majid Khonji∗

Abstract
The AC Optimal Power Flow (OPF) problem is a fundamental problem in power systems
engineering which has been known for decades. It is a notoriously hard problem due mainly
to two reasons: (1) non-convexity of the power flow constraints and (2) the (possible) existence
of discrete power injection constraints. Recently, sufficient conditions were provided for certain
convex relaxations of OPF to be exact in the continuous case, thus allowing one to partially
address the issue of non-convexity. In this paper we make a first step towards addressing the
combinatorial issue. Namely, by establishing a connection to the well-known unsplittable flow
problem (UFP), we are able to generalize known techniques for the latter problem to provide
approximation algorithms for OPF with discrete demands. As an application, we give a quasipolynomial time approximation scheme for OPF in line networks under some mild assumptions
and a single generation source. We believe that this connection can be further leveraged to obtain
approximation algorithms for more general settings, such as multiple generation sources and tree
networks.

1

Introduction

The alternating current (AC) optimal power flow (OPF) problem is a fundamental problem in power
systems engineering which was introduced by Carpentier in 1962 [1, 2], and since then has received
considerable attention (see e.g., [3, 4] for a survey). In its simplest form, we are given an electrical
network represented by an undirected graph, AC generators at some nodes (called buses) and user
power demands at some other nodes. Additionally, edges (called lines) may be associated with
capacities that limit the amount of power that can flow on them. The objective is to minimize
the cost of generation subject to meeting the user demands while satisfying the engineering (e.g.,
line capacity) constraints, and the physical properties of the electrical network captured by the
conservation of power flow (implied by the so-called Kirchhoff laws).
OPF is a notoriously hard problem to solve due mainly to the existence of: (1) non-convex
constraints involving complex-valued entities of power system parameters such as current, voltage
and power, and (2) combinatorial (e.g., discrete power injection) constraints, describing that certain
loads and devices can be either switched on or off. The major bulk of research that dealt with
OPF in the past has been relying on heuristics or on general numerical solvers, which suffer from
the problems of excessive running-time, lack of termination guarantee, or uncertainty of how far the
output solutions deviate from the true optimal solutions [5–10].
Recently, there has been a major progress on tackling OPF using convex relaxations [11–15].
These papers mainly consider radial (i.e., tree) networks and derive sufficient conditions under which
the convex relaxation is exact (i.e., equivalent to the original non-relaxed problem); for example, relaxing the rank-1 constraint in the semidefinite programming (SDP) formulation [11], or relaxing the
equality constraints in the second order cone programming (SOCP) formulation [12–15]. However,
∗
Dept. of Computer Science, Masdar Institute (part of Khalifa University of Science and Technology), Abu Dhabi,
UAE (e-mail: {kelbassioni, mackchau, mkhonji}@masdar.ac.ae).

1

these results yield polynomial time algorithms for OPF with continuous power injection constrains,
i.e., the control of power injection can be partially satisfied (precisely, as fractional control decision variables). In practice, it maybe necessary to consider discrete power injection constrains. For
example, certain loads and devices can be either switched on or off, and hence, the control decision variables are integers. This additional difficulty calls for some techniques from Combinatorial
Optimization.
While OPF is a very well-known problem in the power engineering community, we are not aware
of any work in the TCS community that (directly) considers it (apart form some very simplified
versions [16–21]). In this paper, we observe a connection between the discrete OPF problem and
the well-known unsplittable flow problem (UFP) [22]: given a tree with edge capacities and a set of
paths, each associated with a demand and a utility, the objective is to choose the maximum-utility
subset of paths whose total demand on each edge does not exceed the capacity. This problem has
also received considerable attention and approximation algorithms are known for different variants,
e.g., polylogarithmic-factor approximation algorithms for trees [23], constant-factor approximation
algorithms for trees under the so-called No-Bottleneck assumption [24], constant-factor approximation
algorithms and quasi-polynomial time approximation schemes (QPTASs) for line (or path) graphs
[25–29].
On the hardness side, it was shown in [21] that OPF with discrete demands in a delta network is
hard to approximate within any polynomial guarantees unless P=NP. Consequently, we shall restrict
our attention in this paper to tree topologies. Under this and some other natural assumptions,
we provide a (kind of) black-box reduction that allows one to use a linear programming (LP)-based
approximation algorithm for a generalization of UFP to design an approximation algorithm for
OPF. This multi-dimensional generalization of UFP, which we call d-GUFP, is substantially more
complicated than the standard UFP as it requires the packing of monotone functions of special type
(rather than intervals) within a given capacity function. Hence, known techniques for UFP have to
be extended in a non-trivial way to deal with d-GUFP. As a first step in this direction, we employ
ideas from the QPTAS for UFP on line graphs in [26] to provide a QPTAS for OPF in the case
of a line network. We believe that our reduction can be further leveraged to obtain approximation
algorithms for more general settings, such as multiple generation sources and tree networks.
The rest of this paper is organized as follows. In the next section, we describe the OPF problem,
state our assumptions, and given the SOCP relaxation on which our approximation algorithm will
be based. In Section 3, we give the aforementioned reduction from OPF to a generalization of UFP.
Finally, we introduce an even more general problem called d-GUFP that captures this generalization
of UFP, and show how it can be used to obtain a QPTAS for OPF in line networks in Section 4.

2
2.1

Preliminaries
Optimal Power Flow Problem on Radial Networks

We consider a radial (tree) electric distribution network, represented by a graph T = (V, E). The
set of nodes V = {0, 1, . . . , m} denotes the electric buses, whereas the set of edges E denotes the
distribution lines (see Figure 1). Each line e ∈ E has a (complex) impedance ze ∈ C, with a nonnegative real part representing the resistance of the line (to the flow of current) and imaginary
part representing the reactance (inductance if positive and capacitance if negative). We consider a
simplified model in which a single substation feeder (AC generator) is attached to the root of the tree,
node 0, via a single edge (0, 1). Let V + , V \ {0}. Since T is a tree, |V + | = |E| = m. Let Ti = (Vi , Ei )
be the subtree rooted at node i, and Vi+ , Vi \ {i}. We use the (ordered) pair of subscripts e = (i, j)
as well as e interchangeably to refer to an edge, where we assume that i is the parent of j in T .
For each node j ∈ V + , we are given a set Uj of connected users (called also loads). Let N ,
∪j∈V + Uj be the set of all users, |N | = n. We denote the set of users who reside in the subtree with

2

nodes Vi and Vi+ by Ni and Ni+ , respectively. We denote the unique path from node j to the root
0 by Pj . For each user k ∈ Uj , define Pk , Pj . With a slight abuse of notation, we interchangeably
refer as Pj to the set of edges as well as the set nodes of the path from j to the root. For a user k,
we denote by j(k) ∈ V the node of the tree such that k ∈ Uj(k) .
Among the users, some have inelastic (discrete) power demands, denoted by I ⊆ N . A discrete
demand is either completely satisfied or dropped. An example is an appliance (or an electric vehicle
charger) that is either switched on with a fixed power consumption rate or switched off. The rest of
users, denoted by F , N \I, have elastic demands which can be partially satisfied. A demand for
user k is represented by a complex-valued number sk ∈ C; the real part sR
k represents the so-called
I represents the reactive power; the apparent power is defined
active power while the imaginary
part
s
k
q

I 2
2
as the magnitude |sk | = (sR
k ) + (sk ) of sk . We refer the reader to [30] for a good introduction
to the basics of electrical power systems. Associated with each user k ∈ I is also a number uk ∈ R+
indicating the utility (or profit accrued from) user k if her demand sk is fully satisfied.
Throughout the paper, we write ν R , Re(ν) for the real part and ν I , Im(ν) for the imaginary
part of a given complex number ν ∈ C. We also interchangeably denote a complex number by a
2D-vector as well as a point in the complex plane. In particular, for ν, ν 0 ∈ C, we write ν ≤ ν 0 to
mean ν R ≤ ν 0R and ν I ≤ ν 0I . We use |ν| to denote the magnitude of ν, arg(ν) to denote the phase
angle that ν makes with the real axis, and ν ∗ to denote the complex conjugate of ν.
We consider the optimal power flow (OPF) problem defined by the following mixed integer
programming formulation, known as the (angle-relaxed) Branch Flow Model [31, 32].

Input : v0 ; (v j , v j )j∈V + ; (S e , `e , ze )e∈E ; (sk )k∈N
Output : s0 ; (vj )j∈V + ; (Se , `e )e∈E ; (xk )k∈N
(OPF) max f (s0 , x),
s.t. `i,j =
Si,j =

s0 ,x,v,`,S
|Si,j |2

v
Xi

, ∀(i, j) ∈ E
X
s k xk +
Sj,t + zi,j `i,j , ∀(i, j) ∈ E

k∈Uj

(1)
(2)

t:(j,t)∈E

S0,1 = −s0

(3)
2

vj = vi + |zi,j | `i,j −

∗
2Re(zi,j
Si,j ),
+

∀(i, j) ∈ E

(4)

v j ≤ vj ≤ v j , ∀j ∈ V

(5)

|Se | ≤ S e , | − Se + ze `e | ≤ S e , ∀e ∈ E

(6)

`e ≤ `e ∀e ∈ E
xk ∈ {0, 1}, ∀k ∈ I, xk ∈ [0, 1], ∀k ∈ F

(7)
(8)

vj ∈ R+ , ∀j ∈ V + `e ∈ R+ , Se ∈ C, ∀e ∈ E

(9)

The variables. We assume (without loss of generality1 ) that power flows from the root (node 0) to
the leafs. We use a complex variable Si,j to represent the complex power output at node i along the
edge (i, j). We use vj , |Vj |2 and `e , |Ie |2 to represent the voltage and current magnitude squares at
node j and link e, respectively. Note that the model we consider below is a relaxation for OPF as the
phase angles for the voltages and currents, arg(Vj ) and arg(Ie ), are eliminated from the formulation.
However, it was shown in [33] that for radial networks, this relaxation is exact, that is, it is possible (in
polynomial time) to uniquely recover the phase angles once a solution to the relaxation is obtained.
1

The authors in [14] show that there is a simple bijection between solutions of either orientation.

3

Figure 2: Conservation of power flow at node j.
Figure 1: A radial network.
Finally, we assign a control variable xk to each user demand k ∈ N ; if k ∈ I, then xk ∈ {0, 1},
otherwise, xk ∈ [0, 1] for k ∈ F. Define vectors S , (Se )e∈E , ` , (`e )e∈E , x , (xk )k∈N , v = (vi )i∈V + .
The objective. The goal of the OPF problem is to assign values to the control vector x, complex
power vector S, and current and voltage magnitude vectors ` and v, such that a concave non-negative
objective function2
X
R
uk xk ,
f (s0 , x) = f0 (sR
0 ) + f1 ((sk xk )k∈F ) +
k∈I

is maximized, while satisfying the physical and operating constraints described below.
The constraints. Let v j , v j ∈ R+ be respectively the minimum and maximum allowable voltage
magnitude squares at node j, and S e , `e ∈ R+ be respectively the maximum allowable apparent
power and current magnitude on edge e ∈ E, respectively. We assume the generator voltage v0 ∈ R+
is given. In the above OPF formulation, Eqn. (1) is immediate from the definition of the magnitude
∗ . Eqn. (2) (in complex variables) is the conservation of power
of the complex power Si,j = Vi Ii,j
flow equation at node j (see Figure 2); it enforces that the power output at node i along the edge
(i, j) minus the power lost on P
the line (zi,j `i,j = zi,j |Ii,j |2 ) is equal to the total power consumed by
the loads at node j (namely,
k∈Uj sk xk ) plus the the total power output at the lines going out
P
from j (which is t:(j,t)∈E Sj,t ). Eqn. (3) is the special case of Eqn. (2) applied to node 0 (assuming
an artificial edge (0, 0)), where the demand s0 is negated to indicate power generation (rather than
consumption). Eqn. (4) is a consequence of Ohm’s law: Vi − Vj = zi,j Ii,j , and the definition of power
∗ . The inequalities in (5) and (7) limit the voltage and current magnitudes at each node
Si,j = Vi Ii,j
and on each line, respectively, to the allowable range, while those in (6) upper-bound the apparent
power on each link in both directions by the capacity of the link: |Si,j | ≤ S i,j and |Sj,i | ≤ S i,j , where
2
∗ = −V I ∗ = −(V − z I )I ∗ = −S
Sj,i = Vj Ij,i
i
i,j i,j i,j
i,j + zi,j |Ii,j | .
j i,j
By Opt we denote the objective value of an optimal solution for OPF.
Assumptions.

We shall make the following (natural) assumptions:

2
R
Traditionally, the objective is to minimize the generation cost c(S0,1
), which is typically a non-decreasing convex
R
function of the active generation power S0,1
. In the discrete demand case considered in this paper, we combine the
minimization of the generation cost with the utility maximization of the satisfied demands by using the function
R
R
f (s0 , x), where f0 (sR
0 ) , M − c(S0,1 ) = M − c(−s0 )), for a sufficiently large number M , is a nonnegative concave
R
function, non-decreasing in s0 ).

4

A0: f0 (·) is non-decreasing in sR
0 (as in [12, 13]).
A1: ze ≥ 0 for all e ∈ E, which naturally holds in distribution networks.
A2: v j ≤ v0 ≤ v j for all j ∈ V + . Typically in a distribution network, v0 = 1 (per unit), v j = (.95)2
and v j = (1.05)2 ; in other words, a 5% deviation from the nominal voltage is allowed.
A3: Re(ze∗ sk ) ≥ 0 for all k ∈ N , e ∈ E. Equivalently, the angle difference between ze and sk is at
most π2 .
A4: arg(sk ) − arg(sk0 ) ≤ π2 for any k, k 0 ∈ N . In practical settings, the so-called load power factor
usually varies between 0.8 to 1 [34] and thus the maximum phase angle difference between any
pair of demands is restricted to be in the range of [0, 36◦ ]. We also assume sR
k ≥ 0 for all k ∈ N ,
which always holds in power systems (assuming no power generation at non-root nodes in V + ).
A5: The range of impedances and demands is quasi-polynomial, that is,
(
)
I
max
s
maxe∈E zeR
maxe∈E zeI maxk∈N sR
k∈N k
k
max
,
,
,
= 2polylog(m,n) .
I
mine:zeR >0 zeR mine:zeI >0 zeI mink:sR >0 sR
min
s
I
k:s >0 k
k
k

k

Assumptions A3 and A4 are motivated, from a theoretical point of view, by the inapproximability
results in [21] (if either assumption does not hold, then the problem cannot be approximated within
any polynomial factor unless P=NP; see [35] for details). Assumption A3 also holds in reasonable
practical settings, see [12]. As we will see in the next section, by performing an axis rotation, we may
assume by A4 that sk ≥ 0. Clearly, under this and assumption A1, the reverse power constraint in (6)
is implied by the forward power constraint (|Se | ≤ S e ). It will also be seen that under assumptions
A1, A2 and A3, the voltage upper bounds in (5) can be dropped. Assumption A5 is only needed for
the running time analysis of the QPTAS and may possibly be removed using techniques from [27].

2.2

Rotational Invariance of OPF

The following simple lemma states that if we rotate all complex quantities (namely, ze , sk ) by a
fixed angle, the OPF problem’s structure remains the same. This property allows us to replace
assumptions A0 and A4 by the following assumptions:
I
R I
A00 : f0 (sR
0 cos φ + s0 sin φ) is non-decreasing in s0 , s0 .

A40 : sk ≥ 0 for all k ∈ N .
Note that A1 and A40 already imply A3.
Lemma 2.1. Assume A4 and suppose that sk , for all k ∈ N , and ze , for all e ∈ E, are rotated by
an angle φ , min{maxk∈N − arg(sk ), 0} ∈ [0, π2 ]. Denote the resulting OPF problem by OPFφ :
(OPFφ )

max

s0 ,x,v,`,S

f (s0 e−iφ , x),

s.t. (1) − (9), with ze replaced by ze eiφ , and sk replaced by sk eiφ .
Then OPFφ is equivalent to OPF and satisfies assumptions A00 , A1, A2, A3 and A40 .
Proof. One can easily show that a feasible solution F = (s0 , x, v, `, S) of (OPFφ ) can be converted
to a feasible solution F̄¯ = (s̄¯0 , x, v, `, S̄¯) to OPF, such that S̄¯i,j , Si,j e−iφ , s̄¯0 , s0 e−iφ are rotated
by φ, and vise versa. Moreover, the two objective functions are equal. It is immediate to see that
assumptions A00 A1, A2, A3, and A40 hold for OPFφ .
From now on, we consider the rotated problem which we simply denote by OPT.
5

2.3

Exact Second Order Cone Relaxations

Note that the feasible set for OPF is non-convex due to the quadratic equality constraint (1).
|S |2
Replacing this constraint by `i,j ≥ i,j
vi , one obtains an SOCP relaxation of OPF, denoted by
cOPF:
(cOPF)

max

s0 ,x,v,`,S

f (s0 , x),

s.t. (2) − (9),
|Si,j |2
, ∀(i, j) ∈ E.
(10)
vi
We denote the relaxation of cOPF, where the integrality constraints in (8) are replaced by xk ∈ [0, 1]
for all k ∈ N , by rcOPF. For a given x̂ ∈ [0, 1]n , we denote by cOPF[x̂] the restriction of cOPF
where we set x = x̂.
Recent results [12–15] present sufficient conditions for cOPF to have an optimal solution in
which Cons. (10) holds with equality. For our purposes, we use the following result which is a
slightly simplified version of that in [12].
`i,j ≥

Lemma 2.2. Under assumptions A0, A1, A2, and A3, for any given x0 ∈ [0, 1]n , there exists an
optimal solution F 0 = (s00 , x0 , v 0 , `0 , S 0 ) of cOPF[x0 ] that satisfies `i,j =
a solution can be found in polynomial time.

0 |2
|Si,j
vi0

for all (i, j) ∈ E. Such

Proof. The proof follows essentially the same lines as in [12–15]; we sketch it here for completeness.
Let F 00 = (s000 , x0 , v 00 , `00 , S 00 ) be an optimal solution of cOPF[x0 ], which can be found (to within any
desired accuracy) in polynomial time, by solving a convex program. Next, we consider the following
convex program.
X
(cOPF0 [x0 ]) min
`e ,
s0 ,x,v,`,S

e∈E

s.t. (2) − (7), (9), (10)
x = x0
f (s0 , x) ≥ f (s000 , x0 ).

(11)
(12)

Clearly, cOPF0 [x0 ] is feasible as F 00 satisfies all its constraints. Hence, it has an optimal solution
F 0 = (s00 , x0 , v 0 , `0 , S 0 ), which we claim to satisfy the statement of the lemma. Suppose, for the sake of
|S 0 |2

contradiction, that there exists an edge (h, t) such that `0h,t > vh,t0 . We construct a feasible solution
h
P
0
˜ S̃) for cOPF0 [x0 ] such that P
˜
F̃ = (s̃0 , x0 , ṽ, `,
e∈E `e <
e∈E `e , leading to a contradiction.
We apply the forward-backward sweep algorithm, illustrated in Alg. 1 below, on the solution F 0
to obtain a feasible solution F̃ . To complete the proof, we show the feasibility of F̃ in Appendix A.

3

From Optimal Power Flows to Unsplittable Flows

In the following we show how to use an LP-rounding approximation algorithm for a generalization of
the unsplittable flow problem, to obtain an approximation algorithm for OPF. It is important to note
here that an approximation algorithm that is not based on LP-rounding may not be useful in this
lemma. For instance, it is known that for UFP on line graphs, where all intervals start from the root,
there is an FPTAS based on dynamic programming [36], while the natural LP has a non-constant

6

Algorithm 1 Forward-Backward-Sweep
|S 0 |2

Input: A feasible solution F 0 = (s00 , x0 , v 0 , `0 , S 0 ) to cOPF0 [x0 ] such that `0h,t > vh,t0 for some
h
(h, t) ∈ E
˜ S̃) to cOPF0 [x0 ] such that x̃ = x0 and P
˜
Output:
A
feasible
solution
F̃
=
(s̃
,
x̃,
ṽ,
`,
0
e∈E `e <
P
0
e∈E `e
1: x̃ ← x0 ; ṽ0 ← v0
2: Number nodes V = {0, 1, . . . , m} in a breadth-first search order
3: for j = m, m − 1, . . . , 1 do /* Forward sweep */
4:
Let i be s.t. (i, j) ∈ E
|S 0 |2
5:
`˜i,j ← i,j
v0
Pi
P
6:
S̃i,j ← k∈Nj sk x̃k + t:(j,t)∈E S̃j,t + zi,j `˜i,j
7:
8:
9:
10:

s̃0 ← −S̃0,1
for j = 1, 2, . . . , m do /* Backward sweep */
Let i be s.t. (i, j) ∈ E
∗ S̃ )
ṽj ← ṽi + |zi,j |2 `˜i,j − 2Re(zi,j
i,j

11:

return F̃

integrality gap [37]. Thus, when considering line networks in the next section, we have to use on a
more complicated LP for d-GUFP, that is guaranteed to have a small integrality gap.

Lemma 3.1. Let F 0 = s00 , x0 , v 0 , `0 , S 0 be a feasible solution for rcOPF. Let x̄ ∈ [0, 1]N be such
that
X
X
uk x̄k ≥
uk x0k − εf (s00 , x0 ), for some ε ∈ [0, 1]
(13)
k∈I

X
k∈N

Re



X

k∈I



∗
sk x̄k ≤
zh,t

(h,t)∈Pk ∩Pj

X


Re

sR
k x̄k ≤

k∈Nj

∀(i, j) ∈ E,

(14)

0
sR
k xk

∀(i, j) ∈ E,

(15)

sIk x0k

∀(i, j) ∈ E,

(16)

k∈Nj

k∈Nj

X

X


∗
sk x0k
zh,t

(h,t)∈Pk ∩Pj

k∈N

X

X

sIk x̄k ≤

X
k∈Nj

x̄k = x0k

∀k ∈ F.

(17)

Then, under assumptions A00 , A1, A2, and A3 and A40 , rcOPF[x̄] has a feasible solution F̃ =
˜ S̃ such that f (s̃0 , x̃) ≥ (1 − ε)f (s0 , x0 ).
s̃0 , x̃, ṽ, `,
0
Proof. The argument is similar to that used in the proof of Lemma 2.2. We apply a slightly modified
version of the forward-backward sweep algorithm Alg. 1 in Section 2.3, on the solution F 0 to obtain
a feasible solution F̃ . We replace steps 1 and 5 in Alg. 1, respectively, by:
1: x̃ ← x̄; ṽ0 ← v0 , and 5: `˜i,j ← `0 .
(18)
i,j

By Steps 6, 7 and 10 of the (modified) algorithm, all equality constraints of (rcOPFφ [x̄]) are
satisfied. By (modified) Step 5 and the feasibility of F 0 , we also have
`˜e = `0e ≤ `e for all e ∈ E.
(19)
P
P
Write ∆Se , S̃e − Se0 , and ∆|Se |2 , |S̃e |2 − |Se0 |2 , for e ∈ E. Let Sj0 , k∈Nj sk x0k , S̃j , k∈Nj sk x̃k ,
P
and L̃i,j ,
ze `˜e . Note by (62) that S̃i,j = S̃j + L̃i,j and, S 0 = S 0 + L̃i,j . It follows that,
e∈Ej ∪{(i,j)}

i,j

7

j

for all (i, j) ∈ E,
∆Si,j = S̃j − Sj0 =

X

sk x̄k −

k∈Nj

X

sk x0k ≤ 0,

(20)

k∈Nj

where the inequality follows from (15) and (16). In particular, for (i, j) = (0, 1), we obtain
R
0R
0R
s̃R
0 = −S̃0,1 ≥ −S0,1 = s0 ,

(21)

I
0R
0I
implying by A00 that f0 (s̃R
0 cos φ + s̃0 sin φ) ≥ f0 (s0 cos φ + s0 sin φ)) and hence f (s̃0 , x̃) ≥ (1 −
ε)f (s00 , x0 ) follows from (13) and (17).
Furthermore,
0 2
∆|Si,j |2 = |S̃i,j |2 − |Si,j
|
R 2
0R 2
I 2
0I 2
= (S̃i,j
) − (Si,j
) + (S̃i,j
) − (Si,j
)
R
R
0R
I
I
0I
= ∆Si,j
(S̃i,j
+ Si,j
) + ∆Si,j
(S̃i,j
+ Si,j
)
R
I
I
0I
I
= ∆Si,j
(S̃jR + Sj0R + 2L̃R
i,j ) + ∆Si,j (S̃j + Sj + 2L̃i,j ) ≤ 0,

where the last Inequality follows by A1, A40 and (20). Therefore,
0
|S̃i,j | ≤ |Si,j
| ≤ S i,j .

(22)

Next, we show v j ≤ ṽj ≤ v j . As in (71), we rewrite Cons. (4) by recursively substituting
j moving away from the root, and then substituting for S̃h,t using (62):

 X

X
X
X 
X

∗
∗
Re zh,t
ze `0e +
|zh,t |2 `0h,t
vj0 = v0 − 2
Re
zh,t
sk x0k − 2
k∈N

(h,t)∈Pk ∩Pj

e∈Et

(h,t)∈Pj

vj0 ,

for

(23)

(h,t)∈Pj

˜ respectively.
A similar equation can be derived for ṽj , where x0 and `0 in (23) are replaced by x̃ and `,
By assumptions A2 and A3, we have

 X

X
X
X
X 

∗
∗
Re zh,t
ze `˜e +
zh,t
sk x̃k − 2
|zh,t |2 `˜h,t ≤ v0 < v j .
ṽj = v0 − 2
Re
(h,t)∈Pk ∩Pj

k∈N

e∈Et

(h,t)∈Pj

(h,t)∈Pj

Moreover, since `˜e = `0e and x̃ = x̄ satisfies (14), we get by A1 and the feasibility of F 0 ,

 X

X
X
X
X 

∗
ze `0e +
|zh,t |2 `0h,t = vj0 ≥ v j .
Re zh,t
sk x0k − 2
ṽj ≥ v0 − 2
Re
zh,t
(h,t)∈Pk ∩Pj

k∈N

e∈Et

(h,t)∈Pj

(h,t)∈Pj

(24)
Finally, by Inqs. (22) and (24), `˜i,j = `0i,j =

0 |2
|Si,j
vi0

≥

|S̃i,j |2
ṽi ,

hence `˜i,j satisfies Cons. (10).

Remark 1. If the voltage lower bound v j is a non-decreasing function in j (as j moves away from
the root), we can replace (14) by a simpler inequality:
X

ρk,j x̄k ≤ cj

∀ leaf j ∈ V,

(25)

k∈I

P


 P

 P
P
∗
0
2 0
where ρk,j , Re
(h,t)∈Pk ∩Pj zh,t sk and cj , v0 −v j − 2
(h,t)∈Pj Re zh,t
e∈Et ze `e + (h,t)∈Pj |zh,t | `h,t −
P
k∈F ρk,j x̄k . In the line network case, (25) reduces to a single Knapsack inequality that, together
with (15) and (16), provides a 3-dimensional generalization of UFP on a line, where all intervals
start from the same point in each dimension. In the tree case, (25) is a packing integer program [38],
where the demands ρk,j have a special structure.

8

4
4.1

A QPTAS for OPF on a Line Network
A Multi-dimensional Generalization of UFP

Let d ∈ Z+ be a fixed positive integer. We define d-GUFP to be the following problem. Given a line
network G = (V, E), with root 0, we assume that the edges are, ordered by distance from the root
e1 < e2 . . . < en , where ei = (i − 1, i). Given a set of users I, we assume that each user demand is
given by a d-dimensional vector fk = (fk1 , . . . , fkd ), where for each r, fkr : E → R+ are either monotone
non-increasing or monotone non-decreasing step functions over the set of edges. (For example fkr
is monotone non-decreasing if fkr (e) ≤ fkr (e0 ) whenever e ≤ e0 .) For convenience of presentation,
we assume without loss of generality below (by reversing the order on E if necessary) that fkr (·) is
monotone non-decreasing for all k, r.
As before user k has utility uk ≥ 0. Each edge e ∈ E is associated with a d-dimensional capacity
vector c = (c1 , . . . , cd ), where cr : E → R+ is a monotone non-decreasing function on E. The objective
is to select the maximum-utility subset of users (we assume temporarily that all users are inelastic,
N = I) such that the total demand on each edge satisfies the capacity constraint in each dimension:
(d-GUFP[I, c])
X

s.t.

max
xk

fkr (e)xk ≤ cr (e),

X

uk xk ,

k∈I

∀ e ∈ E,

∀ r ∈ [d]

(26)

k∈I

xk ∈ {0, 1},

∀k ∈ I

(27)

Assumptions on fkr (·). We will make the following separability assumption on the function fkr (·).
We assume that we are given positive integers T1 , . . . , Tr and monotone (non-decreasing) functions
b(r,t) : E → R+ , for t = 1, . . . , Tr and r ∈ [d]. For each k ∈ N , we also assume that are given
(r,t)
non-negative numbers ak ∈ R+ and edges erk , êrk ∈ E, for t = 1, . . . , Tr . We assume that fkr (·) takes
the following form

if e < erk ,
T
 0
X
(r,t) (r,t)
(r,t)
r
(r,t)
b (e)
if erk ≤ e < êrk ,
ak b̃k (e), where b̃k (e) =
(28)
fk (e) =
 (r,t) r
t=1
b (êk ) otherwise.
We shall make use of the following simple lemma which essentially states that we can partition
the line into logarithmic number of regions such that, for each user k, the function fk (·) is roughly
constant in each region.
Lemma 4.1. For any Cr > 1, r ∈ [d], E can be partitioned along each coordinate r ∈ [d] into Pr
S r r
intervals E r = Pp=1
Ep , where Epr := {ei(p,r) , ei(p,r)+1 , . . . , ei(p,r) }, and
· · · < ei(p−1,r) < ei(p,r) < ei(p,r)+1 · · · < ei(p,r) < ei(p+1,r) < · · · ,
with the following property:
p,r

f k ≤ Cr · f p,r
,
k

(r,t) (e), br
t∈[Tr ]: b(r,t) (e)>0 b
maxe∈Epr fkr (e) = fkr (ei(p,r) ).

where br := mine∈E,
p,r

and f k :=

∀k ∈ N , ∀p ∈ [Pr ], ∀r ∈ [d],
:= maxe∈E,

(r,t) (e)
t∈[Tr ] b

(29)

= b(r,t) (en ), f p,r
:= mine∈Epr :
k

r
fkr (e)>0 fk (e)

Proof. Fix r ∈ [d]. For t ∈ [Tr ], let j t,1 ∈ V be the smallest index such that br,t ((j t,1 , j t,1 + 1)) > 0,
0
and for `0 = 2, 3, . . . , let j t,` ∈ V, be the smallest index such that
0

0

0

0

br,t ((j t,` , j t,` + 1)) > Cr · br,t ((j t,` −1 , j t,` −1 + 1)).

9

(30)

Let `0 be the largest index for which (30) is possible (if no such index exists, we are done with Pr = 1),
and set `t := `0 + 1 and j t,`t := m. Note that (30) implies that br,t (en ) > Cr`t −1 · br,t ((j t,1 , j t,1 + 1))
which implies in turn that
`t ≤ logCr

r
br,t (en )
b 
≤
log
,
Cr
br,t ((j t,1 , j t,1 + 1))
br

(31)

Moreover, (30) implies
br,t ((j − 1, j))
0
0
≤ Cr , ∀j, j 0 ∈ {j t,` + 1, . . . , j t,` +1 }, ∀`0 = 2, . . . , `t − 1.
(32)
br,t ((j 0 − 1, j 0 ))
S
P r
0
The set t∈[Tr ] {j t,` : `0 ∈ [`t ]} ⊆ V defines a partition of E into Pr ≤ Tt=1
(`t − 1) intervals
r
r
E1 , . . . , EPr . By (31),
r

b 
Pr < Tr logCr r .
(33)
b
Consider any interval Epr := {ei(1,p) , ei(1,p)+1 , . . . , ei(1,p) } in the partition. Then by (28) and (32), for
any e, e0 ∈ Epr , we have
b̃r,t (e) ≤ Cr · b̃r,t (e0 ),

whenever e0 ≥ erk

and thus, it follows form (28) that, whenever fkr (e0 ) > 0 (and hence e0 ≥ erk ), we have
fkr (e) =

Tr
X

(r,t) (r,t)
b̃k (e)

ak

≤

t=1

Tr
X

(r,t)

ak

(r,t)

Cr b̃k

(e0 ) ≤ Cr fkr (e0 ),

t=1

as required by (29).
Discretizing the instance. Let umax := maxk∈I uk and  ∈ (0, 1) be a given constant. Define
Î := {k ∈ I : uk ≥ umax
instance, where Opt
n }, where n := |N |. Note that umax ≤ Opt for a feasible
P
is the value of an optimal solution for (d-GUFP[I, c]). It follows that k∈I\Î uk ≤ umax ≤ Opt
P
and hence, k∈Î uk ≥ (1 − )Opt.
r
For k ∈ Î and r ∈ [d], let f rk := mine: fkr (e)>0 fkr (e), f k := maxe fkr (e) = fkr (en ), f r := mink f rk and
l
rm
r
r
f := maxk f k . We consider discrete levels of function values: for l = −∞, 0, 1, 2, . . . , log(1+) nf
r
f
l
rm
nf
r
l
r
r
r
r
let Fl := (1 + ) f , and F := {Fl : l = −∞, 0, 1, 2, . . . , log(1+) f r }. Let F := maxr∈[d] F .
Partitioning the instance. For each r ∈ [d], we assume the partition of E guaranteed by
r,t
r,t
r
Lemma 4.1, and let ar := mink∈Î, t∈[Tr ]: ar,t >0 ar,t
k and a := maxk∈Î, t∈[Tr ] ak . Note that if ak > 0
k

and k ∈ Î then
uk
umax
umax
≤ r,t ≤ r .
nar
a
ak
l
m
Q
Q r
r
We partition the users in Î into Q := dr=1 Tt=1
Qr,t groups, where Qr,t := log na
ar + 1:
I q = {k ∈ Î : 2qr,t −1 L ≤

for q = (qr,t

uk

< 2qr,t L for all t ∈ [Tr ], r ∈ [d]},
ar,t
k
Qd QTr
: t ∈ [Tr ], r ∈ [d]) ∈ Q := r=1 t=1 {1, . . . , Qt,r − 1, ∞}, where3 L :=
Pd

Q := maxt,r Qr,t ,. Then Q ≤ Q
3

r=1 Tr

(34)
umax
nar .

.

For convenience, we assume in (34) that the strict inequality is replaced by an inequality when ar,t
k = 0.

10

Let

Figure 3: A profile and its (h, )-restriction.
Structure of the optimal solution. Consider an optimal solution x∗ to (d-GUFP[I, c]). For
P
q ∈ Q, let T ∗ = {k ∈ Î : x∗k = 1}, Then (f ∗ )q,r (e) := k∈T ∗ ∩I q fkr (e), for r ∈ [d], defines a monotone
non-decreasing function on E. We call such a function a “profile” defined by the optimal solution in
group I q . For p ∈ [Pr ], let (h∗ )q,p,r = maxe∈Epr (f ∗ )q,r (e) be the peak demand defined by the optimal
solution (from group q) within the interval Epr .
For q ∈ Q, let (L∗ )q := {k ∈ I q ∩ T ∗ : f p,r
> 2 (h∗ )q,p,r for some p ∈ [Pr ], r ∈ [d]} be the set of
k
“large” demands within group I q in the optimal solution, and let S q := I q ∩ T ∗ \ (L∗ )q be the set of
“small” demands within the same group. Note that, by definition of (h∗ )q,p,r and the monotonicity
of fkr (·), there cannot be more than 12 demands k in I q ∩ T ∗ such that f p,r
> 2 (h∗ )q,p,r , and hence
k
Pd

P

r
|(L∗ )q | ≤ r=1
. The situation with small demands is more complicated as there can be many of
2
them in the optimal solution. However, with a small loss in the objective value, we can restrict the
profile defined by such small demands into one that admits a small description. This motivates the
following definition (generalizing the one in [26]).

Definition 4.2. ((h, )-restricted profile) Let  > 0 be such that 1/ ∈ Z+ . For r ∈ [d] and p ∈ [Pr ],
let h = (hp,r )p∈[Pr ], r∈[d] be a given vector of numbers such that hp,r ∈ F r and hp,r ≥ hp−1,r , for all
p = 2, . . . , Pr and r ∈ [d]. An (h, )-restricted profile g = (g r )r∈[d] is vector of monotone functions
g r : E → R+ such that
g r (e) ∈ {lhp,r : l ∈ {0, 1 . . . , 1/}, p ∈ [Pr ]}.
Pd

The total number of (h, )-restricted profiles is at most m
For q ∈ Q and for p ∈ [Pr ], define
H q,p,r :=

r=1

Tr r,t
X
b (ei(p,r) )
t=1

2qr,t L

.

Pr / .

(35)

Note that
q
r
∀p ∈ [Pr ] : H q,p,r > 0 ⇔ ∃t ∈ [Tr ] : qr,t 6= ∞ ⇔ ∀k ∈ I q ∃t ∈ [Tr ] : ar,t
k > 0 ⇔ ∀k ∈ I : fk (en ) > 0.
(36)
Pd

P

Let Hq := {r ∈ [d] : H q,Pr ,r > 0}, and α := P r=1q Prr . We assume Hq 6= ∅ since otherwise, fkr (en ) = 0
r∈H
for all k ∈ I q and hence we can take all users in I q in the solution without affecting the constraints.
We extend two lemmas from [26] as follows.
11

Lemma 4.3. Fix q ∈ Q and  ∈ (0, 1). Let S q ⊆ I q be a set of demands within group q such
that f p,r
≤ B p,q,r for all k ∈ S q , p ∈ [Pr ], r ∈ [d], and some numbers B p,q,r ∈ R+ . Let hq =
k
(hq,p,r )p∈[Pr ], r∈[d] be a given vector of numbers such that hq,p,r ∈ F r and hq,p,r ≥ hq,p−1,r , for all
q
p = 2, . . . , Pr and r ∈ [d], and (x̃k )k∈[S q ] ∈ [0, 1]S be such that
X p,r
f k x̃k ≤ (1 + )hq,p,,r , ∀p ∈ [Pr ], ∀r ∈ [d].
(37)
k∈S q
q

Then we can find in polynomial time an integral vector (x̂k )k∈S q ∈ {0, 1}S and an (hq , )-restricted
q , such that
profile gP
P
(i) k∈S q fkr (e)x̂k ≤ g q,r (e) ≤ k∈S q fkr (e)x̃
Pk for all e ∈ E, r ∈ [d], and

P
P
P
Pr
Cr
αPr B q,Pr ,r
q,p,r
q,p,r
+B
) + H q,Pr ,r .
(ii) k∈S q uk x̂k ≥ k∈S q uk x̃k − r∈Hq
p=1 H q,p,r (h
The above lemma essentially sates that, when all demands are small, we can round a given
fractional solution x̃ for d-GUFP, to an integral solution x̂ that fits within a capacity profile with a
small description, losing only a small part of the utility of x̃.
P
Proof. For r ∈ [d], consider the graph of the fractional profile k∈S q fkr (e)x̃k shown in Figure 3. For
p ∈ [Pr ], slice the region between the horizontal axis and horizontal line at height hq,p,r with 1 + 1
horizontal lines, with inter-distance hq,p,r . The intersections of the optimal profile with these lines
define a monotone function g q,r , as shown in Figure 3, with g q,r (e) ∈ {lhp,r : l ∈ {0, 1 . . . , 1/}, p ∈
[Pr ]}, for all e ∈ E. We use the greedy procedure shown in Algorithm 2 below to remove a set
of demands from S q in each interval Epr such that the remaining set of demands fractionally fits
below g q,r (see lines 2-9). This works essentially by removing the “left-most” set of demands that
minimally ensures that the remaining demands in S q can be packed under capacity g q,r . This defines
¯ for (d-GUFP-R[S q , g q ]), where g q = (g q,r )r∈[d] , which can be
an intermediate fractional vector x̄
converted to a basic feasible solution (BFS) with the same or better objective value. We finally
¯ to obtain an integral solution x̂.
round down the fractional components of x̄
We first show that condition (i) holds when x̂ is replaced by x̄. For r ∈ [d], let J r (ei ) be the set
of demands k ∈ S q forP
which x̄k was set to 0 in step 7 when
P considering edge ei ∈ E. Consider an
edge e ∈ Epr such that k∈S q fkr (e)x̄k > 0. Note that 0 ≤ k∈S q fkr (e)x̃k − g q,r (e) ≤ hq,p,r by (37)
and the definition of g q,r . By the monotonicity of fkr (·) and the condition of the while-loop in step 5
we have
X
X
X
X
fkr (e)x̄k =
fkr (e)x̃k −
fkr (e)x̃k
k∈S q

k∈S q

≤

X

i: ei ≤e k∈J r (ei )

fkr (e)x̃k −

k∈S q

≤

X

X

X

fkr (ei )x̃k

i: ei ≤e k∈J r (ei )

fkr (e)x̃k − hq,p,r

k∈S q
q,r

≤g

(e).

q q
¯
Since x̄ is feasibleP
for (d-GUFP-R[S
P , g ]), we can obtain a basic feasible solution x̄ for the same
¯k ≥ k∈S uk x̄k as in step 10 of procedure Modify. Finally we round
linear program with k∈S q uk x̄
¯ to obtain an integral solution x̂. Note that, for all e ∈ E,
down the fractional components in x̄
X
X
X
¯k ≤ g q,r (e) ≤
fkr (e)x̂k ≤
fkr (e)x̄
fkr (e)x̃k ,
k∈S q

k∈S q

k∈S q

and hence (i) holds.

12

Note that the total fractional utility of demands removed by Algorithm 2 in steps 2-9 is
X

X

r∈[d], e∈E k∈J r (e)

r∈[d]:

≤

Pr X
X

X

uk x̃k =

H Pr ,r >0

1

X

r∈Hq p=1 e∈Epr k∈J r (e)

=

X

r∈Hq p=1

uk x̃k

p=1 e∈Epr k∈J r (e)

Pr X
X X

Pr
X

X

1
H q,p,r

X

H q,p,r
X

Tr
X

r,t
ar,t
k b (ei(p,r) )x̃k

t=1

fkr (ei(p,r) )x̃k

e∈Epr k∈J r (e)



Pr
X X
X
X
Cr 
fkr (e)x̃k 
≤
q,p,r
H
r
q
r
r∈H p=1

≤

e∈Ep k∈J (e)

Pr
X X
Cr
(hq,p,r + B q,p,r ),
q,p,r
H
q

r∈H 0 p=1

where we use the fact that k ∈ I q in the first inequality, property (29) in the second inequality, and
f p,r
≤ B q,p,r and the condition of the while-loop in step 5 in the last inequality. (Note that we sum
k
above over r ∈ [d] such that in H q,Pr ,r > 0 since k ∈ J r (e) implies that fkr (e) > 0, which in turn
implies by (36) that H q,Pr ,r > 0.)
It follows that
Pr
X
X X
X
X
X X
Cr
uk x̄k ≥
uk x̃k −
uk x̃k ≥
uk x̃k −
(hq,p,r + B q,p,r ).
(38)
q,p,r
H
q
q
q
q
r
r,e
k∈S

k∈S

k∈S

k∈J (e)

r∈H p=1

P
By the monotonicity of the functions fkr (·), (d-GUFP-R[S, g q ]) has only 1 dr=1 Pr non-redundant
¯ computed in step 10 has at most
packing inequalities of the form (26). It follows that the BFS x̄
1 Pd
¯
r=1 Pr fractional components x̄ ∈ (0, 1). Thus,

d

X
k∈S q

uk x̂k =

X
k∈S q

¯k −
uk x̄

X
k∈S q :

¯k ≥
uk x̄

X

uk x̄k −

k∈S q

¯k ∈(0,1)
x̄

1X
¯k
Pr · max uk x̄
k

r=1

Pd
X
Pr X Pr B q,Pr ,r
1
,
≥
uk x̄k − P r=1
 r∈Hq Pr
H q,Pr ,r
q
q
k∈S

r∈H

¯k ≤ 1 and
where we use in the last inequality that x̄
P
PPr r,t r,t
P
r
q,Pr ,r
q,Pr ,r
q Pr f (en )/H
r∈Hq Pr
t=1 ak b (en )/H
P
uk ≤
= r∈H P k
r∈Hq Pr
r∈Hq Pr
P
q,P
,r
q,P
,r
r
r
/H
q Pr B
≤ r∈H P
,
r∈Hq Pr
for k ∈ S q . Condition (ii) follows from (38) and (39).

13

(39)

(40)

Algorithm 2 Modify
Input: q ∈ Q; a restricted profile RP (h; w; g); a set of users S q ⊆ I q ; a fractional vector (x̃k )k∈S q ∈
q
[0, 1]S
q
Output: A integral vector (x̂k )k∈S q ∈ {0, 1}S satisfying conditions (i) and (ii) of lemma 4.3
1: x̄ ← x̃; t ← 0
2: for r = 1 to d do
3:
for p = 1, . . . , Pr do
4:
i ← i(p, r)
5:
while t < hq,p,r do
6:
if ∃k ∈ S q such that x̃k fkr (ei ) > 0 then
7:
x̄k = 0
8:
t ← t + x̃k fkr (ei )
9:
else i ← i + 1
P
P
q
¯
¯
10: Convert x̄ to a BFS
 x̄ for (d-GUFP-R[S, g ]) with k∈S uk x̄k ≥ k∈S uk x̄k
¯k c
11: (x̂k )k∈S q ← bx̄
k∈S q
12: return x̂

4.2

OPF on a Line Network

In the case of a line network, we can reduce the OPF problem to (d-GUFP[I, c]) with d = 3. For
k ∈ I and e = (i, j) ∈ E, define
 I
 R

 X
sk if k ∈ Nj
sk if k ∈ Nj
3
∗
2
1
fk (e) =
fk (e) = Re
ze0 sk , fk (e) =
0
otherwise.
0
otherwise,
0
e ∈Pk ∩Pj

is monotone non-decreasing on E when ordered by distance of the root, while fk2 and fk3
Note that
monotone non-decreasing if we consider the reverse order on E. We show that these functions can be
2
2
R
written in th form (28). For r = 2 (similarly, for r = 3), we set T2 = 1, a2,1
k := sk , ek = êk := ej(k) ,
2,1
b (e) := 1. Now consider r = 1. Note that, for e = (i, j) ∈ E,
 X

 X

fk1 (e) =
Re(ze0 ) Re(sk ) +
Im(ze0 ) Im(sk ).
(41)
fk1

e0 ∈Pk ∩Pj

e0 ∈Pk ∩Pj

P
1,2
1,1
1
1
Thus, setting T1 = 2, a1,1
e0 ∈Pj Re(ze0 )
k := Re(sk ), ak := Im(sk ), ek := e1 , êk := ej(k) , b̃ ((i, j)) :=
P
1,2
1
and b̃ ((i, j)) := e0 ∈Pj Im(ze0 ) we can write fk (e) in the form (28).
Our QPTAS proceeds as follows. By Lemma 3.1, if there is a feasible solution for (cOPF) with
xk = 1 for some k ∈ I, then there is a feasible solution with xk = 1 and xk0 = 0 for all k 0 ∈ I.
This implies that Opt ≥ umax and hence by restricting the set of inelastic demands to Î (defined
in Section 4.1) we lose only a value of at most Opt from the optimal solution. We discretize the
instance and partition the users in Î into Q groups (I q )q∈Q , as described in Section 4.1. We also
partition E into intervals E r satisfying assumption (29), as per Lemma 4.1 (with Cr = 2).
Then for each group q ∈ Q, we guess the set of large demands Lq ⊆ I q in the optimal solution,
and the peaks hq,p,r , within 1 + , of the small demands in the optimal solution within the interval
Epr . Let L = (Lq )q∈Q and hq = (hq,p,r )p∈[Pr ], r∈[d] where hq,p,r ∈ F r . Define a restrictive version of
rcOPF, denoted by rcOPF[L, h], which enforces that xk = 1 for all k ∈ Lq and q ∈ Q and that
the peak total contribution of the small demands in group q within the interval Epr is at most hq,p,r :
P
p,r
q,p,r . Here, the set of small demands within group q ∈ Q is defined as
k∈S q f k xk ≤ (1 + )h
n
o
q,p,r
S q := k ∈ I q : f p,r
≤
B
for
all
p
∈
[P
],
r
∈
[d]
,
(42)
r
k
h
i
P
p,r
where B q,p,r := 2 hq,p,r + k∈Lq f k .
14

(rcOPF[L, h])

max f (s0 , x),

s0 ,x,v,`,S

s.t. (2) − (7), (9), (10)
X p,r
f k xk ≤ hq,p,r , ∀p ∈ [Pr ], ∀r ∈ [d], ∀q ∈ Q

(43)
(44)

k∈S q

[

(Lq ∪ S q )

(45)

∀k ∈ Lq , ∀q ∈ Q
[
xk ∈ [0, 1], ∀k ∈ F ∪ (
S q ).

(46)

xk = 0,

∀k ∈ I \

q∈Q

xk = 1,

(47)

q∈Q


Given a feasible solution F 0 = s00 , x0 , v 0 , `0 , S 0 to rcOPF[L, h], we apply Lemma 4.3 with x̃ = x0 .
By the lemma, we can find (in polynomial time) an integral solution x̂ satisfying conditions (i) and
(ii). Next, we recalculate s0 , S, `, v using the program cOPF[x̄] given in Section 2.3, and then apply
Lemma 2.2 to obtain a feasible solution to OPF.
We formally state our QPTAS in Alg. 3 below.
Algorithm 3 QPTAS
Input: An approximation parameter  ∈ (0, 1); OPF input v0 ; (v j , v j )j∈V + ; (S e , `e , ze )e∈E
Output: A solution F̂ to OPF such that f (F̂ ) ≥ (1 − O())Opt
1: for each selection (L = (Lq )q∈Q , h = (hq = (hq,p,r )p∈[Pr ], r∈[d] ))q∈Q ) such that Lq ⊆ I, |Lq | ≤
Pd

2:
3:
4:
5:
6:
7:

8:
9:
10:
11:
12:
13:

Pr

and hq,p,r ∈ F r do
if rcOPF[L, h] is feasible then
F 0 ← Solution of rcOPF[L, h]
for q ∈ Q do
Let S q be given by (42)
for every (h, )-restricted profile g q do
(x̂k )k∈S q ← Integral vector returned by applying Lemma 4.3 with vector hq , and
(x̃k )k∈S q = (x0 )k∈S q
S
x̂k if k ∈ q∈Q S q ,
S
x̄k ←
x0k if k ∈ N \ ( q∈Q S q )
F̃ ← Solution of cOPF[x̄]
if f (F̃ ) > f (F̂ 0 ) then
F̂ 0 ← F̃
Apply Lemma 2.2 to convert F̂ 0 to a feasible solution F̂ for OPF
return F̂
r=1
2

Define
(
M := max

r

z
f
, max
z r fr

)
=


z

sR
k
max
, max
, max
 z k,k0 ∈I sR
k,k0 ∈I
k0

sIk
,
max
sIk0 k,k0 ∈I, (i,j),(i0 ,j 0 )∈E

P
 
∗

Re
e0 ∈Pk ∩Pj ze0 sk
P
 ,

∗
Re
e0 ∈P 0 ∩P 0 ze0 sk0
k

j

(48)
where z := min{mine:Re(ze )>0 Re(ze ), mine:Im(ze )>0 Im(ze )} and z := maxe∈E max{Re(ze ), Im(ze )}.
Let n := |N |.
) O(log
Theorem 4.4. For any fixed ε ∈ (0, 1), Alg. 3 obtains a (1−ε)-approximation in time ( n log(nmM
)
ε

Note that the running time is quasi-polynomial if M = 2polylog(m,n) .
15

9 nmM
( ε

)/ε2 )

.

Proof. Let  :=

β = maxr∈Hq 2 (2Cr + αPr ) = O(log2 (mM )). The number of possible

choices for

is at most n

ε
3(2β+1) , where
each Lq in step 1

Pd

r=1

Pr /2 ,

where
n = |N |. Thus, using d = 3, P1 =
P

O(log(mM )), P2 = P3 = 1, T1 = 2, T2 = T3 = 1, Q ≤ Q
possible choices for L is at most
n

Pd

r=1

Pr Q/2

≤n

Pd

r=1

Pr Q

Pd
r=1 Tr /2

The number of choices for each hq = (hq,p,r )p∈[Pr ],
number of choices for Q in step 4 is
Pd

Q

r=1

Tr

d
r=1

Tr

, and Q = O(log nM
 ), the number of

= nO(log(mM ) log
Pd

r∈[d]

≤ log

4



is F
nM


r=1

Pr

4 nM
( 

)/2 )

.

(49)

) log(mM )
= O(( log(nM
)
), and the



,

(50)

giving at most


Pd



log(mM ) !Q
log(mM ) !Q r=1 Tr
log(mM ) log4 ( nM ) !



log(nM
)
log(nM
)
log(nM
)


 = O
O
=O



(51)
choices for h = (hq )q∈Q in step 1. The number of choices for the -restricted profiles in step 6 is
Pd
bounded from above by m r=1 Pr / = mO(log (mM )/) . The bound on the running time follows from
this and (49),(51) and (50).
We now argue that the solution
F̂ output by the algorithm is (1 − O())-approximation for OPF.

Let F ∗ = s∗0 , x∗ , v ∗ , `∗ , S ∗ be an optimal solution for OPF of objective Opt , f (F ∗ ). By the
definition of Î, we have
X
uk ≤ Opt ≤ f (F ∗ ).
(52)
k∈I\Î

P
p,r
Define T ∗ , {k ∈ Î | x∗k = 1} and (h∗ )q,p,r = k∈T ∗ ∩I q f k , for p ∈ [Pr ], r ∈ [d] and q ∈ Q. Let
p,r
∗
q
q
∗
2
∗
q,p,r
(L ) := {k ∈ I ∩ T : f k >  (h )
for some p ∈ [Pr ], and some r ∈ [d]} be the set of large
q
demands within group I in the optimal solution, and let (S ∗ )q := I q ∩ T ∗ \ (LP∗ )q be the set of
d

P

r
“small” demands within the same group. Note by this definition that |(L∗ )q | ≤ r=1
, and thus
2
∗
∗
q
q
L = ((L ) )q∈Q and h = (h )q∈Q will be one of the guesses considered by the algorithm in step 1.
0
Let us focus on this particular iteration of the loop in step 1. Let hq,p,r = (1 + )` f r , where `0 is the
P
p,r
smallest integer (including −∞) such that hq,p,r + k∈Lq f k ≥ (h∗ )q,p,r . Note that hq,p,r ∈ F r , and
X p,r
X p,r
1 q,p,r
h
+
f k ≤ (h∗ )q,p,r ≤ hq,p,r +
fk .
(53)
1+
∗ q
∗ q

k∈(L )

k∈(L )

Note that for any k ∈ (S ∗ )q , q ∈ Q, p ∈ [Pr ], and r ∈ [d], we have by (53),


X p,r
f p,r ≤ 2 (h∗ )q,p,r ≤ 2 hq,p,r +
fk  ,
k

k∈(L∗ )q

and hence (S ∗ )q ⊆ S q . Note also that




X p,r
X p,r
B q,p,r = 2 hq,p,r +
f k  ≤ 2 hq,p,r + (1 + )
f k  ≤ 2 (1 + )(h∗ )q,p,r .
k∈(L∗ )q

k∈(L∗ )q

16

(54)

Furthermore, x∗ is feasible for the constraint (44) as
X p,r
X p,r
X p,r
X p,r
f k x∗k =
f k x∗k =
f k = (h∗ )q,p,r −
f k ≤ hq,p,r .
k∈S q

k∈(S ∗ )q

k∈(S ∗ )q

k∈(L∗ )q

It follows that F ∗ is feasible for R1[L, h], implying by (52) that the solution F 0 obtained in step 3
of the algorithm satisfies
f (F 0 ) ≥ (1 − )f (F ∗ ).

(55)

gq

For each q ∈ Q, there is an (h, )-restricted profile
and an integral solution (x̂k )k∈S q that satisfy
Lemma 4.3. Since we try all possible (h, )-restricted profiles, the profile g q will be found in one of
the
in the
6. Let us consider this iteration. By condition (i) of the lemma,
P iterations
P loop rin line
r (e)x̂ ≤
0 for all e ∈ E and r ∈ [d], which implies that conditions (14)-(17) of
f
f
(e)x
q
q
k
k∈S
k∈S
k
k
k
Lemma 3.1 hold for the vector x̄, defined in line 8 of the algorithm. By Condition (ii) of Lemma 4.3
and (54),



Pr 
q,Pr ,r
X
X
X X
C
αP
B
r
r


(hq,p,r + B q,p,r ) +
uk x̂k ≥
uk x0k −
q,p,r
q,Pr ,r
H
H
q
q
q
p=1
r∈H
k∈S
k∈S



Pr 
2 (1 + )(h∗ )q,Pr ,r
X X
X
C
αP

r
r


=
uk x0k −
(1 + )2 (hq,p,r )∗ +
q,p,r
q,Pr ,r
H
H
p=1
r∈Hq
k∈S q



Pr 
∗
q,P
,r
X
X X
r
Cr
αPr (h )

.
(56)
=
uk x0k − (1 + )
(1 + )(hq,p,r )∗ +
q,p,r
q,Pr ,r
H
H
q
q
r∈H

k∈S

p=1

On the other hand, for k ∈ S q and r ∈ [d] such that fkr (en ) > 0 (and hence H q,p,r > 0 for all p ∈ [Pr ]
by (36)), we have uk ≥ 2qr,t −1 Lar,t
k and hence
uk

br,t (ei(p,r) )
2qr,t −1 L

r,t r,t
r,t
≥ ar,t
k b (ei(p,r) ) ≥ ak b̃ (ei(p,r) ).

(57)

p,r

Summing up (57) over t ∈ [Tr ], we get uk ≥ 2Hf kq,p,r .; summing this inequality over k ∈ T ∗ ∩ I q , we
get
p,r
X
X
(h∗ )q,p,r
fk
Optq :=
uk ≥
=
.
(58)
q,p,r
2H
2H q,p,r
∗
q
∗
q
k∈T ∩I

Summing (58), over r ∈

k∈T ∩I

Hq

and p ∈ [Pr ], we get



Pr
Pr 
∗
q,p,r
∗
q,P
,r
X X
X
X
r
(h )
1
Cr
αPr (h )

.
Optq ≥
≥ ·
(1 + )(hq,p,r )∗ +
q,p,r
q,p,r
2H
β
H
H q,Pr ,r
q
q
r∈H p=1

r∈H

p=1

Thus, it follows from (56) and (59) that
X
X
X
uk x̂k ≥
uk x0k − (1 + )βOptq ≥
uk x0k − (1 + )βOptq .
k∈S q

(59)

k∈S q

k∈(S ∗ )q

17

(60)

Summing (60) over all q ∈ Q and using (55) and (60) give


X
X
X
X

uk x̄k +
uk x̄k 
uk x̄k =
k∈S q

k∈(L∗ )q

q∈Q

k∈I




≥

X

X

=

uk x0k +


X

uk x0k − (1 + )β

k∈T ∗

=

X

≥
≥

X

≥

X

X

X

uk x0k − (1 + )β

k∈T

uk x0k

uk

k∈T ∗

k∈I

X

uk x0k − (1 + )βOptq 

k∈(S ∗ )q

k∈(L∗ )q

q∈Q

X

uk

∗

∗

− f (F ) − (1 + )βf (F ∗ )

k∈I

k∈Î

uk x0k −

(1 + (1 + )β)
f (F 0 )
1−

uk x0k − 3(2β + 1)f (F 0 ).

k∈Î

Thus condition (13) is satisfied with ε = 3(2β + 1) implying that F̃ is a feasible solution for (cOPF)
with f (F̃ ) ≥ (1 − ε)f (F 0 ) ≥ (1 − ε)f (F ∗ ).

References
[1] J. Carpentier, “Contribution á létude du dispatching économique,,” Bulletin de la Société
Franaise des Électriciens,, vol. 3, no. 8, pp. 431–447, 1962.
[2] J. Carpentier, “Optimal power flows,” International Journal of Electrical Power & Energy Systems, vol. 1, no. 1, pp. 3 – 15, 1979.
[3] S. Frank, I. Steponavice, and S. Rebennack, “Optimal power flow: a bibliographic survey I,”
Energy Systems, vol. 3, pp. 221–258, Sep 2012.
[4] S. Frank, I. Steponavice, and S. Rebennack, “Optimal power flow: a bibliographic survey II,”
Energy Systems, vol. 3, pp. 259–289, Sep 2012.
[5] R. A. M. van Amerongen, “Optimal power flow solved with sequential reduced quadratic programming,” Archiv für Elektrotechnik, vol. 71, pp. 213–219, May 1988.
[6] G. L. Torres and V. H. Quintana, “An interior-point method for nonlinear optimal power flow
using voltage rectangular coordinates,” IEEE Transactions on Power Systems, vol. 13, pp. 1211–
1218, Nov 1998.
[7] F. Milano, “Continuous newton’s method for power flow analysis,” IEEE Transactions on Power
Systems, vol. 24, pp. 50–57, Feb 2009.
[8] C. Coffrin and P. V. Hentenryck, “A linear-programming approximation of ac power flows,”
INFORMS Journal on Computing, vol. 26, no. 4, pp. 718–734, 2014.
[9] M. NIU, C. WAN, and Z. XU, “A review on applications of heuristic optimization algorithms
for optimal power flow in modern power systems,” Journal of Modern Power Systems and Clean
Energy, vol. 2, pp. 289–297, Dec 2014.
18

[10] T. Sowa, A. Stroband, W. Cramer, S. Koopmann, and A. Schnettler, “An ac power flow linearization for power system optimization using linear programming,” in 2016 IEEE Electrical
Power and Energy Conference (EPEC), pp. 1–5, Oct 2016.
[11] S. Bose, D. F. Gayme, K. M. Chandy, and S. H. Low, “Quadratically constrained quadratic
programs on acyclic graphs with application to power flow,” IEEE Transactions on Control of
Network Systems, vol. 2, pp. 278–287, Sept 2015.
[12] S. Huang, Q. Wu, J. Wang, and H. Zhao, “A sufficient condition on convex relaxation of ac
optimal power flow in distribution networks,” IEEE Transactions on Power Systems, vol. 32,
no. 2, pp. 1359–1368, 2017.
[13] L. Gan, N. Li, U. Topcu, and S. H. Low, “Exact convex relaxation of optimal power flow in
radial networks,” IEEE Transactions on Automatic Control, vol. 60, no. 1, pp. 72–87, 2015.
[14] S. Low, “Convex relaxation of optimal power flow, part I: Formulations and equivalence,” Control of Network Systems, IEEE Transactions on, vol. 1, pp. 15–27, March 2014.
[15] S. Low, “Convex relaxation of optimal power flow, part II: Exactness,” Control of Network
Systems, IEEE Transactions on, vol. 1, pp. 177–189, June 2014.
[16] C. Chau, K. Elbassioni, and M. Khonji, “Truthful mechanisms for combinatorial allocation of
electric power in alternating current electric systems for smart grid,” ACM Trans. Economics
and Comput., vol. 5, no. 1, pp. 7:1–7:29, 2016.
[17] C.-K. Chau, K. Elbassioni, and M. Khonji, “Truthful mechanisms for combinatorial AC electric power allocation,” in Proceedings of the 2014 International Conference on Autonomous
Agents and Multi-agent Systems (AaMAS), International Foundation for Autonomous Agents
and Multiagent Systems, 2014.
[18] M. Khonji, C.-K. Chau, and K. Elbassioni, “Inapproximability of Power Allocation With Inelastic Demands in AC Electric Systems and Networks,” in 23rd International Conference on
Computer Communication and Networks (ICCCN), pp. 1–6, Aug 2014.
[19] M. Khonj, C.-K. Chau, and K. Elbassioni, “Optimal power flow with inelastic demands for
demand response in radial distribution networks,” to appear in IEEE Transactions on Control
of Network Systems, 2016. http://arxiv.org/abs/1601.02323.
[20] M. Khonji, A. Karapetyan, K. Elbassioni, and C.-K. Chau, “Complex-demand scheduling problem with application in smart grid,” in International Computing and Combinatorics Conference
(COCOON), 2016. http://arxiv.org/abs/1603.01786.
[21] M. Khonji, C.-K. Chau, and K. Elbassioni, “Optimal power flow with inelastic demands for
demand response in radial distribution networks,” IEEE Transactions on Control of Network
Systems, 2016.
[22] J. M. Kleinberg, “Single-source unsplittable flow,” in 37th Annual Symposium on Foundations
of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pp. 68–77,
1996.
[23] C. Chekuri, A. Ene, and N. Korula, “Unsplittable flow in paths and trees and column-restricted
packing integer programs,” in Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques, pp. 42–55, Springer, 2009.
[24] C. Chekuri, M. Mydlarz, and F. B. Shepherd, “Multicommodity demand flow in a tree and
packing integer programs,” ACM Trans. Algorithms, vol. 3, no. 3, p. 27, 2007.
19

[25] A. Anagnostopoulos, F. Grandoni, S. Leonardi, and A. Wiese, “A mazing 2+ε approximation for
unsplittable flow on a path,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium
on Discrete Algorithms, pp. 26–41, SIAM, 2014.
[26] N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber, “A quasi-ptas for unsplittable flow
on line graphs,” in Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of
Computing, STOC ’06, (New York, NY, USA), pp. 721–729, ACM, 2006.
[27] J. Batra, N. Garg, A. Kumar, T. Mömke, and A. Wiese, “New approximation schemes for
unsplittable flow on a path,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), pp. 47–58, 2015.
[28] P. S. Bonsma, J. Schulz, and A. Wiese, “A constant factor approximation algorithm for unsplittable flow on paths,” in 52nd IEEE Annual Symposium on Foundations of Computer Science
(FOCS), pp. 47–56, 2011.
[29] A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar, “Approximation algorithms for the
unsplittable flow problem,” Algorithmica, vol. 47, no. 1, pp. 53–78, 2007.
[30] J. L. Kirtley, Electric Power Principles: Sources, Conversion, Distribution and Use. New Jersey:
Wiley, 2010.
[31] M. E. Baran and F. F. Wu, “Optimal capacitor placement on radial distribution systems,” IEEE
Transactions on Power Delivery, vol. 4, no. 1, pp. 725–734, 1989.
[32] M. E. Baran and F. F. Wu, “Optimal sizing of capacitors placed on a radial distribution system,”
IEEE Transactions on Power Delivery, vol. 4, no. 1, pp. 735–743, 1989.
[33] M. Farivar and S. H. Low, “Branch flow model: Relaxations and convexification–part ii,” IEEE
Transactions on Power Systems, vol. 28, pp. 2565–2572, Aug 2013.
[34] P. Korovesis, G. Vokas, I. Gonos, and F. Topalis, “Influence of large-scale installation of energy
saving lamps on the line voltage distortion of a weak network supplied by photovoltaic station,”
IEEE Transactions on Power Delivery, vol. 19, pp. 1787–1793, Oct 2004.
[35] M. Khonji, S. C. Chau, and K. M. Elbassioni, “Optimal power flow with inelastic demands for
demand response in radial distribution networks,” CoRR, vol. abs/1601.02323, 2016.
[36] N. Bansal, Z. Friggstad, R. Khandekar, and M. R. Salavatipour, “A logarithmic approximation
for unsplittable flow on line graphs,” ACM Trans. Algorithms, vol. 10, pp. 1:1–1:15, Jan. 2014.
[37] A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar, “Approximation algorithms for the
unsplittable flow problem,” Algorithmica, vol. 47, no. 1, pp. 53–78, 2007.
[38] C. Chekuri, A. Ene, and N. Korula, “Unsplittable Flow in Paths and Trees and ColumnRestricted Packing Integer Programs,” in Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques (I. Dinur, K. Jansen, J. Naor, and J. Rolim, eds.),
vol. 5687 of Lecture Notes in Computer Science, pp. 42–55, Springer Berlin Heidelberg, 2009.

A

Appendix: Completing the Proof of Lemma 2.2

Proof. We show the feasibility of the solution F̃ . By Steps 6, 7 and 10 of Alg. 1, all equality
constraints of cOPF0 [x0 ] are satisfied. By Step 5 and the feasibility of F 0 , we also have
`˜e ≤ `0e ≤ `e for all e ∈ E.
(61)
20

Next, by rewriting S̃i,j , recursively substituting from the leaves, we get
X
X
ze `˜e .
S̃i,j =
sk x̃k +

(62)

e∈Ej ∪{(i,j)}

k∈Nj

Write ∆`e , `˜e − `0e ≤ 0, ∆Se , S̃e − Se0 , and ∆|Se |2 , |S̃e |2 − |Se0 |2 , for e ∈ E. Let Sbj ,
P
P
0
0
0
˜
b
k∈Nj sk xk , L̃i,j ,
e∈Ej ∪{(i,j)} ze `e , and Li,j ,
e∈Ej ∪{(i,j)} ze `e . Note by (62) that S̃i,j = Sj + L̃i,j
and, similarly, Si,j = Sbj + L0i,j . It follows that, for all (i, j) ∈ E,
X
ze ∆`e ≤ 0,
(63)
∆Si,j = L̃i,j − L0i,j =
P

e∈Ej ∪{(i,j)}

where the inequality follows by assumption A1. In particular, for (i, j) = (0, 1), we obtain
R
0R
0R
s̃R
0 = −S̃0,1 ≥ −S0,1 = s0 ,

(64)

0R
implying by A0 that f0 (s̃R
0 ) ≥ f0 (s0 ) and hence (12) is satisfied.
Furthermore,
0 2
∆|Si,j |2 = |S̃i,j |2 − |Si,j
|

=
=

(65)

R 2
0R 2
I 2
0I 2
(S̃i,j
) − (Si,j
) + (S̃i,j
) − (Si,j
)
R
R
0R
I
I
0I
∆Si,j
(S̃i,j
+ Si,j
) + ∆Si,j
(S̃i,j
+ Si,j
)

X

=

zeR ∆`e 2SbjR + L̃R
i,j

(66)
(67)
X


+ L0R
i,j +

e∈Ej ∪{(i,j)}

X

=

zeI ∆`e 2SbjI + L̃Ii,j + L0Ii,j



(68)

e∈Ej ∪{(i,j)}

X

2∆`e Re(ze∗ Sbj ) +

e∈Ej ∪{(i,j)}

X

∆`e Re(ze∗ L̃i,j ) +

e∈Ej ∪{(i,j)}

∆`e Re(ze∗ L0i,j ) ≤ 0,

e∈Ej ∪{(i,j)}

(69)
where Eqn. (69) follows by A1, A3 (or

A40 )

and ∆`e ≤ 0. Therefore, by the feasibility of Se ,

|S̃e | ≤ |Se0 | ≤ S e

for all e ∈ E.

(70)

Note that, by assumption A1, Ineqs. (70) also implies that the reverse power constraint in (6) is
satisfied for S̃.
Rewrite Cons. (4) by recursively substituting ṽj , for j moving away from the root, and then
substituting for S̃h,t using (62):
X
X
∗
ṽj = v0 − 2
Re(zh,t
S̃h,t ) +
|zh,t |2 `˜h,t
(h,t)∈Pj

X

= v0 − 2

(h,t)∈Pj



X

∗
Re zh,t

= v0 − 2

X

Re

k∈N

−2

X



∗
zh,t
sk x̃k − 2

(h,t)∈Pk ∩Pj

|zh,t |2 `˜h,t +

(h,t)∈Pj



X

X

ze `˜e



+

e∈Et ∪{(h,t)}

k∈Nt

(h,t)∈Pj

X

sk x̃k +

X

X

|zh,t |2 `˜h,t ,

(h,t)∈Pj



∗
Re zh,t

(h,t)∈Pj

X

ze `˜e



e∈Et

|zh,t |2 `˜h,t ,

(71)

(h,t)∈Pj

where the last statement follows from exchanging the summation operators, and ze∗ ze = |ze |2 . Thus,

 X

X 
X
X
X

∗
∗
ṽj = v0 − 2
Re
zh,t
sk x̃k − 2
Re zh,t
ze `˜e +
|zh,t |2 `˜h,t ≤ v0 < v j ,
k∈N

(h,t)∈Pk ∩Pj

(h,t)∈Pj

e∈Et

(h,t)∈Pj

(72)
where the first inequality follows by A1 and A3, and the last inequality follows by A2. Since `˜e ≤ `0e
21

and x̃ = x0 , we get by A1 and the feasibility of F 0 ,

 X

X 
X
X
X

∗
ṽj ≥ v0 − 2
Re
zh,t
sk x0k − 2
Re zh,t
ze `e +
|zh,t |2 `h,t = vj0 ≥ v j .
k∈N

(h,t)∈Pk ∩Pj

(h,t)∈Pj

e∈Et

(h,t)∈Pj

(73)
By Ineqs. (70) and (73), `˜i,j =

0 |2
|Si,j
vi0

≥

|S̃i,j |2
ṽi ,

hence, F̃ is feasible.

Finally by the first inequality in (61) and the fact that `0h,t >
P
0
0
0 0
e∈E `e , contradicting the optimality of F for cOPF [x ].

22

|Sh,t |2
vh

P
= `˜h,t , we have e∈E `˜e <

