arXiv:1404.4944v1 [math.OC] 19 Apr 2014

Unit commitment with valve-point
loading effect
João Pedro Pedroso
INESC Porto and Faculdade de Ciências, Universidade do Porto, Portugal
jpp@fc.up.pt
Mikio Kubo
Tokyo University of Marine Science and Technology, Japan
kubo@kaiyodai.ac.jp
Ana Viana
INESC Porto and Instituto Superior de Engenharia, Instituto Politécnico do Porto, Portugal
aviana@inescporto.pt

Technical Report Series: DCC-2014-05

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
Rua do Campo Alegre, 1021/1055,
4169-007 PORTO,
PORTUGAL
Tel: 220 402 900 Fax: 220 402 950
http://www.dcc.fc.up.pt/Pubs/

Unit commitment with valve-point loading effect
João Pedro Pedroso
INESC Porto and Faculdade de Ciências, Universidade do Porto, Portugal

Mikio Kubo
Tokyo University of Marine Science and Technology, Japan

Ana Viana
INESC Porto and
Instituto Superior de Engenharia, Instituto Politécnico do Porto, Portugal

Abstract
Valve-point loading affects the input-output characteristics of generating units, bringing the fuel costs
nonlinear and nonsmooth. This has been considered in the solution of load dispatch problems, but
not in the planning phase of unit commitment.
This paper presents a mathematical optimization model for the thermal unit commitment problem
considering valve-point loading. The formulation is based on a careful linearization of the fuel cost
function, which is modeled with great detail on power regions being used in the current solution, and
roughly on other regions.
A set of benchmark instances for this problem is used for analyzing the method, with recourse to
a general-purpose mixed-integer optimization solver.
Keywords: Unit Commitment, Load Dispatch, Combinatorial Optimization, Mixed-integer
Programming

1. Introduction
The unit commitment problem (UCP) consists of deciding which power generating units must be
committed/decommitted over a planning horizon, usually lasting from 1 day to 2 weeks and split
into periods of one hour. The production levels at which units must operate (pre-dispatch) must
also be determined to optimize a cost function which includes both fixed and variable costs. The
committed units must satisfy the forecasted system load and reserve requirements, as well as a large
set of technological constraints. This problem has great practical relevance, due to the savings that
can be achieved with an optimized schedule.
Simple approaches for this problem model the cost as a linear function, which provides a rather
rough approximation; accuracy can be improved by switching to a quadratic function. For these
models general-purpose mixed-integer convex optimization solvers can be used to find optimum
solutions for realistic, large instances. Nonetheless, much better approximations of the true costs
can be obtained if the valve-point loading effect is taken into account; however models become much
more difficult to optimize.
Valve-point loading affects the input-output characteristics of generating units, making the fuel
costs nonlinear and nonsmooth. This has been considered in the heuristic solution of load dispatch
problems — see, e.g., [1, 2, 3, 4], but there are no exact methods available in the literature.
Email addresses: jpp@fc.up.pt (João Pedro Pedroso), kubo@kaiyodai.ac.jp (Mikio Kubo),
aviana@inescporto.pt (Ana Viana)

2

Concerning the planning phase of unit commitment, even for convex models most of the research
on the solution of the UCP focuses in heuristic methods. Recently, however, improvements in
the capabilities of mixed-integer programming solvers has encouraged the thorough exploitation of
their capabilities [5]. Extensive surveys of different optimization techniques and modeling issues are
provided in [6, 7, 8], but the valve-point loading effect is not considered in any of the exact methods
proposed. A mixed integer quadratically constrained model to solve unit commitment on real-life,
large-scale power systems is presented in [9]; it details some features of the units, but not the valvepoint loading effect. Another approach, where a mixed integer linear formulation is used for modeling
nonlinear output of generators and applied to unit commitment, is presented in [10]. A process with
some similarities to the method we propose, also involving the assessment of lower and upper bounds
to a nonlinear function and iteratively converging to the optimum, has been presented in [11] and
applied to a related problem: that of optimizing short-term hydro scheduling.
The main contribution of this paper is a method based on a careful linearization of the fuel cost
function, which is modeled with great detail on power regions being used in the current solution
and roughly on other regions; this formulation is used in an iterative process that converges to the
optimum. The method may be used both for load dispatch (by setting the number of planning periods
to one) and for unit commitment. When the solution process stops, e.g. due to a limit on CPU usage,
the method provides both an upper and a lower bound to the optimum; this information is usually
very important in practice.

2. Mathematical model

Cost

A concise, complete description of the unit commitment problem as a mathematical optimization
model has been provided in [5]. When valve-point loading is taken into account that model can be
used as is, except for the shape of the objective function: instead of a quadratic function, as considered
in [12], it is now a nonconvex, nonsmooth function, as has been proposed for load dispatching in [13]
(cited by [14]).

P min

Power

P max

Figure 1: Typical shape of the fuel cost considering the valve-point loading effect.

3

2.1. Objective
A commonly used function of the fuel costs in a generating unit in terms of the power produced
p, taking into account the valve-point loading effect, is the following [13]:

F (p) = a + bp + cp2 + e sin f (P min − p) ,

(1)

where a, b, c, e, f are function’s parameters (see Figure 4), as are the minimum and maximum operating powers P min and P max . The first three terms describe a quadratic function, as usually taken into
account when valve-point loading is not considered; when it is, there is a periodic factor, as described
in the rightmost term.
This function being nonlinear, nonconvex, and nonsmooth, methods for optimizing it under
constraints on load limit and demand satisfaction — i.e., in an economic load dispatch setting
— usually involve specifically designed heuristic approaches, many of them based on evolutionary
algorithms [4, 15].
There is, however, a way of tackling this problem exactly (i.e., with arbitrarily low error). Let us
first notice that the valve points — where there is a discontinuity — limit areas where the function
is concave. Thus, if we evaluate the function into several points and use them as breakpoints for
joining the two valve points, we obtain a linear function that is never larger than the true function
(see Figure 2). Given a power production level this function provides, thus, a lower bound to the
objective value; on the other hand, the evaluation of the true function provides a trivial upper bound.
For any solution satisfying all the problem’s constraints, a lower and an upper bound to possible values
of the objective can therefore be obtained by the piecewise-linear lower approximation and the true
function, respectively.

UB

Cost

Cost

LB

exact function
approximation
Power

Power

p

Figure 2: Fuel cost and its representation with a piecewise-linear function (left). Upper bound (UB, exact function
evaluation) and lower bound (LB, piecewise-linear approximation) at a given production level p (right).

For obtaining increased precision, a large number of breakpoints may be required; this is likely
to be the limiting step for large instances. In order to obviate this problem as much as possible, we
may have the cost function represented with greater detail in power regions of potential operation,
whereas on other areas the representation may be more rough; in the limit, there may be a single
straight line joining two valve points (see Figure 3). Later in this section we propose an algorithm
for determining where to expand the number of breakpoints. The final shape of the piecewise-linear
approximation may resemble that of Figure 3.
Considering a set of units U and a set of periods T , for a given unit u ∈ U and period t ∈ T , once
the coordinates (Xutk , Yutk ) for the set of breakpoints k = 0, . . . , K to be considered is known, the
lower approximation of the objective function can easily be included in a mixed-integer programming
(MIP) linear model by means of a convex combination of these points:
4

Cost

Cost

exact function
approximation

exact function
approximation
P min

Power

Power

P max

Figure 3: Piecewise-linear fine approximation in important areas, rough on the other areas (left). Fuel cost and its
possible final representation with a piecewise-linear function (right).

K
X

put =

Xutk zutk , ∀u ∈ U, ∀t ∈ T ,

(2)

k=0

Lut =

K
X

Yutk zutk ,

∀u ∈ U, ∀t ∈ T ,

(3)

∀u ∈ U, ∀t ∈ T .

(4)

k=0
K
X

zutk ≤ yut ,

k=0

PK
In a standard convex combination model the last equation is written as k=0 zutk = 1. However,
in the case a unit is not committed in a given period, both the production level put and the linearized
fuel cost Lut must be zero. For taking this into account, in the right hand size of equation (4)
instead of 1 there must be variable yut , which indicates whether unit u was committed to produce in
period t (yut = 1) or not (yut = 0). Additionally, for the model to be correct, there must be points
corresponding to minimum and maximum operating powers, i.e., Xut0 = Pumin and XutK = Pumax , for
each unit u and period t.
For the minimization of non-convex functions represented by piecewise-linear segments, as in the
present case, it is necessary to introduce binary variables, each corresponding to a zutk , limiting
which may be non-zero; also an additional constraint for forcing the convex combination to take
on two consecutive points is necessary (i.e., there can be zutk > 0 and zu,t,k+1 > 0 only for one
value of k ∈ {0, . . . , K − 1}). Alternatively, we may use a convenience of most modern MIP solvers
that assures the same thing by declaring that, for each u and t, the set of variables zutk , ∀k forms a
so-called special ordered set constraint of type II (SOS2) [16].
The objective is to minimize the total production costs,
minimize

XX

(Lut + Sut ) ,

(5)

t∈T u∈U

which include start-up costs Sut ; these are modeled as
hot
cold cold
Sut = ahot
u sut + au sut ,

(6)
(7)

hot
where ahot
u is the hot start up cost and variable sut = 1 if there was a hot start for unit u in period
t, 0 otherwise. Equivalently for cold start up, with acold
and scold
u
ut . (See also constraints (15) to (18).)

5

2.2. Constraints
In this problem the following constraints will be considered: system power balance and generation
limits (i.e., load dispatch), system reserve requirements, unit initial conditions, and unit minimum
up and down times; this MIP model was introduced in [5].
Demand satisfaction is modeled by constraint (8), and power reserve requirements by constraint (9).
X

put = Dt ,

∀t ∈ T ,

(8)

Pumax yut ≥ Dt + Rt , ∀t ∈ T .

(9)

u∈U

X
u∈U

Power production levels of thermal power units are within the range defined by the technical
minimum and maximum production levels in (10).
Pumin yut ≤ put ≤ Pumax yut , ∀u ∈ U, ∀t ∈ T .

(10)

When a unit u is switched on, it must remain on for at least Tuon consecutive periods; similarly,
it must be kept off for at least Tuoff after being switched off. Constraints (11) and (12) model this
aspect for the initial state, while constraints (13) and (14) do the same for the remaining planning
off
prev
off
horizon. In (11) θuon represents max(0, Tuon − tprev
u ), and θu in (12) stands for max(0, Tu − tu ); the
prev
previous state of unit u is the parameter yu , which is 1 if the unit was on, 0 if it was off.
yut = 1, ∀u ∈ U : yuprev = 1, for t = 0, . . . , θuon ,
yut = 0, ∀u ∈ U :

yuprev

= 0, for t =

0, . . . , θuoff .

(11)
(12)

off
Constraints (13) and (14) determine if a unit u is started/switched off in period t (xon
ut = 1, xut = 1,
off
on
off
on
respectively, or 0 otherwise); variables τut and τut stand for max(t−Tu +1, 1) and max(t−Tu +1, 1),
respectively.
t
X

xon
ui ≤ yut ,

∀u ∈ U, ∀t ∈ T ,

(13)

xoff
ui ≤ 1 − yut , ∀u ∈ U, ∀t ∈ T .

(14)

on
i=τut

t
X
off
i=τut

Constraints (15) state that every time a unit is switched on, a start-up cost will be incurred.
cold
on
shot
ut + sut = xut ,

∀u ∈ U, ∀t ∈ T .

(15)

Constraints (16) determine the start-up type of each unit, i.e., decide whether it is a cold or a
hot start type. It will be a cold start if the unit remained off for more than tcold
periods of time, and
u
a hot start otherwise.
t−1
X

yut −

yui ≤ scold
ut , ∀u ∈ U, ∀t ∈ T .

(16)

i=t−tcold
u −1

Constraints (17) determine each unit’s switch-on variables, and (18) determine the switch-off
variables.
yut − yu,t−1 ≤ xon
ut ,
xoff
ut

=

xon
ut

∀u ∈ U, ∀t ∈ T ,

(17)

+ yu,t−1 − yut , ∀u ∈ U, ∀t ∈ T .

(18)

6

2.3. Solution approach
There is not, to the best of our knowledge, exact solution method for the load dispatching problem
when the valve-point loading effect is taken into account, let alone the full unit commitment problem.
The solution approach that we propose achieves this, in the sense that it converges to a solution with
an arbitrary degree of precision.
The method is based in the replacement of the function defined by Equation (1) by a piecewiselinear function; a careful selection of the breakpoints allows the construction of a model that provides
a lower bound to the exact function. Upon a feasible solution obtained by this linear model, we
can evaluate the true function; this will provide an upper bound to the value of the objective. As
described in Algorithm 1, if the deviation between the upper and lower bounds are within a userspecified tolerance, then the method will stop. Otherwise, the number of breakpoints is increased
(though only in the required intervals), thus leading to a better approximation, and the optimization
problem is resolved. This process is repeated until the relative deviation between upper and lower
bounds is small enough (or the allowed CPU time is exceeded). Notice that the solution of an iteration
is feasible to the problem of the next, the only changes are in its evaluation. We can, therefore, supply
it as a starting point to the MIP solver in line (4) of the algorithm.
Algorithm 1: Solution procedure.
Input: UCP instance, CPU limit, tolerance
Output: A solution to the input instance
(1)
foreach unit u ∈ U , period t ∈ T :
(2)
But := set of breakpoints containing only the valve points
(3)
while true
(4)
solve problem with piecewise-linear objective, breakpoints B
(5)
if U B − LB < tolerance or CPU limit exceeded:
(6)
return solution
(7)
foreach u, t with coarse objective representation in the solution:
(8)
divide the inter-valve interval containing put into K segments
(9)
add corresponding points to But
(10)
if there were no u, t with coarse objective in put :
(11)
K := 2K
(12)
for each u, t recompute But based on K segments in the inter-valve interval containing
put

The value K used in this algorithm should ideally be setup in such a way that the initial
approximation is just good enough to solve the instance with sufficient precision. If K is set too
high, there will be too many intervals in the piecewise-linear representation of the objective function,
leading to great precision but requiring unnecessary CPU for solving the problem; if is it set too low,
additional iterations will be necessary for providing the required precision (each iteration doubling
the value of K), and again unnecessary CPU will be used.
The most important properties of this algorithm are summarized next. Let us denominate P1 the
problem of maximizing the true objective,
XX
minimize
[Sut + yut Fut (put )]
(19)
t∈T u∈U

where

min
Fut (p) = au + bu p + cu p2 + eu sin fu (Put
− p) ,
under constraints (6) to (18), and P2 its linearized counterpart, i.e., the problem of maximizing (5)
under the same constraints and additionally (2), (3) and (4).
Property 1. Feasible solutions for P2 are feasible for P1 .
Proof. P2 includes all the variables of P1 , and contraints of P2 are a superset of constraints of P1 .
Property 2. The evaluation of the objective function (19) at a feasible solution obtained for P2 is
an upper bound to the optimum of P1 .
7

wi′
wi+1

wi+1

Cost

wi

Cost

wi

wK

wK

wK−1

wK−1
Power

Power

Figure 4: Linear approximations in consecutive iterations.

Proof. Follows from Property 1 and from the notion of optimum: the objective at any feasible solution
of a minimization problem provides an upper bound to its optimum.
Property 3. An optimum of P2 is a lower bound to the optimum of P1 .
Proof. Between two consecutive valve points the function F (p) defined by Equation 1 is concave as
long as c ≤ ef 2 /2 (see Appendix B); therefore, if this condition is observed, any piecewise-linear
interpolation between consecutive valve points is not larger than F . In the construction of the
piecewise-linear approximation we are considering all the valve points, as well as the extreme point
of the domain of F , as interpolation points; hence, the linear interpolation is not larger than F
in its domain. We can thus conclude that the minimum of P2 — where the objective is a linear
interpolation in the previous conditions — is not larger than the minimum of P1 , where the objective
is function F .
Property 4. With tolerance ǫ = 0, when the number of iterations increases the solution provided by
Algorithm 1 converges to the optimum solution of P1 .
Proof. Let us denote the linear approximation of F at an iteration i by Gi , and define G = limi→∞ Gi .
Note that Gj (p) ≥ Gi (p), for any j > i, and for all p in the domain of F . As functions Gi are nondecreasing with increasing i and are limited above by F , the sequence Gi converges.
It remains to prove that the optimum solution with Gi as the objective function, when i tends to
infinity, is an optimum solution with F as the objective function. We will assume that this is not true,
i.e., that the optimum F ∗ is strictly greater than G∗ , and show that this leads to a contradiction.
Notice that F ∗ > G∗ is equivalent to F ∗ − G∗ = ǫ∗ , with ǫ∗ > 0, which implies that there must be
some u, t such that Fut (p∗ ) − Gut (p∗ ) = ǫ′ > 0. However, lines (11) and (12) of Algorithm 1 imply
that the number of segments in each inter-valve interval containing p∗ut tends to infinity when the
number of iterations tends to infinity. This means that Gut (p∗ ) becomes arbitrarily close to Fut (p∗ ),
and hence ǫ′ cannot be positive.

3. Computational results
In order to run economic load dispatch instances with the current model we must set up an
instance with only one period; generators must have the previous status as operating, and must be
forced to keep operating by adjusting the minimum number of on periods. We have thus prepared
data for the most widely used benchmark instances for load dispatching with valve-point loading
8

179300

55900
upper bound
lower bound

upper bound
lower bound

179200

55850

179100
179000

55800

Total cost

Total cost

178900
55750

55700

178800
178700
178600

55650

178500
178400

55600

178300
178200

55550
0

5

10

15

20

0

25

5

10

15

20

25

Iteration

Iteration

Figure 5: Bounds as a function of the iteration number, for instance ucp40 with one period (optimal solution was
found) and three periods (final solution was not optimal).

effect: eld13 (first described in [13]) and eld40 (first described in [17]); we have used the tables
available in [14]1 .
The setup used was the following: a computer with an Intel Xeon processor at 3.0 GHz and
running Linux version 2.6.32, using Gurobi version 5.0.1 [16]. Only one thread was assigned to
this experiment. Models were written in the Python language and the default Gurobi parameters
were used until reaching the user-defined tolerance; then, parameters were changed to the maximum
precision supported by Gurobi. The aim of this procedure is to avoid spending too much CPU in the
initial iterations, where the representation of the objective function is still rather course.
Instance
eld13
eld13
eld40

Load
1800
2520
10500

Lower bound
17963.83
24169.92
121412.53

Upper bound
17963.83
24169.92
121412.54

Error
<1.e-7
<1.e-7
<1.e-7

CPU time
19.1s
1.8s
7.6s

N
34
19
27

Table 1: Solution to economic load dispatch instances: bounds to the objective value, maximum relative error, CPU
time employed, and number of iterations performed.

The results presented in Table 1 are optima, and are approximately equal to the best solutions
found by the best methods available in the literature [4].2
As for the unit commitment problem, to the best of our knowledge there are no test instances
taking into account the valve-point effect. We have therefore prepared a set of benchmarks, based on
the instances for unit commitment provided in [12], and on the instances for economic load dispatch
mentioned above. Instance ucp10 corresponds to the standard instance described in [12]; ucp5 is
based on that instance, by selecting only half of the units and adjusting demand. Instances ucp13
and ucp40 have costs taken from eld13 and eld40, respectively, and data concerning multi-period
operation based on [12]. Notice that the difference between instances eld13 and ucp13 with one
period (besides possible differences in the demand value) is that in the former the commitment
decision has already been made, and all units considered must be operating; the same for eld40 and
ucp40. These results are presented in Table 2. Figure 5 plots the evolution, for a particular case,
of the lower and upper bounds with respect to the iteration number; as expected, the lower bound
is non-decreasing, whereas the upper bound may increase (when the linear approximation at the
solution of the previous iteration was poor).
1 All
the
data
and
programs
used
are
available
in
this
paper’s
Internet
page,
http://www.dcc.fc.up.pt/~ jpp/code/valve
2 Results presented in [15] are better than the optimum for eld13, indicating that there is likely an error in that
paper. Possibly this is due to a rounding error; if we calculate the cost for the solutions provided in the paper we
obtain values greater than those reported.

9

Instance
ucp5
ucp5
ucp5
ucp5
ucp5
ucp10
ucp10
ucp10
ucp10
ucp10
ucp13
ucp13
ucp13
ucp13
ucp13
ucp40
ucp40
ucp40
ucp40
ucp40

Periods
1
3
6
12
24
1
3
6
12
24
1
3
6
12
24
1
3
6
12
24

Lower bound
7352.46
24506.12
59127.38
153575.68
308482.03
13826.85
45929.36
109919.97
285808.54
572943.80
11701.28
38849.84
91405.97
231587.47
464053.01
55644.79
178395.51
416108.42
1112370.94
2235970.56

Upper bound
7352.46
24506.12
59127.39
153575.69
309152.47
13826.85
45929.36
109919.98
286067.44
574554.02
11701.28
38849.84
91783.98
232537.37
466186.98
55644.79
178547.12
416605.93
1113801.09
2238504.45

Error
<1.e-7
<1.e-7
<1.e-7
<1.e-7
0.22%
<1.e-7
<1.e-7
<1.e-7
0.091%
0.28%
<1.e-7
<1.e-7
0.41%
0.41%
0.46%
<1.e-7
0.085%
0.12%
0.13%
0.11%

CPU time
0.12
0.29
1.2
54.
3600.
0.17
1.3
31.
3600.
3600.
0.15
3.3
3600.
3600.
3600.
3.9
3600.
3600.
3600.
3600.

N
5
5
6
7
3
6
7
9
5
3
6
11
10
4
3
25
30
15
11
7

Table 2: Solution to unit commitment instances: bounds to the objective value, maximum relative error, CPU time
employed, and number of iterations performed.

4. Conclusions
The main contribution of this paper is a model and an algorithm for solving the unit commitment
problem taking into consideration the valve-point loading effect in fuel cost computation. This model
can be used for planning which units to commit in each period so as to match demand, meeting
reserve constraints, and under a set of technological constraints. The algorithm iteratively calls a
general-purpose mixed-integer programming solver for tackling optimization subproblems, and uses
the solution to improve the accuracy of fuel cost approximation until reaching an error below a given
tolerance, or reaching a given limit on CPU usage.
The model can also be used for load dispatching, when only one period is considered and the subset
of units that will operate is already selected; this is known as the economic load dispatch problem
with valve-point effect; the method proposed was able to solve well known benchmark instances of
this problem for which the optimum was not known.
To the best of our knowledge, there are no standard benchmarks for unit commitment taking
into account the valve-point loading effect. We present a set of them, based on data from load
dispatch and unit commitment. Using our algorithm for their solution, the optimum was obtained
for a subset of instances, and very good approximations, with a relative error below 1%, were found
for the remaining.

Acknowledgements
This work was partly funded by project “NORTE-07-0124-FEDER-000057”, under the North
Portugal Regional Operational Programme (ON.2 O Novo Norte) and the National Strategic Reference Framework through the European Regional Development Fund, and by national funds through
Fundação para a Ciência e a Tecnologia (FCT), and by FCT (under Project PTDC/EGE-GES/099120/2008)
through “Programa Operacional Temático Factores de Competitividade (COMPETE)” of “Quadro
Comunitário de Apoio III”, partially funded by FEDER.
10

References
[1] Al-Sumait J, Al-Othman A, Sykulski J. Application of pattern search method to power system
valve-point economic load dispatch. International Journal of Electrical Power & Energy Systems
2007;29(10):720 –30.
[2] Hemamalini S, Simon SP. Dynamic economic dispatch using artificial immune system for
units with valve-point effect. International Journal of Electrical Power & Energy Systems
2011;33(4):868 –74.
[3] Roy P, Roy P, Chakrabarti A. Modified shuffled frog leaping algorithm with genetic algorithm
crossover for solving economic load dispatch problem with valve-point effect. Applied Soft
Computing 2013;13(11):4244 –52.
[4] Reddy AS, Vaisakh K. Shuffled differential evolution for economic dispatch with valve point
loading effects. International Journal of Electrical Power & Energy Systems 2013;46(0):342 –52.
[5] Viana A, Pedroso JP. A new MILP-based approach for unit commitment in power production
planning. International Journal of Electrical Power and Energy Systems 2013;44:997–1005.
[6] Sen S, Kothari D. Optimal thermal generating unit commitment: a review. International Journal
of Electrical Power & Energy Systems 1998;20(7):443–51.
[7] Padhy NP. Unit commitment – a bibliographical survey. IEEE Transactions in Power Systems
2004;19(2):1196–205.
[8] Yamin HY. Review on methods of generation scheduling in electric power systems. Electric
Power Systems Research 2004;69:227–48.
[9] López JÁ, Ceciliano-Meza JL, Moya IG, Gómez RN. A MIQCP formulation to solve the unit
commitment problem for large-scale power systems. International Journal of Electrical Power &
Energy Systems 2012;36(1):68 – 75.
[10] Simoglou CK, Biskas PN, Bakirtzis AG. Optimal self-scheduling of a thermal producer in shortterm electricity markets by milp. IEEE Transactions on Power Systems 2010;25(4):1965 –77.
[11] Lima RM, Marcovecchio MG, Novais AQ, Grossmann IE. On the computational studies
of deterministic global optimization of head dependent short-term hydro scheduling. IEEE
Transactions on Power Systems 2013;28(4):4336 –47.
[12] Kazarlis SA, Bakirtzis AG, Petridis V. A genetic algorithm solution to the unit commitment
problem. IEEE Transactions on Power Systems 1996;11:83–92.
[13] Wood A, Wollenberg B. Power Generation, Operation, and Control. New York, NY: John Wiley
& Sons; 1984.
[14] dos Santos Coelho L, Mariani V. Combining of chaotic differential evolution and quadratic
programming for economic dispatch optimization with valve-point effect. IEEE Transactions on
Power Systems 2006;21(2):989–96. (See also a correction to this paper).
[15] dos Santos Coelho L, Mariani VC. An efficient cultural self-organizing migrating strategy for
economic dispatch optimization with valve-point effect. Energy Conversion and Management
2010;51(12):2580 –7.
[16] Gurobi Optimization, Inc. .
http://www.gurobi.com; 2012.

Gurobi Optimizer

Reference Manual,

Version 5.0.

[17] Sinha N, Chakrabarti R, Chattopadhyay PK. Evolutionary programming techniques for
economic load dispatch. IEEE Transactions on Evolutionary Computation 2003;7(1):83–94.
11

Appendix A. Notation
Constants
• T – length of the planning horizon.
• T = {1, . . . , T } – set of planning periods.
• U – set of units.
• Pumin , Pumax – minimum and maximum production levels for unit u.
• Tuon , Tuoff – minimum number of periods that unit u must be kept switched on/off.
• Dt – system load requirements in period t.
• Rt – spinning reserve requirements in period t.
• au , bu , cu , eu , fu – fuel cost parameters for unit u.
cold
• ahot
– hot and cold start up costs for unit u.
u , au

• tcold
– number of periods after which the start up of unit u is evaluated as cold.
u
• yuprev – previous state of unit u (1 if on, 0 if off).
– number of periods unit u has been on or off prior to the first period of the planning
• tprev
u
horizon.
Decision variables
• yut – 1 if unit u is on in period t, 0 otherwise.
• put – production level of unit u, in period t.
Auxiliary variables
off
• xon
ut , xut – 1 if unit u is started/switched off in period t, 0 otherwise;

• shot
ut – 1 if unit u has a hot start in period t, 0 otherwise;
• scold
ut – 1 if unit u has a cold start in period t, 0 otherwise;
Production costs
• Fut – fuel cost for unit u in period t.
• Sut – start up cost for unit u in period t.
Appendix B. Conditions for concavity of the fuel costs
In this appendix westate the conditions for concavity of the fuel cost function F (p) = a + bp +
cp2 + e sin f (P min − p) (Equation 1) between two valve points. Recall that a differentiable function
is concave in a given region if its second derivative is less than or equal to zero in all points of that
region.

If the term within the absolute value,
e sin f (P min − p) , is positive, the first derivative of F (p) is

F ′ (p) = 2cp + b − ef cos f (P min − p) , and the second derivative is F ′′ (p) = 2c − ef 2 sin(f (P min − p)).

2
For the function F to be concave there must be F ′′ (p) ≤ 0, i.e., c ≤ ef2 sin f (P min − p) . As
sin(x) ≤ 1, ∀x, F is concave for c ≤ ef 2 /2.
Similarly, if the term within
the first derivative of F (p) is F ′ (p) =
 the absolute value is negative,
min
′′
2cp + b + ef cos f (P
− p) , and the second derivative is F (p) = 2c + ef 2 sin f (P min − p) . Again,
12


2
for F to be concave there must be c ≤ − ef2 sin f (P min − p) . As sin(x) ≥ −1, ∀x, this condition is
observed for c ≤ ef 2 /2.
Therefore, for
c ≤ ef 2 /2
the function F (p) is concave between two valve points. This condition is valid for all the instances
analyzed in this paper.

13

