1

Efficient Algorithm for Scalable Event-based
Demand Response Management in Microgrids

arXiv:1610.03002v1 [math.OC] 10 Oct 2016

Areg Karapetyan, Majid Khonji, Chi-Kin Chau Member, IEEE, Khaled Elbassioni, and
H. H. Zeineldin, Senior Member, IEEE

Abstract—Demand response management has become one of
the key enabling technologies for smart grids. Motivated by
the increasing demand response incentives offered by service
operators, more customers are subscribing to various demand
response programs. However, with growing customer participation, the problem of determining the optimal loads to be
curtailed in a microgrid during contingencies within a feasible
time frame becomes computationally hard. This paper proposes
an efficient approximation algorithm for event-based demand
response management in microgrids. In event-based management,
it is important to curtail loads as fast as possible to maintain
the stability of a microgrid during the islanded mode in a
scalable manner. A simple greedy approach is presented that can
rapidly determine a close-to-optimal load curtailment scheme to
maximize the aggregate customer utility in milliseconds for a
large number of customers. This paper further derives a novel
theoretical guarantee of the gap between the proposed efficient
algorithm and the optimal solution (that may be computationally
hard to obtain). The performance of algorithm is corroborated
extensively by simulations with up to thousands of customers.
For the sake of practicality, the proposed event-based demand
response management algorithm is applied to a feeder from the
Canadian benchmark distribution system. The simulation results
demonstrate that the proposed approach efficiently optimizes
microgrid operation during islanded mode while maintaining
appropriate voltage levels and network constrains.
Keywords—Demand response management, microgrids, approximation algorithms, integer variables.

N OMENCLATURE
N
n
k
uk
xk
X

Set of customers
Cardinality of customers’ set
Index of a customer
Utility of the k-th customer if his power demand
is not curtailed
Binary decision variable if the k-th customer’s
power demand is retained (i.e., not curtailed)
Set of customers whose power demand are retained (i.e., not curtailed)

A. Karapetyan, C.-K. Chau, and K. Elbassioni are with the Department of Electrical Engineering and Computer Science at Masdar Institute
of Science and Technology, UAE (e-mail: {akarapetyan, ckchau, kelbassioni}@masdar.ac.ae). M. Khonji is with Dubai Electricity and Water Authority (DEWA), Dubai, UAE (e-mail: majid.khonji@dewa.gov.ae). H. H.
Zeineldin is with the Electrical Engineering and Computer Science Department, Masdar Institute of Science and Technology, Abu Dhabi, United Arab
Emirates, and currently on leave from the Faculty of Engineering, Cairo
University, Giza 12316, Egypt. (email: hzainaldin@masdar.ac.ae)

Sk
Pk
Qk
C
θ
UMDR

Apparent power demand of the k-th customer,
represented by a complex number
Active power demand of the k-th customer, represented by a real number
Reactive power demand of the k-th customer,
represented by a real number
Total (apparent) generation power capacity
Maximum difference between the phase angles
of any pair of power demands.
Utility Maximizing Demand Response Problem
I.

M

I NTRODUCTION

ICROGRIDS (MGs) typically are medium-to-low voltage networks with integrated Distributed Generation
(DG), capable of operating in grid connected or islanded mode.
There is a high probability that an MG once initiated will be
short of power, consequently resulting in significant voltage
and frequency deviations, and leading to its instability. Designing an MG with the capability of operating in an islanded
mode can enhance system reliability and power quality.
Demand response (DR) programs can be broadly classified
into three classes: economic DR, emergency DR, and ancillary
services DR. In particular, emergency DR [1] is utilized when
there is insufficient supply of power to meet the available
demand, especially for MGs. DR is a key feature for smart
grids and can be used to alter loads during contingency conditions. DR has been proven to have many benefits including the
reduced price variations [2], increased reliability [3], enhanced
congestion management [4] and security enhancement [5].
Sudden islanding of MGs can cause high imbalances between the local generation and demand and thus, DR management strategies are required to ensure the endurance of an
MG during its autonomous operation [6]. The DR management
schemes for islanded MGs have received increasing attention
recently [7]. Innovative DR management strategies for MGs
can contribute to the improvement of stability especially during
emergency conditions [6]. The emergency DR methods, proposed in [6], [8], are based on local frequency measurement
to decide the on/off states of loads. However, such methods
do not take into account customer utility. In [9], a multistage centralized scheme for MGs is proposed in order to
minimize the load shedding cost. The problem is formulated
as a non-linear integer programming problem with power flow
equations and voltage limits, and is solved using a numerical
solver in a small scale. In [10], a DR scheme is proposed
to minimize the total amount of load shedding in order to
resolve the transformer overload. The aforementioned prior

2

studies concerning centralized demand management for MGs
have only considered systems with a small number of loads
(e.g., less than 50), and thus the optimization of operation for
an MG within a short time frame during emergency conditions
(within milliseconds) is plausible.
The energy management systems for control and optimization of MGs can be broadly classified into two groups,
distributed and centralized [11]. In [12]–[14] a centralized MG
control strategy is envisioned with the goal of effectively optimizing system operation and/or economic benefits. Usually,
centralized energy management approaches are more efficient
and, unlike the distributed ones, do not require computations
to be performed in each node of the network as well as do
not face synchronization problems. Distributed strategies, on
the other hand, do not suffer from the scalability problem and
are computationally tractable for large number of customers.
With growing customer participation, centralized energy management approaches for MGs require large and extensive computational resources, and thus a distributed energy management
approach is adopted in several prior studies. A distributed
energy management strategy that minimizes the dissatisfaction
of customers and power losses is proposed in [15]. In [16]
a scalable DR scheme is proposed due to a large number of
customers who need to be managed. The main objective is
to maximize the aggregate utilities of the appliances in the
households and minimize power losses.
This paper proposes a scalable centralized event-based DR
management algorithm for MGs considering a large number of
customers. The proposed algorithm can pave the foundations
for more effective distributed strategies. The problem is formulated as an integer programming problem of determining which
loads to be curtailed, as to maximize the cumulative customer
utility subject to the maximum available MG capacity. This
problem is known to be computationally hard (in particular, it
is strongly NP- HARD to obtain an optimal solution). In this
paper, an efficient greedy algorithm is proposed to achieve
very short computational time (within a few milliseconds), in
spite of a large number of customers. An important aspect
of this approach is that it is capable of obtaining a closeto-optimal solution, with a theoretical guarantee of the gap
to an optimal solution. The proposed approach is empirically
evaluated in terms of computational time and quality of solution, compared with the conventional numerical solver (e.g.,
Gurobi). The observed computational time of the proposed
algorithm significantly outperforms that of the conventional
numerical solver by an order of 103 times faster. With regards
to the observed quality of solution of the proposed algorithm
depicted in Fig. 3 and Fig. 2 in Section V, the empirical results
of various practical case studies recorded up to 10% deviation
from the optimal solution generated by the numerical solver,
considering up to 1000 customers.
Lastly, we investigate the feasibility of the load curtailment
schemes produced by the proposed DR management algorithm
on a 4-bus feeder from Canadian benchmark distribution
system. The observed simulation results show that the solutions
produced by the proposed algorithm are feasible and do not
violate network constraints and voltage levels.

II.

P ROBLEM F ORMULATION

As mentioned earlier, most of the available literature considers a small number of customers. As indicated in [15], a
centralized controller for energy management will likely be
computationally demanding. One of the main challenges for
MGs is to maintain stable operations especially during the
islanded mode when there is a shortage of power. This paper
proposes a scalable framework for implementing an eventbased DR scheme that can optimally determine the loads
to be curtailed subject to a capacity constraint taking into
account significant customer participation. In this scheme,
each customer submits his reactive and active power demand,
and his utility that reflects how much he is willing to pay
if his demand is satisfied. This setting assumes a customer
submitting a single utility value that reflects the value of
retaining the complete set of own demands. It is noteworthy
to mention, that this scheme could be easily extended for
practical purposes such that a customer is allowed to submit
different utilities (independent of each other) for corresponding
subsets of own demands. This enables customers to prioritize
own demands based on their importance and value without
altering the proposed formulation. A computationally efficient
centralized MG controller with an objective of maximizing
the total utility of the satisfied customers is proposed. The
MG controller will be responsible for sending curtailment
signals to the corresponding customers. To effectively control
load curtailment, low-latency communication infrastructure
between the controller and customers using separate power
supply will be utilized in event-based DR management. Such
a low-latency communication infrastructure is enabled by the
standards of smart grid communication protocols [17].
A Utility Maximizing Demand Response (UMDR) problem
is formulated with an objective to maximize the total utility of
satisfiable customers:
(UMDR)
subject to

max

uk xk

(1)

Sk xk ≤ C ,

(2)

xk ∈{0,1}

X

X
k∈N

k∈N

where N is the set of customers, uk is the utility of kth customer, Sk = Pk + iQk ∈ C is the complex-valued
apparent power demand for k-th customer, C ∈ R+ is a
real-valued generation capacity of total apparent MG power.
Here, xk is a binary decision variable that takes value 1 if
and only if the k-th customer’s power demand is retained.
Note that the customers’ utilities may be provided in advance,
which will be taken into account during the islanding of
MGs. It is worthwhile mentioning that when deploying the
DR scheme practically time-varying customer utilities could
be incorporated. Particularly, this scheme relies on a dynamic
rather than a flat customer utility plan in which utilities could
fluctuate based on time of day, so empowering customers’
choice over utility values for peak and off-peak hours. Upon
initiation of the proposed algorithm, the respective utility value
is adopted according to the execution timing. In MGs, most

3

power demand can be attributed to customers’ demands, and
hence, the effect of transmission loss is negligible.
While UMDR problem as a Quadratically Constrained
Integer Programming (QCIP) problem is not entirely new
[18], its application to power systems was recently realized in
[19]. There were only few results in the literature concerning
UMDR problem unlike its well-known relaxations, namely
the classical 0-1 knapsack and continuous knapsack problems.
The former problem resembles the special case of UMDR
problem. Specifically, UMDR problem is equivalent to the
classical knapsack problem when setting zero reactive power,
namely, Qk = 0 for all k ∈ N . This seemingly small change
in the problem formulation, in effect, drastically impacts its
computational complexity. Note that UMDR is a quadratically
constrained integer programming problem, whereas the classical knapsack is a linear integer programming problem. The
latter problem is known to be weakly NP- HARD [20], in other
words, it is highly unlikely that there is any fully polynomial
time algorithm to compute the exact optimal solution.
On the other hand, the presence of complex-valued power
demands in UMDR problem creates substantially more challenging problem than the classical knapsack problem (which
is shown to be strongly NP- HARD [21]–[23]). Though there
exist in the literature a number of exact and approximation
algorithms for the classical knapsack problem including greedy
algorithms and dynamic programming [20], there is no known
efficient practical algorithm that can solve UMDR problem
with provable optimality guarantees. This paper provides an
efficient algorithm to compute solutions of UMDR problem
that are close to the optimal solution, with a precise theoretical
guarantee on their approximation ratio (that is, the deviation
of the computed solution from the optimal solution). Moreover, the algorithm yields a scalable running time, which is
necessary in event-based DR for MGs in practice.
A number of prior studies [10], [15], [16], [24]–[26] formulated the DR management problem as an optimal power
flow (OPF) problem with the objective of maximizing the
cumulative user utilities or minimizing the power supply costs,
losses or curtailed load, by considering continuous decision
variables. If the (discrete) binary decision variables (xk ) in
UMDR problem are allowed to be continuous variables,
such that xk ∈ [0, 1], then the resulting problem becomes a
convex quadratic programming problem, which can be solved
optimally in polynomial time, for e.g., by applying Interior
Point methods. Furthermore, a slightly modified variant of
the proposed algorithm with a worst-case guarantee notably
close to 1 can be devised while requiring only an order
of O(n log n) running time. However, setting the decision
variable (xk ) to be discrete or continuous alters not only the
complexity of UMDR problem but also affects its practical
application aspects. Particularly, the continuous case corresponds to customers having elastic (i.e., divisible) power
demands allowing partial curtailment. Whereas, the discrete
case requires a customer load either to be curtailed or retained
holistically. This paper focuses on the latter case where binary
decision variables (xk ) are incorporated since it is much harder
to solve and is more realistic in practice.
The non-linear power and voltage constraints present in the

OPF problem make it practically inefficient to exactly solve
the DR management problem in distribution systems even with
hundreds of customers. Most of prior work consider the convex
relaxation of the problem instead or employ conventional numerical solvers to tackle the non-linear optimization problem.
The conventional numerical solvers, as the one adopted in
this study, usually are not guaranteed to terminate within a
reasonable time frame (unless otherwise explicitly restricted)
and necessarily return optimal solutions for integer programming problems. For example, we observe that Gurobi optimizer
sometimes failed to terminate and return a solution to UMDR
problem considering the specified optimality parameters.
For the purpose of this study, we focus on analyzing and
solving the event-based DR management problem in islanded
MGs focusing on their special requirements, philosophy of
operation and problem specific practical constraints. Typically,
for large-scale power systems, power flow equations are included to guarantee that the voltage levels are within the IEEE
standard limits. This is unlikely to be an issue for isolated MGs
where the size of the grid is typically small and thus power
flow equations have been excluded from UMDR problem. It is
assumed that by maintaining a balance between the generation
and demand on the island the system voltages are within the
acceptable range. This assumption is also followed in [12],
[27]–[29].
In order to measure the quality of the computed solution, a
measure denoted by approximation ratio is defined as follows.
Definition 2.1: Let P
x∗k be an optimal solution to UMDR
problem and O PT , k∈N uk x∗k be the corresponding total
utility. An approximate solution with worst-case guarantee α ∈
[0, 1] to UMDR problem is a feasible solution (x̂k )k∈N ∈
{0, 1}n satisfying:
X
uk x̂k ≥ α · O PT
(3)
k∈N

and

X

Sk x̂k ≤ C.

(4)

k∈N

The worst-case guarantee α is also called the approximation ratio, which characterizes the ratio between the optimal
solution and the approximate solution. When α = 1, this
becomes an exact optimal solution. In the subsequent sections,
an efficient algorithm is presented with a definite worst-case
guarantee α independent of the number of customers.
III.

E FFICIENT A LGORITHMS

In this section, three greedy algorithms are presented, where
the first two follow from the conventional strategies, and the
last one is a novel strategy proposed in this paper. Without loss
of generality, assume |Sk | ≤ C for all k (since any demand
k with |Sk | > C cannot be part of any feasible solution). An
allocation (xk )k∈N can be equivalently represented by the set
of satisfied customers X P
, {k ∈ N | xk = 1}. For a subset
X ⊆ N , denote u(X) , k∈X uk .
The three greedy algorithms are described as follows.

4

1)

Greedy Utility Algorithm (GUA): First, sort the customers in N = {1, ..., n} by their utilities in a nonincreasing order (with arbitrary tie-breaking), such that
u1 ≥ u2 ≥ ... ≥ un .

2)

Then, select the satisfiable demands sequentially from
the first customer
P according to the order whenever
feasible (i.e.
k Sk xk ≤ C).
Greedy Demand Algorithm (GDA): Similar to GUA,
but sort the customers by the magnitudes of their
demands in a non-decreasing order, such that
|S1 | ≤ |S2 | ≤ ... ≤ |Sn | .

3)

(5)

(6)

Then, select the satisfiable demands sequentially from
the first customer
P according to the order whenever
feasible (i.e.
k Sk xk ≤ C).
Greedy Ratio Algorithm (GRA): Similar to GUA and
GDA, but sort the customers by the efficiency (i.e.,
uk
|Sk | ) in a non-increasing order, such that
u2
un
u1
≥
≥ ... ≥
.
|S1 |
|S2 |
|Sn |

(7)

Then, obtain the greedy solution X by selecting sequentially from the first customer
according to the order
P
whenever feasible (i.e.
k∈X Sk xk ≤ C). Find the
single customer with the highest utility (maxk∈N {uk }).
Lastly, output the solution with the higher utility between X and the highest utility customer. A flowchart
for GRA is depicted in Fig. 1.
It is worthy to note that GUA and GDA are the common strategies of standard load curtailment in practice [30].
However, unlike GRA, they may produce arbitrarily worse
solutions for UMDR problem when compared to the optimum
solution. This claim could be easily verified by considering the
following two simple examples of UMDR problem.
Example 1: Consider an instance with n = 2 and C = F ,
where F is a real positive number. For simplicity, consider
setting zero reactive power for all customers. Customer 1 has
demand of |S1 | = 1 and utility of u1 = 1 and customer 2 has
demand of |S2 | = F and utility of u2 = F .
The optimal solution set would consist of customer 2 thus
reaching an optimal solution value of F . Whereas, GDA would
select customer 1 thus producing a solution with value of 1.
For a suitably large selection of F the relative performance
guarantee of GDA compared to the optimal solution could be
arbitrarily close to 0.
Example 2: Consider the following instance with n = b
and C = 10, where b is an integer positive number greater
than 2. For clarity, consider setting zero reactive power for all
customers. Customer 1 has a demand of |S1 | = 10 and utility
of u1 = 10 and customers 2 to b have demand of 10/b and
utility of 9.
The optimal solution would be to select customers 2 to b
thus producing an optimal solution with value 9(b − 1). GUA,
instead, will select only customer 1 thus generating a solution
with a value of only 10. For considerably large values of b

Fig. 1: Flow chart for Greedy Ratio Algorithm (GRA).
the ratio between solutions generated by GUA and optimal
solution value could be arbitrarily close to 0.
In fact, among the three algorithms, only GRA possesses
a worst-case guarantee. More precisely, GRA provides a
solution that in the worst possible case is at least 12 cos θ2 of
the optimal solution for UMDR problem, as described in the
following theorem. Each customer’s power demand has a phase
angle between the reactive and apparent powers. Define θ to
be the maximum difference between the phase angles of any
pair of power demands of the customers.
Theorem 1: Algorithm GRA produces a feasible solution
within a worst-case guarantee of 12 cos θ2 of any optimal
solution of UMDR problem.
The appendix provides a detailed proof of Theorem 1. The
worst-case guarantee of GRA depends on the angle θ; the
smaller θ is, a better approximation guarantee is achieved. If
Pk
θ = 0, then all customers have the same ratio Q
. In practical
k
settings, the load power factor usually varies between 0.8 to 1
[31] and thus the maximum phase angle difference θ between
any pair of demands is restricted to be in the range of [0, 36◦ ].
This implies that the approximation ratio is at least 0.475.
It is worth mentioning that GRA achieves the aforementioned approximation ratio only in order of O(n log n) time.
One can notice from Fig. 1 that the algorithm requires three
basic procedures to terminate, namely sorting followed by
a linear iteration over the newly sorted set and determining
the customer with the highest utility. Each of the latter two

5

procedures require O(n) operations, while sorting could be
performed in order of O(n log n) time by adopting a wellknown sorting algorithm (e.g. Merge sort). Therefore, the
running time complexity of GRA is O(n log n + 2n) =
O(n log n).
IV.

S YSTEM AND S ETTINGS U NDER S TUDY

To evaluate the performance of the proposed algorithm, an
MG with an overall capacity of 2MVA and over thousands of
customers is considered. Each customer has a specific power
demand (including both active and reactive power) and a utility
that is generated according to a probability preference model.
The amount of generation on an MG is typically less than the
amount of demand and thus, the customers may suffer from a
reduction of generation capacity occasionally. Various types
of loads are considered including residential and industrial
customers ranging between 300KVA to 1MVA. It is also
assumed that the MG is equipped with a two-way communication infrastructure capable of sending the optimal load
management signals (determined by the centralized controller)
and allowing for customer demand and utility to be sent back
to the centralized controller. The central controller is assumed
to have full control over the on/off operations of its customers.
In order to quantify the performance of the proposed algorithm, Gurobi optimizer is employed to obtain the close-tooptimal solutions numerically. In this paper, the output solution
of Gurobi optimizer is denoted by O PT. The following parameters were set in Gurobi optimizer: (1) the total time expended
for solving the problem was 200 seconds, (2) absolute mixed
integer programming (MIP) optimality gap (i.e., the threshold
of the absolute gap between the lower and upper objective
bound) was set to zero, and (3) infeasibility tolerance was
set to 10−9 . It is worth noting that there are no guarantees
that given an integer programming problem the optimizer will
return an optimal solution nor it will terminate in a reasonable
time (i.e., within 200 seconds for each run). Whenever the
optimizer exceeds the time limit, the current best solution is
considered to be optimal.
The simulations were evaluated using 2 Quad core Intel
Xeon CPU E5607 2.27 GHz processors with 12 GB of RAM.
The algorithms were implemented using Python programming
language with Scipy library for scientific computation. The
power system analysis package PSCAD was utilized for testing the load curtailment schemes produced by the proposed
algorithm. Typically, the load power factor varies between 0.8
to 1 and thus the maximum phase angle θ between any pair
of demands is restricted to be in the range of [0, 36◦ ].
Various case studies are performed to evaluate the proposed
algorithm by taking into account the correlation between
customer load and utility considering various load types. The
following are settings for the case studies in this paper.
(i) Utility-demand correlation:
a) Correlated setting (C): The utility of each customer is a function of the power demand:
2

uk (|Sk |) = a · |Sk | + b · |Sk | + c ,

where a > 0, b, c ≥ 0 are constants. For simplicity, uk (|Sk |) = |Sk |2 is considered in the
simulation.
b) Uncorrelated setting (U): The utility of each
customer is independent of the power demand
and is generated randomly from [0, |Smax (k)|].
Here Smax (k) depends on the customer type (as
defined below): if customer k is an industrial
customer then |Smax (k)| = 1MVA, otherwise
|Smax (k)| = 5KVA.
(ii) Customer types:
a) Residential (R) customers: The customers are
comprised of residential customers having small
power demands ranging from 500VA to 5KVA.
b) Mixed (M) customers: The customers are comprised of a mix of industrial and residential
customers. Industrial customers have big power
demands ranging from 300KVA up to 1MVA and
constitute no more than 20% of all customers
chosen at random.
In this paper, the case studies will be represented by the
aforementioned acronyms. For example, the case study named
CM stands for the one with mixed customers and utilitiesdemand correlation.
V.

S IMULATION R ESULTS

A. Comparative Analysis
In this subsection the proposed approaches are compared in
terms of quality of solution. The optimal solutions computed
by Gurobi are considered to be the base case for the comparison. The algorithms are applied to various case studies
where each case study is analyzed considering changes in the
set of customers. As an example, GRA is applied 30 times
for each of the m number of customers (where m varies
between 100 to 1500 in steps of hundred) for case study CR
(i.e., correlated, residential) considering random changes in
demands and utilities of customers. Thus, the total number of
experiments for each case study is 450. In particular, Table I
highlights the results obtained using GRA, GUA, and GDA
for the various case studies. The results in Table I present the
minimal ratio between the solutions obtained by the proposed
algorithms and Gurobi. It is worthy to note that the closer this
value is to 1, the closer is the solution to the optimum.
TABLE I: The worst-case approximation ratios of GRA,
GUA, and GDA with respect to the optimal solutions computed by Gurobi optimizer.

GRA
GUA
GDA

(8)

C

U

R

0.999

0.883

M

0.921

0.568

R

0.999

0.934

M

0.921

0.403

R

0.541

0.839

M

0.002

0.262

6

1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

CR

GDA

GUA

CM

1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

UR

200 400 600 800 1000 1200 1400

1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

UM

200 400 600 800 1000 1200 1400

Number of customers

Maximized utility

Approximation ratio

GRA

GRA
9
x10
9
8
7
6
5
4
3
2
1
0
6
3.0 x10
2.5
2.0
1.5
1.0
0.5
0.0
200 400 600

CR

OPT

GDA

12
2.0 x10

GUA

CM

1.5
1.0
0.5
0.0
6
UM
5.5 x10
5.0
4.5
4.0
3.5
3.0
2.5
2.0
1.5
200 400 600 800 1000 1200 1400
800 1000 1200 1400

UR

Number of customers

Fig. 2: The average approximation ratios of GRA, GUA and Fig. 3: The average objective values of GRA, GUA, GDA
GDA against the number of customers at 95% confidence and O PT against the number of customers at 95% confidence
interval.
interval.
As can be observed from Table I when there is a utilitydemand correlation for all customers, GRA and GUA obtain
solutions that are very close to the optimal O PT. Furthermore, for all the case studies GRA provides the highest
approximation ratio in the worst-case (worst-case of GRA
is 0.568, while that of GUA is 0.403) when compared to
other candidate algorithms. Figure 3 presents the maximized
utility for the three algorithms at 95% confidence interval
considering different customer set cardinality. Similarly, each
point presented in Fig. 3 represents the average objective value
among 30 iterations. It was observed experimentally that 30
iterations was sufficient for convergence of the sample mean
and variance.
It is observed that GDA performs the worst in terms of
the quality of solution. In fact, GDA performance degrades
significantly as the number of customers increase when there
is correlation between utilities and demands. The reason is that
GDA heuristically selects the smallest demands first which
on contrary obtain lower utility when considering a quadratic
utility function. This situation does not occur when there is
no such correlation (namely, in case studies UR and UM). For
case study UR, the observed performance of GUA is slightly
better than that of GRA when considering large customer
participation. This could be due to the fact that with increasing
customer participation the probability of having a customer
with a small utility but high utility to demand ratio increases.
Unlike GUA, GRA selects those customers first thus failing
to consider the customers with relatively large utilities. All
algorithms can output optimal solutions when having only
few residential customers, because at this scale all customers’
demands are below the total capacity of 2MVA and hence can
be all satisfied (see case studies CR and UR in Fig. 3).
The observed approximation ratios are plotted in Fig. 2
against the number of customers for each scenario. When
a curve is close to the line y = 1, it indicates a close to
optimal solution. The observed approximation ratios of GRA
and GUA are approximately 1 for case studies CR and CM

for scalable number of customers. As highlighted earlier, the
theoretical guarantees on the worst-case approximation ratio
of GRA is 0.475, computed using θ = 36 degrees (refer to
Theorem 1). Nevertheless as can be observed from Table I
GRA, for the majority of cases, can achieve almost twice
higher approximation ratio compared to the theoretical bound.
B. Computational Running Time
As stated earlier a major problem with most of the available
centralized demand management schemes is the computational
time. It is very important to develop fast and efficient algorithms capable of executing optimal decisions when considering significant customer participation. Thus, one of the key
parameters utilized to evaluate the performance of the proposed
algorithm is the computational time.
In this subsection the computational time of the proposed
GRA is compared against the Gurobi solver. Computational
time is of significant importance when designing centralized
controllers for MGs since this will have implications on the
stability of MG. Note that the running time complexity of
GUA and GDA is the same as that of GRA. For clarity of
presentation, however, we investigate only the running time of
GRA.
The running time of GRA is compared to that of Gurobi
optimizer in Fig. 4. For brevity, only the results related to a
case study CR are presented in Fig. 4. However, it is worthy to
note that nearly the same running time was observed for GRA
and Gurobi optimizer when considering the rest case studies.
The computational time reported is the average running time
over 30 iterations. As can be observed, for an MG with roughly
600 customers the centralized controller operated using Gurobi
solver will take roughly 5 seconds.
In these case studies it is expected that the MG will not be
capable of maintaining stable operation. On the contrary, for
the same number of customers the computational time needed
for the GRA is nearly 5 milliseconds. This would allow load

7

Running time (milliseconds)

management decisions to be made almost instantaneously and
thus allowing for the MG to stabilize.
For an MG with up to 1400 customers, the GRA is
capable of providing close to optimal solutions in less than
10 milliseconds. Furthermore, it is worthy to mention that for
some cases the Gurobi optimizer did not return an optimal
solution within 200 seconds, but on the contrary GRA can
always output a solution in nearly linear time.
1

4.0 x10
3.5
GRA
3.0
2.5
2.0
1.5
1.0
0.5
0.0
200 400 600 800 1000 1200 1400

4

4.0 x10
3.5
OPT
3.0
2.5
2.0
1.5
1.0
0.5
0.0
200 400 600 800 1000 1200 1400

Number of customers

Fig. 4: The average running time of GRA (left) and O PT
(right) against the number of customers at 95% confidence
interval.
C. Dynamic Generation Capacity
The previous subsections considered an MG with a fixed
generation capacity of 2MVA and varying load capacities.
Here simulations are performed considering the case when the
MG’s generation capacity is varying over time due to possible
occurrences (e.g., due to failure, maintenance or resumption),
whereas the set of customers of cardinality 1000 is fixed.
GRA

OPT

0

Capacity

2000

4000

UR

6000

8000

10000
10 6 x 2.5
2.0
1.5
1.0
0.5
0.0

Capacity

Maximized utility

4
3
2
1
0

Capacity
10 6 x 2.5
2.0
1.5
1.0
0.5
0.0

UM

7

1.0 x10
0.8
0.6
0.4
0.2
0.0
0
6
5 x10

2000

4000

6000

Time (seconds)

8000

10000

Fig. 5: The maximum utility of GRA and O PT considering
dynamic generation capacity.
The generation capacity of MG is dynamically varied between 100KVA and 2MVA and is applied to the proposed
problem formulation from time 0 to 10000 (seconds). The
events, namely Failure and Resumption, occur according to an
exponential distribution with a rate of 0.005. When the MG is

in the Failure state, the generation capacity decreases randomly
from 5% − 35%, whereas when in the Resumption state the
MG’s generation capacity is fully resumed (i.e., C = 2MVA).
Whether an event is in a Failure or Resumption state, is
determined according to a Markov chain with the following
settings:
1) Steady → Failure with a probability of 65%.
2) Steady → Resumption with a probability of 35%.
In Fig. 5, GRA’s maximum utility is slightly lower than O PT
in both case studies UM and UR (other case studies, namely
CM and CR, GRA is even closer to O PT). It is observable that
the gap between GRA and O PT is reduced when the generation
capacity is reduced due to the Failure events. The results show
that GRA is capable of obtaining close to optimal solutions
under various case studies with minimal computational time.
D. Application on a Feeder of Benchmark Canadian System
The proposed algorithm is applied to one of the feeders of
the Canadian benchmark bystem. The power system simulation
software PSCAD has been employed to simulate the feeder
which is rated at 8.7MVA, 400A and 12.47KV. Each feeder
section is a 700MCM Cu XLPE cable with Z = 0.1529 +
J0.1406 Ω/km. Each node consists of a 2MVA total load
as given in Fig. 6. Overall, up to 1500 customers have been
allocated among the nodes.
To account for the losses in the system, the worst case is
executed where it is assumed that a total of 8MVA will be
allocated at the end of feeder (bus 4). The maximum losses
expected under such case is Ploss = 24.4KW and Qloss =
22.496KVA. This amount of power losses is allocated in each
iteration and withheld from the maximum MG DG capacity.
This is done to assure sufficient power balance between load,
losses and generation. Figures 7 and 8 present the active and
reactive demand generated by the DG source, consumed by
the load at bus 4 as well the voltage for 20 iterations of utility
bidding for case studies CR and CM respectively. As can be
seen, the total generated capacity is less than 4MVA to account
for losses. The voltage of the end of the feeder (bus 4) is within
the IEEE standard 1547 limits.
Bus1

Bus2

Bus3

Bus4

4 MVA
2 MVA Load

2 MVA Load

2 MVA Load

2 MVA Load

Fig. 6: A 4-bus feeder from Canadian benchmark distribution
system.
E. Network and Voltage Constraints
In this subsection the proposed algorithm GRA is extended
to consider network and voltage constraints, and is applied
on a feeder from the Canadian benchmark distribution system
depicted in Fig. 6. The extended algorithm, denoted by GRA PF
is a heuristic approach for producing load curtailment schemes
which maximize the cumulative utility of the satisfied customers without violating the network and voltage constrains.
The execution of GRA PF is identical to that of GRA but with

8

Active power (MW)
Reactive power (MVAR)

Active power (MW)
Reactive power (MVAR)

Total Supplied

Active and Reactive Power

Active and Reactive Power

4
3
2
1
1.2

Bus 4

1
0.8
0.6

2
1

Bus 4

1.25
1
0.75
0.25

0.2

Bus 4

Voltage (p.u.)

Voltage (p.u.)

3

0.5

0.4

0.995
0.994
0.993
0

Total Supplied

4

2

4

6

8

10

12

14

16

18

20

Bus 4
0.995
0.994
0.993
0.992
0

2

4

6

8

10

12

14

16

18

20

Iteration

Iteration

Fig. 7: The generation capacity of MG, load and voltage profile Fig. 8: The generation capacity of MG, load and voltage profile
on bus 4 for case study CM.
on bus 4 for case study CR.
GRA

CR

1.2
1.1
1.0
0.9
0.8
0.7
0.6
0.5
600 800 1000 1200 1400 1600

GRAPF

UM
7.0 x10
6.5
6.0
5.5
5.0
4.5
4.0
3.5
3.0
2.5
600 800 1000 1200 1400 1600
6

Number of customers

Fig. 9: The average objective values of GRA PF , GRA and
OPT OPF against the number of customers at 95% confidence
interval.

Running Time (seconds)

Furthermore, the UMDR problem is formulated in an optimal power plow framework, and is denoted by UMDR-OPF
which is presented in the appendix. To compare the quality
of solution and computational running time of both GRA
and GRA PF algorithms, we generalize the previous simulations in subsection V-D. The solutions computed by Gurobi
optimizer for UMDR-OPF problem denoted by OPT OPF are
considered as a base case for comparison. As mentioned in
subsection V-D, the amount of Ploss = 24.4KW and Qloss =
22.496KVA is suppressed from MG generation capacity in
each iteration when GRA is executed. On the other hand, for
GRA PF , the problem is solved considering full MG generation
capacity (i.e., C = 4MVA) since the load flow equations
account for power losses.
The results in Figs 9 and 10 illustrate the maximized utility
and running time of GRA, GRA PF and OPT OPF algorithms
at 95% confidence interval. As observed from Fig. 9, the
former two algorithms achieve significantly close solutions to
OPT OPF for all case studies. The results illustrated in Fig. 9
show that the objective value of GRA is nearly the same and
sometimes slightly lower than that of GRA PF since GRA
employs a worst-case approach for quantifying the system
losses. For optimizing the MG operation with 1400 customers,
GRA required nearly 10 milliseconds, whereas GRA PF terminated nearly in 20 seconds. It is worthy to mention that the
solutions obtained by Gurobi (OPT OPF ) require approximately
60 seconds for an MG with 1400 customers. The running
time of the candidate algorithms plotted in Fig. 10 reflects
the trade-off between optimality and scalability in the context
of computational complexity.

OPTOPF
x10 10

Maximized utility

an additional subroutine of performing load flow and checking the capacity, voltage and network constrains with each
customer addition. However, the feasibility of the generated
solutions by GRA PF comes with a cost of increased running
time (refer to Fig. 10) and the absence of theoretical guarantees
as compared to GRA.

140
GRA
120
GRAPF
100
OPTOPF
80
60
40
20
0
600 700 800 900 1000 1100 1200 1300 1400 1500 1600

Number of customers

Fig. 10: The average running time of GRA PF , GRA and
OPT OPF , against the number of customers at 95% confidence
interval.

9

A PPENDIX
In the appendix, the full proof of Theorem 1 is presented
followed by the formulation of UMDR-OPF problem.

Reactive Power

A. Proof of Theorem 1
Proof: First, note that the problem is invariant, when the
arguments of all complex-valued demands are rotated by the
same angle (see Fig. 11 for an illustration).

(i.e., the argument) that any other demand makes with S1 (see
Fig. 11 for an illustration). Note that in practice θ < π2 , because
there are regulations that require electric equipment to conform
with a certain maximum power factor. More precisely, θ is
usually restricted to be in the range of [0, 36◦ ] [31]. For the
clarity of presentation, this paper assumes (via a rotation) that
Pk ≥ 0 and Qk ≥ 0.
Reactive Power

VI. C ONCLUSION
This paper presents a computationally efficient centralized
algorithm for event-based DR management in MGs considering a large number of customers. The proposed algorithm
relies on a greedy approach with a provable approximation
guarantee. Various greedy strategies are analyzed and compared to identify the most efficient one in terms of quality
of the solution. Furthermore, the proposed greedy approach
is compared, in terms of computational time, to Gurobi optimizer known for its efficient computational speed. The results
show that the Greedy Ratio Algorithm (GRA) is superior
over the other strategies in terms of quality of the solution.
The proposed algorithm is capable of optimizing the demand
management in MGs with a large number of customers within
acceptable time. For the majority of case studies the proposed
algorithm demonstrated near optimal performance in little
computational time which is an essential feature for eventbased DR management in MGs. Lastly, we investigate the
feasibility of the produced solutions by GRA algorithm on
a feeder from Canadian benchmark distribution system. The
simulation results confirm that the produced solutions do not
violate network constrains and voltage levels. Recently, this
work has been extended to consider scheduling, optimal power
flow and online setting [32]–[34].

solve

Active Power

Fig. 12: The red vectors (thick arrows) represent a feasible
solution to UMDR such that the total magnitude of the red
demands lies within the radius C.
Denote by Z GRA the utility of the output solution of GRA.
∗
Let
P S ⊆ N be an optimal solution of UMDR, and the O PT ,
k∈S ∗ uk be the corresponding total utility.
If customers’ complex-valued power demands are substituted in UMDR problem by its real-valued magnitude and
the binary decision variable xk is relaxed such that it takes
non-negative real values instead of only integers values (i.e.,
(xk )k∈N ∈ [0, 1]n ) the following linear programming (LP)
problem is formulated as follows:
(LP1)
subject to

X

max

uk xk

(11)

|Sk |xk ≤ C

(12)

xk ∈[0,1]

X

k∈N

k∈N

rotate

Active Power

Fig. 11: Each vector represents a power demand Sk . The figure
shows that the demands are rotated by the same angle. θ is the
maximum angle between any pair of demands.

DenotePby SL∗ ⊆ N an optimal solution of LP1 and by
O PTL , k∈S ∗ uk the corresponding total utility. In chapter
L
2 of [20] it was shown that the optimal solution to LP1
problem can be determined easily, since the problem admits the
greedy choice property. In other words, a global optimum of
the problem can be achieved by choosing a series of locally
optimal choices. The greedy choice for LP1 problem is to
select customers in sorted order defined by Eqn. (7). Assume
at some iteration t adding the next customer to X that causes
capacity constraint violation, that is
t−1
X

|Sk | ≤ C and

k=1

Each customer’s power demand has a phase angle between
the reactive and apparent powers. Define θ to be the maximum
difference between the phase angles of any pair of power
demands of the customers (see Fig. 11). Without loss of
generality, this paper assumes that one of the demands, say
S1 is aligned along the positive real axis, and defines a class
of sub-problems, by restricting the maximum phase angle θ

t
X

|Sk | > C.

(13)

k=1

The greedy execution is stopped at this point and the remaint−1
P
ing capacity C −
|Sk | is occupied by the corresponding
k=1

fractional part of the t-th customer’s power demand. Observe
that the preceding greedy strategy is the adapted version of
GRA algorithm for the relaxed UMDR problem with continuous decision variable (xk )k∈N ∈ [0, 1]n and complex-valued

10

Pn

i=1

|di |2 + 2

P

1≤i<j≤n

Pn

2
i=1 |di | + 2
1≤i<j≤n |di | · |dj |
Pn
P
2+2
|d
|
i=1 i
1≤i<j≤n |di | · |dj | cos(θi

|di | · |dj |

P

=
|di | · |dj |(sin θi sin θj + cos θi cos θj )
Pr
( i=1 |di |)2
= r
.
X
X
X
2
|di | + 2
|di ||dj | cos(θi − θj ) + 2|dr |
|di | cos(θi − θr )

Pn

i=1

|di |2 + 2

i=1

P

1≤i<j≤n

1≤i<j<r

power demands. Let p̂ ,

uk and umax , maxk∈N uk . It

k=1

k=1

Evidently, Z

GRA

|Sk |)

ut
≤ p̂ + umax .
|St |

O PTL ≤ Z GRA + umax .

(14)

(15)

On the other hand, by Lemma 1 below it follows that
X
X
Si ≤ C ,
(16)
|Si | ≤
cos θ2 ·
i∈S ∗

since θ is restricted to be at most π2 . Note that the subset S ∗
becomes a feasible solution to LP1 if the relaxed decision
variable is set xi = cos θ2 for ∀i ∈ S ∗ and xi = 0 otherwise.
This implies that
O PTL ≥ cos θ2 · u(S ∗ ) = cos θ2 · O PT.

(17)

In GRA, Z GRA ≥ umax , and hence by Eqns (15) and (17)
it follows that
Z GRA ≥

where

1 + x2 + 2x
.
1 + x2 + 2x cos θ

The first derivative f 0 (x) =

≥ p̂. This gives

i∈S ∗

(10)

f (x) ,

was also shown in [20] that

O PTL = p̂ + (C −

(9)

1≤i<r

t−1
P

t−1
X

− θj )

1
cos θ2 · O PT.
2

(18)

Lemma 1: Given a set of 2D vectors {di ∈ R2 }ni=1
Pn
|di |
Pi=1
≤ sec θ2 ,
n
d
i=1 i
where θ is the maximum angle between any pair of vectors
{di ∈ R2 }ni=1 and 0 ≤ θ ≤ π2 .
Proof: The below statement will be proven by induction:
Pn
( i=1 |di |)2
2
Pn
≤
cos θ + 1
| i=1 di |2
q
Note that sec θ2 = cos 2θ+1 .
First, expand the left hand side in Eqn. (9), where θi is the
angle that di makes with the x axis.
Consider the base case: n = 2. Eqn. (9) is
 |d | 
|d1 |2 + |d2 |2 + 2|d1 | · |d2 |
2
=f
,
(19)
2
2
|d1 | + |d2 | + 2|d1 | · |d2 | cos(θ)
|d1 |

(1 + x2 + 2x cos θ)(2x + 2) − (1 + x2 + 2x)(2x + 2 cos θ)
(1 + x2 + 2x cos θ)2
is zero only when x = 1. Hence, f (1) is an extreme point.
Compare f (1) with f (x) at the boundaries x ∈ {0, ∞}:
f (1) = cos 2θ+1 ≥ f (0) = limx→∞ f (x) = 1. Therefore, f (x)
has a global maximum of cos 2θ+1 .
Next proceed to the inductive step. Assume that
r
Pr−1
2
i=1 |di |
,
≤
Pr−1
cos θ + 1
i=1 di
where r ∈ {1, . . . , n}. Without loss of generality, assume θ1 ≥
θ3 ≥ · · · ≥ θn ≥ θ2 .
Eqn. (9) can be rewritten to obtain Eqn. (10).
Let g(θr ) be the denominator of Eqn. (10). Take the second
derivative of g(θr ):
X
g 00 (θr ) = −2|dr |
|di | cos(θi − θr ).
1≤i<r

Note that cos(θi − θr ) ≥ 0, and hence, the second derivative
is always negative. This indicates that all local extreme in
[0, θr−1 ] of g(θn ) are local maximum. Hence, the minimum
occur at the boundaries:
min

θr ∈[0,θr−1 ]

g(θr ) ∈ {g(0), g(θr−1 )}

(20)

If θr ∈ {0, θr } there must exist at least a pair of vectors in
{di }ri=1 with the same angle. Combining these two vectors into
one, one can obtain an instance with r − 1 vectors. Hence, by
the inductive hypothesis, the same bound holds up to r vectors.

B. Formulation of UMDR-OPF Problem
The constrains present in OPF problem are broadly defined in the literature by two models, namely Bus Injection
Model (BIM) and Branch Flow Model (BFM) (a.k.a DistFlow
model) [35]. Variables in BIM (i.e., voltage and power) are
assigned for every bus (or node). On the other hand, variables
in BFM are assigned for every branch (or edge). BFM was first
proposed by [36]. It was shown by [37] that both models are in
fact equivalent. In this paper we utilize BFM model [35] for

11

introducing voltage, network and operational constrains into
UMDR problem.
In order to model the power flow constrains we represent
an MG by a graph G = (V, E). The set of nodes V denote
the buses, whereas the set of edges E denote the distribution
lines. We index the nodes in V by {0, 1..., |V|}, where the node
0 denotes the generation source or MG. For node i ∈ V, we
denote its voltage by Vi ∈ C. For each edge e = (i, j) ∈ E, we
denote its current from i to j by Ii,j , its transmitted power by
Ŝi,j , and its impedance by zi,j ∈ C (also denoted by ze ). Let
vi , |Vi |2 and `i,j , |Ii,j |2 be the magnitude square of voltage
and current respectively. For each node i ∈ V\{0}, there is a
set of customers attached to i, denoted by Ni . Given a complex
number ψ ∈ C, denote its real and imaginary components
by Re(ψ) and Im(ψ) respectively, and its complex conjugate
by ψ ∗ . Let vmin , vmax ∈ R+ be the minimum and maximum
allowable voltage magnitude square at any node. We define the
UMDR-OPF problem by the following mixed integer nonlinear programming problem.
X

max

(UMDR-OPF)

xk ,vi ,`i,j ,Ŝi,j

[3]

[4]

[5]

[6]

[7]

[8]

[9]

uk xk
[10]

k∈N

2

|Ŝi,j |
,
∀(i, j) ∈ E
(21)
v
X
Xi
=
Sk xk +
Ŝj,l + zi,j `i,j , ∀(i, j) ∈ E

s.t. `i,j ≥
Ŝi,j

k∈Nj

[11]

l:(j,l)∈E

(22)
∗
vj = vi + |zi,j |2 `i,j − 2Re(zi,j
Ŝi,j ),

[12]

∀(i, j) ∈ E (23)

|Ŝ0,1 | ≤ C
vmin ≤ vj ≤ vmax , ∀j ∈ V\{0}
xk ∈ {0, 1},
∀k ∈ N

(24)
(25)
(26)

vi ∈ R+ , `i,j ∈ R+ , Ŝi,j ∈ C

(27)

We remark that OPF problem is non-convex due to the
quadratic equality constraints

[13]

[14]

[15]

[16]
2

`i,j =

|Ŝi,j |
,
vi

∀(i, j) ∈ E

(28)

and thus is computationally intractable in general. We therefore
consider relaxing them to inequalities (21) in UMDR-OPF
problem to convexify the problem. Due to the same reason
in [15], [35] the same relaxation is adopted. Obviously, when
the equality in (21) is attained in the solution to UMDR-OPF
then the OPF relaxation is exact.

[17]
[18]

[19]

[20]

R EFERENCES
[21]
[1]

W. Chen, X. Wang, J. Petersen, R. Tyagi, and J. Black, “Optimal
scheduling of demand response events for electric utilities,” IEEE
Transactions on Smart Grid, vol. 4, no. 4, pp. 2309–2319, Dec 2013.
[2] C.-L. Su and D. Kirschen, “Quantifying the effect of demand response
on electricity markets,” IEEE Transactions on Power Systems, vol. 24,
no. 3, pp. 1199–1207, Aug 2009.

[22]

A.-H. Mohsenian-Rad and A. Leon-Garcia, “Optimal residential load
control with price prediction in real-time electricity pricing environments,” IEEE Transactions on Smart Grid, vol. 1, no. 2, pp. 120–133,
Sept 2010.
A. Khodaei, M. Shahidehpour, and S. Bahramirad, “Scuc with hourly
demand response considering intertemporal load characteristics,” IEEE
Transactions on Smart Grid, vol. 2, no. 3, pp. 564–571, Sept 2011.
Y. Wang, I. Pordanjani, and W. Xu, “An event-driven demand response
scheme for power system security enhancement,” IEEE Transactions on
Smart Grid, vol. 2, no. 1, pp. 23–29, March 2011.
C. Gouveia, J. Moreira, C. Moreira, and J. Pecas Lopes, “Coordinating
storage and demand response for microgrid emergency operation,” IEEE
Transactions on Smart Grid, vol. 4, no. 4, pp. 1898–1908, Dec 2013.
Y.-Y. Hong, M.-C. Hsiao, Y.-R. Chang, Y.-D. Lee, and H.-C. Huang,
“Multiscenario underfrequency load shedding in a microgrid consisting
of intermittent renewables,” IEEE Transactions on Power Delivery,
vol. 28, no. 3, pp. 1610–1617, July 2013.
K. Samarakoon, J. Ekanayake, and N. Jenkins, “Investigation of domestic load control to provide primary frequency response using smart
meters,” IEEE Transactions on Smart Grid, vol. 3, no. 1, pp. 282–292,
March 2012.
M. Abdelaziz, M. Shaaban, H. Farag, and E. El-Saadany, “A multistage
centralized control scheme for islanded microgrids with pevs,” IEEE
Transactions on Sustainable Energy, vol. 5, no. 3, pp. 927–937, July
2014.
B. Hayes, I. Hernando-Gil, A. Collin, G. Harrison, and S. Djokic,
“Optimal power flow for maximizing network benefits from demandside management,” IEEE Transactions on Power Systems, vol. 29, no. 4,
pp. 1739–1747, July 2014.
N. Hatziargyriou, A. Dimeas, and A. Tsikalakis, “Centralized and decentralized control of microgrids,” International Journal of Distributed
Energy Resources, vol. 1, no. 3, pp. 197–212, 2005.
A. Tsikalakis and N. Hatziargyriou, “Centralized control for optimizing microgrids operation,” IEEE Transactions on Energy Conversion,
vol. 23, no. 1, pp. 241–248, March 2008.
J. Peas Lopes, C. Moreira, and A. Madureira, “Defining control strategies for MicroGrids islanded operation,” IEEE Transactions on Power
Systems, vol. 21, no. 2, pp. 916–924, May 2006.
A. Mehrizi-Sani and R. Iravani, “Potential-function based control of a
microgrid in islanded and grid-connected modes,” IEEE Transactions
on Power Systems, vol. 25, no. 4, pp. 1883–1891, Nov 2010.
W. Shi, X. Xie, C.-C. Chu, and R. Gadh, “Distributed optimal energy
management in microgrids,” IEEE Transactions on Smart Grid, vol. 6,
no. 3, pp. 1137–1146, May 2015.
W. Shi, N. Li, X. Xie, C.-C. Chu, and R. Gadh, “Optimal residential
demand response in distribution networks,” IEEE Journal on Selected
Areas in Communications, vol. 32, no. 7, pp. 1441–1450, July 2014.
E. Hossain, Z. Han, and H. V. Poor, Smart Grid Communications and
Networking. Cambridge University Press, 2012.
G. J. Woeginger, “When does a dynamic programming formulation
guarantee the existence of a fully polynomial time approximation
scheme (FPTAS)?” INFORMS Journal on Computing, vol. 12, no. 1,
pp. 57–74, 2000.
L. Yu and C. Chau, “Complex-demand knapsack problems and incentives in AC power systems,” in International Conference on Autonomous
Agents and Multi-agent Systems (AAMAS), 2013, pp. 973–980.
H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems.
Springer, 2010.
C.-K. Chau, K. Elbassioni, and M. Khonji, “Truthful mechanisms for
combinatorial AC electric power allocation,” in International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2014.
——, “Truthful mechanisms for combinatorial allocation of electric
power in alternating current electric systems for smart grid,” to appear in ACM Transactions on Economics and Computation, 2016,
http://arxiv.org/abs/1507.01762.

12

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

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), Aug 2014, pp. 1–6.
N. Li, L. Gan, L. Chen, and S. Low, “An Optimization-based Demand
Response in Radial Distribution Networks,” in IEEE Globecom Workshops (GC Wkshps), Dec 2012, pp. 1474–1479.
B. Zhang, A. Lam, A. Dominguez-Garcia, and D. Tse, “An optimal and
distributed method for voltage regulation in power distribution systems,”
IEEE Transactions on Power Systems, vol. 30, no. 4, pp. 1714–1726,
July 2015.
T. Fernandes, J. Lenzi, and M. Mikilita, “Load shedding strategies using
optimal load flow with relaxation of restrictions,” IEEE Transactions on
Power Systems, vol. 23, no. 2, pp. 712–718, May 2008.
Z. Wang, K. Yang, and X. Wang, “Privacy-preserving energy scheduling
in microgrid systems,” IEEE Transactions on Smart Grid, vol. 4, no. 4,
pp. 1810–1820, Dec 2013.
Y. Zhang, N. Gatsis, and G. Giannakis, “Robust energy management
for microgrids with high-penetration renewables,” IEEE Transactions
on Sustainable Energy, vol. 4, no. 4, pp. 944–953, Oct 2013.
M. Moradi, M. Eskandari, and S. Mahdi Hosseinian, “Operational
strategy optimization in an optimal sized smart microgrid,” IEEE
Transactions on Smart Grid, vol. 6, no. 3, pp. 1087–1095, May 2015.
S. Hirodontis, H. Li, and P. Crossley, “Load shedding in a distribution
network,” in International Conference on Sustainable Power Generation
and Supply (SUPERGEN), April 2009, pp. 1–6.
P. Korovesis, G. Vokas, I. Gonos, and F. Topalis, “Influence of largescale 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, no. 4, pp. 1787–1793, Oct 2004.
M. Khonji, A. Karapetyan, K. Elbassioni, and C.-K. Chau, “Complexdemand scheduling problem with application in smart grid,” in International Conference of Computing and Combinatorics (COCOON).
Springer International Publishing, 2016, pp. 496–509.
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.
A. Karapetyan, M. Khonji, K. Elbassioni, and C.-K. Chau, “Online
Algorithm for Demand Response with Inelastic Demands and Apparent
Power Constraint,” Masdar Institute, Tech. Rep., 2016.
S. Low, “Convex relaxation of optimal power flow, part I: Formulations
and equivalence,” Control of Network Systems, IEEE Transactions on,
vol. 1, no. 1, pp. 15–27, March 2014.
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.
B. Subhonmesh, S. Low, and K. Chandy, “Equivalence of branch
flow and bus injection models,” in Annual Allerton Conference on
Communication, Control, and Computing (Allerton), Oct 2012, pp.
1893–1899.

