Power plant investment planning by stochastic programming/Stochastinio programavimo naudojimas planuojant elektros energijos infrastruktura ir gamyba.
Sakalauskas, Leonidas ; Zilinskas, Kestutis
1. Introduction
The energy sector needs to be environmentally sustainable while as
being economically sustainable. Energy utilities need to earn an
adequate return and satisfy shareholders, whilst understanding their
corporate responsibilities and a wider social impact of their business.
Uncertainty of the power market should be taken into account when
planning the power system (Freund 2004; Beraldi et al. 2008; Fleten and
Kristoffersen 2008). Although the problem of rational power generation
under uncertainty has been extensively studied, traditional planning
models and methods do not offer good solutions to this problem,
especially in a competitive electricity market environment where many
factors are uncertain (Graymore et al. 2008; Grundey 2008). In this
paper the problem is considered of an energetic concern that has to
invest in a regional system of power plants to meet current and future
demand for electrical power of the region. These plants are to be built
for the first year only, and are expected to operate for some years
under a certain budget, which is to be allocated for different types of
plants. A stochastic optimization model is formulated under the
presumption that the generation outputs and load demands can be modelled
as following to specified continuous probability distributions. The
objective is to find the structure of the power plant capacity that
minimizes the sum of the investment cost and the expected value of the
operating cost over the planning horizon taking into account the impact
on the environment including the appropriated environmental costs to
operating ones. The optimization problem is solved by means of a novel
numerical approach that exploits a particular problem structure.
Finally, we report some preliminary computational experiments.
2. Power Plant Investment Planning Problem
The structure of the task considered corresponds to the power
investment planning problem that often arises in the developing regions.
The model and data considered in the paper involve main parts of the
sustainable energetic development of the region in the long term
perspectives and are created following to sources (Freund 2004; Hezri
and Dovers 2006; Karger and Hennings 2009; Paiders 2008; Stepanonyte and
Blynas 2008; Training Material in Financial Engineering 2009).
Let the plants to be projected for the open field investment. Say,
the details of the problem to be solved are as follows. Let the plants
be expected to operate over T = 15 years. The budget for the
construction of power plants is S = $10 billion, which is to be
allocated for n = 4 different types of plants: gas turbine, coal,
nuclear power, and hydroelectric. The budget should take into account
the discounting factor, because usually investments in construction and
building of power plants are not done once. The objective is to minimize
the sum of the investment cost and the expected value of the operating
cost over T years that leads to minimizing the influence upon the nature
during the process of power generation. Assume, the prognosticated
demand for electric power is distributed with a specified probability
distribution. Assume, m=5 blocks of demand are requiring for different
amount of power during the year.
Known solutions of power planning under uncertainty exploit the
two-stage or multi-stage stochastic programming framework with a
discrete number of scenarios (see Ruszczynski and Shapiro 2003; Wallace
and Fleten 2003; Beraldi et al. 2008; Fleten and Kristoffersen 2008).
However, the adequate evaluation of scenarios and its probabilities is
not an easy task in practice, therefore the analysis of a continuously
distributed set of scenarios may offer more opportunities. The
parameters of distribution of the scenario are choosing by means of
statistical analyses of historical data of energetic development of the
region. Thus, without loss of generality assume the demands in blocks to
be independently and normally distributed.
The mean and standard deviations of the expected power demands that
with durations of the blocks are shown in Table 1.
Power plants are priced according to their electric production
capacity, measured in gigawatts (GW). Table 2 shows the investment cost
for each type of plants (Freund 2004).
Since the production of hydroelectric energy depends on the
availability of rivers that may be dammed, the geography of the region
constrains the hydroelectric power capacity no more than P = 5.0 GW.
The operating costs for the first year of each type of power
plants, as well as the cost of purchasing power from an external source,
are shown in Table 3, where the units are in cents per kilowatt-hour
(KWh). The operating costs consist of the expenses for expenditures of
fuel, water and extra electric power, chemical and technological
materials and of the taxes for air and water pollution, the discounting
factor, the costs of utilization of waste products and of the activity
for the nature safety (Hezri and Dovers 2006; Karger and Hennings 2009;
Paiders 2008; Training Material in Financial Engineering 2009). These
expenses depend linearly on the capacity of the plants to be built
(Stepanonyte and Blynas 2008; Training Material in Financial Engineering
2009). The environmental issues of power plant construction and
exploitation are related with waste and water usage. The waste products
of the gas turbine plant are CO, CO2, NOx, while solid particles and
S[O.sub.2] are additional waste products of the coal plant. The factors
of emissions of coal and gas turbine plants are shown in Table 4.
The amount of water usage is often of great concern for electricity
generating systems as populations increase and droughts become a
concern. General numbers for fresh water usage of different power
sources are shown in Table 5.
The operating costs for hydroelectric and nuclear plants are lower
as these plants make smaller influence upon the natural environment. The
operating costs for nuclear plants don't estimate the costs for the
utilization of the waste products after closing the plant but
corresponding data might be easily included to the task.
Thus, the problem is modeled as a two-stage stochastic linear
program (SLP) model
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (1)
subject to
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)
where
S is the budget for the construction,
P is the capacity of the hydroelectric power,
T is the number of years,
n is the number of the different types of power plants,
m is the number blocks of demand,
x = ([x.sub.1],[x.sub.2], [x.sub.3], [x.sub.4]) is a vector,
representing the capacity to be built for each type of plant,
[y.sub.ijk] is the amount of electricity capacity used to produce
electricity by power plant type
i for demand block j in year k in GW,
[c.sub.i] is the investment cost per GW of capacity for power plant
type i,
[q.sub.i] is the operating cost of power generation for power plant
type i,
[h.sub.j] is the duration of the demand block j,
[D.sub.jk] is the power demand in year k at demand block j:
N([[mu].sub.j], a),
[w.sub.k] is the limitation of the fresh water usage in year k.
Since the model aims to find the best structure of power plants
capacity to satisfy the region power demands the vector x is assumed to
be varying continuously. Of course, the values of the capacities should
be specified implementing the solution, while the details of facility
allocation and possible technical solutions are taken into account.
3. Monte-Carlo estimators for stochastic optimization
The adaptive method for solving SLP (1), (2) by series of
Monte-Carlo samples is applied, exploiting the asymptotic properties of
Monte-Carlo sampling estimators. This method is based on the handling of
a statistical simulation error in a statistical manner and the rule for
iterative control of the size of Monte-Carlo samples (Sakalauskas 2002,
2004).
Details of the method are as follows, in general. Let a two-stage
SLP problem with a complete recourse be considered:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)
subject to a feasible set
D = {x|A x = b, x [member of [R.sup.n.sub.+]}, (4)
where
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)
(See details in Sakalauskas and Zilinskas 2009).
We have by the duality that the gradient of the objective function
might be expressed as
[[nabla].sub.x]F(x)= E(g(x,[zeta])), (6)
where g (x,[zeta]) c-T x [u.sup.*] is given by a set of solutions
of a dual problem (Sakalauskas and Zilinskas 2009)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)
Assume that Monte-Carlo samples Y = ([y.sup.1], [y.sup.2],...,
[y.sup.N]), where [y.sup.i] are independent random variables identically
distributed at density p(x, x), are provided for any x [member of] D.
Then the sampling objective estimator
[??](x) = 1/N [N.summation over (j=1)]f (x, [y.sup.j]) (8)
and the sampling variance estimator
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)
can be obtained from these samples. Next, the gradient can be
evaluated using the same random sample:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)
for any x [member of] D (Sakalauskas and Zilinskas 2006, 2009). The
sampling covariance matrix
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)
is introduced, too.
4. Stochastic procedure for optimization
To create an optimizing sequence, the gradient search approach with
projection to a e-feasible set is applied to avoid problems of
"jamming" or "zigzagging" (Sakalauskas and Ailinskas
2009). The set offeasible directions is defined as follows:
V(x)= {g [member of][[R.sup.n]|Ag = 0, [[for all].sub.1][less than
or equal to]i[less than or equal to] <n([g.sub.j] [less than or equal
to] 0, if [x.sub.j] = 0)},
where [g.sub.U] is assumed as projection of vector g onto the set U
and the [epsilon]--feasible set is also defined by similar way
(Sakalauskas 2004):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The stochastic optimization procedure is defined in a recurrent
manner:
[x.sup.1+1] = [x.sup.t] - [[rho].sup.t] x
[[??].sub.[epsilon]([x.sup.t]), (12)
where [[??].sup.t.sub.[epsilon]] is a projection of stochastic
gradient estimator (10) to the e-feasible set, [MATHEMATICAL EXPRESSION
NOT REPRODUCIBLE IN ASCII] is a step-length multiplier taken at the
point [x.sup.t], and [x.sup.0] [member of] D is some initial point
(Sakalauskas and Ailinskas 2006). Let the initial sample be generated of
size N0. Note that is no great necessity to compute estimators with a
high accuracy when starting the optimization process, because then it
suffices only to approximately evaluate the direction leading to the
optimum. Therefore, one can obtain not so large samples at the beginning
of the optimum search and, later on, increase the size of samples so as
to get the estimate of the objective function with a desired accuracy
just at the time of decision making on finding the solution to the
optimisation problem. Thus, the following rule is proposed for
regulating the sample size (Sakalauskas 2004):
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)
Minimal [N.sub.min] (usually ~ 100) and maximal [N.sub.max]
(usually ~ 1 000 000) values are introduced to avoid great fluctuations
of sample size in iterations. [N.sub.max] can also be chosen from the
conditions on the permissible confidence interval of estimates of the
objective function.
A possible decision on finding of optimal solution should be
examined at each step of the optimization process. Since we know only
the Monte-Carlo estimates of the objective function and that of its
gradient, we can test only the statistical optimality hypothesis. As far
as the stochastic error of these estimates depends in essence on the
Monte-Carlo samples size, a possible optimal decision could be made, if,
first, there is no reason to reject the hypothesis of equality to zero
of the gradient, and, second, the sample size is sufficient to estimate
the objective function with the desired accuracy. The following criteria
used for the making of decision on the optimal solution finding and the
termination of the algorithm:
1. The optimality hypothesis is accepted for some point [x.sub.t]
with the significance 1 - [mu], if
1/n x([n.sup.t] - n) x [??]([x.sup.t])x[(Z([x.sup.t])).sup.-1] x
[??]([x.sup.t])[less than or equal to] Fish ([mu],n,[N.sup.t]-n]). (14)
2. The objective function is estimated with permissible accuracy
[delta], if
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (15)
where [??]([x.sup.t]) is a sampling variance of the objective
function, [[eta].sub.[beta]] is the [beta]--quantile of a standard
normal distribution (Sakalauskas 2002, 2004).
The procedure (12) is iterated adjusting the sample size according
to (13) and testing conditions (14) and (15) at each iteration. If the
latter conditions are met both at some iteration, then there are no
reasons to reject the hypothesis on the optimum finding. Therefore,
there is a basis to terminate the optimization and make a decision on
the optimum finding with an admissible accuracy. If at least one
condition is unsatisfied, then the next sample is generated and the
optimization is continued. The convergence analysis shows that
optimization process should terminate after generating a finite number
of Monte-Carlo samples (Sakalauskas 2002).
5. Implementation in power investment planning
The approach developed is implemented to solve the two-stage SLP
problem of power investment planning defined above. The limit for the
fresh water usage is 5 x [10.sup.4] [m.sup.3] per year ([w.sub.k] =
5-[10.sup.4], k = 1, 2,... 15).
Thus, the first stage contains 6 variables and 4 restrictions,
while the second stage contains 375 variables and 375 restrictions. The
solving algorithm was terminated after 123 iterations. The size of the
last Monte-Carlo sample is 15887, whereas the size of all Monte-Carlo
samples is 290932. Hence, the method requires only 18.3 times (ratio)
more computations in total than the calculation of one function value.
Details of the computational experiment performed are reported in
Fig's 1-4 to illustrate the behavior of the optimization process,
where the dependencies of the objective function, the sample size, the
confidence interval of the objective function and the Hotelling
statistic by the iteration number t are given.
The optimal cost of power plant investment planning problem is
$16.508 [+ or -] 0.028 billion versus the deterministic cost $17.137 [+
or -] 0.053 billion which illustrates the importance of uncertainty to
be taken into account when investments are planned. Traditional planning
methods are using deterministic approach to describe the demand. Thus
the deterministic problem was constructed solving the problem (1), (2)
while the demand of the electric power is equal to the expected demand
[[mu].sub.j] ([[sigma].sub.j] = 0, j = 1, 2,... 5).
The problem solution is shown in Table 6. The structure of the
optimal construction decision based on stochastic data shows that no
power is taken from the external sources and most of the electric power
is generated in hydroelectric and nuclear plants which the operating
costs for environmental safety are lower.
[FIGURE 1 OMITTED]
[FIGURE 2 OMITTED]
[FIGURE 3 OMITTED]
[FIGURE 4 OMITTED]
The approach developed enables us also to investigate the impact of
closure costs of the nuclear power plant on profitability of a power
generation system. Namely, in the fourth column of Table 6, the optimal
decision without nuclear power plants is given, to which the cost of the
power plant investment planning problem $19.725 [+ or -] 0.037 billion
corresponds. Thus, if the closure costs exceed about $3.7 billion, there
is no reason to build the nuclear power plants.
The results of numerical experiments with various limits on the
fresh water usage per year are shown in Table 7.
The changes of optimal construction of power plant capacity are
given in Fig. 5 to a considerable extent by the limits of the fresh
water usage for energy production.
The number of iterations, the total number of the Monte Carlo
trials used for solution finding as well as the ratio of the total
number of trials to number of trials taken at the last iteration are
shown in Table 8 (varying the limits for the fresh water usage).
Hence, the optimization process requires only several times more
computations in the whole as compared with the computation of one
function value at the last iteration. The numerical experiments
corroborate the theoretical conclusions on the convergence the method
(Sakalauskas 2002, 2004) and shows that the approach developed makes it
possible to solve stochastic power plant investment problems with an
admissible accuracy by means of an acceptable amount of computations.
[FIGURE 5 OMITTED]
6. Conclusions
The energetic planning problem taking into account the
environmental impact has been considered containing the energetic
situation of the region. The model and data of the problem solved
involve main parts of the sustainable regional energetic development in
the long term perspectives.
The main data consists of investment costs, operational generating
costs with assumption of the ecological costs and energetic demand. The
dynamics of demand depends on the need of the energy for particular
periods of the year and is described by continuous distribution of
scenarios. The generating of the power is related with large ecological
costs: the expenses for expenditures of fuel, water and extra electric
power, chemical and technological materials and of the taxes for air and
water pollution, the costs of utilization of waste products and of the
activity for the nature safety.
The analysis of the problem in the paper indicates that effective
solution can be done by stochastic programming methods. The stochastic
iterative method has been developed to solve SLP problems by a finite
sequence of Monte-Carlo sampling estimators applied to solve the
stochastic power planning problem. The approach developed enables us to
decrease the total expected costs of building and operating of regional
power system versus the deterministic planning solution taking into
account the impact on the environment as well as to evaluate the closure
costs of nuclear plant for which a building of the nuclear power plant
is profitable.
doi: <DOI>10.3846/tede.2010.46</DOI>
References
Beraldi, P.; Conforti, P.; Violi, A. 2008. A two-stage stochastic
programming model for electric energy producers, Computers &
Operations Research 35(10): 3360-3370.
Fleten, S.-E.; Kristoffersen, T. K. 2008. Short-term hydropower
production planning by stochastic programming, Computers &
Operations Research 35(8): 2656-2671.
Freund, R. M. 2004. Optimization under Uncertainty. Massachusetts
Institute of Technology.
Graymore, M. L. M.; Sipe, N. G.; Rickson, R. E. 2008. Regional
sustainability: How useful are current tools of sustainability
assessment at the regional scale? Ecological Economics 67(3): 362-372.
doi:10.1016/j.ecolecon.2008.06.002
Grundey, D. 2008. Applying sustainability principles in the
economy, Technological and Economic Development of Economy 14(2):
101-106. doi:10.3846/1392-8619.2008.14.101-106
Hezri, A. A.; Dovers, S. R. 2006. Sustainability indicators, policy
and governance: Issues for ecological economics, Ecological Economics
60(1): 86-99. doi:10.1016/j.ecolecon.2005.11.019
Karger, C. R.; Hennings, W. 2009. Sustainability evaluation of
decentralized electricity generation, Renewable and Sustainable Energy
Reviews 13(3): 583-593. doi:10.1016/j.rser.2007.11.003
Paiders, J. 2008. Status of environmental protection as a source
finance for regional economic development: measurement of environmental
and regional policy with the Fisher function, Journal of Environmental
Engineering and Landscape Management 16(1): 45-55.
doi:10.3846/1648-6897.2008.16.45-55
Ruszczynski, A.; Shapiro, A. 2003. Stochastic programming models,
Handbooks in Operations Research and Management Science 10: 1-64.
doi:10.1016/S0927-0507(03)10001-1
Sakalauskas, L. 2002. Nonlinear stochastic programming by
Monte-Carlo estimators, European Journal on Operational Research 137:
558-573. doi:10.1016/S0377-2217(01)00109-6
Sakalauskas, L. 2004. Application of the Monte-Carlo method to
nonlinear stochastic optimization with linear constraints, Informatica
15(2): 271-282.
Sakalauskas, L.; Ailinskas, K. 2006. Application of statistical
criteria to optimality testing in stochastic programming, Technological
and Economic Development of Economy 12(4): 314-320.
Sakalauskas, L.; Ailinskas, K. 2009. Stochastic power plant
investment planning problem, in Proc. of the 5th International Vilnius
Conference "Knowledge-based Technologies and OT Methodologies for
Strategic Decisions of Sustainable Development" KORSD2009:
September 30--October 3, 2009, Vilnius, Lithuania. Vilnius: Technika,
266-210.
Stepanonyte, D.; Blynas, J. 2008. Thermodynamic assessment of
carbamide use for reducing boiler NOX, CO flue gas emissions, Journal of
Environmental Engineering and Landscape Management 16(3): 143-150.
doi:10.3846/1648-6897.2008.16.143-150
Training Material in Financial Engineering, 2009. Cleaner
Production in Baltic Countries 2009, ENSI Energy Saving International
AS, The Norwegian Effiency Group, NEFCO Nordic Environment Financial
Corporation, Part 4. Environmental Advantages, Table 1.
Wallace, S. W.; Fleten, S. E. 2003. Stochastic programming models
in energy, Handbooks in Operations Research and Management Science 10:
637-677. doi:10.1016/S0927-0507(03)10010-2
Leonidas Sakalauskas (1), Kestutis Zilinskas (2)
University of Siauliai, Visinskio g. 19, LT-77156 Siauliai,
Lithuania
E-mails: (1) sakal@ktl.mii.lt; (2) kest.zil@gmail.com
Received 11 February 2010; accepted 20 October 2010
Leonidas SAKALAUSKAS. Doctor Habilis, Professor, Dept of
Operational Research, Institute of Mathematics and Informatics, Vilnius,
Lithuania. Phd (Candidate of Technical Sciences, Kaunas Politechnical
Institute, 1974), Doctor Habilis (Institute of Mathematics and
Informatics, 2000), Professor (Vilnius Gediminas Technical University,
2006). He is a Vice-President of the Lithuanian Operation Research
Society (2001), Member of International Association of Official
Statistic (IAOS, 2001), Elected Member of the International Statistical
Institute (ISI, 2001), Member of European Working Groups on financial
modelling (2001), multicriterial decisions (2002), continuous
optimization (2003), operations research iin construction and
sustainable development (2009). Author more 130 scientific papers.
Research interests: continuous optimization, stochastic approximation,
data mining, monte-carlo method, optimal design.
Kestutis ZILINSKAS. Associate Professor, Phd, Dept of Informatics.
Siauliai University. First degree in mathematics and physics (Siauliai
Pedagogical Institute, 1981), Master of Science (1994), Phd (2007).
Member of European Working Group on continuous optimization (2007),
member of Council of the Lithuanian Operational Research Society (2007).
Author of 7 scientific articles. Research interests: stochastic
programming, Monte Carlo method, statistical methods.
Table 1. Power demand during the year
The standard
deviation of
Expected power power demands, Block
Demand Block demand, [mu] (GW) [sigma] (GW) duration, (h)
1 26.0 1.3 490
2 21.5 1.1 730
3 17.3 0.9 2190
4 13.9 0.7 3260
5 11.1 0.6 2090
Table 2. Investment costs for power plants
Power plant type Cost, $ [10.sup.8]/GW
Gas Turbine 1.1
Coal 1.8
Nuclear power 4.5
Hydroelectric 9.5
Table 3. Power generation operating costs
Power plant type Operating cost, (cents/kWh)
Gas Turbine 3.92
Coal 2.44
Nuclear 1.40
Hydroelectric 0.40
External Source 15.0
Table 4. Factor of the emissions of natural gas and coal
Factor of the emissions Natural gas * Coal **
S[O.sub.2] 0.10 16.0
[NO.sub.x] 1.00 4.5
CO 0.01 0.03
Volatile organics 0.01 0.8
Solid particles 0.001 1.4
C[O.sub.2] (t/TJ) 56.9 94.6
* g/kg ** l/kg.
Table 5. Fresh water usage for different power sources
Power source Water usage ([m.sup.3]/GWh)
Natural gas 150
Coal 480
Nuclear power 550
Hydroelectric 1430
Table 6. Power plant capacity optimal construction decisions
Power plant type Decision based Decision based Decision based
on expected on stochastic on stochastic
data (GW) data (GW) data without
nuclear power
plant (GW)
Gas Turbine 1.78 4.45 9.31
Coal 3.23 4.36 10.87
Nuclear 4.07 4.60 0
Hydroelectric 5.00 5.00 5.00
Cost (billion $) 17.137 [+ or -] 16.508 [+ or -] 19.725 [+ or -]
0.053 0.028 0.037
Table 7. Power plant capacity optimal construction,
costs and decisions with respect to fresh water usage
Fresh water Gas Coal Nuclear Hydroelectric Optimal cost
usage Turbine (GW) (GW) (GW) (billion $)
([10.sup.4]
[m.sup.3])
5 4.5 4.4 4.6 5.0 16.508
4 6.9 1.9 6.5 3.1 17.854
3 6.9 1.9 8.8 0.8 19.705
2 8.8 0 9.6 0 24.113
1 15.4 0 3.1 0 38.911
Table 8. Number of iterations, the total number of Monte Carlo
trials used for optimal solution finding, the ratio of the total
number of trials to the number of trials taken at the last
iteration by the limit on the fresh water usage
Fresh water usage Confidence interval Number of Total number Ratio
([10.sup.4] (billion $) iterations of trials
[m.sup.3])
5 0.028 123 290932 18.3
4 0.027 127 291224 18.4
3 0.033 119 289745 18.2
2 0.034 133 292335 18.1
1 0.035 135 293457 18.5
