Optimal Placement of Distributed Energy Storage in
Power Networks
Christos Thrampoulidis,
Student Member, IEEE,
Subhonmesh Bose,
Student Member, IEEE,
and Babak Hassibi
Fellow, IEEE
.
Abstract
—We formulate the optimal placement, sizing and control of
storage devices in a power network to minimize generation costs with
the intent of load shifting. We assume deterministic demand, a linearized
DC approximated power flow model and a fixed available storage budget.
Our main result proves that when the generation costs are convex and
nondecreasing, there always exists an optimal storage capacity allocation
that places zero storage at generation-only buses that connect to the rest
of the network via single links. This holds regardless of the demand
profiles, generation capacities, line-flow limits and characteristics of the
storage technologies. Through a counterexample, we illustrate that this
result is not generally true for generation buses with multiple connections.
For specific network topologies, we also characterize the dependence of
the optimal generation cost on the available storage budget, generation
capacities and flow constraints.
I. I
NTRODUCTION
A. Motivation
Energy storage technologies have been argued as
“critical to
achieving national energy policy objectives and creating a modern
and secure electric grid system.”
[1]. They have many potential
applications in power networks, e.g., see [2], [3] for a detailed
survey. At faster time scales (seconds to minutes), storage can be
used to reduce variability of renewable sources of energy like wind
or solar [4]–[7]. At slower time scales (over hours), it can be used
for load shifting [8], [9], i.e., generate when it is cheaper and use
storage dynamics to follow the demand. Though still very expensive,
storage devices based on pumped hydro, compressed air, Lithium-
ion based and other technologies have shown significant technical
improvements and cost drops [9], [10] over the last decade and are
expected to play a central role in an efficient power system [1], [2],
[8], [11]–[16].
Two natural questions to ask for storage are: (a) What is the optimal
investment policy for storage? Where to place them, and how to size
them? (b) Once installed, what is the optimal control policy for the
storage as well as the generation schedule to minimize generation
costs? In this paper, we formulate both problems for
slower time-
scales
in a common framework and present results on sizing such
storage units in a network and a charging/ discharging policy for the
installed units.
B. Prior work
Now, we provide a brief overview of the relevant literature. Optimal
control policy for storage units has been extensively studied. While
the authors in [17]–[19] examine the control of a single storage device
without a network, the authors in [20], [21] explicitly model the
role of the networks in the operation of distributed storage resources.
Emails:
(cthrampo, boses, hassibi)@caltech.edu
.
This
work was supported in part by NSF under grants CCF-0729203, CNS-
0932428 and CCF-1018927, NetSE grant CNS 0911041, Office of Naval
Research MURI grant N00014-08-1-0747, Caltech Lee Center for Adv. Net.,
ARPA-E grant DE-AR0000226, Southern Cali. Edison, Nat. Sc. Council
of Taiwan, R.O.C. grant NSC 101-3113-P-008-001, Resnick Inst., Okawa
Foundation and Andreas Mentzelopoulos Scholarships for the Univ. of Patras.
Storage resources at each node in the network are assumed to be
known
a priori
in these settings.
Sizing of storage devices has been studied by several authors,
e.g., [22], [23] using purely economic arguments, without explicitly
considering the network constraints of the physical system. Authors
in [18], [24] have looked at optimal sizing of storage devices in
single-bus power systems for fast-time scales, while Kanoria et al.
[20] compute the effect of sizing of distributed storage resources on
generation cost for specific networks.
The optimal storage placement problem on a general power net-
work has been formulated and studied recently through simulations.
The network imposes non-convex power-flow constraints that render
such optimization problems NP-hard. These are handled through (a)
linearization using DC approximation [25], [26], or (b) a relaxation
of the feasible sets using semidefinite programming [27]–[29]. For
the storage placement problem, Sj
̈
odin et al. in [30] uses the former,
while Bose et al. in [31] uses the latter.
C. Our Contribution
In this paper, we study the joint investment decision and con-
trol problem for storage devices in a power network. Our main
contribution is the result in Theorem 1:
when minimizing a convex
and nondecreasing generation cost with any fixed available storage
budget over a slow time-scale of operation, there always exists an
optimal storage allocation that assigns zero storage at nodes with
only generation that connect via single transmission lines to the rest
of the network. This holds for arbitrary demand profiles and other
network parameters
.
First, we describe the salient features of our model. As in [18],
[20], the investment decision problem is an infinite horizon problem.
Hourly aggregate demands over large geographical locations often
show periodicity [32] and hence the optimization can be equivalently
solved over one time period. The storage units are assumed to
have finite capacities and ramp rates. Power exchanges with these
devices suffer losses due to inefficiencies. Also, since we optimize
the amount of storage placed on each bus, storage is assumed to
be infinitely divisible. This is, however, not a limitation for our
main result, as is explained in Section IV. The generators have
finite capacities with convex nondecreasing costs [19], [20], [33].
The network has been modeled using linearized DC power-flow
approximation [34] with finite line-flow capacities. This neglects
reactive power over the network, defines voltage magnitudes to be at
their nominal values at all buses and assumes the voltage phase angle
differences between nodes to be small. Though this is a simplification
of the full AC model of the power system with known limitations
[26], this approximation is widely used for analysis in optimal
power flow [26], [34], [35], transmission expansion planning [36]
and electricity market operations [37]–[39]. The focus of this work
is to derive structural properties of the storage placement problem
using the linearized DC model as in [20], [30]; this complements
the studies without network models in [18], [19] and simulation
studies with a full AC model of the power flow equations [21],
[31]. The result generalizes our work in [40] and provides (partial)
analytic justification of the observation made empirically in [21], [30],
[31]: optimal storage allocation seldom places storage capacities at
generator-only buses.
Next, we briefly discuss some of the qualifications of this work.
First, to solve a complete storage investment strategy, we need a cost-
benefit analysis of installing this new technology. In other words,
the savings due to storage needs to be matched with the cost of
installation and operation of such units on the grid. In this work, how-
ever, we only focus on minimizing cost of generation that estimates
the potential benefits of storage. Second, our main result applies to
bulk storage on a slow time-scale and does not naturally generalize
to scenarios with intermittent renewable generation. Dealing with
fast time-scale variability of generation needs a stochastic control
framework as in [18], [20]; this, however, is not the focus of the
current paper. Third, our main result characterizes storage allocation
at generation-only buses that link to the rest of the network via a
single transmission line. As shown in Section IV-D, the result does
not necessarily hold for generator-only buses with multiple links to
the network. Also, it does not address the sizing or placement for
any other kind of nodes in the network. We emphasize that this
is a preliminary work on storage placement. To the best of our
knowledge, this is the first theoretical result on this problem so far
over a general power network. Our analysis suggests that there is
a potential to exploit the rich underlying structure of this problem;
ongoing research aims at finding these properties and overcoming the
limitations mentioned.
The paper is organized as follows. We formulate the optimal
storage placement problem in Section II. The main result is stated
and proven in Section III. A detailed discussion on the interpretation
and some extensions of the result are presented in Section IV. We
conclude the paper in Section V.
II. P
ROBLEM FORMULATION
Consider a power network that is defined by an undirected con-
nected graph
G
on
n
nodes (or buses)
N
=
{
1
,
2
,...,n
}
. For two
nodes
k
and
l
in
N
, let
k
∼
l
denote that
k
is connected to
l
in
G
by a transmission line. We model time to be discrete and indexed by
t
. Now consider the following notation.
•
d
k
(
t
)
is the known real power demand at bus
k
∈ N
at time
t
. Hourly demand profiles often show diurnal variations [41],
i.e., they exhibit cyclic behavior. Let
T
time-steps denote the
cycle length of the variation. In particular, for all
k
∈N
,
t
≥
0
,
assume
d
k
(
t
+
T
) =
d
k
(
t
)
.
•
g
k
(
t
)
is the real power generation at bus
k
∈ N
at time
t
and
it satisfies
0
≤
g
k
(
t
)
≤
g
k
,
(1)
where,
g
k
is the generation capacity at bus
k
.
1
•
c
k
(
g
k
)
denotes the cost of generating power
g
k
at bus
k
∈N
.
The cost of generation is assumed to be independent of time
t
and depends only on the generation technology at bus
k
. Also,
suppose that the function
c
k
:
R
+
→
R
+
is non-decreasing
and convex. These assumptions apply to commonly used cost
functions in the literature [21], [28], [29], [33], e.g., convex and
nondecreasing piecewise linear or quadratic ones.
•
The power
p
kl
sent from bus
k
towards bus
l
for two nodes
k
∼
l
in
G
is limited by thermal and stability constraints as
|
p
kl
(
t
)
|≤
f
kl
,
(2)
1
We do not include ramp constraints on the generators.
where
f
kl
is the capacity of the corresponding line.
storage
device
∼
·
·
·
g
k
(
t
)
d
k
(
t
)
γ
k
(
t
)
α
γ
γ
k
(
t
)
δ
k
(
t
)
1
α
δ
δ
k
(
t
)
p
kl
(
t
)
Fig. 1: Power balance at node
k
∈N
.
•
γ
k
(
t
)
and
δ
k
(
t
)
are the average charging and discharging powers
of the storage unit at bus
k
∈ N
at time
t
, respectively. The
energy transacted over a time-step is converted to power units
by dividing it by the length of the time-step. This transformation
conveniently allows us to formulate the problem in units of
power [31]. Let
0
< α
γ
,α
δ
≤
1
denote the charging and
discharging efficiencies, respectively of the storage technology
used, i.e., the power flowing in and out of the storage device
at node
k
∈ N
at time
t
is
α
γ
γ
k
(
t
)
and
1
α
δ
δ
k
(
t
)
, respectively
[18], [42]. The roundtrip efficiency of this storage technology is
α
=
α
γ
α
δ
≤
1
.
•
s
k
(
t
)
denotes the storage level at node
k
∈N
at time
t
and
s
0
k
is the storage level at node
k
at time
t
= 0
. From the definitions
above, we have
s
k
(
t
) =
s
0
k
+
t
∑
τ
=1
(
α
γ
γ
k
(
τ
)
−
1
α
δ
δ
k
(
τ
)
)
.
(3)
For each
k
∈ N
, assume
s
0
k
= 0
, so that the storage units are
empty at installation time.
•
b
k
≥
0
is the storage capacity at bus
k
. Thus,
s
k
(
t
)
for all
t
satisfies
0
≤
s
k
(
t
)
≤
b
k
.
(4)
•
h
is the available storage budget and denotes the total amount
of storage capacity that can be installed in the network. Our
optimization algorithm decides the allocation of storage capacity
b
k
at each node
k
∈N
and thus, we have
2
∑
k
∈N
b
k
≤
h.
(5)
•
The charging and discharging rates of storage device at node
k
∈ N
are bounded above by ramp limits; these limits are
assumed to be proportional to the installed storage capacity at
node
k
, i.e.,
3
0
≤
γ
k
(
t
)
≤
γ
b
k
,
(6a)
0
≤
δ
k
(
t
)
≤
δ
b
k
,
(6b)
where
γ
∈
(0
,
1
α
γ
]
and
δ
∈
(0
,α
δ
]
are fixed constants.
2
Note that we do not restrict the capacity sizes
b
k
,k
∈ N
a priori
. The
problem formulation can be extended to include any linear constraints on
b
k
’s.
3
Note that
γ
and
δ
are specific to a storage technology. We consider
the installment of one kind of storage over the network. Though we present
our results with one storage technology, it can be generalized to the joint
placement of installing multiple storage types with individual storage budgets
for each technology.
Balancing power that flows in and out of bus
k
∈N
at time
t
, as
shown in Figure 1, we have:
g
k
(
t
)
−
d
k
(
t
)
−
γ
k
(
t
) +
δ
k
(
t
) =
∑
l
∼
k
p
kl
(
t
)
.
(7)
The power flow
p
kl
from bus
k
to bus
l
relates to the voltages at the
buses through Kirchoff’s law. Since power is quadratic in voltage, the
power flow equations introduce quadratic equalities that render most
optimization problems over power networks nonconvex and hence
hard to solve and analyze. The role of nonconvexity in power flow
optimization has been widely studied in the power system literature ;
see [43], [44] surveys. Nonconvex optimizations, in general, are hard
to solve and difficult to analyze. To make the model amenable to
analysis, one option is to linearize the power flow equations around
an operating point. Such a linearization technique popularly used in
the literature is the DC approximation [45, Ch. 9] [46, Ch. 6] [25];
for completeness, we discuss it in Appendix A. In this model, the
transmission losses (resistances in transmission lines) and reactive
power flows in the network are ignored. Specifically, suppose
B
kl
is
the susceptance of the transmission line joining buses
k
and
l
and
θ
k
(
t
)
is the voltage phase angle at bus
k
∈N
at time
t
. Then, using
DC approximation, it can be shown that
p
kl
(
t
) =
B
kl
[
θ
k
(
t
)
−
θ
l
(
t
)]
.
(8)
Though we ignore all transmission losses for presenting our result,
we generalize it in Section IV-B to include losses. The loss model
used is discussed further in Appendix A.
Optimally placing storage over an infinite horizon is equivalent to
solving this problem over a singe cycle, provided the state of the
storage levels at the end of a cycle is the same as its initial condition
[31]. Thus, for each
k
∈N
, we have
T
∑
t
=1
(
α
γ
γ
k
(
t
)
−
1
α
δ
δ
k
(
t
)
)
= 0
.
(9)
For convenience, denote
[
T
] :=
{
1
,
2
,...,T
}
. Using the above
notation, we define the following optimization problem.
Storage placement problem
P
:
minimize
∑
k
∈N
T
∑
t
=1
c
k
(
g
k
(
t
))
over
(
g
k
(
t
)
,γ
k
(
t
)
,δ
k
(
t
)
,p
kl
(
t
)
,b
k
,θ
k
(
t
))
,
k
∈N
, k
∼
l, t
∈
[
T
]
,
subject to
(1)
−
(9)
,
where, (1) represents generation constraints, (2), (7) represent power
flow constraints, (4),(5),(6),(9) represent the constraints imposed on
the charging/discharging control policy of the energy storage devices,
and (8) represents the DC approximated Kirchoff’s laws. For the
power network,
θ
k
(
t
)
,k
∈ N
and
p
kl
(
t
)
,k
∼
l
in
G
are state
variables, while
g
k
(
t
)
,γ
k
(
t
)
,δ
k
(
t
)
,b
k
are controllable inputs to the
system.
Given the demand profiles and network parameters,
P
can be
efficiently solved to define the optimal investment decision strategy
for sizing storage units at different buses, the economic dispatch of
the various generators and the optimal control policy of the installed
storage units.
Now, restrict attention to network topologies where each bus either
has generation or load but not both
4
. Partition the set of buses
N
into
two groups
N
G
and
N
D
where they represent the generation-only and
load-only buses respectively and assume
N
G
and
N
D
are non-empty.
4
An intermediate bus (one that has no generation or load) is modeled as a
load bus. Any losses associated with the node is included as a load.
For any subset
K
of
N
G
, define the following optimization problem.
Restricted storage placement problem
Π
K
:
minimize
∑
k
∈N
T
∑
t
=1
c
k
(
g
k
(
t
))
over
(
g
k
(
t
)
,γ
k
(
t
)
,δ
k
(
t
)
,θ
k
(
t
)
,p
kl
(
t
)
,b
k
)
,
k
∈N
, k
∼
l, t
∈
[
T
]
,
subject to
(1)
−
(9)
,
b
k
= 0
, k
∈K
.
Problem
Π
K
corresponds to placing no storage at the (generation)
buses of the network in subset
K
. We study the relation between the
problems
P
and
Π
K
in the rest of the paper.
We say bus
k
∈ N
has
a single connection
if it has exactly one
neighboring node
l
∼
k
. Similarly, a bus
k
∈ N
has
multiple
connections
if it has more than one neighboring node in
G
. We
illustrate the notation using the network in Figure 2.
N
G
=
{
1
,
2
,
7
}
and
N
D
=
{
3
,
4
,
5
,
6
}
. Buses 1 and 2 have single connections and
all other buses in the network have multiple connections.
1
2
3
4
5
6
7
generatorbus
loadbus
Fig. 2: A sample network.
III. M
AIN
R
ESULT
For a subset
K ⊆ N
G
, let
p
∗
and
π
∗
K
be the optimal values for
problems
P
and
Π
K
, respectively. Now, we are ready to present the
main result of this paper.
Theorem 1.
Let
K⊆N
G
be a subset of generation nodes that have
single connections. Consider the storage placement problem
P
, the
restricted storage placement problem
Π
K
and their respective optimal
costs
p
∗
and
π
K
∗
. If
P
is feasible, then
Π
K
is feasible and
p
∗
=
π
K
∗
.
Problem
P
, in general, may have multiple optimal solutions, but
Theorem 1 proves that there
always
exists an optimal allocation of
storage capacities that places
no
storage at any subset of generation
buses with single connections, regardless of the demand profiles, gen-
eration capacities, line-flow limits and characteristics of the storage
technologies.
Next, we make the following remarks about the result. (a) Notice
that we have restricted our attention to generator buses in
K
that
have single connections only. This does not generalize to the case
if
K
includes generator buses with multiple connections; see Section
IV-D for an example. (b) Storage capacity allocation at each bus
has been assumed to be infinitely divisible, i.e., each
b
k
,k
∈ N
that satisfies the budget constraint
∑
k
∈N
b
k
≤
h
in (5) is feasible.
But it might be impractical to implement an optimal allocation with
arbitrarily small storage capacities. This, however, is not a limitation
for the result in Theorem 1 as it only specifies zero storage capacities
at some buses and does
not
characterize storage sizes at others. (c) In
our formulation, we assume perfect knowledge of the entire demand
profile. The result in Theorem 1, however, holds true for
any
demand
profile as long as the storage placement problem
P
is feasible.
Before presenting the proof, we provide some intuition behind the
result. Consider a generator bus
k
that has a single connection to node
l
in the network. First, we solve the storage placement problem
P
for
this network. Suppose this results in some storage capacity installed at
bus
k
with some charging/ discharging profile
γ
∗
k
(
t
)
,δ
∗
k
(
t
)
, t
∈
[
T
]
.
To construct a solution of the restricted storage problem
Π
{
k
}
, a
natural idea to explore is to
shift
this storage from bus
k
to bus
l
and operate it with the optimal control policy (
γ
∗
k
(
t
)
,δ
∗
k
(
t
)
, t
∈
[
T
]
)
obtained from the solution of
P
. This shift can be done, provided that
the optimal generation profile
g
∗
k
(
t
)
,t
∈
[
T
]
, itself, defines a feasible
flow over the transmission line, i.e.,
g
∗
k
(
t
)
≤
f
kl
for all
t
∈
[
T
]
. The
key insight to prove this fact is that at the time instant where
g
∗
k
(
t
)
is at its maximum, the storage at bus
k
cannot be charging. If it was
indeed charging, one could generate less and charge less at the same
time. In what follows, we formalize this argument.
A. Proof of Theorem 1
We only prove the case where the round-trip efficiency is
α <
1
, but the result holds for
α
= 1
as well. Assume
P
is feasible
throughout. For any variable
z
in problem
P
, let
z
∗
be the value of
the corresponding variable at the optimum. In our proof, we use the
following technical result.
Lemma 1.
Suppose
φ
:
R
→
R
is convex. Then, for any
x
1
< x
2
and
0
≤
η
≤
(
x
2
−
x
1
)
:
φ
(
x
1
+
η
) +
φ
(
x
2
−
η
)
≤
φ
(
x
1
) +
φ
(
x
2
)
.
Proof:
Applying Jensen’s inequality to the convex function
φ
(
·
)
,
we have
(
1
−
η
x
2
−
x
1
)
φ
(
x
1
) +
(
η
x
2
−
x
1
)
φ
(
x
2
)
≥
φ
(
x
1
+
η
)
,
(
η
x
2
−
x
1
)
φ
(
x
1
) +
(
1
−
η
x
2
−
x
1
)
φ
(
x
2
)
≥
φ
(
x
2
−
η
)
.
The result follows from adding the inequalities above.
Consider node
k
∈K
and
k
∼
l
. Node
l
is uniquely defined as
k
has a single connection. Problem
P
, in general, has multiple optima.
In the following result, we characterize only a subset of these optima.
Lemma 2.
There exists an optimal solution of
P
such that for all
t
∈
[
T
]
and all
k
∈K
,l
∼
k
,
(a)
g
∗
k
(
t
)
γ
∗
k
(
t
)
δ
∗
k
(
t
) = 0
,
(b)
g
∗
k
(
t
)
≤
f
kl
.
Proof:
The feasible set of problem
P
is a bounded
5
polytope
and the objective function is a continuous convex function. Hence
the set of optima of
P
is a convex compact set [47]. Now, with
every point in the set of optimal solutions of
P
, consider the function
∑
k
∈K
,t
∈
[
T
]
(
γ
k
(
t
) +
δ
k
(
t
))
. This is a linear continuous function on
the compact set of optima of
P
and hence attains a minimum.
Consider the optimum of
P
where this minimum is attained. We
prove parts (a) and (b) in Lemma 2 for this optimum.
(a) Suppose, on the contrary, we have
g
∗
k
(
t
0
)
>
0
,
γ
∗
k
(
t
0
)
>
0
and
δ
∗
k
(
t
0
)
>
0
for some
t
0
∈
[
T
]
. Define
∆
g
′
:= min
{
(1
−
α
)
γ
∗
k
(
t
0
)
,
1
−
α
α
δ
∗
k
(
t
0
)
,g
∗
k
(
t
0
)
}
.
Note that
∆
g
′
>
0
. Now, for bus
k
, construct modified generation,
charging and discharging profiles
̃
g
k
(
t
)
,
̃
δ
k
(
t
)
,
̃
γ
k
(
t
)
,t
∈
[
T
]
that
differ from
g
∗
k
(
t
)
,δ
∗
k
(
t
)
,γ
∗
k
(
t
)
only at
t
0
as follows:
̃
g
k
(
t
0
) :=
g
∗
k
(
t
0
)
−
∆
g
′
,
5
Without loss of generality, let bus
1
be the slack bus and hence
θ
1
(
t
) = 0
for all
t
∈
[
T
]
. Boundedness of the set of feasible solutions of
P
then follows
from the relations in (1), (2), (5), (6) and (8).
̃
γ
k
(
t
0
) :=
γ
∗
k
(
t
0
)
−
1
1
−
α
∆
g
′
,
̃
δ
k
(
t
0
) :=
δ
∗
k
(
t
0
)
−
α
1
−
α
∆
g
′
.
Note that, for all
t
∈
[
T
]
, the storage level
s
k
(
t
)
and the power
p
kl
(
t
)
flowing from bus
k
to bus
l
remain unchanged throughout. It
can be checked that the modified profiles define a feasible point of
P
. Since
c
k
(
·
)
is non-decreasing, we have
c
k
( ̃
g
k
(
t
0
))
≤
c
k
(
g
∗
k
(
t
0
))
and hence the additivity of the objective in
P
over
k
and
t
implies
that this feasible point has an objective function value of at most
p
∗
.
It follows that this feasible point defines an optimal point of
P
. Also,
we have
̃
γ
k
(
t
0
) +
̃
δ
k
(
t
0
)
< γ
∗
k
(
t
0
) +
δ
∗
k
(
t
0
)
and thus, this optimum
of
P
has a strictly lower
∑
k
∈K
,t
∈
[
T
]
(
γ
k
(
t
) +
δ
k
(
t
))
, contradicting
our hypothesis. This completes the proof of Lemma 2(a).
(b) If
g
∗
k
(
t
) = 0
for all
t
∈
[
T
]
, then
g
∗
k
(
t
)
≤
f
kl
trivially holds.
Henceforth, assume
max
t
∈
[
T
]
g
∗
k
(
t
)
>
0
, and consider
t
+
∈
[
T
]
,
such that
g
∗
k
(
t
+
) = max
t
∈
[
T
]
g
∗
(
t
)
.
If
γ
∗
k
(
t
+
) = 0
, then,
max
t
∈
[
T
]
g
∗
k
(
t
) =
g
∗
k
(
t
+
) =
p
∗
kl
(
t
+
)
︸
︷︷
︸
≤
f
kl
+
γ
∗
k
(
t
+
)
︸
︷︷
︸
=0
−
δ
∗
k
(
t
+
)
︸
︷︷
︸
≥
0
≤
f
kl
,
and Lemma 2(b) holds.
Now, suppose that
γ
∗
k
(
t
+
)
>
0
and hence
δ
∗
k
(
t
+
) = 0
from Lemma
2(a). Since storage charges by an amount
α
γ
γ
∗
k
(
t
+
)
>
0
, we have
s
∗
k
(
t
+
)
>
0
. Also,
s
∗
k
(
T
) =
s
0
k
= 0
by hypothesis and hence the
storage at node
k
discharges from
s
∗
k
(
t
+
)
to zero in
[
t
+
+ 1
,T
]
. Let
t
−
be the first time instant after
t
+
when the storage device at bus
k
discharges, i.e.
t
−
:= min
{
t
∈
[
t
+
+ 1
,T
]
∣
∣
∣
α
γ
γ
∗
k
(
t
)
−
1
α
δ
δ
∗
k
(
t
)
<
0
}
.
(10)
Thus,
δ
∗
k
(
t
−
)
>
0
. Now, we argue that
g
∗
k
(
t
−
) =
g
∗
k
(
t
+
)
. Since
g
∗
k
(
t
+
) = max
t
∈
[
T
]
g
∗
k
(
t
)
, clearly
g
∗
k
(
t
−
)
≤
g
∗
k
(
t
+
)
. Suppose this
inequality is strict. Then we show how to construct an optimum
of
P
with a lower
∑
k
∈K
,t
∈
[
T
]
(
γ
k
(
t
) +
δ
k
(
t
))
to contradict our
hypothesis. Define
∆
g
:= min
{
γ
∗
k
(
t
+
)
,
1
α
δ
∗
k
(
t
−
)
, g
∗
k
(
t
+
)
,
1
α
(
g
∗
k
(
t
+
)
−
g
∗
k
(
t
−
)
)
}
.
Observe that
∆
g >
0
. Construct the modified generation, charging
and discharging profiles at node
k
,
̃
g
k
(
t
)
,
̃
δ
k
(
t
)
,
̃
γ
k
(
t
)
that differ from
g
∗
k
(
t
)
,δ
∗
k
(
t
)
,γ
∗
k
(
t
)
only at
t
+
and
t
−
as follows:
̃
g
k
(
t
+
) :=
g
∗
k
(
t
+
)
−
∆
g,
̃
g
k
(
t
−
) :=
g
∗
k
(
t
−
) +
α
∆
g,
̃
γ
k
(
t
+
) :=
γ
∗
k
(
t
+
)
−
∆
g,
̃
γ
k
(
t
−
) :=
γ
∗
k
(
t
−
)
,
̃
δ
k
(
t
+
) :=
δ
∗
k
(
t
+
) = 0
,
̃
δ
k
(
t
−
) :=
δ
∗
k
(
t
−
)
−
α
∆
g.
Also, define the modified storage level
̃
s
k
(
t
)
using
̃
γ
k
(
t
)
and
̃
δ
k
(
t
)
.
To provide intuition to the above modification, we essentially generate
and store less at time
t
+
by an amount
∆
g
. This means at a future
time
t
−
, we can discharge
α
∆
g
less from the storage device and
hence have to generate
α
∆
g
more to compensate. From the definition
of
∆
g
, it follows that for
t
=
t
+
,t
−
, we have
0
≤
̃
g
k
(
t
)
≤
g
k
,
0
≤
̃
γ
k
(
t
)
≤
γ
b
∗
k
, and
0
≤
̃
δ
k
(
t
)
≤
δ
b
∗
k
. Also, the line flows
p
kl
(
t
)
remain unchanged. For the storage levels, it can be checked
that
0
≤
s
∗
k
(
t
+
−
1)
≤
̃
s
k
(
t
)
≤
s
∗
k
(
t
)
≤
b
∗
k
,
for
t
∈
[
t
+
,t
−
−
1]
,
̃
s
k
(
t
) =
s
∗
k
(
t
)
,
otherwise
.
This proves that the modified profiles define a feasible point for
P
.
Also, we have
c
k
(
̃
g
k
(
t
+
)
)
+
c
k
(
̃
g
k
(
t
−
)
)
≤
c
k
(
g
∗
k
(
t
+
)
−
α
∆
g
)
+
c
k
(
g
∗
k
(
t
−
) +
α
∆
g
)
(11a)
≤
c
k
(
g
∗
k
(
t
+
)
)
+
c
k
(
g
∗
k
(
t
−
)
)
,
(11b)
where (11a) follows from the non-decreasing nature of
c
k
(
·
)
and
(11b) follows from our assumption
g
∗
k
(
t
−
)
< g
∗
k
(
t
+
)
and Lemma 1.
The modified profiles
̃
g
k
(
t
)
,
̃
δ
k
(
t
)
,
̃
γ
k
(
t
)
are feasible in
P
with an
objective value at most
p
∗
. Thus, they define an optimum of
P
. Also,
̃
γ
k
(
t
+
) + ̃
γ
k
(
t
−
) +
̃
δ
k
(
t
+
) +
̃
δ
k
(
t
−
)
=
γ
∗
k
(
t
+
) +
γ
∗
k
(
t
−
) +
δ
∗
k
(
t
+
) +
δ
∗
k
(
t
−
)
−
(1 +
α
)∆
g
︸
︷︷
︸
>
0
.
This
implies
that
this
optimum
of
P
has
a
lower
∑
k
∈K
,t
∈
[
T
]
(
γ
k
(
t
) +
δ
k
(
t
))
, contradicting our hypothesis. Hence,
we have
g
∗
k
(
t
−
) =
g
∗
k
(
t
+
) = max
t
∈
[
T
]
g
∗
k
(
t
)
.
Finally,
max
t
∈
[
T
]
g
∗
k
(
t
) =
g
∗
k
(
t
−
) =
p
∗
kl
(
t
−
)
︸
︷︷
︸
≤
f
kl
+
γ
∗
k
(
t
−
)
︸
︷︷
︸
=0
−
δ
∗
k
(
t
+
)
︸
︷︷
︸
>
0
≤
f
kl
.
This completes the proof of the lemma.
To prove Theorem 1, consider the optimal solution of
P
that
satisfies Lemma 2(b). For
k
∈K
,
g
∗
k
(
t
)
itself defines a feasible flow
over the line joining buses
k
and
l
, where
l
is the unique neighboring
node of
k
in graph
G
. Now, transfer the storage device at bus
k
to bus
l
. In particular, define a new storage capacity
ˆ
b
l
:=
b
∗
k
+
b
∗
l
and operate
it with a charging (and discharging) profile
ˆ
γ
l
(
t
) =
γ
∗
k
(
t
) +
γ
∗
l
(
t
)
(and similarly for
ˆ
δ
l
(
t
)
). For node
k
, define the new voltage phase
angle
ˆ
θ
k
(
t
) :=
θ
∗
k
(
t
) +
1
B
kl
(
γ
∗
k
(
t
)
−
δ
∗
k
(
t
))
. The power flow from
bus
k
to bus
l
is then given as
ˆ
p
kl
(
t
) :=
g
∗
k
(
t
)
. These profiles define
a feasible point of
Π
{
k
}
with an objective value of
p
∗
. Combining
with the fact that
p
∗
≤
π
{
k
}
∗
, we conclude
p
∗
=
π
{
k
}
∗
. Finally, we
do this successively for each
k
∈K
to obtain
p
∗
=
π
K
∗
.
IV. D
ISCUSSION AND EXTENSIONS
Here, we discuss our main result in more detail. We begin by
considering cases where Theorem 1 is helpful to the network planner
in Section IV-A. Then in Section IV-B, we present an extension of
our result to the case with losses in the network. We comment on
the importance of convexity in the problem formulation in Section
IV-C and finally explore storage placement at buses with multiple
connections in Section IV-D.
A. Applicability of Theorem 1
Figure 3 depicts a few power networks, where Theorem 1 applies,
i.e., network topologies with generator buses that have single con-
nections. While this may seem quite restrictive, in practice, many
networks have generators of this type. The single generator single
load case in Figure 3a models topologies where generators and loads
are geographically separated and are connected by a transmission
line, e.g., see [48]. This is common where the resources for the
generation technology (like coal or natural gas) are available far
away from where the loads are located in a network. Figure 3b is an
example of a radial network, i.e., an acyclic graph. Most distribution
networks conform to this topology
6
, e.g., see [29], [49]. Also, isolated
6
Two assumptions in our model hold for transmission networks but not
strictly for distribution networks: (a) Resistances in distribution lines are not
negligible and hence DC approximation does not generally apply [26], (b)
Three different types of loads, namely, constant power, constant current and
constant impedance loads show different behavior in distribution networks
[33]; but in aggregate, demands can be modeled as constant power loads in
transmission networks, as in IEEE distribution feeders [49].
transmission networks, e.g., the power network in Catalina island [5]
are radial in nature.
(a)
(b)
Fig. 3: Examples of power networks (a) Single generator single load
system (b) A radial network.
Next, we discuss how Theorem 1 defines an investment strategy
that is robust to many system parameters. Our result suggests that
it remains optimal not to place any storage at buses in set
K
even
if the demand profiles, generation capacities, line flow capacities or
admittances in the network change. Consider the example in Figure
3a. Suppose the line flow capacity is larger than the peak value of
the demand profile, i.e.,
f
12
≥
max
t
∈
[
T
]
d
2
(
t
)
. It can be checked
that placing all the available storage at the generator bus is also an
optimal solution. If at a later time during the operation of the network,
the demand increases such that the peak demand surpasses the line
capacity, this placement of storage no longer remains optimal and
requires new infrastructure for storage to be built on the demand side
to avoid load shedding. If, however, we use the optimum as suggested
by the problem
Π
K
and place all storage on the demand side from the
beginning, then this placement not only can accommodate the change
in the demand, but it also remains optimal under the available storage
budget. To explore another such direction, suppose another generator
is built to supply the load in Figure 3a. From Theorem 1, it follows
that we still do not need storage allocation at bus 1 even with the
extended network.
B. Modeling losses in the network
Our problem formulation uses linearized DC approximation for the
power flow equations. This approximation ignores all transmission
losses in the network. Here, we explore one popular way to incorpo-
rate losses and generalize the result in Theorem 1. To simplify the
presentation, consider the single generator single load network shown
in Figure 4. Generator at bus 1 is connected to a load at bus 2 using
a single line, i.e.,
K
=
N
G
=
{
1
}
and
N
D
=
{
2
}
. We make further
simplifications: assume
α
γ
=
α
δ
= 1
, i.e., the storage devices are
perfectly efficient. Hence, define for
t
∈
[
T
]
and
k
= 1
,
2
,
r
k
(
t
) :=
γ
k
(
t
)
−
δ
k
(
t
)
.
∼
1
2
r
2
(
t
)
r
1
(
t
)
b
1
b
2
|
p
12
(
t
)
|
≤
f
12
g
1
(
t
)
≤
g
1
d
2
(
t
)
Fig. 4: Single generator single load network. Available storage budget
is
h
≥
b
1
+
b
2
.
Recall that
p
12
is the power injected at bus 1 towards bus 2.
However, it suffers a loss before reaching bus 2. As detailed in
Appendix A, losses in such a network can be approximated to be
quadratic in the power sent, i.e., loss
≈
ξp
2
12
, where
ξ >
0
is some
positive constant that depends on the impedance of the transmission
line. Thus, power received at bus 2 is
p
12
−
ξp
2
12
. Then balancing
power on both buses, we get for
t
∈
[
T
]
,
p
12
(
t
) =
g
1
(
t
)
−
r
1
(
t
)
, p
12
(
t
)
−
ξp
2
12
(
t
) =
d
2
(
t
) +
r
2
(
t
)
.
(12)
Let the storage placement problem with losses incorporated be
P
L
. Following the definition of
Π
{
1
}
, define the restricted storage
placement problem with losses as
Π
{
1
}
,L
; this is essentially the
problem
P
L
with the extra constraint
b
1
= 0
. Let the optimal costs
of these problems be
p
L
∗
and
π
{
1
}
,L
∗
, respectively. With this notation,
we have the following result.
Proposition 1.
The storage placement problems with losses
P
L
and
Π
{
1
}
,L
satisfy
p
L
∗
=
π
{
1
}
,L
∗
.
In what follows, we provide a proof sketch; details are deferred to
Appendix B. Perhaps the first thing one notices about the problems
P
L
and
Π
{
1
}
,L
is that they are nonconvex due to the quadratic
equality in (12). Modify the problems
P
L
and
Π
{
1
}
,L
to their
convex relaxations
, where the second equality in (12) is changed to
p
12
(
t
)
−
ξp
2
12
(
t
)
≥
d
2
(
t
) +
r
2
(
t
)
. Call these relaxations as problems
ˆ
P
L
and
ˆ
Π
{
1
}
,L
, respectively. Let their optimal costs be
ˆ
p
L
∗
and
ˆ
π
{
1
}
,L
∗
, respectively. Using the set inclusion relations among the
feasible sets of the programs
Π
{
1
}
,L
,
P
L
and
ˆ
P
L
, it is easy to argue
that
ˆ
p
L
∗
≤
p
L
∗
≤
π
{
1
}
,L
∗
.
(13)
Then the proof proceeds in two steps. First, we show
ˆ
p
L
∗
= ˆ
π
{
1
}
,L
∗
and then prove that the relaxation
ˆ
Π
{
1
}
,L
is tight, i.e.
ˆ
π
{
1
}
,L
∗
=
π
{
1
}
,L
∗
. Using (13), it is straightforward to see that these two
statements imply Proposition 1.
We briefly discuss our result in Proposition 1 here. First, notice
that the optimization problem
P
L
is non-convex due to the constraint
in (12). Consequently, it is computationally hard to solve. However,
ˆ
Π
{
1
}
,L
considers a convex relaxation of this nonconvex constraint and
ˆ
Π
{
1
}
,L
is a convex program that often admits an efficient solution.
In addition, we have
p
L
∗
= ˆ
π
{
1
}
,L
∗
and thus
ˆ
Π
{
1
}
,L
provides a
computationally tractable way of
exactly
solving
P
L
. Second, notice
that Proposition 1 considers losses that are quadratic in the power
sent. The proof technique generalizes to the case with any
convex
function of the power sent. Third, we have presented Proposition 1 for
a two-node network only. This idea can be generalized to a network
with losses to derive a result similar to Theorem 1, i.e., in a network
with quadratic (or convex) losses, there exists an optimal storage
placement with zero storage at generators with single connections.
C. Effect of concave cost functions
Theorem 1 assumes a nondecreasing
convex
cost of generation;
this is commonly found in practice, e.g., the costs of coal-based
generators are often increasing quadratic functions [33]. Convexity is
sufficient for our result to hold, but may not be necessary. However,
the following example shows that the theorem need not generalize for
arbitrary non-decreasing functions. Consider the network in Figure 4
and let the cost of generation at bus 1 be a concave cost function
c
1
(
g
1
) = 2
g
1
, if
0
≤
g
1
≤
5
and
c
1
(
g
1
) =
g
1
+ 5
otherwise. With
T
= 2
, let the load bus have a demand profile
d
2
= (5
,
5)
and
f
12
= 5
connecting them. Further let
h
= 1
,
α
= 1
,
γ
=
δ
= 1
and
g
1
= 8
. All quantities are in per units. It can be checked that
the optimal generation profile of
Π
{
1
}
is
(5
,
5)
, thus,
π
{
1
}
∗
= 20
. On
the other hand, the generation profile
(6
,
4)
is feasible for
P
. Hence,
p
∗
≤
19
< π
{
1
}
∗
. We also remark that when
c
(
·
)
is not convex,
P
and
Π
K
are not convex programs and, hence, cannot be solved
efficiently.
D. On generators with multiple connections
Our result in Theorem 1 considers generator buses that have single
connections only. A natural direction to generalize the result is to
include generator buses with multiple connections. However, we show
through an example that generator buses with multiple connections
may not always have zero storage capacity in the optimal allocation.
Consider a 3-node network as shown in Figure 5. All quantities are
in per units. Let the cost of generation at node 1 be
c
1
(
g
1
) =
g
2
1
.
Let
T
= 4
and the demand profiles at nodes 2 and 3 be
d
2
=
(9
,
10
,
0
,
10)
and
d
3
= (0
,
10
,
9
,
10)
. Also, suppose that the line and
generation capacities are
f
12
=
f
13
= 9
.
5
and the available storage
budget is
h
= 5
. Finally, assume no losses and ignore the ramp
constraints in the charging and discharging processes, i.e.
α
= 1
and
γ
=
δ
= 1
. The optimal storage allocation
(
b
∗
1
,b
∗
2
,b
∗
3
)
for the two
problems
P
and
Π
{
1
}
is
(4
,
0
.
5
,
0
.
5)
and
(0
,
2
.
5
,
2
.
5)
, respectively.
Also, the optimal generation profile
g
∗
1
(
t
)
,t
= 1
,
2
,
3
,
4
for the two
problems can be computed to be
(14
,
15
,
14
,
15)
and
(12
,
17
,
12
,
17)
,
respectively. Thus,
p
∗
= 842
< π
{
1
}
∗
= 866
.
Fig. 5: A 3-node network with a generator bus with multiple
connections.
We provide some intuition behind the design of the counterexam-
ple. First, notice that if demands at buses 2 and 3 are multiples of
each other, i.e.,
d
2
(
t
) =
φd
3
(
t
)
for some constant
φ
≥
0
(and so
are the line capacities), the 3-node network can be roughly thought
of as two single-generator-single-load systems with nodes
(1
,
2)
and
(1
,
3)
, respectively and one can again prove that the generator node
does not need any storage capacity in an optimal allocation. We
formalize this statement in Proposition 5 in Appendix C. Thus to
expect
b
∗
1
6
= 0
in
P
, we consider demand profiles that show opposite
trends. Second, if
h
=
∞
or
h
is the minimum value required for
a feasible flow, we show in Proposition 4 in Appendix C that there
exists an optimal point with
b
∗
1
= 0
. Hence, we consider a storage
budget that is in the middle. Third, note that if line capacities are
large, then an optimal allocation with
b
∗
1
= 0
trivially exists. Thus,
we construct
f
12
=
f
13
= 9
.
5
for which
P
and
Π
{
1
}
are feasible
but the network is congested. This illustrates some key directions to
look at for characterizing cases where
b
∗
1
= 0
for generator buses
with multiple connections.
V. C
ONCLUDING REMARKS
In this paper, we formulate the optimal storage placement problem
for load shifting at slow time scales. We show in Theorem 1 that
generator nodes with single connections get zero storage capacity at
optimal allocation; this holds regardless of the demand profiles, gen-
eration capacities, line-flow limits and characteristics of the storage
technologies. The counterexample in Section IV-D shows that such
a general result does not hold beyond the settings in Theorem 1.
However, notice that the demand profiles of the two demand nodes
considered in this counterexample show opposite variations. When
demands vary similarly, e.g., in Appendix C (specifically Proposition
5), it can be shown that one does not need storage installed at the
generator node for the same network. This suggests that one would