The Stochastic Short-Term Hydrothermal S
The Stochastic Short-Term Hydrothermal S
The Stochastic Short-Term Hydrothermal S
Abstract: In this document we develop a non linear stochastic integer model formulation for the unit commitment problem
of thermal and hydro units to management demand and optimal short-term operation of a hydrothermal electric facility. We
consider a power generation system comprising thermal and hydro units and the problem concerns the scheduling of
operation levels for all power units and considering the hydro constrains, such that the operation costs over the time horizon
are minimal. The concept of reliability functions is introduced to ensure the meet demand with certain probability. Inflows
to reservoirs, cost coefficients and spillage are considered random. We use the Monte Carlo sampling to optimize the
instances required each period. We report the practical and theoretical results.
1. INTRODUCTION
The systematic coordination of the operation of a system formed by hydroelectric generation plants is a classical problem
involving the planning of the operation of a hydraulic generation system and a thermal system. The generation scheduling
problem consists of determining the optimal operation strategy for the next scheduling period, subject to a variety of
constrains, in literature this is known as the hydrothermal generation scheduling problem (HGSP) (Gil et al. 2003). The
most versions involves the allocation of generation among the hydro-electric and thermal plants so as to minimize the total
operation costs of thermal plants while satisfying the various constrains on the hydraulic and power systems network.
Usually, the short term period covers from 1 to 7 days, and then, this period is subdivided into smaller time intervals of 1 to
4 hours in which the information of the system is known and the decision variables should be optimized.
This is one of the most important problems associated with the management of a power utility and can be viewed as a
problem of production planning, where the good produced is electricity and it is generated from two sources, a
hydroelectric generating plant and a thermal power plant. Here, the problem of inventories does not exist because the good
produced must be delivered to the customer at the time that it is generated. The master programming scheduling (MPS) is
to develop the programming of system operation for each period specifying the state and the generation level of the thermal
set, subject to fundamental constrains that must be satisfied such that the covering of each hourly load (demand),
satisfaction of spinning reserve requirements and transmission capacity limits, the limited energy storage capability of
water reservoirs and other. Under some assumptions (such determinism for example), the mathematical model can be
written in terms of a nonlinear objective function subject to a set of linear or nonlinear constrains. In stochastic approach,
the model includes some parameters as random variables, which the most representative is the load required. To model the
problem more realistically, the load demand the water inflow rate and the reservoir levels of the hydroelectric plants are
considered random and therefore the mathematical complexity of the model significantly increases. Anyway, an efficient
generation schedule not only reduces the production cost but also increases the system reliability securing valuable
reserves, regulating margins, and maximizing the energy capability of the reservoirs, Zoumas et al., (2004).
2. LITERATURE REVIEW
The solution methods of the HGSP problem have been approached from several perspectives, however, literature comprises
them in five major areas: a) Lagrangian relaxation, b) Metaheuristic decomposition, c) Bender's decomposition, d)
Dynamic programming, e) Mixed integer programming.
The Lagrangian relaxation technique uses the Lagrange multipliers to relax system wide demand and reserve
requirements decomposed the main problem into unit-wise subproblems that are much easier to solve. Then, the multipliers
are updated at the high level typically using a subgradient method Lu et al., (1998). There are many variants of the
technique Zuang and Galiana (1988), Virmani et al., (1989), Yan Guan and Rogan (1993) and (1994), Merlin and Sandrin
© International Journal of Industrial Engineering
ISBN # 97809652558-6-8
Proceedings of the 15th Annual
International Conference on Industrial Engineering
Theory, Applications and Practice
Mexico City, Mexico
October 17-20, 2010
(1983), Aoki et al., (1987), Osman and Laporte (1996), Brannlund et al., (1986); but all they are underpinned by the idea
of forming an objective function penalized with model constrains forming the Lagrangian function.
Metaheuristics are a class of approximate methods that have been developed strongly since their inception in the
early 1980's. They are designed to optimize complex optimization problems where classical heuristics and optimization
methods have failed to be effective and efficient. Metaheuristics include, but are not limited to: constraint logic
programming, genetic algorithms, greedy random adaptive search procedures, neural networks, non-monotonic search
strategies, problem and heuristic space-search, simulated annealing, tabu search, threshold algorithms and others (Aoki et
al., (1987)). In connection with the HGSP, there is an important class of techniques called the heuristic decomposition
methods. These, decompose the HGSP problem into hydro and thermal subproblems. The hydro optimization subproblems
use either the thermal cost functions or the thermal system marginal cost to efficiently allocate the water resources within
the scheduling horizon Zoumas et al., (2004), Osman and Laporte (1996), and Brannlund et al., (1986). Then, the hydro
generation and reserve contributions subtracted from the load and reserve requirements, the thermal subproblems solves a
standard unit commitment problem.
Benders decomposition is used to solve the multiperiod HGSP problem and is a natural way to decompose it
because the 0/1 variable decisions are decoupled from continuous variable decision (Duncan et al., (1985)). In general, the
method fixes the start-up and shut-down schedules of the thermal units, while the Benders subproblem solves a multiperiod
optimal power flow. Then, the subproblem sends to the master problem marginal information on the goodness of the
proposed start-up and shut-down schedule, which allows the master problem to suggest an improved start-up and shut-
down schedule and so on (Alguacil and Conejo (1985), Geofrion (1972)) .
In the general approach of the dynamic programming, the problem is decomposed into a thermal subproblem and a hydro
subproblem. The algorithm obtains the non discrete states to substitute the discrete states of water volume levels at each
time period and then determines an optimal generation schedule while achieving the minimum fuel cost of power system.
The spinning reserve of all units provided can satisfy the requirements of the system for any unexpected change in load or
loss of maximum on line generation unit (Lasdon (1970), Yang and Chen (1989), Gorenstin et al., (2002), Dillon et al.,
(1978)).
This paper proposes the use of random coefficients with minimum variance cost (due to the use of short periods of
planning) in the objective function, demand as a random variable normally distributed, and water inflow to the reservoirs
and spillage are also random variables. An important consideration also include, is the use of a reliability function
associated to the power balance equation (customer service level), and the variable and fixed costs of each production unit.
Then, this model can be characterized as a nonlinear, stochastic and integer problem.
In the construction of our proposal we use some of the ideas developed in Gröwe and Römish (2005), i.e., we also consider
planning horizon be discretized into ∈ uniform subintervals, we define the sets and , of thermal and hydro units
the scheduling of start-up/shutdown decisions and of operation levels for all power units as a stochastic process. Let the
, ,
Time interval index (hour).
1
The standard measurement unit of water flow quantities is m3/s, however, in this document the water flow quantities are expressed in m3/h to avoid the
use of conversion coefficients in equations.
267
Proceedings of the 15th Annual
International Conference on Industrial Engineering
Theory, Applications and Practice
Mexico City, Mexico
October 17-20, 2010
Fixed operating costs of th hydroplant in $/h.
Energy demand in megawatts, assumed here a random variable.
Subject to
≤ ≤ , ∈ (Water Vlow rate through the turbine limits), (6)
, , , ≥ 0, (10)
where ) is the mathematical expectation operator, b = (, , ) is a random vector such that )(b) = c, d d, ̅f and the
operating costs related to a thermal unit include variable and fixed production costs. The function + + / ,
expresses the variable costs, and the constant represents the sum of the fixed costs associated to the operation of the th
thermal unit during . Similarly, the constant represents the sum of fixed costs associated to the operation of the th
hydroplant during the period . In practice these costs are well identified (Nilsson and Sjelvgren (2002)), and can be
summarized as: loss of water during maintenance; wear and tear of the windings due to temperature changes during the
start-up; wear and tear of mechanical equipment during the start-up; malfunctions in the control equipment during the start-
Thus, for any ∈ , and by the properties of the mathematical expectation, equation (1) can be simplified as
up; and loss of water during the start-up. In this formulation, equation (2) can be viewed as the customer service level.
Assume that the probability density function (pdf) of the random variable is known and it is given by ij (ξ), ∀ ! .
Then, equation (2) is equivalent to
o
6 7 ≤ , + , 9 = l mnj (ξ) = 1 − ;, ; ∈ (0,1) (12)
∈3 ∈2 L
where p = ∑ 13 + ∑12
In particular, if ~s(t, u / ), with v() = tj and wxy () = u /, equation (11) can be written as follows.
(∑ 13 + ∑12 ) − tj
6 z{ ≤ } = 1 − ;, (13)
√u /
where {~s(0,1). Le~ be the standard value such that nj (~ ) = 1 − ; . Note that, expression (11) is satisfied if and
only if
(∑ 13 + ∑12 ) − tj
≥ ~ ,
√u /
, + , ≥ tj + u~ , (14)
∈3 ∈2
The function of water flow through turbines is assumed known and it has the form (See Wood and Wollenberg (1996))
Finally, and using the binary variables - and 0, equation (4) and (5) can be decomposed as follows
- ( − ≥ 0, !, (17)
4. NUMERICAL EXAMPLE
To illustrate our proposal we used information from Wood and Wollenberg (1996) and Loucks and Bee (2005). We
Tables (2) to (4). Table (1) shows the mathematical expectation of b for each component (, , ), the limits of power
consider 3 hydro plants using Francis turbins and 3 thermal units. The characteristics of the system analyzed are shown in
generation of thermal units and their respective fixed operating costs. Table (2) shows the coefficients proposed for
evaluating water requirements as a function of power demand in each turbine, the operating limits of power generation of
hydro plants and their fixed operating cost. The periods considered and demand parameters are shown in Table (3).
269
Proceedings of the 15th Annual
International Conference on Industrial Engineering
Theory, Applications and Practice
Mexico City, Mexico
October 17-20, 2010
Unit g g ̅
1 561 7.92 0.001562 200 400 79,284
2 310 7.85 0.00194 300 400 105,665
3 78 7.97 0.00482 100 200 20,750
Unit KL KG ggg
K/
1 51216.863 1173.829 16.382 50 120 90,000
2 50834.983 1082.829 15.551 10 100 90,000
3 49816.928 1168.829 12.052 10 150 90,000
tj
1 2 3 4 5 6 7 8 9 10 11 12
uj
800 670 668 675 720 780 800 850 860 900 900 900
tj + uj ~
10 8 9 12 15 15 20 30 32 28 26 26
820 686 686 699 750 810 840 909 923 955 951 951
tj
13 14 15 16 17 18 19 20 21 22 23 24
uj
990 990 850 1000 1150 1210 1214 1225 1240 1245 1100 1050
tj + uj ~
27 21 20 24 26 15 15 16 18 16 14 10
1041 1031 889 1047 1200 1240 1244 1257 1276 1277 1127 1070
With respect to the water inflows, in literature is common to use the following random variables to estimate them (Bobe
and Ashkar (1991), IACWD (1982)) : a) Normal distribution, b) Lognormal distribution (used to describe the flood flows),
c) Gamma distributions (used to model many natural phenomena, including daily, monthly and annual stream flows as well
as flood flows, (IACWD (1982)), d) Log-Pearson type 3 distribution (this distribution has found wide use in modelling
flood frequencies and has been recommended for that purpose (IACWD (1982), Hosking and Wallis (1997)), e) Gumbel
and GEV (Generalized Extreme Value) distributions (In recent years, these have been used as a general model of extreme
events including flood flows, particularly in the context of regionalization procedures (GOVE Hidroelectric Development
(2010)). In our proposal we use the gamma distribution with pdf, mean and variance given by
i (, ;, b) = FG
/
, v() = ;b, wxy() = ;b /
* ()
(21)
and to project the simulated value we use the product (nFG ()) × ϱ, with ϱ = 3600. Here (nFG ()), ∈ (0,1)
represents the inverse transform of the cumulative distribution function of gamma density. Table (4) shows the operating
all ∈ .
conditions of the hydro system and the parameters used in the gamma function to estimate the inflows to each reservoir for
; b
Hydro units characteristics Gamma parameters
,L , ,/
5.2 × 10 150,000 500,000 45,000,000 40,000,000 40,000,000 1.41 47.92 3600
ϱ
2.1 × 10 140,000 500,000 16,000,000 12,000,000 10,200,000 1.62 47.92 3600
1
5.1 × 10 100,000 500,000 21,000,000 14,000,000 14,000,000 1.28 42.81 3600
2
3
generator. It is a technique for estimating the solution, , of a numerical mathematical problem by means of an artificial
Monte Carlo optimization is a class of algorithms that seek a maximum by sampling, using a pseudo-random number
270
Proceedings of the 15th Annual
International Conference on Industrial Engineering
Theory, Applications and Practice
Mexico City, Mexico
October 17-20, 2010
expectation is equal to . As a first approximation, we generate = 100 random vectors ( , ) ! containing feasible
sampling experiment. The estimate is usually given as the average value, in a sample, of some statistic whose mathematical
solutions and then, ordered them to select the lowest. Feasible solutions were obtained under the scheme “here and now”.
Table (5) shows the optimal MPS for one sequence of 24 hrs.
5. CONCLUSSIONS
In this document we proposed a non linear stochastic and integer programming model to obtain the MPS of the
hydrothermal coordination problem. We use a random search technique based on Monte Carlo sampling to optimize the
given instance. The problem was programed in Excel and Math Lab to evaluate the instances generated. Experience showed
that the time required to obtain solutions where power demand is approaching the upper limits of generation capacity
(equations (2), (5) and (6)) grows significantly. In our results the water inflow to dams was greater than the needs of water
flow through the turbines; this caused spillages in reservoirs 1 and 2.
The approach used in this research, proved to be sufficient but not efficient. However, opening the way for the
application of meta heuristics such a genetic algorithms or ant colony. Our main contribution in this proposal is the use of
reliability functions to ensure that, the power generated meets the average demand with certain probability. The use of fixed
and variables costs and the consideration of that, the water inflow rate and the corresponding spillage rate are random
variables.
The next activity in this research involves the application of alternative techniques and to compare their results
(accuracy and speed of convergence) with obtained here.
6. REFERENCES
A. J. Wood and B. F. Wollenberg, (1996), Power Generation Operation and Control, 2nd ed. NY: John Wiley & Sons, Inc.
A.J. Wood and B.F. Wollenberg, (1984), Power Generation Operation and Control, New York, Wiley.
A.M. Geofrion. Generalized Benders, (1972), Decomposition. Journal of Optimization Theory and Applications, JOTA,
Vol. 10, No. 4, pp. 237 - 260.
271
Proceedings of the 15th Annual
International Conference on Industrial Engineering
Theory, Applications and Practice
Mexico City, Mexico
October 17-20, 2010
B. Bobe. and F. Ashkar., (1991), The gamma distribution and derived distributions applied in hydrology. Littleton Colo.,
Water Resources Press.
B.G. Gorenstin., N. M. Campodonico., J. P. Costa., and M. V. F. Pereira, (May 2002), Stochastic Optimization of a Hydro-
thermal System Including Network Constraints, IEEE Trans. Power Syst., vol. 7, pp. 791 - 797.
C. E. Zoumas., A.G. Bakirtzis., J.B. Theocharis., and V. Pertridis, (May. 2004), A Genetic Algorithm Solution Approach to
the Hydrothermal Coordination Problem, IEEE Transactions on Power Systems, vol. 19, No. 2, pp. 1356 -1364.
D. P. Loucks and E. Van Bee, (2005), Water Resources Systems Planning and Management: An Introduction to Methods,
Models and Applications, Studies and Reports in Hydrology, ISBN 92-3-103998-9, UNESCO PUBLISHING.
E. Gil., J. Bustos., and H. Rudnick., (Nov. 2003), Short-Therm Hydrothermal Generation Scheduling Model Using a
Genetic Algorithm, IEEE Transactions on Power Systems, vol. 18, No. 4, pp. 1256 -1264.
F. Zhuang and F. D. Galiana, (May. 1988), Toward a More Rigorous and Practical Unit Commitment by Lagrangian
Relaxation, IEEE Transactions on Power Systems, vol. 3, No. 2, pp. 763 - 773.
H. Brannlund., J. A. Budenko., D. Sjelvgren., and N. Andersons, (Nov. 1986), Optimal short term operation planning of a
large hydrothermal power system based on a nonlinear network flow concept, IEEE Trans. Power Syst., vol. PWRS-1,
pp. 75-82.
H. Yan., P. B. Luh., X. Guan., and P. M. Rogan, (Aug. 1996), A flexible approach to short-term hydrothermal coordination.
Part II: Dual problem solution procedure, IEEE Trans. Power Syst., vol. 11, pp. 1572 - 1578.
H. Yan., P. B. Luh., X. Guan., and P. M. Rogan, (May 1994), Optimization-based scheduling of hydrothermal power
systems with pumpedstorage units, IEEE Trans. Power Syst., vol. 9, pp. 1023 -1031.
H. Yan., P. B. Luh., X. Guan., and P. M. Rogan, (Feb. 1999), Short-term hydrothermal coordination by Lagrangian
relaxation: Solution of the dual problem, IEE Trans. Power Syst., vol. 14, pp. 89 – 95.
I.H. Osman., G. Laporte., (1996), Metaheuristics: A bibliography, Annals of Operations Research, 63, pp. 513 - 623.
IACWD (Interagency Advisory Committee on Water Data), (1982), Guidelines for determining flood flow frequency,
Bulletin 17B. Reston, Va., US Department of the Interior, US Geological Survey, Office of Water Data Coordination.
J. F. Benders, (1962), Partitioning procedures for solving mixed-variables programming problems, Numerische
Methematik, vol. 4, pp. 238- 252.
J. Yang and N Chen, Short Therm Hydrothermal Coordination Using Multi-Pass Dynamic Programming, IEEE Trans.
Power Syst., vol. 4, pp. 1050 - 1056, Aug. 1989.
J.R.M. Hosking and J.R. Wallis, (1997), Regional frequency analysis: an approach based on L-moments. Cambridge,
Cambridge University Press.
K. T. Aoki., K. Satoh., and M. Itoh, (Nov. 1987), Unit commitment in a large-scale power system including fuel
constrained thermal and pumped storage hydro, IEEE Trans. Power Syst., vol. PWRS-2, pp. 1077 - 1084.
L.S. Lasdon, (1970), Optimization Theory of Large Systems, Optimization for Large Systems. New York, Mc. Millan.
Merlin and P. Sandrin, (May 1983), A new method for unit commitment at electricite de france, IEEE Trans. Power App.
Syst., vol. PAS-102, pp. 1218 -1225.
N. Alguacil., and A.J. Conejo, (Feb. 2000), Multiperiod Optimal Power Flow Using Benders Decomposition, IEEE
Transactions on Power Systems, vol. 15, No. 1, pp. 1256 -1264.
N. Gröwe-Kuska, and W Römish., (2005), Stochastic Unit Commitment Power Production Planning, in “Applications of
Stochastic Programming”, edited by Stein W. Wallace and William T. Ziemba, MPS-SIAM Series on Optimization,
pp. 633 - 653, Philadelphia, PA. EEUU.
Nilsson, O. and Sjelvgren, D., (Aug. 2002), Hydro unit start-up costs and their impact on the short term scheduling
strategies of Swedish power producers, IEEE Trans. Power Syst., vol. 12, Issue 1, pp. 38 - 44.
P. B. Luh., D. Zhang., R.N Tomastik, (May 1998), An Algorithm for solving the Dual Problem of Hydrothermal
Scheduling, IEEE Transactions on Power Systems, vol. 13, No. 2, pp. 593 -600.
R. A. Duncan., G. E. Seymore., D. L. Streiffert., and D. J. Engberg, (May 1985), Optimal hydrothermal coordination for
multiple reservoir river systems, IEEE Trans. Power App. Syst., vol. PAS-104, pp. 1154-1161.
S. Ruzic., N. Rajakovic., and A. Vuckovic, (Aug. 1996), A flexible approach to short-term hydrothermal coordination. Part
I: Problem Formulation and general solution procedure, IEEE Trans. Power Syst., vol. 11, pp. 1564 -1571.
S. Virmani., E. C. Adrian., K. Imhof., and S. Mukherjee, (Aug. 1993), Implementation of a Lagrangian relaxation based
unit commitment problem, IEEE Trans. Power Syst., vol. 4, pp. 1373-1380, Nov. 1989. H. Yan, P. B. Luh, X. Guan,
and P. M. Rogan, Scheduling of hydrothermal power systems, IEEE Trans. Power Syst., vol. 8, pp. 1358-1365.
T. S. Dillon., K. W. Edwin., H.D. Kochs., and R. J. Tand, (Nov/Dic. 1978), Integer Programming Approach to the Problem
of Optimal Unit Commitment whit probabilistic reserve determination, IEEE Trans. Power App. Syst. PAS 97, No. 6,
pp. 2154 - 2166.
272