Electric Power Systems Research 105 (2013) 115–123

Contents lists available at ScienceDirect

Electric Power Systems Research

journal homepage: www.elsevier.com/locate/epsr

Enhanced priority list unit commitment method for power systems

with a high share of renewables
E. Delarue a , D. Cattrysse b , W. D’haeseleer a,∗
a
University of Leuven (KU Leuven) Energy Institute, TME branch (Applied Mechanics and Energy Conversion), Celestijnenlaan 300A box 2421,
B-3001 Leuven, Belgium
b
University of Leuven (KU Leuven) Centre for Industrial Management/Traffic and Infrastructure, Celestijnenlaan 300A box 2422, B-3001 Leuven, Belgium

a r t i c l e i n f o a b s t r a c t

Article history: Over the past decade, mixed integer linear programming (MILP) has become the preferential way to
Received 12 April 2013 solve unit commitment problems for electricity generation. However, as this paper demonstrates, this
Received in revised form 1 July 2013 method faces increasing computational difficulty when the residual demand (i.e., original demand minus
Accepted 28 July 2013
variable renewables) in a power system sinks to relatively low values. Hence, a new unit commitment
Available online 26 August 2013
method is developed to specifically solve problems with low residual demand. The algorithm is set up
based on an enhanced priority list of power plants (EPL). Plants are activated according to this list, while
Keywords:
schedules are adapted to respect technical restrictions as minimum up and down times, and minimum
Unit commitment
Power generation scheduling
operating points (particularly important in a low residual demand setting). The developed EPL algorithm
Priority list is compared to a MILP set up, first on a benchmark system and second on a low residual demand case.
Renewables Results are compared in terms of output and computational effort. Performance of the EPL algorithm is
Low residual demand very satisfying (both in terms of optimality and calculation speed), thereby demonstrating its usefulness
for real-life simulation and policy analysis, or, e.g., to be used in combination with MILP solvers to provide
a starting solution.
© 2013 Elsevier B.V. All rights reserved.

1. Introduction with. Also toward policy making and planning, this UC is useful
as a tool to perform market simulations and assess the impact of
The demand and supply of electricity need to be in constant specific measures. On the other hand, from the viewpoint of a sin-
balance. As demand for electricity has a typical diurnal, weekly gle market player, a price-based UC problem can be considered,
and seasonal pattern, power plants need to be carefully sched- optimizing output toward maximum profit, based on electricity
uled to meet this fluctuating demand. This scheduling optimization price forecasts [2]. This paper will focus on the first kind of UC, i.e.,
is known as the unit commitment (UC) problem and has been security-constrained UC. For the sake of simplicity, in the remainder
widely discussed in the literature. Traditionally, the UC problem of this paper, we will refer to this just as UC.
was solved centrally, minimizing overall system cost. With the lib- A wide range of solution techniques for the UC problem have
eralization of electricity markets worldwide, the aim is to operate been proposed and developed over the years. Examples include
the electricity generation systems with higher (economic) effi- priority listing (heuristics), Lagrangian relaxation, dynamic pro-
ciency. Focus has shifted to optimal economic performance and gramming, genetic algorithms, etc., together with hybrid methods
profit maximization. On the one hand, the UC problem can be combining several of these. For an overview of methods, see, e.g.,
considered from a system’s perspective, i.e., the so-called security- [3], and further in this paper. Over the past decade, especially mixed
constrained UC [1]. This type of UC is similar to the traditional UC integer linear programming (MILP) has been put forward [4,5].
and is what an independent system operator (ISO) currently deals Electric power systems worldwide are, however, changing. To
cut greenhouse gas emissions and for reasons of security of sup-
ply (in terms of strategic primary energy security), a massive
deployment of renewable energy sources (RES) like wind and solar
Abbreviations: EPL, enhanced priority list; ISO, independent system operator; photovoltaics (PV) is currently taking place or at least aimed for, in
MILP, mixed integer linear programming; PV, photovoltaics; RES, renewable energy certain countries (e.g., Germany) or states (e.g., California). These
sources; UC, unit commitment.
∗ Corresponding author. Tel.: +32 16 322511; fax: +32 16 322985.
renewable sources are characterized by a high degree of variability,
i.e., they only produce electricity when the wind blows or when
E-mail addresses: [email protected] (E. Delarue),
[email protected] (D. Cattrysse), the sun shines. A further massive deployment of these intermit-
[email protected] (W. D’haeseleer). tent renewables will render a net or residual load profile (as seen

0378-7796/$ – see front matter © 2013 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.epsr.2013.07.014
116 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123

operational solutions on relatively large sale, or use the model in

Nomenclature combination with other techniques such as MILP, to provide a start-
ing solution.
Sets
Toward this end, a new enhanced priority list (EPL) based
I power plants (index i; number of elements ni)
method is developed. Several priority list methods have been devel-
J time periods (index j; number of elements nj)
oped in the literature, e.g., [6–9]. These have a main focus on
L stepwise linear segments of output cost curve
computational speed and on increasing the level of optimality.
(index l; number of elements nl)
However, these models are typically not directly suited to be used
R ranked power plants (index r)
in settings with low residual load (where minimum load problems
T time periods, up to period j (index t; number of ele-
occur, or downward reserves become relevant). Furthermore, as far
ments nt)
as the impact of intermittent RES (e.g., wind) on generator sched-
uling algorithms is concerned, the focus in the literature has been
Parameters
mainly on dealing with the uncertainty (see, e.g., [10,11]). The issue
A fuel cost at minimum working point
of increasing computational effort for systems with low residual
a, b, c cost coefficients
demand has not really been addressed so far.
cc cold startup cost
Hence, in this paper, a new UC method is developed specifically
D demand
for low residual demand settings. As will be demonstrated, this new
F slope of segment of linearized cost
EPL based algorithm extends existing priority list methods such as,
FD weighting factor
e.g., [9], not only regarding computational efficiency, but especially
FMU parameter used in up time correction
regarding feasibility for low residual load problems.
G generation level to be used in cost metric M
This paper proceeds as follows. The next section presents the
hc hot startup cost
basic formulation of the UC problem. The third section describes the
Inist initial state
algorithm of the newly developed EPL method. The fourth section
L lower bound of operating range
provides the input data used in the simulations. Numerical results
LD low residual demand
are then presented in the fifth section. In a first case, the MILP and
M cost metric
EPL models are used on a benchmark system. In a second step, a
MDT minimum down time
specific low load case is set up and optimized (again both with MILP
MS cost metric for startup cost
and EPL). The difficulties faced by MILP to solve such problems are
MUT minimum up time
demonstrated, while the adequate performance of the EPL method
Pmax maximum output
is shown. The final section concludes.
Pmin minimum working point
R reserves
SC startup cost 2. Problem formulation
T upper limits of power segments (linearized cost
function) A basic cost based unit commitment optimization problem is
tcold offline period determining startup (hot or cold) considered. This problem has been described widely in the litera-
U upper bound of operating range ture. The description as presented below is partly based on [4].
The objective to be minimized is the total generation cost tc,
Variables which is equal to the sum of fuel costs fc and startup costs sc over
dt down time all power plants i and all time periods j (in this case hourly time
fc fuel cost steps):
g generation  
sc startup cost minimize tc = fc(i, j) + sc(i, j) (1)
tc total cost i,j i,j
ut up time
The fuel cost of a power plant is typically a quadratic function
z commitment status
of its output g and commitment status z (with a, b and c the cost
ı generation in power segment
coefficients, I the set of power plants and J the set of time periods)
[12]:
2
by the conventional dispatchable power plants) that is both lower fc(i, j) = ai · z(i, j) + bi · g(i, j) + ci · g(i, j) , ∀i ∈ I, ∀j ∈ J (2)
and more volatile.1 As will be demonstrated in this paper, compu-
This (convex) quadratic cost function can be linearized by a
tation times of MILP UC models increase heavily when (residual)
number of stepwise linear segments (set L, index l). Let Pmax and
demand levels are low compared to the overall system size. Hence,
Pmin be the maximum and minimum power output (if online),
the aim of this paper is to set up an adequate UC optimization tool
respectively, A the fuel cost at minimum output, Fl the slope of
that is able to cope with variable and low net demand profiles in
the cost function of segment l, and Tl the upper bound power limit
an efficient way.
of each segment (note that in this case for the last segment nl:
Such model is relevant for several market parties, all with their
Tnl = Pmax). With ı the actual generated power in each segment
specific objectives. It can for example serve as an algorithm in
l, the fuel cost and generation limits are set by the following equa-
market simulation exercises for planning purposes, e.g., by market
tions:
operators. It is further usable for energy and climate policy evalu- 
ation and assessment, focusing on RES integration. Also electricity fc(i, j) = Ai · z(i, j) + Fi,l · ı(i, j, l), ∀i ∈ I, ∀j ∈ J (3)
generating companies can use this kind of model, e.g., to provide
l


1
g(i, j) = Pmini z(i, j) + ı(i, j, l), ∀i ∈ I, ∀j ∈ J (4)
Residual demand is the load to be covered by the centralized (i.e., dispatchable)
system; it equals the total demand minus generation by e.g., wind and solar PV. l
 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123 117

g(i, j) ≤ Pmaxi · z(i, j), ∀i ∈ I, ∀j ∈ J (5)

Rank power plants according to cost metric

ı(i, j, l) ≤ Ti,l − Ti,l−1 , ∀i ∈ I, ∀j ∈ J, ∀l = 2, . . ., nl (6)

Set up lower and upper power bound

ı(i, j, l) ≤ Ti,l − Pmini , ∀i ∈ I, ∀j ∈ J, l = 1 (7)

Activate the lowest number of power plants, able to meet demand
and reserve requirement (account for minimum operating points)
ı(i, j, l)≥0, ∀i ∈ I, ∀j ∈ J, ∀l ∈ L (8)

Parameter Ai is the cost [$/h] at minimum output, and deter-

mined as Correct for minimum up and down time violations

Ai = ai + bi · Pmini + ci · Pmin2i , ∀i ∈ I, ∀j ∈ J (9)

The commitment status z is a binary variable: Activate additional power plants if needed

z(i, j) ∈ {0, 1}, ∀i ∈ I, ∀j ∈ J (10)

Turn off plants in specific hours where this improves the overall
The startup cost is a function of the time t the plant has been solution, while still respecting minimum up times
offline, previous to the startup. This is implemented as follows, with
parameter SCt presenting the startup cost if previously shut down
for t hours (set T):
Dispatch activated power plants and calculate costs
 

t
sc(i, j)≥SCi,t · z(i, j) − z(i, j − n) , ∀i ∈ I, ∀j ∈ J, ∀t ∈ T (11)
Fig. 1. Flow chart of the newly developed EPL algorithm.
n=1

sc(i, j)≥0, ∀i ∈ I, ∀j ∈ J (12) 3.1. Ranking of power plants

During all time periods j, the sum of the power generated g of In the considered UC problem, fuel costs and startup costs are
all the power plants should be equal to the demand Dj : taken into account. The fuel cost is dependent on the power plant’s
 output, and is described by a quadratic cost function. Hence, there
g(i, j) = Dj , ∀j ∈ J (13) is no single marginal or average operational cost for a power plant.
i As a criterion for the ranking of power plants, one could take the
average cost of the power plant at its minimal working point, at its
Furthermore, a certain amount of system reserves Rj need to be
maximum power output, or indeed anywhere in between. Accord-
present in the system, both up- and downwards:
ing to the chosen metric, a different stacking order can be obtained.

Pmaxi · z(i, j)≥Dj + Rj , ∀j ∈ J (14) This is illustrated in Fig. 2. The cost curves of two different power
plants are presented (these correspond to plants 4 and 5, respec-
i
tively, from the system as used further in the simulations). The
 segments for the stepwise linear approximation are also indicated
Pmini · z(i, j) ≤ Dj − Rj , ∀j ∈ J (15) (8 segments). One can see that if the average cost at minimum out-
i put is chosen as metric (slope of the steepest dashed and dotted
Finally, the minimum up and down times (MUT and MDT, lines), plant 5 is preferred over plant 4 (i.e., listed first). However,
respectively) are imposed as follows: if one opts for the average cost at maximum output, the order
reverses. To some extent, the choice of the metric should be based
z(i, j) − z(i, j − 1) − z(i, j + n) ≤ 0, on the expected operating point of a power plant on the margin,
i.e., where the order will have an important impact. In our model,
∀i ∈ I, ∀j ∈ J, ∀n = 1, . . ., MUTi − 1 (16)
the metric is initially set equal to the average cost in the middle
of the operating range of the power plant (i.e., the slope from the
z(i, j − 1) − z(i, j) + z(i, j + n) ≤ 1,

∀i ∈ I, ∀j ∈ J, ∀n = 1, . . ., MDTi − 1 (17) 4000

plant 4
3500
plant 5
Note that corrections need to be made to these equations for
3000
the start (initial conditions) and the end of the considered time
interval (set J). The UC problem consists of the objective (1) and the 2500
cost [$/h]

constraints (3)–(17).
2000

3. Enhanced priority list (EPL) based algorithm 1500

To solve the UC problem as outlined in the previous section, two 1000

methods are used. A MILP model is set up, basically by direct imple-
500
mentation of the equations from Section 2. Second, a new model
is developed based on enhanced priority listing (EPL), specifically 0
focusing on low demand issues. This section presents this newly 0 20 40 60 80 100 120 140 160 180
plant output [MW]
developed algorithm. The algorithm comprises of different steps,
which are sequentially passed through. These steps are presented Fig. 2. Power plant fuel cost over operating range, presented for two different power
in Fig. 1 and are subsequently discussed below. plants.
118 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123

origin to the fifth marker in the figure). This cost metric is denoted levels drop, however, it could be that no feasible interval exists.
M and expressed as follows: Hence, to deal with low load systems, this algorithm is extended as
follows. If no interval is found, the last interval r with Ur still lower
ai + bi · Gi + ci · Gi2
Mi = , ∀i ∈ I (18) than the demand and reserve is started from, with these r plants
Gi being activated. According to the stacking order, the algorithm now
with tries to identify the first next plant that can be activated, ensuring
 Pmax + Pmin  that if this plant is activated, both the demand minus reserves and
i i
Gi = , ∀i ∈ I (19) the sum of demand and reserve are situated between the summed
2
minimum and maximum output of all activated plants. Hence, this
If startup costs are relatively high compared to fuel cost, the met- plant will not be the plant on position r + 1, because initially no
ric Mi could be complemented with a term accounting for startup feasible interval was found. If no single plant fits this search require-
costs. If turned on, a power plant needs to be online for at least ment, this algorithm is iteratively repeated, each time identifying
the minimum up time MUTi . Based on an average startup cost, and and activating a plant in a similar way.
assuming a certain generation output Gi , the term accounting for
startup costs in the metric could be (with nt the number of elements 3.4. Correction of minimum up and down time violations
in set T):
  The corrections for minimum up and down time are carried out
nt
SCi,t /nt
t=1 in three different steps. These are subsequently discussed below.
MSi = , ∀i ∈ I (20)
MUTi · Gi Before each step, the actual up times ut(i,j) and down times dt(i,j)
of all power plants are calculated and updated.2
This term MSi would have to be added to Mi as defined above
in (18). Because of the modest startup costs in the considered data,
Step 1: If a power plant is online for a number of periods lower than
this has not been applied in the present model. According to the
a certain factor FMU multiplied by the plant’s minimum up
chosen metric, power plants are now ranked (indexed r) with a
time MUT, it is shut down.3
basic sorting algorithm. This is the priority list.
Step 2: A correction for minimum down times is carried out. If a
plant is offline for a number of time periods lower than the
3.2. Set up lower and upper bound
minimum down time, the plant is brought online in these
periods if this is feasible regarding the minimum operating
According to the ranking established in the previous step, a
point. I.e., demand (minus reserve requirement) in these
series of power intervals is determined, based on the power plant’s
periods must be higher than the sum of the minimum oper-
minimum and maximum output. Let r be the index of the ranked
ating points (lower bound) of the activated power plants
power plants (the first one is the cheapest one, the last one the most
(comprising the considered plant). If this is not the case
expensive). If all plants up to the rth plant would be activated in a
(lower demand), the plant is not activated but shut down
certain hour, their operating range is [Lr ,Ur ], with
in additional hours (toward end), to respect the minimum

r
down time MDT.
Lr = Pminn , ∀r = 1, . . ., ni (21) Step 3: A correction for minimum up times is carried out. If a plant
n=1 is online for a number of time periods lower than the min-
imum up time, the plant is brought online in additional

r
periods, if this is feasible both regarding the power sys-
Ur = Pmaxn , ∀r = 1, . . ., ni (22) tem’s cumulative minimum power (lower bound) and the
n=1 new down times. In a first try, the activation of the power
L is the cumulative sum of the minimum power output (accord- plant is extended in a symmetric way (i.e., both in hours
ing to the stacked list), U presents the cumulative sum of the before and after the originally activated periods). If this is
maximum power output and ni is the number of elements in set not possible (due to violation of the restrictions above), a
I. The intervals determined by these two vectors will be used in the second try is undertaken to extend the activation toward
following step of the algorithm, to determine appropriate power the end, or, if still not feasible, toward the front. If none of
plant activation levels. these work out, the plant is shut down in the periods where
the initial up time was too low.
3.3. Activation of the power plants
A schematic flow diagram of these different steps is presented
For every hour, the interval [Lr ,Ur ] with lowest index r is deter- in Fig. 3. After going through all three steps, all up and down times
mined, which comprises both the demand minus the reserves of the plants are feasible and the cumulative minimum operat-
(accounting for downward reserves requirement) and the sum ing point (lower bound) is respected. It could, however, be that
of the demand and reserves (accounting for the upward reserves during certain hours not enough plants are committed to satisfy
requirement) during that hour. I.e., the minimum r for which the
following two equations hold is to be found:
2
A straightforward algorithm is implemented toward this end. This algorithm
Lr ≤ Dj − Rj , ∀j ∈ J (23) basically counts the number of periods that a plant is on- or offline. If plant i is online,
the variable ut(i,j) is equal to the number of periods the plant is subsequently online
Dj + Rj ≤ Ur , ∀j ∈ J (24) and the variable dt(i,j) is zero. E.g., if a plant is online for 5 h, the variables ut(i,j)
during these periods all have a value of 5. If a plant i is offline during period j, the
The power plants up to this level r are activated. This way the variable dt(i,j) presents the number of hours the plant is offline, while ut(i,j) is zero.
3
minimum number of power plants that is required, is activated each FMU must lie between 0 and 1, and is determined based on an iterative opti-
mization (by varying this parameter, and comparing the final objective value). This
hour. parameter cannot be too high (too many power plants will be shut down in this
Note that in sufficiently large systems, with a sufficiently high step) nor too low (it will have no effect). After an iterative optimization, this factor
demand, such interval [Lr ,Ur ] should normally be found. If demand FMU is set at 0.3.
 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123 119

3.6. Shutting down excess power

Calculate current up ut(i,j) and down times dt(i,j)

In this step, two algorithms are run to turn off power plants that
Step 1: Shut down power plants i in periods j where are not required if this leads to a better solution. Such a shutdown
ut(i,j) < FMU·MUTi can only take place if the new solution still respects the MUT and
MDT constraints.

Update current up ut(i,j) and down times dt(i,j)

3.6.1. Shut down power plant over entire activated range
This algorithm runs over all the power plants, starting with the
most expensive plant (last one), then moving up in the priority list
Step 2: Correct for minimum down times:
up to the first plant. For every plant, it is checked whether there are
Turn on plant i in periods j where dt(i,j) < MDTi if feasible
towards minimum generation; if not feasible, turn plant on in time periods where the plant is scheduled on, and whether during
adjacent periods such that new dt(i,j) = MDTi . these hours, the other activated power plants are able to meet the
demand and reserve requirement:
∀i ∈ I, find j ∈ J that satisfies:
Update current up ut(i,j) and down times dt(i,j) 
m
z(i, j) = 1 and Pmaxn · z(n, j) − Pmaxi ≥Dj + Rj (25)
n=1
Step 3: Correct for minimum up times:
Turn on plant i in adjacent periods of j where ut(i,j) < MUTi if If a set of subsequent time periods j is found, and if it is bounded
by z equal to zero on both sides (right before and after the inter-
feasible towards minimum generation and new down times; if not
val), the plant is shut down during these hours, if the overall cost
feasible, turn plant off in periods j.
of this new solution is lower than the original one (for cost deter-
mination, see next step). This way, no violations against the MUT
Update current up ut(i,j) and down times dt(i,j) and/or MDT constraint can be triggered. A plant can only be turned
off during a previously entire set of activated periods, bounded by
zeros.
Fig. 3. Flow chart of the correction in activation levels to respect minimum up and
down times.
3.6.2. Shut down power plant during specific selected hours
In contrast to the previous algorithm running over plants, this
the demand and reserve requirement. The next step of the overall algorithm runs over the time periods. A backward loop (starting
algorithm (explained in Section 3.5) will take care of this. at the last period running toward the first one) is executed first,
while the entire algorithm is performed again in a forward loop
afterwards (starting at the first period running up to the last one).
3.5. Activation of additional power plants if needed
For every time period, the algorithm identifies power plants that
meet the following conditions: the plant is on; the plant is off in
After the previous step where plants have been potentially shut
the following period (backward loop) or off in the previous period
down, it could occur that during certain hours not enough power
(forward loop); the rest of the activated power plants is able to
plants are online to meet the demand and reserve requirement.
meet the demand and reserve constraint; the up time is strictly
Therefore, in this step, additional power plants are brought online
larger than the minimum up time. Mathematically, this results in:
in these cases.
∀j ∈ J, find i ∈ I that satisfies:
The hours with a shortage in activated capacity are identified. In
these hours, the algorithm tries to commit additional power plants z(i, j) = 1 (26)
according to the priority list, ensuring feasibility regarding the min-
imum operating points and up and down times. If a power plant
z(i, j + 1) = 0 (backward loop) or z(i, j − 1) = 0
is brought online, it needs to be on for at least its MUT, while the
down times that are also affected, need to stay feasible as well. Fur- (forward loop) (27)
thermore, during the additional activated periods, the cumulative
minimum operating point (lower bound) needs to be respected. The
algorithm basically subsequently (according to priority list) checks 
ni
Pmaxn · z(n, j) − Pmaxi ≥Dj + Rj (28)
for all plants that are off whether they can be turned on given the
n=1
restrictions above. If a plant is found, it is activated. The hours with
a shortage in activated capacity are updated and the algorithm is
repeated. This way, enough power is committed in each hour (e.g., ut(i, j) > MUTi (29)
it could be that in certain hour multiple power plants need to be If a power plant i is found that satisfies these constraints, the
activated). fuel costs during the considered hour j are calculated for the case
If during a shortage hour no plant can be activated, the last acti- with this plant on and for the case where the plant is turned off (in
vated plant (according to the priority list) is shut down, i.e., it is this case a term accounting for a startup cost increase needs to be
shut down for MDT periods,4 and if the affected up times are lower added if a cold start is triggered instead of hot start, because of this
than the MUT, it is shut down in these periods as well. The search shut down). If the latter is cheaper, the plant is turned off during
is then repeated for that hour, with the plant that has been shut this specific hour. If it is not beneficial to turn the plant off, it stays
down now not being allowed to turn on again. on.
If during a specific hour multiple plants are found respecting
the constraints listed above, the cost differences are calculated for
4
If there is an adjacent down period, it is only turned off in this specific hour, as a shutdown of all of these plants individually. The shutdown of
feasibility regarding MDT is then automatically ensured. the power plant that yields the highest cost reduction (if any) is
120 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123

Table 1
Power system characteristics.

Pmax Pmin MUT MDT Inist a b c hc cc tcold

[MW] [MW] [h] [h] [h] [$/h] [$/MWh] [$/MWh2 ] [$/h] [$/h] [h]

Plant 1 455 150 8 8 8 1000 16.19 0.00048 4500 9000 5

Plant 2 455 150 8 8 8 970 17.26 0.00031 5000 10,000 5
Plant 3 130 20 5 5 −5 700 16.60 0.00200 550 1100 4
Plant 4 130 20 5 5 −5 680 16.50 0.00211 560 1120 4
Plant 5 162 25 6 6 −6 450 19.70 0.00398 900 1800 4
Plant 6 80 20 3 3 −3 370 22.26 0.00712 170 340 2
Plant 7 85 25 3 3 −3 480 27.74 0.00079 260 520 2
Plant 8 55 10 1 1 −1 660 25.92 0.00413 30 60 0
Plant 9 55 10 1 1 −1 665 27.27 0.00222 30 60 0
Plant 10 55 10 1 1 −1 670 27.79 0.00173 30 60 0

Table 2
Hourly electricity demand.

Hour [h] 1 2 3 4 5 6 7 8 9 10 11 12
Demand [MW] 700 750 850 950 1000 1100 1150 1200 1300 1400 1450 1500

Hour [h] 13 14 15 16 17 18 19 20 21 22 23 24
Demand [MW] 1400 1300 1200 1050 1000 1100 1200 1400 1300 1100 900 800

retained, while the algorithm is executed again for this same hour, A 24-h time frame is considered. The demand is presented in
as it might be beneficial to turn off more than one plant. Table 2, while the reserve requirement is equal to 10% of the hourly
This algorithm cannot trigger violations regarding minimum up demand [13].
and down times. The variable z is only adjusted from 1 to zero if
it is adjacent to at least another zero (thereby only extending a 5. Numerical simulation
previously feasible down time) and if the up time was strictly larger
than the minimum one. The EPL algorithm is implemented entirely in Matlab [14]. The
MILP model (formulation partly based on the model described in
3.7. Dispatching of activated power plants and calculating the [4]) is implemented in Matlab [14] and GAMS [15], and uses the
cost Cplex 12.2 solver [16]. Simulations are run on an Intel® Core(TM )
i7-2620 M CPU @2.7 GHz computer with 8 Gb of RAM. In a first step,
In this final step the actual power generation level of each plant a reference (benchmark) case is considered, with the data as pre-
is determined, together with the fuel and startup costs. For every sented in Section 4. In a second case, the reference case is adjusted
hour, the plants are dispatched as follows. First, the generation of toward a system facing low residual demand. The EPL and the MILP
all activated power plants (z = 1) is set at their minimum generation method are used on this setting and results are compared.
output Pmin. Second, the marginal costs of the linearized segments
(see above) of all the activated power plants are put in a single 5.1. Benchmark case
list and ranked. Given convex cost functions, this ranking is used
to subsequently fill up these segments, until overall generation is The system as described in Section 4 is used, in a 10, 20, 40, 60, 80
equal to the demand. Afterwards, the actual fuel cost is calculated and 100 unit-setting. Each system is composed of the appropriate
with the original quadratic cost functions, and startup costs are number of copies of the original 10 unit system,5 with the demand
determined (based on the down times). profile scaled accordingly. This test system, originally set up in [13],
has been used extensively in the literature, to test a wide range of
algorithms, see, e.g., [4,7,8,10,13,17–29]. In this benchmark case,
4. Data description
only upward reserves are considered (consistent with the litera-
ture). As stated previously, the reserve requirement is set to 10% of
The input data are presented in Table 1 [13]. A ten-unit gen-
the demand.
eration system is considered, which will also serve as a basis to
The results of the EPL method and the MILP model are pre-
construct larger systems. These data have been used extensively in
sented in Table 3. The MILP model is run with an optimality gap6 of
the literature to test a wide set of algorithms.
zero (effectively proven optimality) for the systems of ten up to 40
Inist presents the initial state of the power plant, previous to the
units,7 and with an optimality gap of 0.5% for all systems (10 up to
time frame considered in the optimization. A positive number indi-
100 units). The calculation times of both models are also presented
cates an up time, while a negative number indicates a down time.
in Table 3. It can be seen that the EPL has very low calculation times
The startup cost is modeled as a stepwise cost function with two
for all systems, while these of the MILP in 0.5% optimality setting
steps, i.e., a cold (cc) and a hot start (hc). If a power plant is offline
stay within reasonable limits as well. If strict optimality is required
for more than the sum of the parameter tcold and the minimum
down time (MDT), a cold startup is required, with a cost equal to
cc. If the down time is shorter or equal to this sum, a hot start can
take place (hc). This results in: 5
The original system is identically duplicated (with the same power plant char-
acteristics).
6
SCi,t = hci , ∀i ∈ I, ∀t = 1, . . ., tcoldi + MDTi (30) MILP solvers can terminate when a feasible solution is found which lies within
a predefined range (i.e., the optimality gap) of a current best relaxed bound. This
solution is then proven to be within this range close to optimal.
7
For the 60 power plant system or higher, the optimal solution could not be found
SCi,t = cci , ∀i ∈ I, ∀t > tcoldi + MDTi (31) within the imposed time limit of 3600 s.
 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123 121

Table 3
Objective and computation time of the developed EPL algorithm and the MILP model (with optimality gap equal to zero and to 0.5%).

# units Total cost [$] Computation time [s]

EPL MILP MILP EPL MILP MILP

opt gap = 0 opt gap = 0.5% opt gap = 0 opt gap = 0.5%

10 563,977 563,938 564,672 0.01 1.2 1.0

20 1,124,481 1,123,308 1,125,721 0.01 5.9 2.2
40 2,246,926 2,242,609 2,246,243 0.02 3139 3.6
60 3,366,240 – 3,367,262 0.03 – 5.1
80 4,489,342 – 4,488,560 0.04 – 7.0
100 5,609,109 – 5,609,210 0.06 – 7.6

(zero optimality gap), MILP faces higher calculation times, reaching 1500 FD 0
the time limit of 3600 s with a system of 60 power plants. FD 0.5
FD 1
As can be seen from Table 3, the EPL method turns out to be

demand [MW]
RES profile FD 1
highly effective. It is fast while it provides solutions which are very 1000

close to optimal.
500
5.2. Low residual load case

0
Especially in the framework of high RES penetration, low resid- 24 48 72 96 120
ual demand (as seen by the dispatchable power plants) might occur hour [h]

more frequently. The EPL algorithm is specifically designed to deal

Fig. 5. Different demand profiles and RES profile, in the 5 day setting.
with low load and puts a high focus on technical feasibility in this
regard (e.g., minimum operating constraints).
The demand level from the reference case is adapted to a low Both the EPL algorithm and the MILP model (ran with an opti-
demand pattern, denoted LD. The demand is modified by subtrac- mality gap of 0.5%) are now applied on these low load cases. The
ting a certain term. This term could represent a wind front passing results are summarized in Table 4, presenting the MILP calcula-
by in combination with an amount of other intermittent RES like tion times, and the relative differences between MILP and EPL, for
solar PV. This term is made very generic and based on a sine func- the different power systems (10–100 units), for a demand with FD
tion, being zero at the beginning and end of the considered time ranging from 0 (which is effectively the reference case as discussed
interval, reaching a peak in the middle between. in the previous section) up to 1.5, in steps of 0.5. Results for the 1
 (j − 1) ·   day demand and the 5 day demand case are presented.
LDj = Dj − FD · D
- · sin , ∀j ∈ J (32)
nj − 1
5.3. One day demand pattern
FD is a weigh factor, D is the minimum value of the demand
Dj , and nj is the number of time periods considered. Next to the 1 First the 1 day demand pattern is considered. A first important
day profile, also a 5 day setting is applied. This is constructed as thing to note from Table 4 is the steep increase of computation
5 subsequent copies of the 1 day profile. In this case, Eq. (32) is times of the MILP model toward lower load (higher FD). This
applied on the 5 days as a whole (i.e., nj in this case equal to 120). increase is even higher than the increase of moving toward larger
Compared to the benchmark case, downward reserves (Eq. (15)) systems.8 This clearly demonstrates the difficulty MILP models
are now also included (10% of demand). have in solving low load problems. In high or medium load situ-
FD ranges from zero (effectively resulting in the original demand ations, the large (mostly least-flexible) power plants are typically
pattern) up to 1.5 in the single day (24 h) case and from zero up to used in base-load mode, meaning they are committed continu-
1 in the 5 day (120 h) case. As an illustration, the demand LD is pre- ously. The optimization of the commitment of more expensive
sented in Figs. 4 and 5 below, for the 1 and 5 day case, respectively. power plants constitutes the actual computational effort. These are,
Demand is shown for different values of FD. The generic RES profile however, typically the smaller and the more flexible plants, with
is also shown for FD = 1. As can be seen, the minimum demand is lower (absolute) minimum operating points and minimum up and
close to zero when FD is at its highest values. down times. At low demand, on the other hand, only few plants
are required, moving the optimization toward these larger and less
flexible cheaper plants, making it more difficult to determine fea-
sible/optimal solutions.
1500 FD 0 (original)
The EPL algorithm is in this case run with 3 different values
FD 0.5
for the cost metric (Gi in Mi ), i.e., at the beginning, in the mid-
FD 1
dle and at the end of the fuel cost curve. The best solution of the
demand [MW]

FD 1.5
1000 three simulations is each time retained.9 The calculation time of
RES profile FD 1

500 8
The computation time of MILP problems typically scales to some extent expo-
nentially with problem size (number of binary variables).
9
The reason for this way of optimization is to use/test different stacking orders.
0 Dependent on the stacking order, the marginal plant(s) might be running more on
4 8 12 16 20 24 minimum operating point (Gi = Pmini ), in the middle of their operating range, or at
hour [h] full load. Hence, dependent on the load profile, it might be worth testing different
metrics, if the fuel cost curves of the different power plants lie close together or
Fig. 4. Different demand profiles and RES profile, in the 1 day setting. intersect.
122 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123

Table 4
Relative difference [%] between EPL and MILP objective, together with computation time of MILP, for the 1 day (FD 0–1.5) and 5 day (FD 0–1) low demand simulations.

# units MILP computation time [s] Relative difference EPL–MILP

1 day demand pattern 1 day demand pattern

FD 0 FD 0.5 FD 1 FD 1.5 FD 0 FD 0.5 FD 1 FD 1.5

10 1.1 1.2 1.2 8.0 −0.12% 0.45% 0.15% 2.00%

20 2.0 11.5 9.9 3600.0* −0.11% 0.69% 0.26% 1.70%*
40 3.5 21.7 781.1 3600.0* 0.03% 0.53% 0.43% 1.83%*
60 5.1 177.2 3549.1 – −0.03% 0.44% 0.46% –
80 7.0 75.7 1133.6 – 0.02% 0.52% 0.48% –
100 7.7 101.3 230.0 3600.0* 0.00% 0.46% 0.45% 1.69%*

# units MILP computation time [s] Relative difference EPL–MILP

5 day demand pattern 5 day demand pattern

FD 0 FD 0.5 FD 1 FD 0 FD 0.5 FD 1

10 3.7 9.0 3600.0* −0.10% 0.31% 1.85%*

20 6.6 1944.7 – 0.01% 0.29% –
40 41.3 – 3600.0* 0.24% – 0.58%*
60 860.2 – 3600.0* 0.06% – 0.75%*
80 3273.7 3600.0* 3600.0* 0.22% −17.91%* 0.25%*
100 2616.5 3600.0* 3600.0* 0.32% −17.96%* 0.60%*

The cases marked by a * indicate that the MILP was bounded by the imposed computation time limit of 3600 s. In these cases, the current best solution is provided, but this
solution is not guaranteed to lie within the optimality gap of 0.5%. In 5 cases no solution was found by the MIP solver within the provided time (3600). The EPL method found
a solution in all cases. A positive relative difference indicates a better solution by MILP, a negative value indicates a better solution by EPL. Difference with the benchmark
case (Section 5.1) can occur (1 day demand pattern, FD = 0) as downward reserves are now included, and the EPL is now run for three different values of Gi retaining only the
best solution.

a single simulation stays overall well below 0.1 s, meaning that 6. Conclusion
this way of optimization basically takes no more than 0.3 s. Hence,
compared to MILP, the EPL method has drastically lower compu- UC models are required for optimizing the activation levels of
tation times (for the sake of brevity, these are not displayed in power plants over time. A wide range of algorithms have been
Table 4). developed in the past to address this issue, with MILP currently
Table 4 also presents the relative differences in outcome (total being the preferential method. However, in various power systems
cost) between the two algorithms. As can be seen from these across the globe, RES start to play an increasingly important role. In
results, the performance of the EPL slightly decreases toward this regard, market models (relying on a UC algorithm) are required,
lower load. The higher relative deviations at lower load are at effectively dealing with systems with low residual demand (e.g., for
least partly explained by the fact that the same absolute differ- planning issues or policy evaluation). This paper has demonstrated
ence simply results in a higher relative difference if the system that MILP is not well suited for this setting (i.e., to deal with low
is smaller or if the load is lower (which have a lower absolute residual demand). Hence, a new UC method is developed specif-
solution). Overall, results are close to optimal. Furthermore, the ically to deal with low load situations. The method is based on a
EPL method found a solution in all cases, while the MILP did priority list which is used in a heuristic algorithm to come to a fea-
not find a feasible solution in 2 cases within the provided time sible solution, which is then potentially improved in further steps.
(3600 s). Throughout the algorithm, specific focus is on feasibility toward
When having a detailed look at the solutions provided by the the power plants’ minimum operating points and minimum up and
two algorithms, part of the differences originate from the fact that down times (important for a low load setting).
the EPL algorithm uses a single ranking throughout the entire sim- The developed EPL model is first used on a benchmark case
ulation horizon. During specific moments of variable and low load, which has been widely used in the literature and compared to MILP.
however, it might be beneficial to commit more expensive plants The EPL turns out to be both very accurate and fast.
which have a lower minimum up time (e.g., peak plants (such as In a second step, the developed EPL model is employed in a
plant 8), which can be quickly turned on and off, although with a low demand setting (which is derived from the reference case),
higher variable cost). Nevertheless, the performance of the EPL is and compared to the MILP model in this same setting. The com-
satisfactory. putational difficulties of MILP are demonstrated this way: MILP
computation times increase heavily as the residual demand is being
reduced, rendering this method (used as such) less suitable in this
5.4. Five day demand pattern context. The EPL method on the other hand remains highly effec-
tive, both in outcome and especially in calculation time.
The results for the 5 day case are also presented in Table 4. In The EPL is built up as a ‘once-through’ algorithm (consecutive
3 cases, the MILP did not converge to a feasible solution, while steps, no iteration), which makes it fast, and to some extent mod-
the EPL found a feasible solution in all cases. Furthermore, in a ular and adjustable for additional constraints. An electric network
high number of cases, the MILP was restricted by the computa- might be incorporated by using the developed EPL as optimizer
tion time limit of 3600 s. The current best values provided in these within an overall iterative algorithm (adjusting generation in dif-
cases are possibly still far away from optimal, as the EPL method ferent nodes to respect network constraints). An extension toward
in some cases provides values which are significantly lower (up to further optimization could be to combine the EPL with MILP, where
almost 18%). The EPL method again proves to be very accurate, with the EPL would first identify a feasible good solution, which can then
differences mostly below 1%. The EPL stays overall below 1 s (not serve in a second step as starting point for the MILP optimization
presented in the table), while the MILP often encounters the 3600 s (especially relevant in cases where the MILP did not converge to
time limit. any feasible solution).
 E. Delarue et al. / Electric Power Systems Research 105 (2013) 115–123 123

Acknowledgements [13] S.A. Kazarlis, A.G. Bakirtzis, V. Petridis, A genetic algorithm solution to the unit
commitment problem, IEEE Transactions on Power Systems 11 (1996) 83–92.
[14] The Mathworks, Matlab, 2013, http://www.mathworks.com/products/matlab/
E. Delarue is a post-doctoral research fellow of the Research [15] General Algebraic Modelling System, GAMS, 2013, http://www.gams.com/
Foundation – Flanders (FWO). The authors thank the anonymous [16] IBM, Cplex Solver, 2013 http://www-01.ibm.com/software/integration/
reviewers for their useful comments and suggestions. optimization/cplex-optimizer/
[17] M. Afkousi-Paqaleh, M. Rashidinejad, M. Pourakbari-Kasmaei, An implemen-
tation of harmony search algorithm to unit commitment problem, Electrical
References Engineering 92 (2010) 215–225.
[18] K. Chandrasekaran, S. Hemamalini, S.P. Simon, N.P. Padhy, Thermal unit com-
[1] M. Shahidehpour, H. Yamin, Z. Li, Market Operations in Electric Power Systems: mitment using binary/real coded artificial bee colony algorithm, Electric Power
Forecasting, Scheduling, and Risk Management, Wiley-Interscience, New York, Systems Research 84 (2012) 109–119.
2002. [19] C. Chuan-Ping, L. Chih-Wen, L. Chun-Chang, Unit commitment by Lagrangian
[2] E. Delarue, P. Van Den Bosch, W. D’haeseleer, Effect of the accuracy of price relaxation and genetic algorithms, IEEE Transactions on Power Systems 15
forecasting on profit in a Price Based Unit Commitment, Electric Power Systems (2000) 707–714.
Research 80 (2010) 1306–1313. [20] I.G. Damousis, A.G. Bakirtzis, P.S. Dokopoulos, A solution to the unit-
[3] N.P. Padhy, Unit commitment – a bibliographical survey, IEEE Transactions on commitment problem using integer-coded genetic algorithm, IEEE Transac-
Power Systems 19 (2004) 1196–1205. tions on Power Systems 19 (2004) 1165–1172.
[4] M. Carrion, J.M. Arroyo, A computationally efficient mixed-integer linear for- [21] J. Ebrahimi, S.H. Hosseinian, G.B. Gharehpetian, Unit commitment problem
mulation for the thermal unit commitment problem, IEEE Transactions on solution using shuffled frog leaping algorithm, IEEE Transactions on Power
Power Systems 21 (2006) 1371–1378. Systems 26 (2011) 573–581.
[5] B.F. Hobbs, M.H. Rothkopf, R.P. O’Neill, H.-p. Chao, The Next Generation of Elec- [22] M. Eslamian, S.H. Hosseinian, B. Vahidi, Bacterial foraging-based solution to
tric Power Unit Commitment Models, Kluwer Academic Publishers, Boston, the unit-commitment problem, IEEE Transactions on Power Systems 24 (2009)
2001. 1478–1488.
[6] V.N. Dieu, W. Ongsakul, Ramp rate constrained unit commitment by improved [23] K.A. Juste, H. Kita, E. Tanaka, J. Hasegawa, An evolutionary programming solu-
priority list and augmented Lagrange Hopfield network, Electric Power Systems tion to the unit commitment problem, IEEE Transactions on Power Systems 14
Research 78 (2008) 291–301. (1999) 1452–1459.
[7] T. Senjyu, T. Miyagi, A.Y. Saber, N. Urasaki, T. Funabashi, Emerging solution of [24] S.S. Kumar, V. Palanisamy, A dynamic programming based fast computation
large-scale unit commitment problem by Stochastic Priority List, Electric Power Hopfield neural network for unit commitment and economic dispatch, Electric
Systems Research 76 (2006) 283–292. Power Systems Research 77 (2007) 917–925.
[8] T. Senjyu, K. Shimabukuro, K. Uezato, T. Funabashi, A fast technique for unit [25] W. Ongsakul, N. Petcharaks, Unit commitment by enhanced adaptive
commitment problem by extended priority list, IEEE Transactions on Power Lagrangian relaxation, IEEE Transactions on Power Systems 19 (2004) 620–628.
Systems 18 (2003) 882–888. [26] L. Sun, Y. Zhang, C. Jiang, A matrix real-coded genetic algorithm to the unit
[9] K.R. Voorspools, W.D. D’haeseleer, Long-term unit commitment optimisation commitment problem, Electric Power Systems Research 76 (2006) 716–728.
for large power systems: unit decommitment versus advanced priority listing, [27] A. Viana, J.P. de Sousa, M.A. Matos, Fast solutions for UC problems by a
Applied Energy 76 (2003) 157–167. new metaheuristic approach, Electric Power Systems Research 78 (2008)
[10] H. Siahkali, M. Vakilian, Electricity generation scheduling with large-scale wind 1385–1395.
farms using particle swarm optimization, Electric Power Systems Research 79 [28] T.A.A. Victoire, A.E. Jeyakumar, Unit commitment by a tabu-search-based
(2009) 826–836. hybrid-optimisation technique, IEE Proceedings on Generation, Transmission
[11] H. Siahkali, M. Vakilian, Stochastic unit commitment of wind farms integrated and Distribution 152 (2005) 563–574.
in power system, Electric Power Systems Research 80 (2010) 1006–1017. [29] J. Yun-Won, P. Jong-Bae, J. Se-Hwan, K.Y. Lee, A new quantum-inspired binary
[12] A. Wood, B. Wollenberg, Power Generation, Operation and Control, 2nd ed., PSO: application to unit commitment problems for power systems, IEEE Trans-
Wiley, New York, 1996. actions on Power Systems 25 (2010) 1486–1495.