ABSTRACT
Title of Dissertation: THERMAL GENERATION ASSET VALUATION
PROBLEMS IN A COMPETITIVE MARKET
Wei Zhu, Doctor of Philosophy, 2004
Dissertationdirectedby: Assistant Professor Chung-Li Tseng
Department of Civil and Environmental Engineering
With deregulation in the electric power industry, traditional approaches for
minimizing production costs have become unfit for the present competitive en-
vironment. Owners of generation assets must now consider price uncertainty
in solving unit commitment problems for scheduling and operating their power
plants. Operation flexibility of the generating assets, such as fuel switching and
overfire, becomes an important issue. Because in a competitive market with
volatile electricity prices, these flexibility may add significant values. On the
otherhand, operationalconstraints, suchasrampandminimumuptime/downtime
constraints, present physical limits for the generating assets to flexibly react to
rapid price changes, which have a negative effect on the asset value. Both of the
operational flexibility and operational constraints must be considered simulta-
neously so as to achieve optimal operation under uncertainty. This dissertation
devotes to this very important subject.
Deregulation in the power industry allows new firms to freely enter the gen-
eration markets. As a result, capacity expansion is no longer the responsibility
of local utility companies and has become a pure investment problem. Overesti-
mating the value of a power may result in stranded capital for a long time period.
Therefore, to ensure a successful investment a fair valuation method is essential.
The generation asset valuation must fully account for market uncertainty, which
results in not only risks but also opportunities. To minimize the risks, one must
first have sound models for market uncertainties. In this research, we consider
not only the uncertainties of electricity price and fuel price, but also environ-
ment temperature because some characteristics of power plants may be sensitive
to the temperature. To fully capitalize on profitable opportunities arising in
the marketplace due to price spreads of different commodities, such as fuel and
electricity, a real options approach is considered, in which different options are
exercised at different but ?optimal? timings.
Overall, this research is expected to contribute a new methodology for fair
generation valuation that accounts for multiple and interdependent uncertain-
ties and complex physical constraints. The proposed approach can help opera-
tors achieving optimal operation and investors making appropriate investment
decisions. In the long run, customers also benefit from the improved societal
efficiency.
THERMAL GENERATION ASSET VALUATION PROBLEMS
IN A COMPETITIVE MARKET
by
Wei Zhu
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
2004
Advisory Committee:
Assistant Professor Chung-Li Tseng, Chairman/Advisor
Dr. Ibrahim Assakkaf
Associate Professor Zhi-Long Chen
Assistant Professor Nengjiu Ju
Associate Professor David Lovell
c Copyright by
Wei Zhu
2004
ACKNOWLEDGEMENTS
First of all, I need to send my greatest appreciation to my advisor, Dr.
Chung-Li Tseng, from whom I learn how to do research including how to find,
analyze and solve problems. In addition, I also learn from Dr. Tseng a practical
but rigorous work style, which will have a positive influence on my future work,
study and life.
I also appreciate other members in my dissertation committee, Dr. David
Lovell, Dr. Zhi-Long Chen, Dr. Nengjiu Ju and Dr. Ibrahim Assakkaf, for their
valuable suggestions and comments.
I thank my friend Dr. Tong Zhao for his kind helps in my life and many
useful discussions about my research.
Finally, I dedicate this dissertation to my parents and my wife for their love
and support.
ii
TABLE OF CONTENTS
List of Figures vii
List of Tables viii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Summary of contributions . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organization of the dissertation . . . . . . . . . . . . . . . . . . . 3
2 Background 6
2.1 Power plant operation . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Unit commitment . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Fuel switching . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.3 Overfire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Maintenance of thermal units . . . . . . . . . . . . . . . . 12
2.2 Multivariate linear regression . . . . . . . . . . . . . . . . . . . . 13
2.3 DCF analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Options theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Least squares Monte Carlo method . . . . . . . . . . . . . . . . . 19
3 Literature Review 22
3.1 Unit commitment problem . . . . . . . . . . . . . . . . . . . . . . 22
3.1.1 Deterministic unit commitment problem . . . . . . . . . . 22
iii
3.1.2 Stochastic unit commitment problem . . . . . . . . . . . . 23
3.1.3 Methodologies . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Real options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Applications of real options in electric industry . . . . . . 28
3.3 Asset valuation of power generation units . . . . . . . . . . . . . . 30
3.3.1 Overviews . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.2 Valuation methods . . . . . . . . . . . . . . . . . . . . . . 32
4 Optimal Self-Scheduling Problem 36
4.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.1 The mathematical formulation . . . . . . . . . . . . . . . . 39
4.1.2 Related methods . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 Algorithm development . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.1 A network graph approach . . . . . . . . . . . . . . . . . . 45
4.2.2 An active-set method for solving (Qt2t1) . . . . . . . . . . . 50
4.2.3 A numerical test on ramp-constrained SSP . . . . . . . . . 55
4.3 Stochastic ramp-constrained SSP . . . . . . . . . . . . . . . . . . 57
4.3.1 Solving ramp-constrained SSP using LSMC . . . . . . . . 59
4.3.2 Numerical tests . . . . . . . . . . . . . . . . . . . . . . . . 61
4.4 Summery and conclusions . . . . . . . . . . . . . . . . . . . . . . 62
5 Valuing Power Generation Units with Fuel Switching Options 65
5.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.1.1 Overview of fuel-switching units . . . . . . . . . . . . . . . 67
5.1.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
iv
5.1.3 Fuel-switching options . . . . . . . . . . . . . . . . . . . . 70
5.1.4 Profit function of a fuel-switching unit . . . . . . . . . . . 72
5.1.5 Operational constraints of a fuel-switching unit . . . . . . 72
5.2 Problem formulation and solution procedure . . . . . . . . . . . . 73
5.2.1 Solution procedure . . . . . . . . . . . . . . . . . . . . . . 74
5.2.2 Boundary conditions . . . . . . . . . . . . . . . . . . . . . 76
5.2.3 Price processes . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.4 Algorithm development . . . . . . . . . . . . . . . . . . . . 79
5.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3.1 Baseline: a non-switching case . . . . . . . . . . . . . . . . 81
5.3.2 A fuel-switching unit . . . . . . . . . . . . . . . . . . . . . 84
5.3.3 Sensitivity analysis on ?gas;oil . . . . . . . . . . . . . . . . 86
5.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Valuing Thermal Generation Units with Overfire Options and
Maintenance Constraints 89
6.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.2 A valuation framework considering overfire options and mainte-
nance constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.1 The mathematical model . . . . . . . . . . . . . . . . . . . 95
6.2.2 Temperature model . . . . . . . . . . . . . . . . . . . . . . 102
6.2.3 Stochastic price process . . . . . . . . . . . . . . . . . . . 104
6.3 Algorithm development . . . . . . . . . . . . . . . . . . . . . . . . 104
6.3.1 Solution procedure . . . . . . . . . . . . . . . . . . . . . . 104
6.3.2 Overfire options . . . . . . . . . . . . . . . . . . . . . . . . 106
6.3.3 Maintenance options . . . . . . . . . . . . . . . . . . . . . 107
v
6.3.4 Boundary conditions . . . . . . . . . . . . . . . . . . . . . 107
6.3.5 Algorithm for the asset valuation . . . . . . . . . . . . . . 108
6.4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 Valuing a GT with overfire capacity and maintenance con-
tract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.4.2 Overfire option value . . . . . . . . . . . . . . . . . . . . . 119
6.4.3 Maintenance option value . . . . . . . . . . . . . . . . . . 121
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7 Conclusions and Further Research Directions 123
References 126
vi
LIST OF FIGURES
1.1 Overview of the research. . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 An example of production schedule for an overfired unit. . . . . . 11
4.1 An example network graph with five time periods. . . . . . . . . . 48
4.2 A feasible solution to Q150 . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Comparison of average CPU times for solving (P). . . . . . . . . . 57
4.4 Optimal dispatch rule q?1(?) for different ramp rates. . . . . . . . . 61
4.5 An example of  (q1j?1) with ?q=100MW. . . . . . . . . . . . . . 63
5.1 A state transition diagram between two fuels (on-line and off-line). 71
5.2 CPU time of the lattice model and the LSMC approach. . . . . . 83
5.3 The asset value of the lattice model and the LSMC approach. . . 84
5.4 The asset value with and without fuel switching options (FSO). . 86
5.5 The asset value vs. ?gas;oil. . . . . . . . . . . . . . . . . . . . . . . 87
6.1 State transition diagram including operation and maintenance
processes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2 The state transition diagram for this case. . . . . . . . . . . . . . 116
6.3 Capacity value of the GT over time. . . . . . . . . . . . . . . . . . 118
6.4 Asset value affected by environment temperature in summer. . . . 119
6.5 Asset value affected by environment temperature in winter. . . . . 120
6.6 Capacity value affected by overfire limit. . . . . . . . . . . . . . . 121
vii
LIST OF TABLES
4.1 Average CPU time (seconds) . . . . . . . . . . . . . . . . . . . . . 56
5.1 Mean reverting process coefficients of electricity, gas and oil . . . 82
5.2 Mean log Price of electricity: mt(t) . . . . . . . . . . . . . . . . . 83
5.3 Average CPU time (seconds) . . . . . . . . . . . . . . . . . . . . . 83
5.4 Asset value (dollars) . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Asset Value (dollars) . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.1 Value of the parameters of the temperature model . . . . . . . . . 103
6.1 Mean reverting process coefficients of electricity and gas . . . . . 116
6.2 Mean log Price of electricity: mt(t) . . . . . . . . . . . . . . . . . 117
viii
Chapter 1
Introduction
1.1 Motivation
With deregulation in the electric power industry, traditional approaches for
minimizing production costs have become unfit for the present competitive en-
vironment. Owners of generation assets must now consider price uncertainty
in solving unit commitment problems for scheduling and operating their power
plants. Operation flexibility of the generating assets, such as fuel switching and
overfire, becomes an important issue. Because in a competitive market with
volatile electricity prices, these flexibility may add significant values. On the
otherhand, operationalconstraints, suchasrampandminimumuptime/downtime
constraints, present physical limits for the generating assets to flexibly react to
rapid price changes, which have a negative effect on the asset value. Both of the
operational flexibility and operational constraints must be considered simulta-
neously so as to achieve optimal operation under uncertainty. This dissertation
devotes to this very important subject.
Deregulation in the power industry allows new firms to freely enter the gen-
1
eration markets. As a result, capacity expansion is no longer the responsibility
of local utility companies and has become a pure investment problem. Overesti-
mating the value of a power may result in stranded capital for a long time period.
Therefore, to ensure a successful investment a fair valuation method is essential.
The generation asset valuation must fully account for market uncertainty, which
results in not only risks but also opportunities. To minimize the risks, one must
first have sound models for market uncertainties. In this research, we consider
not only the uncertainties of electricity price and fuel price, but also environ-
ment temperature because some characteristics of power plants may be sensitive
to the temperature. To fully capitalize on profitable opportunities arising in
the marketplace due to price spreads of different commodities, such as fuel and
electricity, a real options approach is considered, in which different options are
exercised at different but ?optimal? timings.
Overall, this research is expected to contribute a new methodology for fair
generation valuation that accounts for multiple and interdependent uncertain-
ties and complex physical constraints. The proposed approach can help opera-
tors achieving optimal operation and investors making appropriate investment
decisions. In the long run, customers also benefit from the improved societal
efficiency.
1.2 Summary of contributions
The research in this dissertation has the following original contributions:
? It uniquely develops an efficient method to solve ramp-constrained self-
scheduling unit commitment problem with and without price uncertainties.
2
A polynomial-time algorithm is proposed for solving the self-scheduling
problem when the electricity prices are known with certainty.
? It is the first one to propose a general framework to value a thermal gener-
ation unit with fuel-switching options considering operational constraints.
In this framework, three correlated uncertainties including electricity price
and two different fuel prices are considered.
? It uniquely integrates both overfire options and maintenance constraints
to value a thermal generation unit in competitive power market.
? It is the first one to incorporate a stochastic ambient temperature model
with the asset valuation of power plants.
1.3 Organization of the dissertation
The remaining sections of this dissertation are structured as follows. Chapter
2 presents some background knowledge related to this research, including power
plant operations, multivariate linear regression, discounted cash flow (DCF),
and options theory. Chapter 3 provides a thorough literature review in unit
commitment, real options, and asset valuation of power generation units. A
self-scheduling unit commitment problem, subject to ramp constraints and price
uncertainties, is discussed in Chapter 4. A regression-based method is devised
to determine the optimal commitment and dispatch decision rule under price
uncertainty in terms of reductions of fuel economy, heat-electricity transforma-
tion efficiency, and available generation capacity. Chapter 5 presents a Monte
Carlo (MC) simulation approach to value fuel-switching units. Chapter 6 values
3
a gas turbine considering overfire options, maintenance constraints and environ-
ment temperature in the competitive power market based on a MC method.
Finally, Chapter 7 concludes this dissertation and suggests some future research
directions.
An overview of this dissertation is illustrated in Fig. 1.1. It can be seen that
this dissertation is composed of three main parts. Part I focuses on the optimal
self-scheduling problem in the deregulated electric market (Chapter 4). Part II
discusses the value of a power generating unit with fuel switching options (Chap-
ter 5). In Part III, overfire options, maintenance constrains, and environment
temperature are considered to value a thermal generation unit in the competitive
power market (Chapter 6).
4
Optimal self-scheduling problem
with ramp constraints
Part I
Part II
Part III
(Chapter 4)
Valuing power generation units
with fuel switching options
(Chapter 5)
Valuing thermal power generation units
considering overfire options,  maintenance
constraints and environment temperature
(Chapter 6)
Figure 1.1: Overview of the research.
5
Chapter 2
Background
In this Chapter, a brief introduction of background knowledge related to this
research will be given, including power plant operation, multivariate linear re-
gression, DCF analysis, options theory and least squares Monte Carlo approach.
2.1 Power plant operation
In terms of the load and size, power plants can be classified into two groups:
base-load units and peak-load units. The base-load units are normally with
large size, including nuclear units, hydro units and large-scale thermal units
etc. Such units may always stay on-line whether in regulated or deregulated
environment except for scheduled maintenance or unexpected malfunctions. On
the other hand, the peak-load units are smaller. One representative is gas turbine
(GT). Because a GT can start up within minutes, it is preferred in a volatile
competitive power market. In this dissertation, I focus on thermal power plants.
Some important concepts relative to the operation of thermal power plants are
provided next.
6
2.1.1 Unit commitment
Unit commitment (UC) is an important optimization problem for power util-
ities to economically schedule generating resources to achieve cost minimization
under the traditional regulatory regime. Although the electricity industry is
moving toward deregulation, the importance of the UC does not diminish along
with the restructuring trend.
The objective of the traditional UC problem is to minimize the total generat-
ing cost over the planning horizon subject to system constraints, such as demand
and spinning reserve constraints, and operational constraints, such as capacity
constraints, minimum up/down time constraints and ramp rate constraints.
In this dissertation, only the gas-fired or oil-fired units are considered. The
dynamic processes of a gas unit operation are relatively simple. For such a
generation unit, the startup (or shutdown) cost can be estimated by a constant
or a linear function of startup (or shutdown) rate. The fuel cost can be captured
by a quadratic function of power amount produced in the corresponding time
period.
There are many constraints considered in the typical UC problem. They are
stated as follows.
? Demand constraint
The amount of power produced must equal the power consumed in each
time period. This is due to the unique characteristic of electricity that it
cannot be stored in inventory.
? Spinning reserve constraint
Spinning reserve refers to capability that the system can quickly make up
7
for loss of some unit(s) and may be modeled as the total capacity of all
on-line units less the present load. The amount of spinning reserve at any
time must follow certain rules, usually set by regional reliability councils.
? Capacity constraint
There exists a upper bound (qmax) and lower bound (qmin) for the produc-
tion level of each unit, which is determined by the physical characteristics
of each unit.
? Minimum up/down time constraint
A thermal unit is turned on (resp. shut down), it is required to stay on-
line (resp. off-line) for a minimum period, known as the minimum uptime
(resp. downtime), before it can be shut down (resp. turned on) again. In
other words, a thermal unit cannot switch frequently between the on-line
and the off-line mode, due to the unit?s response time and the damaging
effects of stress.
? Ramp rate constraint
Ramp rate limits the capability of a unit to move between scheduled op-
erating levels over short time periods. With the ramp rate constraints,
the generation level of a unit becomes interdependent in all hours, which
complicates the solution procedure of the UC problem.
More detailed information for UC can be found in Tseng (1996), Baldick
(1995) and Lai (1999).
8
2.1.2 Fuel switching
Generally speaking, fuel switching of a generating unit refers to the ability to
convert alternate fuels, such as nature gas (gas, for short) or fuel oil, to electricity.
Switching occurs when one fuel out-of-the-money is replaced by another in-the-
money (or less out-of-the-money), and can be categorized based on the rate of
occurrence:
? Short-term: switch between gas and oil in dual-fired units within hours;
? Mid-term: switch from one unit which can only burn gas or oil to another
dual-fired unit through device modifications within days or weeks;
? Long-term: switch from a gas-fired unit to an oil-fired unit (or from an oil-
fired unit to a gas-fired unit) through new equipment installation within
months or years.
In power industry, players may prefer nature gas to fuel oil because nature gas is
much ?cleaner? than fuel oil under environment restriction on emission of waste.
Therefore, fuel switching has been considered as an emission abatement means.
On the other hand, nature gas prices are much more expensive than fuel oil
prices based on per British thermal unit. Power producers may have to react to
the soaring price of natural gas by switching to cheaper, more environmentally
harmful fuel sources. Overall, to reduce power producers? exposure to price
volatility or possible supply disruptions in the present deregulated environment,
industrial users are expected to increasingly seek the flexibility to switch fuels
using hybrid technologies. Motivated by this, this dissertation focuses on the
short-term switchable units.
9
2.1.3 Overfire
Overfire is an ability to generate power over the upper bound of a unit?s
production capacity (qmax) under the normal conditions. The disadvantage of
overfire is that the unit may wear out more quickly because the overfiring temper-
ature inside the unit is much higher than the designed one in normal conditions.
This is also the reason why a unit is not allowed to overfire continuously for a
long time period. Therefore, a unit that overfires frequently will require more
frequent maintenance. In addition, there also exists an upper limit (qover) for
the overfired production level due to the damage effects of high temperature.
Normally, qover is different from unit to unit and it is usually about 5 ? 20%
over qmax. In a volatile market, overfire can be viewed as a real option ( the
concept of real options is reviewed in Section 2.4), which can be exercised when
the benefit outweighs the cost of outage due to maintenance. Fig. 2.1 shows a
typical production schedule of a unit with overfire capacity.
Furthermore, overfire can be regarded as a compound options (an option of
options), because the a unit can be overfired only when it has been on-line. In
other words, overfire options cannot be isolated from the real option of turning
on/off the power plant.
In a regulated world, overfire is only used as a temporary remedy in emer-
gency. For example, when a large unit is shut down suddenly due to a serious
malfunction, and operators cannot obtain enough spinning-reserved capacity or
turn on the other units in a short time to meet the demand load, a simple and
efficient way is to overfire some on-line units to meet the demand without delay
and startup costs. After deregulation, the demand constraints do not exist any
more especially for some peak-load units controlled by individual owners, who
10
0                 5                 10                 15                20
Time (Hours)
Output
qover
qmax
qmin
Figure 2.1: An example of production schedule for an overfired unit.
produce for profit. In this situation, overfire can be viewed as a useful option if
exercised properly.
There are two types of overfire processes in thermal power generation units
as follows:
1. Similar to the fuel switching process (especially for large-scale units), two
fuels can be burned to generate power. One fuel is assumed to be consider-
ably more expensive and provides additional capability. In this sense, the
fuel cost function will also change correspondingly during overfire.
2. Only one kind of fuel is burned, but additional capacity is provided by
additional fuel (particularly for small-scale units). The fuel cost function
will not change.
In this dissertation, overfire is assumed to be the latter case for small-size power
11
generation units. The capacity of overfired units can be improved around 5 ?
15% over qmax by adding the same additional fuel.
The overfire decisions involve the amount of power to be added and the
times at which they should be added. Typically, the overfire options should be
exercised without any hesitation once they are profitable in the short run. How-
ever, in the long run, overfire may increase maintenance cost and maintenance
frequency at the same time, which may cost more than the profit made from
overfiring. Therefore, overfire options must be considered in conjunction with
maintenance constraints. That is, the value of the overfire options should be
incorporated in the asset valuation framework to maximize the total profit of a
thermal generation unit. Omission of the option value of overfire may result in
over or under valuation of power plants.
2.1.4 Maintenance of thermal units
For a thermal generation unit, whether a steam turbine (ST) or a gas turbine
(GT), maintenance in time is always one necessary operation to keep the unit
working economically and reliably. A typical maintenance process of thermal
unit includes: (1) let the unit cool down; (2) clean all working parts; (3) test hot
section components; (4) replace ineffective ones with new parts; (5) reassemble
the unit and lubricate it.
In this dissertation, we do not consider the detailed maintenance process
and how to improve the reliability of thermal units, but only focus on how to
minimize maintenance costs while preserving service safety.
The maintenance cost consists of the following two parts:
1. Direct cost: including the salary of maintenance crews, the cost of new
12
parts and some resources and utilities, such as electricity, gas and water.
2. Indirect cost: during the time period of maintenance interval, the unit has
to stay off. That means loss of many hours for generating power and the
corresponding revenue.
In power industry, maintenance itself is a complicated problem, especially for
a large unit (Shahidehpour and Marwali 2000). A maintenance manager must
consider many factors, including crew availability, resource availability, seasonal
limitations, desirable schedule, and reliability check, before making any mainte-
nance plan. In order to simplify maintenance constraints, we transform all these
constraints into a maintenance contract, which is common in small-scale units
and will be discussed in detail in Chapter 6. The payment of the maintenance
contract can be viewed as maintenance cost. In this dissertation, a valuation
framework is developed for determining the value of thermal generating unit
while considering maintenance contracts, overfire options and other operation
constraints in the competitive power market.
2.2 Multivariate linear regression
The multiple regression model is typically generalized to handle the pre-
diction of several dependent variables. To illustrate the model, we may let
x1;x2;???;xn be n dependent variables related to a response variable y. The
linear regression model with a single response takes the following form:
y = a0 +a1x1 +???+anxn +" (2.1)
The term linear regression refers to that the right hand side of (2.1) is a linear
13
function of the unknown parameters a0;a1;???;an. It is not necessary for the
predictor variables to enter the model as first-order terms.
When we have m independent observations on y and the associated values of
x1 to xn, the complete model becomes
y1 = a0 +a1x11 +a1x12 +???+anx1n +"1
y2 = a0 +a1x21 +a1x22 +???+anx2n +"2
... ... ...
ym = a0 +a1xm1 +a1xm2 +???+anxmn +"m
(2.2)
where the error terms " are assumed to have the following properties:
? E("i) = 0;
? var("i) =  2;
? cov("i;"j) = 0; i 6= j.
The purpose of the regression analysis is to develop a functional relation
that will allow the investigator to predict the response for given values of the
predictor variables. Thus it is necessary to fit the model (2.2) to the observed y
and the associated x. That is, we must determine the values for the regression
coefficients a and the error variance  2 consistent with the available data. The
value of a can be obtained by the following formula derived from least squares
estimation:
A = (XTX)?1XTY (2.3)
14
where A = (a0;a1;???;an)T, Y = (y1;y2;???;ym)T and
X =
0
BB
BB
BB
BB
BB
@
1 x11 x12 ??? x1n
1 x21 x22 ??? x2n
... ... ... ... ...
1 xm1 xm2 ??? xmn
1
CC
CC
CC
CC
CC
A
Let ?Y = (?y1; ?y2;???; ?ym)T = XA denote the fitted value of Y, ?y = Pmi=1 yi=m
be the average value of Y. Thus, the quality of the model fit can be measured
by the coefficient of determination
R2 =
Pm
i=1(?yi ? ?y)
2
Pm
i=1(yi ? ?y)2
(2.4)
Here R is called the multiple correlation coefficient. When R is close to 1, it
means that the fitted equation passes through most of the data points. On
the other hand, when R is close to 0, it represents the dependent variables
x1;x2;???;xn have no influence on the response.
2.3 DCF analysis
Before the electricity industry move toward deregulation, electricity prices
were set by the regulators based on the cost of service. At that time, the eco-
nomic viability of investment in power generation units could be determined
by a traditional economic evaluation, so called the discounted cash flow (DCF)
method (e.g., Riggs et al. 1996). The DCF method identifies estimated cash
flows over time, and then discount the cash flows back to the present with cri-
terion of net present value (NPV). NPV represents the difference between the
present value of the discounted cash flows and the investment costs. If the NPV
15
is positive, the investment is accepted, otherwise, it is rejected. In the research,
the corresponding NPV can be determined by this DCF analysis coupled with
a simulation model that produces the projected cash flow of a generation unit
under some loads. For example, a cash flow stream (x0;x1;???;xT) that spans
over time period [0, T], the NPV is as follows:
NPV =
TX
t=0
xt
(1+r)t (2.5)
where r is the discount rate per time period.
DCF method assumes that the investment opportunity is not reversible and
is a now or never opportunity. That means new information and future opportu-
nities are ignored. Therefore, DCF often underestimates the value of investment
strategies. Although DCF method tends to undervalue assets in the presence of
uncertainty since that approach tends to ignore the value of real options, such
as turning off a plant when the price is too low, this analysis can still helpful
and play a role in valuing a power plant in the current electric industry.
2.4 Options theory
A brief introduction to options theory will be given in this section. A more
thorough introduction can be found in classical textbooks, such as Luenberger
(1998). Some basic concepts about options theory in finance are stated as follows:
? Option: an option is defined as the right, but not the obligation, to buy
(or sell) an asset under specified terms (e.g., Luenberger 1998; Hull 1999).
Usually there are a specified price and a specified period of time over which
the option is valid.
16
? Call option: A call option gives the right to purchase something.
? Put option: A put option gives the right to sell something.
? Exercise price (or strike price): For each option, usually there is a specified
price (called an exercise price or strike price) at which the underlying asset
can be purchased or sold upon exercise of the option and within a specified
period of time over which the option is valid.
? American option: An American option allows exercise at any time before
and including the expiration date.
? European option: A European option allows exercise only on the expiration
date.
? In the money or out of money: A call option is called in the money, at the
money, or out of the money, depending on whether the underlying asset?s
price is greater than, equal to, or less than the exercise price; whereas put
options have reverse terminology, since the payoff at exercise are positive
only if the asset?s price is less than the strike price.
For example, consider a call option that allows you to buy a specified stock
at exercise price K at some future time T. This option will be valuable if the
stock price at T, denoted by S(T), turns out to be higher than K. The call
option can be exercised by buying the stock at K and then reselling the stock
back to the market at a profit of S ?K. However, if the stock price falls below
K at T, this call option is virtually worthless then.
In general, an option provides an opportunity for the decision-maker to take
some action after uncertainties are revealed. For example, the owner of a call
17
option will exercise the option only after learning that the stock price S(T) is
greater than K. Again, to determine whether holding this option is worthy the
expected option payoff should be compared with the cost to acquire the option.
Note that risk preference can be taken into account through either the discount
rate or the probability measure.
In the recent, the concept of options has been extended toward a variety of
areas other than financial contracts. One of the most popular subjects is known
as real options valuation. Real options allows evaluating the investment tak-
ing into account the value of flexibility embedded in real operational processes,
activities, or investment opportunities that are not financial instruments (e.g.,
Trigeorgis 1996). Typically, a real option gives the option holder the right but
not the obligation to take an action in the future. An embedded real options
in valuing electric generating units is one immediate example of real options
because turning on/off a power plant is an obvious real option in the volatile
marketplace. It is no doubt that a power plant owner would only exercise the
operational right at time t when the electricity price less generating fuel cost
is positive at that time. A spark spread call option is an option that yields its
holder the positive part of electricity price less the production cost at its matu-
rity time. Therefore, the value of the underlying power plant can be estimated
by summing up a set of spark spread call options with maturity time spanning
the lifetime of the plant (e.g., Deng 1999).
Another recognition of real options theory is that the most valuable invest-
ment opportunities may come with uncertainty (Ameram 1999). Its focus is
strategic investment and operating decisions. Some types of real options are
given below (Trigeorgis 1996):
18
? Option to defer: enables management to defer investment and benefit from
more information. It is an American call option where the investment is
the exercise price and value of underlying asset is the operating cash flow.
? Option to expand: is a call option to acquire an additional part of the base
project, paying the investment as exercise price.
? Option to contract: is to reduce the production if market conditions turn
bad. It is a put option on part of the base sale project with exercise price
equal to the potential cost savings.
? Option to abandon: is to abandon a project when the market conditions
turn bad in order to avoid loss. It is an American put option on the
project?s current value with an exercise price of the salvage value.
? Option to switch: is the possibility to switch one input to a cheaper input
or one output to a more profitable output as the prices of input and output
fluctuate.
More discussions on real options can be found in Chapter 3 of literature
review.
2.5 Least squares Monte Carlo method
The least squares Monte Carlo (LSMC) approach was first introduced by
Longstaff and Schwartz (2001) to value American-like financial options. As well
known that standard simulation programs follow forward algorithms to generate
the paths of state variables over time. It is not enough to value American-like
options purely by the forward algorithms, and generally a backward algorithm
19
is required to look for the optimal exercise strategy due to the property of early
exercise.
At any exercise time, the holder of an American option compares the payoff
of immediate exercise with the expected payoff from retaining it, then exercise if
the immediate payoff is higher. The holder can get the highest expected payoff
by doing so, thus it is the optimal exercise strategy, which is fundamentally
determined by the conditional expectation of the payoff from continuing to keep
the option alive. The key characteristics is that the conditional expected function
can be estimated from the representational information in the simulation by
using least squares regression. The realized payoff from retaining the option are
regressed to estimate the parameters of the conditional expected functions. The
fitted value of this regression is an efficient unbiased estimate of the conditional
expected function. By estimating the conditional expectation function for each
exercise time period, we can obtain the optimal exercising rule along each path.
To apply the LSMC method to generation asset valuation problem, consider
the following (generic) multi-stage stochastic program. Assume that at unit state
xt at time t, the uncertainty Qt is revealed. After observing Qt the decision
maker (i) must realize the current asset value ft(xt;Qt); and (ii) can maximize
the expected value of the unit for the rest time periods by making decision vt.
Let Ft(xt;Vt;Qt) be the value-to-go function of the unit for the remaining period
at state xt at time t with operational option set Vt. Then this problem can be
formulated as the following recursive relations:
Ft(xt;vt;Qt) = ft(xt;Qt)+maxv
t2Vt
Et[Ft+1(xt+1;vt+1;Qt+1)] (2.6)
where Et denotes the expectation operator, and the subscript t indicates that
the expectation is based on the available information for uncertainty at time t,
20
and t 2 [0;T ?1], T represents the length of the unit?s lifetime. The last term
in (2.6) with the expectation operator defines another stochastic program to be
considered in the subsequent time period. Also the optimization problem in
(2.6) is subjected to a set of operational constraints. When boundary conditions
FT and initial conditions x0, v0 and Q0 are given, the optimal value of F?,
representing the maximal expected unit value with operational option set Vt
over the period [0;T], can be obtained from the last step of recursive relation as
F0(x0;v0;Q0).
Thedifficultyforsolving(2.6)comesfromthelasttermEt[Ft+1(xt+1;vt+1;Qt+1)],
which in general cannot be expressed in an analytical form. This term, however,
can be approximated using the LSMC method. Through simulating a set of
random variables, the expected value yields the least square error. Thus the
expected value of Ft+1(xt+1;vt+1;Qt+1) can be approximated by a conditional
expected function  t(xt;Qt) that regresses Ft+1 on the revealed uncertain data
Qt. The functional form  (?) can be obtained by the linear regression method
treating xt and Qt as the predictor variables and  t as the corresponding response
variable. The Monte Carlo method is used to generate the observations of  t and
the associated values of Qt. Once Qt is realized, for any state xt at time t, one
would know how to make optimal decisions for the next time period based on the
above regression function  t(xt;Qt). This is the basic idea of the LSMC method.
The above LSMC approach will be used to solve other complex asset valu-
ation problems similar to (2.6) in this dissertation. Like other regression-based
methods, the most difficult part of LSMC method is to find the suitable basis
functions of the relevant state variables, which may affect the regression quality
significantly.
21
Chapter 3
Literature Review
In this section, a complete review will be given the subjects related to the
valuation of a thermal power plant in the present electric industry, including
research on unit commitment, real options, and asset valuation etc.
3.1 Unit commitment problem
3.1.1 Deterministic unit commitment problem
In power industry electricity is a non-storable commodity and needs to be
produced and consumed at the same rate. It is very important to determine when
to switch generating units between on and off mode, in order to schedule a group
of generators over a set of time periods to satisfy a series of constraints at least
cost (Baldick 1995). The decision problem of optimally scheduling the operation
of generating units is known as the unit commitment (UC) problem (Wood and
Wollenberg 1996). In a typical UC problem, especially for thermal units, the
objective is usually to minimize the total generating cost of a power system
over the planning horizon and to come up with the detailed generating schedule
22
involving when to start up or shut down and generation levels in each time period
for each generator simultaneously (Bard 1988). The constraints usually include
demand constraints, spinning reserve constraints, capacity constraints, minimum
up/down time constraints and ramp constraints etc. These restrictions make the
unit commitment complicated and become a difficult mixed integer program (Lai
and Baldick 1999). The NP-hardness of the unit commitment problem has been
rigorously proved in literature (Tseng 1996).
UC is a short-term planning problem with a time horizon ranging from a
day to a week and considers unit operation on an hourly basis. As opposed
to the short-term UC problem, there are also mid-term and long-term planning
problems. The time horizon for a mid-term planning problem could be a month
or a quarter, which is suitable to manage hydro units. For a long-term problem,
the time horizon could be a year or a decade, especially useful for the electric
utilityplanningandthestudyofthecyclicalnaturesofelectricitymarkets(Marin
and Salmeron 1998; Louveaux 1988).
Generally speaking, the UC problem is usually very complex to solve because
it has both on/off combination and continuous production level optimization
components. Some coupling constraints, especially ramp constraints, make this
problem even more complicate.
3.1.2 Stochastic unit commitment problem
In a regulated environment, the UC problem is independent of the price
of electricity, which is predetermined by the customer demand and the total
generating capacity. In this sense, the decisions on how to operate the generating
units have no effect on the total revenue of the company. The maximum profit is
23
guaranteed by the minimization of the production costs (Sheble and Fahd 1994).
However, the price of electricity is not predetermined any more under dereg-
ulation (Galiana and Ilic 1998). When restructuring is completed, the utility
company will be under no obligation to serve any or all of the demand. For
example, the power generating utility has the option to turn off the units and
refuse to deliver the power when the electricity price in the spot market is so
low that its production cost cannot be recovered by its revenue.
Since the spot prices of electricity are highly volatile, the power industry will
no longer rely on traditional rules. The UC problem needs to incorporate a new
stochastic formulation considering load uncertainty and price uncertainties in
the spot market.
In literature, Allen and Ilic (1999) provided a new formulation of the unit
commitment problem in the deregulated environment. They discussed the sto-
chastic characteristics of the spot market prices derived from available data on
market-clearing prices, load, and covariates (temperature). Then Takriti et al.
(2000) developed a stochastic model for the UC problem in which the demand
and price uncertainties are introduced via a set of possible scenarios generated
by the MC method. Tseng (2001) mentioned that the prices of electricity and
fuel can be modelled by Ito processes. However, it is still a challenge to find an
efficient way to generate representative scenarios and to forecast price trend in
the future, because we may need many years of data, which may not be available.
Besides, the electricity price under deregulation could be highly volatile and the
history data may not affect the future price in some sense.
24
3.1.3 Methodologies
Researchers have developed different methods for solving the UC problem.
Among these methods, priority list-based methods (Lee 1988; Chandler et al.
1953) are typical heuristic methods, which can commit available units in a pre-
determined order, but may yield a far from optimal, or even infeasible solution.
Dynamic programming methods can solve the UC problem efficiently (Hobbs et
al. 1987), but still suffer fromthefamiliar curse ofdimensionalityespecially when
the size of state space is large. Similar to the dynamic programming methods,
branch-and-bound methods can schedule a small power system within reason-
able time, but fail to solve real-world power system scheduling problems due to
the large size of the search space (Cohen et al. 1983; Dillon 1978). Lagrangian
relaxation (LR) based technique (Ferreire et al. 1989; Guan et al. 1992) seems
to be the most efficient and popular, because it attempts to solve the problem
indirectly by solving the dual problem. Zhuang and Galiana (1988) proposed a
simulated annealing approach to obtain dual optimal solutions, but the corre-
sponding reserve-feasible commitments are not guaranteed to be dispatchable.
To ensure the feasibility of solution, a new unit decommitment method is in-
troduced to not only improve the solution quality, but also be able to relieve
unpredicted heuristic effects and make the LR approach more robust (Tseng
1996). As to other methods, genetic algorithms (Kazarlis et al. 1996; Cheng et
al. 2000) have also been tried, but the results are not encouraging. A hybrid
method of genetic algorithms and neural networks, reported by Huang et al.
(1997), seems to produce reasonable results. Further references regarding the
UC can be found in the book of Wood and Wollenberg (1996).
Compared with the deterministic UC problem, there were few attempts to
25
solve the stochastic unit commitment (SUC) problem in earlier periods, but sub-
ject to limitation in computer hardware. Recently, the SUC problem has been
solvable with advanced computers. Valenzuela et al. (2000) report on the statis-
tical analysis of hourly demand covering a region of the Eastern United States.
They have shown that when the effect of temperature is suitably subtracted from
the hourly load, such a process can represent the demand quite accurately. Both
Carpentier et al. (1996) and Takriti et al. (1996, 2000) use a set of scenarios
with associated probabilities to model the random electric load over the plan-
ning horizon. Thus the SUC problem is solved by minimizing the expected cost
of running the electric system while meeting the load of the different scenarios.
To decompose the stochastic model, Carpentier et al. (1996) relax the demand
constraints. As a result, each generating unit has its own separate stochastic dy-
namic programming. In Takriti et al. (1996, 2000), both electric and fuel price
uncertainty are incorporated in their model in addition to load uncertainty. The
cost function of each generator is allowed to change with fuel prices. That means
this model is a multi-stage, mixed-integer, stochastic program and each node in
the scenario tree carries information regarding the spot market prices of electric-
ity and fuel as well as the electric demand. Another approach also incorporates
uncertainties into the UC problem in a two-stage stochastic program (Caroe et
al. 1997). In the first stage, the on/off decisions are made, while the generating
level of each unit is determined by the second stage.
26
3.2 Real options
3.2.1 Overview
In literature, many applications of real options (or flexibility) have been
identified and valued by researchers. It is well recognized that flexibility has
value because of uncertainty, and the higher uncertainty in the payoffs of an
investment, the higher value of real options is (Dixit and Pindyck 1994).
The real options approach applies derivative pricing theory to the analysis of
options opportunities in real assets. For example, suppose an investment would
be profitable at the average price, but not at the lower price. The decision
maker can postpone her decision and collect more information about actual
price movement. She invests if the price has gone up, but not if it has gone
down. Thus it avoids the loss if she had invested in the very beginning and then
seen the price go down. This value of waiting option must be traded off against
the loss of profit flow during the waiting time period (e.g., Dixit and Pindyck
1994).
As an extension of financial theory, the real options theory may use the
methods in financial options, which cannot always be applicable because the
optionpricingmethodrequiresthattheunderlyingassetistradablewhilethereal
assets are not always tradable. However, according to Copeland and Antikarov
(2001), the options valuation and the portfolios of traded securities are still
usable, if we adopt same assumptions used by DCF approach which attempts to
determine what a project would be worth if it were to be traded.
Besides, most of investments in real life are not restricted to only one type
of real options. Typically, there exist complicated interdependencies between
27
options, such as compound options, which can not be valued individually or sep-
arately, because the exercise of an option may influence other existing options
or even incur a number of new options. It is difficult for researchers to find
analytical expressions for these complicated options, but approximate solutions
could be achieved through numerical techniques. To evaluates interrelated op-
tions, Herath and Park (2002) develop a binomial lattice framework to model
a multi-stage investment as a compound real options. Kulatilaka (1995) shows
that the value of a collection of interdependent options is less than the sum of
individual options. Similarly, Trigeorgis (1993) finds that the value of a set of
options generally deviates from the sum of the values of each individual option.
The incremental value of an additional option when other options are present is
generally less than the value of the options when it is valued individually.
3.2.2 Applications of real options in electric industry
Since Black and Scholes (1973) and Merton (1973) presented their work on
option pricing theory, many application areas, including valuing complex finan-
cial securities and valuing real options, have been found. Especially after the
electric industry is moving toward restructuring, in which electricity prices be-
come extremely volatile and significant financial risks are introduced, the real
options approach can be a useful tool to take into account the flexibility in
strategic decision-making and operation management in power industry.
In the context of electricity producing firms, real options theory can be used
as a method of identifying and quantifying the contingent decisions embedded
in owning generation assets (Hlouskova et al. 2002). Applications of the real
options approach fall into two broad categories:
28
? Operational options - those related to the UC problem such as fuel switch-
ing capabilities, overfire options, locational arbitrage on regional prices, ar-
bitrage between energy and ancillary services markets (Griffes et al. 1999).
For example, in the operation stage, the option value of a generating unit
can be modelled as a series of call options on the spread between electricity
prices and variable costs (Deng et al. 1999).
? Capital investment options - those related to the acquisition of new plants
or the extension of current plants. The investors will exercise such options
if the market value of the generation unit exceeds the construction cost or
if the extra revenue after the expansion exceeds the expansion cost.
Edleson et al. (1995) analyzed the actual investment decision of a utility
using real options, in order to find a suitable alternative from buying or selling
pollution allowances, installing scrubbers or switching to low-sulphur coal for a
particular coal-fired power plant to account for the pollution levels. Hsu (1998)
compared the spark spread call and put options with financial instruments in
order to mitigate exposure to both electricity and gas price risks. Thus the spark
spread options conveniently tie the power and gas price movements. Pereira et
al. (1999) developed some basic ideas, such as methodologies and computational
toolsonrealoptionstheorytohandleriskanduncertaintyininvestmentplanning
both in traditional power sector and in the competitive environment. Chaton
et al. (1999) discussed how uncertainty affects investment in power market,
if given the uncertainty of demand, the natural gas price and the possibility
of electricity sales between regions. Min (2000) illustrated various options of
capacity expansion and capacity reduction, and evaluated the values of options
for a utility that has two inter-related generation units. Frayer et al. (2001)
29
calculated the value of two plants, one of which is peaking gas-fired plant, the
other is mid-merit coal-fired plant, and shown that the gas-fired plant has a
higher value taking into account its operation flexibility using real options theory.
Similarly, Ajaxetal. (2000)appliedrealoptionstheorytoanalyzetheinvestment
decision on a hydropower and a thermal power plant. The exercise price is
the investment of each plant and the utility?s revenue is collected by selling
electricity both in forward contracts and in spot market. For each plant, the
investor calculates the option value and decides whether to keep the option alive
or delaying the investment, or to exercise it.
3.3 Asset valuation of power generation units
3.3.1 Overviews
The asset value of a power plant can be regarded as the total profit (revenue
less cost) of generating power over its life time. The revenue is dependent upon
the electricity prices, which are determined by the electric spot market. The
cost consists of mainly two parts: one is the production cost (90 ? 95%), the
other is maintenance cost (5 ? 10%). In order to maximize the total profit
of a unit, we need to find optimal commitment, production and maintenance
schedules under price uncertainties considering both production constraints and
maintenance constraints.
Before deregulation, the method of the net present value (NPV) is widely
used in valuing a power generating asset or investment. The economic viability
of such investment can be determined by means of a DCF method (e.g., Dixit and
30
Pindyck, 1994), but the result tends to underestimate the value of power plant
because of ignoring the value of real options associated with the investment.
With the development of financial and physical markets for electricity after
deregulation, the value of a power plant can be modelled as a set of financial
instruments on electricity (Deng et al. 1998; and Hsu 1998). The idea of their
approaches is as follows: a power plant can generate electricity by consuming a
particularfuelwithitsassociatedheatrate. When theelectricitypriceishighbut
the fuel price is low, the power plant should turn on to collect the profitable price
spread between the electricity price and the generation cost of the unit. If the
price spread is negative, then the unit should stay off. Therefore, the value of a
power plant can be regarded as a series of call options of spark spreads, defined as
theelectricityprice less theproduct ofthe heat rate associated with the generator
and the fuel price. Although the option-based valuation provides a much better
result than does the traditional DCF valuation, it overlooks the power plant?s
operational constraints, such as minimum up/down time constraints and ramp
constraints. This may lead to overvalue a power plant.
In Tseng and Barz (1999, 2001), a MC method is introduced to value the
power generating units with physical constraints including ramp constraints over
a short-term period. Although the computational speed of this approach is not
fast, its result of valuation is closer to the ?true? value than the financial op-
tions methods. Similarly in Gardner and Zhuang (2000), employs a real options-
based stochastic dynamic programming method to value power plants consid-
ering operational characteristics including minimum up/down time, ramp rate,
non-constant heat rate and response rate. Their numerical results also show
that operating constraints have a significant impact on power plant values and
31
optimal operating policies.
Understanding the value of the operating flexibility is important for mak-
ing investment decisions in power industry, especially when the environment is
highly volatile and new technology also emerges quickly. For example, when fac-
ing unexpected stochastic prices, a generator with operating options can protect
itself against some of the adverse price movements by switching to an alter-
nate model of operation (e.g., Kulatilaka 1993). Cohen and Ostrowski (1996)
discussed different operating modes including combined cycles, fuel switching,
overfire and duel boiler, but did not consider them from the perspective of op-
erational options, and did not consider their values. To my best knowledge,
there are relatively few papers in the domain of valuing the operating options of
power generating units especially incorporating the operational constraints. The
fuel-switching flexibility of a duel-fuel steam boiler has been valued in Kulatilaka
(1993), which may shed some light on future research about the valuation of the
operating options. As to the overfire options, no literature has been found.
Although there is a great deal of literature on maintenance issues, most of
them are regarding maintenance scheduling. A recent comprehensive review
for maintenance scheduling can be found in Shahidehpour and Marwali (2000).
They provide a general framework for achieving trade-off between minimizing
the maintenance cost and preserving the service reliability.
3.3.2 Valuation methods
Currentlymethodsforassetvaluationcanberoughlyclassifiedintotwotypes:
DCF methods and options-based methods. Because the traditional DCF method
ignores the value of operating flexibility and strategic option, the real options-
32
based methods have become increasingly popular (Trigeorgis and Mason 1987).
Numerous methodologies (see, for example, Dixit and Pindyck 1994; Trigeor-
gis 1995; and Feurstein 2000) in the domain of real options have been developed
to calculate the value of options. Although some valuation techniques in finance
can be used directly in some specific cases, most of real option pricing prob-
lems need to resort to approximation methods because the underlying stochastic
process becomes multivariate due to the interaction of several types of uncer-
tainties. Among these numerical methods, discrete tree/lattice models, finite
difference approaches, and the MC simulation are widely used.
Cox et al. (1979) introduced discrete tree/lattice models to represent stochas-
tic processes in option valuation. To generate a binomial price lattice, we need to
know initial price of the asset, which is assumed to be multiplied by either the up
factor u, or the down factor d, the choice should be made according to the cor-
responding possibilities p and 1?p. The option value at expiration is computed
by boundary conditions and all the other nodes in the option lattice are calcu-
lated sequentially by working backward through the periods (e.g., Luenberger
1998). The trinomial models can also be developed similarly for generation as-
set valuation problems (Tseng and Lin 2004). They develop a framework for
generating discrete-time two-factor price lattices for two general correlated Ito
processes: electricity and fuel prices. In Gardner and Zhuang (2000) and Hull
and White (1994), the price processes for electricity and fuel are also modelled
as a two-factor lattice, which allow fuel prices to be stochastic and make it pos-
sible to model the spark spread directly if the power plant heat rate is assumed
to be constant. Although the lattice models are easy to be implemented, they
still need to face the curse of dimensionality, especially when the option is path
33
dependent and the time horizon is long. If extended to three-factor problems,
the lattice model becomes almost infeasible due to the increased dimensionality.
Parallel to lattice/tree model, there exists an alternate approach, finite dif-
ference methods (FDM) (e.g., Schwartz 1977; Brennan and Schwartz 1978). The
basic idea of FDM is to approximate the solution of the Black-Scholes partial
differential equation to calculate the option prices using numerical techniques.
All state variables are discretized, the boundary conditions are determined by
the value of contingent claim at expiration, and the first and second derivatives
are replaced by a finite difference approximation. Then the option price is solved
backward by using a discretized partial differential equation that represents the
valuation equation. In the domain of valuing electric power generators, a gen-
eral framework for the valuation based on partial-integro-differential equations is
developed by Thompson et al. (2004). This method can handle both European-
like options and American-like options, and achieve high levels of computational
speed, but it cannot treat path-dependent options, and cannot be extended to
multi-factor problems either.
MC simulation is one of the most popular methods to value options. Based on
the idea that the probability distributions of underlying asset values are approx-
imated by simulating price trajectories, Boyle (1977) proposes MC simulation
procedures for European option valuation. Recently, several efforts have been
taken to extend MC simulation techniques to value real American-like options.
Tseng and Barz (1999, 2002) provide a valuation model for short-term gener-
ation asset based on MC simulation. Longstaff and Schwartz (2001) discussed
the solving process of American-like options, in which the criteria of the optimal
option exercise in backward induction was introduced and a detailed review on
34
valuing American-like options via MC simulation was also provided. The main
drawback of the MC technique is that the simulation process is time consuming,
but its major advantage is that MC methods can accommodate general price
processes and can be extended to multi-factor problems easily. For example, in
Chapter 5 a MC-based approach, integrated with stochastic dynamic program-
ming, is proposed to value a thermal generation unit with fuel-switching options
involving three uncertainties: electricity, gas and oil prices.
35
Chapter 4
Optimal Self-Scheduling Problem
4.1 Problem description
Unit commitment (UC) is an important optimization problem for power util-
ities to economically schedule generating resources to achieve cost minimization
in the regulated environment (e.g., Tseng 1996). Although the electricity indus-
try is moving toward deregulation, the importance of the UC does not diminish
along with the restructuring trend. On the other hand, new features and re-
quirements are now considered in UC models such as price uncertainty, which
significantly increase the complexity of the problem (e.g., Hobbs et al 2001).
Some centralized markets (such as the PJM) still perform UC-like optimization
to conduct electricity auctions.
Among the methods that have been proposed to solve the UC problems, the
Lagrangian relaxation (LR) methods are the most widely used ones. One nice
feature of the LR approach for solving the UC problem is its decomposition of
the centralized problem into decentralized unit subproblems, which are linked
by Lagrange multipliers. Under the assumption of competitive market, the mul-
36
tipliers can be viewed as the market prices and each unit subproblem represents
a profit-maximizing commitment decision-making for the unit in response to the
market prices. In this chapter, we focus on thermal units and discuss optimiza-
tion of a decentralized unit subproblem, called the self-scheduling problem (SSP),
which refers to optimal scheduling of a single unit in response to price changes in
the spot market, subject to operational constraints, where the demand constraint
is left out, because nobody needs to take the responsibility to satisfy the electric
demand in the competitive market. In an SSP, the operator of a power plant
intends to maximize total profit by optimally committing the unit to generate
power to sell in a spot market, since no participants have the capabilities to alter
spot prices. The unit commitment is subject to physical constraints including
the ramp constraints. These operational constraints can impact the capability
of how the unit can quickly respond to profitable opportunities. The solution
procedure developed in this chapter can be used to help independent power pro-
ducers achieve optimal commitment and dispatch decisions in the competitive
marketplace. It can also contribute to the traditional UC optimization.
Ramp constraints limit the capability of a unit to the change generation levels
over a short period of time. They can have significant impacts on the solution of
the SSP. When subject to the ramp constraints, the generation levels of a unit
become interdependent in all hours, which complicates the solution procedures.
Thus far, in the LR approach the ramp constraints have only been dealt with by
further relaxation (Svoboda et al 1997), discretization of the generation levels
(Bard 1988), or other methods (Guan et al 1992 and Lai and Baldick 1999). None
of these approaches can achieve optimality of the SSP, or achieve it efficiently.
More discussions of these approaches will be given in the next section.
37
Arroyo and Conejo (2000) proposed a rigorous approach using a mixed linear
integer programming (MILP) method to solve the SSP with ramp constraints.
Their approach is general and does not assume convexity of operating costs.
However all nonlinear cost structures need to be linearlized. Although the
method produces a satisfactory result for a 24-hour test case, it may not be ap-
plicable to larger cases, such as 7-day ones, in unit commitment. This is because
the MILP solvers (e.g., CPLEX used in their paper) are based on branch-and-
bound or branch-and-cut searches, whose computational complexity normally
increases exponentially with the problem size.
In this paper, we first tackle the SSP by assuming the spot prices are known
with certainty, same as in Arroyo and Conejo (2000). A network graph method
is proposed to solve the SSP with the ramp constraints. We will show that
under the convexity assumption, the ramp-constrained SSP is not NP-hard by
presenting an efficient polynomial-time algorithm. Our proposed algorithm can
guarantee the optimality of the solution without discretizing the generation lev-
els and linearizing the cost functions. Because of its efficient polynomial-time
complexity, the proposed method can be incorporated in large-scale UC related
problems.
Price uncertainty is then introduced to the SSP via price scenarios generated
by the Monte Carlo method. The optimal (deterministic) ramp-constrained SSP
is solved for each scenario. A linear regression- based method is developed to
devise the optimal unit response strategy under the ramp constraints and the
price uncertainty.
38
4.1.1 The mathematical formulation
This section presents a mathematical model for the optimal unit response
problem to spot prices. The following standard notation will be used. Additional
symbols will be introduced when necessary.
t : index for time (in hours), t = 0;???;T, where T is the number of hours of
the operating period.
? : unit startup time.
? : unit shutdown time.
ut : zero-one decision variable indicating whether unit is up or down in time
period t.
?u0 : initial condition of ut at t = 0.
xt : state variable indicating the status of the unit in time period t (length of
time unit has been up or down).
?x0 : initial condition of xt at t = 0.
ton : the minimum number of periods the unit must remain on after it has been
turned on.
toff : the minimum number of periods the unit must remain off after it has been
turned off.
tcold : the number of periods required to cool the unit from shutdown(tcold ? toff).
qt : variable indicating the amount of power the unit is generating in time period
t.
39
?q0 : initial condition of qt at t = 0.
qmin : minimum rated capacity of the unit.
qmax : maximum rated capacity of the unit.
? : ramp rate of the unit.
C(qt) : fuel cost for operating the unit at output level qt in time period t.
S(xt) : startup cost associated with turning on the unit at state xt in time period
t.
?t : spot price at time t for electricity.
?t : spot price at time t for spinning reserve.
The SSP is formulated as a mixed-integer programming problem. The ob-
jective is to maximize the total profit:
(P0) minu;x;q
TX
t=1
(?tqt ?C(qt))ut +?t(qmax ?qt)ut ?S(xt?1)ut(1?ut?1) (4.1)
where revenue is collected from selling electricity to the spot market and provid-
ing spinning reserve. Note that the symbols in bold face are vectors. We assume
that the spot prices and are deterministic and are known. This assumption will
be relaxed in Section x 4.3.
To describe the power plant operation, let ? be the set of states that is
composed of four subsets of states: ?1 for the startup period, ?2 for the normal
operation period, ?3 for the shutdown period, and ?4 for the normal off-line
period.
xt 2 ? = ?1 [?2 [?3 [?4 (4.2)
40
where ?1 ? f1;2;???;?g (4.3a)
?2 ? f? +1;? +2;???;? +tong (4.3b)
?3 ? f?1;?2;???;??g (4.3c)
?4 ? f?? ?1;?? ?2;???;?? ?tcoldg (4.3d)
The optimization is subject to the following constraints.
? State transition constraints:
xt+1 =
8
>>>>
>><
>>>
>>>:
min(? +ton;xt +1); if xt 2 ?1 [?2 and ut+1 = 1;
xt ?1; if xt 2 ?3 and ut+1 = 1;
max(?? ?tcold;xt ?1); if xt 2 ?4 and ut+1 = 0;
(4.4)
and
ut =
8>
>>>
>><
>>>>
>>:
1; if ?? ? xt < ? +ton;
0; if ?? ?toff < xt ??? ?1
0 or 1; otherwise;
(4.5)
? Ramp constraints:
If xt 2 ?1,
qt = qminxt=? (4.6)
If xt 2 ?2,
jqt+1 ?qtj? ? (4.7)
qmin ? qt ? qmax (4.8)
If xt 2 ?3,
qt = qmin(? +xt +1)=? (4.9)
If xt 2 ?4,
qt = 0 (4.10)
41
? Initial conditions:
u0 = ?u0; x0 = ?x0; q0 = ?q0: (4.11)
Remark
Note that the equation (4.6) implies that when the unit is turned on, it takes
? hours with a fixed increasing rate in generation qmin=? to reach the minimum
rated capacity of the unit. Therefore, at xt = ?, qt = qmin. Similarly, (4.9)
implies that at xt = ?1, qt = qmin. That means when an on-line unit is turned
off, its generation level has to be reduced to qmin first, then from qmin it takes
? hours with a fixed decreasing rate in generation qmin=? to reduce to zero. To
sum up, during the startup and shutdown periods, the unit continues to generate
power, but not as much as in the normal on-line period ?2. Therefore, ut = 1
when xt is in ?1, ?2 or ?3.
Problem (P0) is similar to a LR unit subproblem of the unit commitment,
in which ? and ? are Lagrange multipliers of the demand and spinning capac-
ity constraints, respectively. In the following section, we discuss some existing
methods for solving (P0).
4.1.2 Related methods
Wang and Shahidepour (1993, 1994) introduced an artificial neural network
(ANN) method incorporating dynamic programming (DP) to solve the ramp-
constrained unit commitment problems. Although the authors claimed that
they can obtain good results, the solution quality is significantly affected by the
training examples and categories. Also When the size of training set is increased,
42
additional memory and training time required correspondingly. Also, using peak-
load units to accommodate the unit ramping characteristics may introduce errors
and solution feasibility is not guaranteed, let along the solution optimality.
Lee et al. (1995) claimed that ramp-rate constraints can be reflected by
hourly marginal ramp-rate price of generators and these marginal prices can be
achieved by a simple iteration algorithm. It seems that their method can improve
the solution quality to some extent, but cannot avoid infeasible or bad results
either.
In Bard (1988), a LR unit subproblem similar to (P0) was tackled. The au-
thor discretized the generation level qt to accommodate the ramp constraints.
With the discretized generation levels and the discrete states xt, the subproblem
is then solved using dynamic programming. The more refined the discretization
of the generation level is, the more precise the solution is and the greater state
space for the dynamic programming is required. A tradeoff between optimal-
ity and computational feasibility must be made. Since the discretization of the
generation level cannot be made to infinitely refined, this approach obtains only
a sub-optimal (or near-optimal) solution. However, the duality theory of the
LR approach holds only when each subproblem is solved to the exact optimal-
ity. Therefore, the approach using discretization to solve the ramp-constrained
subproblem is somewhat questionable in theory, although it is recognized to be
practically feasible (Peterson et al 1995).
To avoid solving a ramp-constrained subproblem, Svoboda et al. (1997) fur-
ther relaxed ramp constraints in the LR scheme, which incurred additional 2TI
Lagrange multipliers to the original 2T ones, where I is the number of units.
For example, a common test case with 10 units over a 7-day period would re-
43
quire updating 3,696 multipliers simultaneously (as opposed to 336 multipliers
otherwise), which makes the dual optimization much harder to converge. Fur-
thermore, it can be shown that the duality gap increases when more constraints
are relaxed, indicating a potentially worse solution quality. Therefore, a method
that can directly solve a ramp-constrained LR unit subproblem to optimality is
very much in need.
Solving (P0) to optimality was first reported by Arroyo and Conejo (2000).
The authors made efforts to convert the minimum uptime/downtime constraints
to standard integer programming formulations and solved the problem to op-
timality using a commercial mixed-integer linear programming (MILP) solver
CPLEX. In order to use the MILP solver, the cost function C and the start
up cost S must be linearized. Their method does not assume the cost function
C to be convex. The authors reported a satisfactory test result for a 24-hour
instance. Although Arroyo and Conejo (2000) provide a means to solve the
ramp-constrained subproblem to optimality, their method may not be applica-
ble to larger-scale problems in UC. As we will show in the next section, under the
convexity assumption for the cost function C the ramp-constrained unit subprob-
lem is not NP-hard. We demonstrate a polynomial-time algorithm for solving
it. Given the fact that a polynomial- time algorithm exists, the branch-and-
bound (or branch-and-cut) based MILP algorithms become less appealing for
solving such a problem because its computational complexity normally increases
exponentially as the problem size (such as T) increases.
44
4.2 Algorithm development
In this chapter, we assume the cost function C to be a quadratic function:
H(qt) = c0 +c1qt +c2q2t; (4.12a)
C(qt) = H(qt)?PF; (4.12b)
where H(?) is the heat rate function, PF is the fuel price and is assumed fixed.
In the sequel, without loss of generality we will focus on solving the following
problem (P), equivalent to (P0).
(P) minu;x;q
TX
t=1
?t(qt)ut +S(xt?1)ut(1?ut?1) (4.13)
where ?t is a concave quadratic function and (P) is subject to (4.4) - (4.11)
including the ramp constraints. Note the spot price information is now implied
in the subscript t of ?t. Next we will propose a method for solving (P) that does
not require discretization of the generation level or linearization of the objective
function, and has a polynomial-time complexity.
4.2.1 A network graph approach
Consider a directed graph G(N;A), where A and N are the sets of nodes
and arcs, respectively. N is defined as [Tt=0Wt, where Wt is the set of states at
time t:
Wt ? ?1 [?3 [?4 = ?n?2 (4.14)
That is, each node inN corresponds to a state of generating status. Note that ?2
has been suppressed. In the remainder of this chapter, a node (of the network)
and a state yt (a counterpart of xt) are used interchangeably. Acontains directed
45
arcs only, each of which is incident from a state of some time period to another
state of a later time period. Detailed configuration is as follows.
? Arc from yt to yt+1
yt+1 =
8
>>>>
>><
>>>
>>>:
yt +1; if yt 2 [1;?);
max(?? ?tcold;yt ?1); if yt < 0;
1; if yt 2 [?? ?tcold;?? ?toff]:
(4.15)
? Arc from yt1 to yt2 for every t1;t2 2 [0;T] such that t2 ?t1 ? ton
yt1 = ?; yt2 = ?1 (4.16)
Since an arc satisfying (4.16) represents some normal operation period, it
is called an operating arc. Basically, the states in ?2 are replaced by all
possible operating arcs in the proposed approach.
1. Nodal properties
Each node in N is associated with a generation level Qt(a counterpart of
qt), which is a function of the corresponding state yt and is subject to the
following constraints.
Qt(yt) =
8>
>>>>
><
>>>>
>>:
ytqmin=?; if yt 2 ?1;
(? +yt +1)qmin=?; if yt 2 ?3;
0 if yt 2 ?4;
(4.17)
exceptthatQ0(?) = ?q0 andQT(?1)isafreevariablebetweenqmin andqmax.
Each node is associated with a profit(receipt) ?t(Qt), which is collected
when the node is visited.
2. Arc properties
46
? For each arc incident into yt+1 = 1 from yt, a transition cost S(yt) is
incurred, which represents a unit startup cost.
? For each operating arc, incident from yt1 to yt2 satisfying (4.16), a
profit f(t1;t2) is applied, where the profit f(t1;t2) is the optimal ob-
jective function value of the following parametric optimization prob-
lem, denoted by (Qt2t1):
(Qt2t1) f(t1;t2) ? maxq
t2?1X
t=t1+1
?t(qt) (4.18a)
s:t: qt1 = Qt1(?) (4.18b)
qt2 = Qt2(?1) (4.18c)
?? ? qt+1 ?qt ? ?; 8t 2 [t1;t2 ?1] (4.18d)
qmin ? qt ? qmax; 8t 2 [t1;t2] (4.18e)
If (Qt2t1) is not feasible, f(t1;t2) is assigned to be ?1.
3. Start node
A start node is the node in W0 that corresponds to the initial state ?x0. If
?x0 2 ?2, the start node is y0 = ?.
Clearly, each path in G from the start node to any node in WT corresponds
to a feasible ramp-constrained unit schedule, and vice versa. The corre-
sponding commitment and dispatch of a node on a path in G is defined by
(4.5) and (4.17). An operating arc between t1 and t2 implies that ut = 1
and qt are obtained from the optimal solution of f(t1;t2) for all t 2 [t1;t2].
Therefore, solving (P) is equivalent to finding a longest (or shortest) path
from the starting node to any node in WT.
Given a directed network, finding a longest (or shortest) path problem is an
47
x=-n - tcold
x=2
x=t
x=-1
x=-n
x=-n - toff
t=1 t=2 t=3 t=4 t=5
x=1
t=6
Figure 4.1: An example network graph with five time periods.
48
easy task, which can be done efficiently using the dynamic programming.
The most efficient algorithm for finding a shortest path is the Dijvstra
method with O(T2) arithmetic operations required (Murty 1992). Solving
(P), however, includes developing the network graph G and evaluating all
costs associated with arcs. The part that demands the most computational
effort is the evaluation of (Qt2t1) of all operating arcs. There are as many as
O(T2) of problem (Qt2t1) to be solved. Since ?t(?) is assumed to be a con-
vex quadratic function, each (Qt2t1) is a standard quadratic programming
problem with linear constraints, which can be solved in polynomial-time.
The best known result for solving a (Qt2t1) is O(jt2 ?t1j3K) (e.g., Kojima
et al. 1987; Monteiro and Adler 1989), where L is the problem size (Pa-
padimitriou and Steiglitz 1982). Therefore, the optimal solution of (P)
can be solved with no more than O(T5K) arithmetic operations using the
proposed network graph approach.
Theorem The proposed network graph approach solves (P) within a poly-
nomial time.
Remark
Problem (Qt2t1) can be solved using commercial nonlinear programming solvers
such as LSGRG2 and MINOS. The former solver is incorporated in our numerical
tests. Note the algorithm complexity discussed defines algorithm performance
in the worst case. Therefore, in practice, a better complexity may be sought by
a more efficient implementation. In view of this, note that all operating arcs
are not necessarily unrelated. For example, f(t1;t2) and f(t1;t2 + 1) share the
same multipliers (or spot prices) from t1 to t2. Therefore, the optimal solution
49
of f(t1;t2) can be used to create an initial feasible solution for f(t1;t2 +1), e.g.,
incorporating with qt2+1 = qmin. Since the number of (Qt2t1) to be evaluated is
large, such a ?warm start? strategy can make significant savings of CPU time
(see Section 4 for numerical tests). In the next section, I will show how to
take advantage the special structure of the problem and develop a more efficient
algorithm.
In the next section, I will focus on solving (Qt2t1) that is subject to (4.4) ?
(4.11) including the ramp constraints. I will propose a method for solving (Qt2t1)
that does not require discretization of the generation level, linearization of the
objective function, and is polynomial-time.
4.2.2 An active-set method for solving (Qt2t1)
In this section, I will use an example to illustrate the basic idea of a new
algorithm For solving (Qt2t1). Consider solving f(0;15) denoted by (Q150 ), which
is summarized below.
(Q150 )
maxq
1;???;q14
14X
t=1
?t(qt) (4.19a)
s:t: qt?1 ?qt ?? ? 0; t = 1;???;15 (4.19b)
qt ?qt?1 ?? ? 0; t = 1;???;15 (4.19c)
?qt +qmin ? 0; t = 1;???;14 (4.19d)
qt ?qmax ? 0; t = 1;???;14 (4.19e)
q15 = qmin (4.19f)
q0 = qmin (4.19g)
Let ?t, ?t, fit and flt be the Lagrange multipliers associated with (4.19b), (4.19c),
50
(4.19d) and (4.19e), respectively. The Lagrangian of the problem is defined as
follows:
L(qt;?t;?t;fit;flt) =
14X
t=1
?t(qt)+
15X
t=1
 
?t(qt?1 ?qt ??)+?t(qt ?qt?1 ??)
?
+
14X
t=1
 
fit(?qt +qmint )+flt(qt ?qmax)
?
(4.20)
The optimality condition ensures that
@L
@qt =
@L
@?t =
@L
@?t =
@L
@fit =
@L
@flt = 0; 8t (4.21)
and the complementary slackness condition for each constraint.
Starting with a feasible solution, the basic idea of the active-set method is
to determine the values of the Lagrange multipliers corresponding to the active
(or binding) constraints that satisfy the optimality conditions (4.21). If all the
multipliers for the active constraints (inequalities) are nonnegative, then the
feasible solution must be optimal. Note that (Qt2t1) is a convex problem and its
optimal solution is unique. If the multiplier of an active constraint is negative,
it implies that the objective function value could have been improved, had that
constraint not been active. Therefore, one can search along the direction that is
strictly feasible with respect to that constraint alone to locate a better feasible
solution.
For illustrative purpose, consider a feasible solution f?q0;???; ?q15g, which cor-
responds to the sixteen discrete generation levels shown in Fig. 4.2. If a ramp
constraint is binding between two consecutive hours, a solid line is depicted to
connect these two corresponding generation levels, otherwise a dash line is used.
In this example, the two dash segments separate the interval of concern into
51
0   1    2     3    4    5    6    7    8    9    10   11  12  13   14  15
qmin
Figure 4.2: A feasible solution to Q150 .
three subintervals, [0;4], [5;9], and [10;15]. Each of these three subintervals is
not coupled with any adjacent subinterval and can be treated independently.
These three subintervals also illustrate three categories of subintervals that can
cover all possible scenarios. They are discussed below.
? One-end fixed and nondegenerate (t 2 [0;4])
This subinterval has one end point (t = 0) whose generation must be set to
qmin. Because no other points except the end point has its qt equal to qmin or
qmax, this subinterval is called nondegenerate. The issue of degeneracy will
be discussed in more detail later. The corresponding optimality conditions
are as follows, with the multipliers corresponding to inactive constraints
ignored:
@L=@q1 = ?01(?q1)??1 +?2 = 0 (4.22a)
@L=@q2 = ?02(?q2)??2 ??3 = 0 (4.22b)
@L=@q3 = ?03(?q3)+?3 ??4 = 0 (4.22c)
@L=@q4 = ?04(?q4)??4 = 0 (4.22d)
One can solve ?4 from (4.22d), and then plug it to (4.22c) for ?3, (4.22b)
for ?2, and (4.22a) for ?1. If a multiplier is negative, say ?3 < 0, it means
52
that it is an improving direction by further dividing this subinterval to two
subintervals, [0;2] and [3;4], i.e., replacing the corresponding solid line to
a dash line between t = 2 and 3. The subinterval [3;4] then becomes one
with ?both-end free,? to be discussed next.
? Both-end free and nondegenerate (t 2 [5;9])
In this subinterval, both end points are not tied to qmin and none of the
points is either qmin or qmax. We will also call such an subinterval as a free
subinterval. The optimality conditions are as follows.
@L=@q5 = ?05(?q5)+?6 = 0 (4.23a)
@L=@q6 = ?06(?q6)??6 ??7 = 0 (4.23b)
@L=@q7 = ?07(?q7)+?7 +?8 = 0 (4.23c)
@L=@q8 = ?08(?q8)??8 ??9 = 0 (4.23d)
@L=@q9 = ?09(?q9)+?9 = 0 (4.23e)
In this case, one may solve ?6 first from (4.23a), then solve other multipliers
from top-down; or solve ?9 first from (4.23e) and then move from bottom-
up. However, both results may not necessarily coincide. To avoid this,
for a free subinterval, one should always determine its optimal position
by performing parallel shift. For example, in this case one can solve the
following one-dimensional optimization problem.
min
?q
P9
t=5 ?t(?qt +?q) (4.24a)
s:t: j?q5 +?q ? ?q4j? ? (4.24b)
j?q9 +?q ? ?q10j? ? (4.24c)
qmin ? ?qt +?q ? qmax; 5 ? t ? 9: (4.24d)
53
After a free subinterval is positioned optimally, it may no longer be free
if it becomes binding with its adjacent subinterval(s). If this subinterval
remains to be free, solving the multipliers in (4.23a) to (4.23e) either from
top-down or bottom-up would yield the same result.
? A degenerate subinterval (t 2 [10;15])
First, let?s examine the optimality conditions for this subinterval.
@L=@q10 = ?010(?q10)??11 = 0 (4.25a)
@L=@q11 = ?011(?q11)+?11 +?12 ?fi11 = 0 (4.25b)
@L=@q12 = ?012(?q12)??12 ??13 = 0 (4.25c)
@L=@q13 = ?013(?q13)+?13 +?14 ?fi13 = 0 (4.25d)
@L=@q14 = ?014(?q14)??14 ??15 = 0 (4.25e)
@L=@q15 = ?015(?q15)+?15 = 0 (4.25f)
In this subinterval, because ?q11 = ?q13 = qmin, two additional multipliers
fi11 and fi13 appear in the optimality conditions. This creates linear de-
pendence among the linear constraints. Therefore, the system of equations
may have infinitely many solutions. Such a situation is normally termed
as degeneracy. To deal with the degeneracy, it is necessary to drop some
dependent variables, i.e., to make some active constrains inactive while re-
taining enough active constraints to identify the existing feasible solution.
In this example, two variables may be dropped corresponding to the two
additional active constraints. They are one from f?11;?12;fi11g and one
from f?13;?14;fi13g. For example, if ?12 would be dropped, it is equiva-
lent to further dividing the subinterval into two subintervals, [10;11] and
54
[12;15], where the former becomes a free section. It is likely that after
dropping a variable, no improvement in the objective function value can
be made without violating one of the dependent constraints that have been
excluded. In that case, such a constraint must be added back to the active
constraints. One can then try to drop another dependent variable. Finally,
note that the linear dependence among the linear constraints here is not a
unique product of the proposed method. It is, however, ?commonplace in
practical problems, but it is not a serious impediment to practical compu-
tation? (P. 201, Gill et al. 1989). The interested reader is directed to Gill
et al. (1989) for more detailed discussions on how to deal with degeneracy.
4.2.3 A numerical test on ramp-constrained SSP
Numerical tests are conducted to measure the performance of the proposed
approach. The network graph method for solving (P) is implemented in FOR-
TRAN on a Pentium IV PC. Two methods for solving (Qt2t1) are implemented:
LSGRG2 and the proposed active-set-based method. For LSGRG2, the FOR-
TRAN source code of the commercial software is integrated with our programs.
A natural gas-fueled generating unit with the input-output characteristics fol-
lowing (4.12a) and (4.12b) is considered. Assume PF is $ 2.2/MMBtu, and
qmin=250 MW, qmax=750 MW, c0=600, c1=9.121, and c2=0.00131. We also as-
sume that ? = ? = 2, ton = toff = 5, and tcold = 10 to fully capture the influence
of the physical constraints. Assume the startup cost
Su(xt) = 2300(1?exp(xt=4))+950 (4.26)
and a constant shutdown cost $1000. Hourly electricity prices ?t are generated
55
by a uniform random variable between $16/MWh and $25/MWh. Note that
in reality electricity hourly prices may follow some pattern, such as on-peak vs.
off-peak. Without considering any price pattern, our test cases here are actually
harder in the sense that degeneracy is more likely to occur. Without loss of
generality, the spinning reserve market is not considered by setting ?t =0. To
fully observe the algorithm performance in terms of the complexity analysis,
seven cases are tested corresponding to seven operating periods, ranging from 1
day (24 hours) to 7 days (168 hours). For each case, we randomly generate 100
instances of the electricity hourly prices. The LSGRG2 method and proposed
active-set method are used to solve (Qt2t1) for each instance of (P). The average
CPU times are recorded in Table 4.1.
Table 4.1: Average CPU time (seconds)
(T) 24 48 72 96 120 144 168
LSGRG2 0.16 2.42 15.79 57.90 180.77 463.63 972.23
Active-Set 0.03 0.46 1.49 2.92 4.96 7.54 12.19
Note that in the implementations of both methods for solving (Qt2t1), the
warm-start feature, discussed in Section x 4.2.1, has been included, which re-
duced the CPU times as much as 60% on average. Based on the performance
data in Table 1, both approaches reveal a polynomial-time complexity with ap-
proximately O(T5:0) for LSGRG2 and O(T2:5) for the proposed active-set-based
method. The complexity of the proposed active-set-based method is much better
than the theoretic result O(T5K), as shown in Sectionx 4.2.1.
To sum up, the numerical testing result verifies the polynomial-time perfor-
56
0
50
100
150
200
24 48 72 96 120 144 168
GRG
Proposed Method
Planning Horizon T (hours)
CPU Time
 (seconds)
Figure 4.3: Comparison of average CPU times for solving (P).
mance for the proposed methods for solving the optimal unit response problem.
The proposed method also guarantees the optimality of the solution. Because
of the polynomial-time complexity, the proposed method can be incorporated in
large-scale unit commitment related problems.
4.3 Stochastic ramp-constrained SSP
In this section, we consider the SSP under price uncertainty in the spot
markets. Let Pt = (?t;?t) be the market price information at time t. At
time t, the operator observes the price Pt and he needs to make a commitment
decision subject to the physical constraints. We assume a one-hour lead time
for commitment decisions. Therefore, the operator determines ut+1 at time t.
If the unit is on-line at time t (i.e., ut = 1), the operator needs to dispatch the
57
generator. It is assumed that the dispatch decision can be made instantaneously
after the price Pt is observed. The stochastic SSUCP can be formulated as the
following multi-stage recursive equation, denoted by (SP):
(SP) Ft(utjPt) = maxq
t;ut+1
(?t(qt)ut +S(xt?1)ut(1?ut?1)+
Et+1[Ft+1(ut+1jPt+1)]) (4.27)
where Ft(utjPt) represents expected total profit of the unit for the remain-
der of the operating period starting at commitment ut at time t, and Et is the
expectation operator given the available price information at time t. The maxi-
mization in (SP) is subject to constraints (4.4) - (4.11). Without considering the
ramp constraints, (SP) can be solved using the Monte Carlo simulation (Tseng
and Barz 2002) or a lattice approach (Tseng 2001). With the presence of the
ramp constraints, solving (SP) to optimality becomes very difficult because each
stage is interdependent and the dispatch variable qt is a continuous variable. We
consider a two-stage approximate formulation for (SP), in which the first stage
is t = 1 and the second stage covers from t = 2 to T. First, consider the dispatch
decision problem at time t = 1 (given that has been made available at t = 0).
Ft(utjPt) ? maxq
1
 (q1jP1) (4.28)
where
 (q1jP1) ? (?1(q1)u1 +S(?x0)u1(1? ?u0)+
E1[maxu;x;q
TX
t=2
?t(qt)ut +S(xt?1)ut(1?ut?1)jP1]) (4.29)
Apparently, q1 = 0 if u1 = 0 and the dispatch decision in (4.28) is made only
when u1 = 1. The first stage decision q1 (as well as u1) will become the initial
58
condition of the second stage problem. We are interested in the optimal dispatch
rule at t = 1 under ramp constraints and price uncertainty if u1 = 1. That is,
q?1(P1) = argmaxq
1
 (q1jP1) (4.30)
Since we assume that the dispatch can be performed immediately, q?1(P1) rep-
resents the optimal dispatch decision after the operator observes the spot price
P1 at t = 1. This optimal dispatch rule has accounted the ripple effect of the
ramp constraints to the future hours imposed by q?1(P1).
It can be shown easily that the optimal dispatch rule without considering the
ramp constraints (or ?q = 1) is a piecewise-linear function of P1 = (?1;?1):
q?1;?q=1(P1) = max
 
qmin;min
 
qmax; 12c
2
(?1 ??1PF ?c1)
??
(4.31)
where the cost function of the unit is assumed to follow (4.12a) and (4.12b). If
q?1(P1) is available, then the optimal commitment decision u1 (made at t = 0)
can be determined by
u?1 = arg max
u12f0;1g
E0[F1(u1jP1)] (4.32)
The two-stage formulation in (4.29) can then be performed sequentially in time
over a rolling horizon to make optimal commitment and dispatch decisions.
To evaluate  (q1jP1) and q?1(P1), we employ the least squares Monte Carlo
(LSMC) method, originally introduced by Longstaff and Schwartz (2001) for
financial options valuation.
4.3.1 Solving ramp-constrained SSP using LSMC
To determine  (q1jP1), recognize that  (?) can be viewed as some conditional
probability of q1 and P1. Therefore, the functional form  (?) can be obtained by
59
the linear regression method treating q1 and P1 as the predictor variables and
 as the corresponding response variable. The Monte Carlo method is used to
generate the observations of  and the associated values of q1 and P1 . This is
the basic idea of the LSMC method.
Based on the initial condition (q0;P0) at time 0, randomly generate N sam-
ples of (q(j)1 ;P(j)1 ), j = 1;???;N where q(j)1 2 [q0 ? ?q;q0 + ?q] \ [qmin;qmax].
For each P(j)1 , generate a price scenario (vector) for the rest of the operating
period (P(j)2 ;???;P(j)T ), based on which evaluate the corresponding observation
of  , denoted by  (j) =  (q(j)1 jP(j)1 ). Note that to evaluate  (j), a deterministic
SSUCP (over [2;T]) must be solved, which is handled by the proposed network
graph method in Section x4.2.
Finally,  (q1jP1)canbeapproximatedbyregressingf (j)gNj=1 onf(q(j)1 ;P(j)1 )gNj=1.
What remains to show is an appropriate functional form for the regression. Note
the analytic form for  (q1jP1) may not exist. Our experience shows that the fol-
lowing polynomial form works well for the regression.
 (q1jP1) ? a1 +a2q1 +a3q21 +a4?qq1 +a5?1 +a6?1 (4.33)
where ?q = max(q0??q;min(q0 +?q;((?1??1)=PF ?c1)=2c2)) is similar to the
optimal dispatch rule without the ramp constraints in (4.31) , and a1 ? a6 are
the parameters to be fitted in the regression. Here we assume that the heat rate
function of the unit follows the quadratic function given in (4.12a) and c1 and
c2 are the coefficients.
Note that  (q1jP1) is a highly nonlinear function in q1 and P1 and  (q1jP1)
may not be smooth everywhere because it involves ?q. However,  (q1jP1) is a
linear function of the regression parameters a1;???;a6. It is well known that
linear regressions can be done efficiently, which only involves solving a system of
60
21.5                   22                     22.5                     23                   23.5
($/MWh)
q0=400
q=40
q=90 q=
q=20
300
350
400
450
500 q
1(MW)
*
Figure 4.4: Optimal dispatch rule q?1(?) for different ramp rates.
linear equations (a 6?6 linear system in this case.)
Once  (q1jP1) is obtained, the ramp constrained optimal dispatch rule q?1(P1)
in (4.30) can be determined using standard nonlinear programming methods.
4.3.2 Numerical tests
The same natural gas-fired generating unit used in Section x4.2.3 is con-
sidered, and the initial conditions are ?0 = $20=MWh, q0 = 400MW. For
simplicity, the spinning reserve market is not considered by setting ?t = 0 at all
times. Assume a 7-day (168-hour) operating period and the hourly electricity
spot prices ?t are generated based on the mean reverting process reported in
(Tseng and Barz 2002).
61
The expected profit function  (q1j?1) varies with ramp rates ?q, and so does
the optimal dispatch rule q?1(?1). In Fig. 4.4, the optimal dispatch rule q?1(?1)
under the ramp constraints and price uncertainty is displayed for four different
cases: ?q = 1(no ramp), ?q = 90, ?q = 40 and ?q = 20. As shown in
(4.31), q?1(?1) is linear when there is no ramp constraint. From Fig. 4.4, when
the ramp constraints exist, is a s-curve bounded by ?q0 ? ?q. When the ramp
rate ?q decreases, the slope of the s-curve decreases. Again assume the fuel
cost function can be represented by a quadratic function in (4:4) and (4:11). A
less-steep s-curve can be viewed as an equivalent unit with (i) greater c1 and
c2; (ii) reduced available capacity; and (iii) no ramp constraints. A greater c2
indicates a more curved (upward sloping) cost function representing a worse fuel
economy; while a greater indicates a higher (incremental) heat rate representing
aless efficientheat-electricitytransformation. Adjusting the cost function todeal
with ramp rates is commonly practiced in industry. Our test result validates this
practice, but also indicates that it is only an approximation because the s-curve
is nonlinear.
Finally, Fig. 4.5 illustrates the LSMC approach for determining  (q1j?1).
Around 1000 (= N) samples are taken to estimate the conditional expectation
function  .
4.4 Summery and conclusions
In this chapter, the optimal unit response of a thermal unit to an electric-
ity spot market is studied. When the spot prices are known with certainty, a
polynomial-time algorithm based on network graph is proposed for solving the
62
1061.4
1.35
1.3
1.25
1.2
1.15
1.1
1.05
1.0
500
400
300
q
1 (MW)
21            21.5        22          22.5         23          23.5        24
($/MWh)
Figure 4.5: An example of  (q1j?1) with ?q=100MW.
63
problem. Using the developed algorithm to evaluate the unit responses in vari-
ous price scenarios generated by the Monte Carlo method, we obtain the optimal
commitment and dispatch rule under price uncertainty. Our test results indicate
that the ramp constraints impact a thermal unit on its capability of responding
to price uncertainty by reducing its fuel economy, heat-electricity transformation
efficiency, and available generation capacity. Our proposed method provides a
way to quantify these effects.
64
Chapter 5
Valuing Power Generation Units with
Fuel Switching Options
The deregulation of the US electric power market in the last few years has
replaced the vertical utility by a series of independently operating units with a
more horizontal relationship. After the restructuring, the electric utility industry
throughout the US has been facing pressure to increase its efficiency, to reduce
operational costs, and to lower purchase cost of power equipment. In order to
adapt well in the new business environment, generation asset investors must
consider market uncertainty in appraising the asset value.
In addition to market uncertainty, the investors must also consider an as-
set?s operating flexibility that enables the unit to respond to changing exogenous
economic conditions. The importance of such operating options becomes crit-
ical when the market environment is highly volatile. For example, when fac-
ing exogenous stochastic prices a generator with operating options, such as fuel
switching can protect itself against adverse price movements, with the capabil-
ity of switching into an alternative fuel that may be less affected by the adverse
price realizations (e.g. Kulatilaka 1993).
65
In the present competitive environment, a generator will be invested only
when an adequate return on the investment is expected. Since electricity is non-
storable in nature, the generation asset value may be replicated on future spark
spread options (Deng et al. 1999). In addition to pure spark spread options,
physical constraints such as minimum uptime and downtime constraints may
also affect the value. Tseng and Barz (1999, 2002) proposed a Monte Carlo
(MC) simulation to formulate the power plant valuation problem as a multi
stage stochastic problem. In addition, discrete-time price trees for correlated
price processes for both electricity and fuel, such as geometric mean reverting
processes are employed to value power asset. The computational efficiency of the
valuation problem may be improved by using stochastic dynamic programming
via a price tree (Tseng 2000). Although the method produces a satisfactory
result for a two-factor case (referring to two uncertainties such as electricity price
and gas price), it may not be applicable to a three-factor case if an additional
uncertainty must be considered (e.g., for a unit capable of switching fuels). The
tree approach is especially prohibitive when the time horizon is long because
of the ?curse of dimensionality?. Therefore, valuing a generation asset with fuel
switching option (considering three price uncertainties) is a challenging task.
In this chapter, we explore the LSMC approach and use it to value the fuel
switching option.
This chapter is organized as follows. In Section 5.1, we provide an overview of
the fuel switching unit including physical constraints and fuel switching options.
We then formulate and solve the generation asset valuation problem in Section
5.2. Numerical results are presented in Section 5.3. This chapter concludes in
Section 5.4.
66
5.1 Problem statement
5.1.1 Overview of fuel-switching units
A thermal generation unit with fuel-switching options can consume two dif-
ferent fuels, which can be switched within a short time period, and then converts
the fuels into electricity. This conversion involves three commodities with dif-
ferent market prices. The following conditions are implicitly assumed: (1) fuel
switching does not affect normal operation of a unit; (2) fuel switching can be
finished within a reasonable time. In general, the fuel-switching options can
provide the following two advantages:
? Fuel-switching capabilities may help stabilizing the operation of a unit
under limited resources available to a country or region;
? Fuel-switching options may help solving some pollution issues, such as
reducing emissions of waste.
In power industry, players may prefer nature gas to fuel oil because nature
gas is much ?cleaner? than fuel oil under environment restriction on emission of
waste. Therefore, fuel switching has been considered as an emission abatement
means. On the other hand, nature gas prices are much more expensive than fuel
oil prices based on per British thermal unit. Power producers may have to react
to the soaring price of natural gas by switching to cheaper, more environmentally
harmful fuel sources. To reduce power producers? exposure to price volatility or
possible supply disruptions in the present deregulation environment, industrial
users are expected to increasingly seek the flexibility of switching fuels using
hybrid technologies.
67
5.1.2 Notations
The following standard notation will be used to formulate the valuation of a
fuel-switching unit mathematically. Additional symbols will be introduced when
necessary.
t : index for time horizon in hours (t = 0;???;T; where T is the length of time
horizon).
j : index for fuel (j = 1;2, where ?1? represents gas and ?2? represents oil).
xt : state variable indicating the commitment status of the unit in time period
t.
ut : zero-one generation unit commitment decision variable in time period t.
vt : zero-one variable indicating which fuel the unit choose in time period t
(where ?1? represents gas and ?0? represents oil).
tonj : the minimum number of periods the unit must remain on after it has been
turned on for fuel j.
toffj : the minimum number of periods the unit must remain off after it has been
turned off for fuel j.
tcoldj : the minimum number of periods required to cool down the boiler of a unit
after it has been turned off for fuel j.
qt : decision variable indicating the amount of power the unit is generating in
time period t.
qminj : minimum rated capacity of the unit for fuel j.
68
qmaxj : maximum rated capacity of the unit for fuel j.
PEt : electricity price ($/MWh) in time period t.
PF1t : fuel 1 price ($/MMBtu) in time period t.
PF2t : fuel 2 price ($/MMBtu) in time period t.
?t(xt;vt;qt;PEt ;PF1t ;PF2t ) : profit for operating the unit at state xt at output
level qt when the electricity and fuel prices are PEt , PF1t and PF2t in time
period t respectively.
Jt : the asset value of unit in time period t.
h1;1t : the regression function when the unit is on in both time periods t and t+1.
h1;0t : the regression function when the unit is on in time period t and off in time
period t+1.
h0;1t : the regression function when the unit is off in time period t and is on in
time period t+1.
h0;0t : the regression function when the unit is off in both time periods t and t+1.
h0;0;nt : the regression function when the unit is cold in both time periods t and
t+1 without switching fuel.
h0;0;st : the regression function when the unit is cold in both time periods t and
t+1 with fuel switched.
St(ut;ut?1;vt) : startup/shutdown cost when the unit is turned on/off in time
period t.
69
5.1.3 Fuel-switching options
Generally speaking, fuel switching options of a generating unit refers to the
ability to burn alternate fuels, such as nature gas or fuel oil. Switching occurs
when one fuel out-of-the-money is replaced by another in-the-money (or less
out-of-the-money).
Since a fuel-switching unit can operate using different fuels, the cost charac-
teristics of the unit depend on the fuel used. Different fuel may have a different
amount of MMBtu required to produce a MW (Cohen et al. 1996; Zhai et
al. 2001). This property differs from unit to unit and fuel to fuel. The value
of a fuel-switching unit is affected by the operational constraints such as the
minimum up/down time constraints.
In reality, fuel switching is an transitional process, which may take from
minutes to hours dependent upon different units. In this chapter, we assumed
that the fuel switching could be done instantaneously under other conditions to
be addressed next.
There are normally two ways to switch fuels: on-line switching and off-line
switching. The switch takes place when the unit has already been on-line for
at least its minimum uptime periods (i.e., state ton1 . During the switching, it
transits to the shutdown status using another fuel. For the off-line switching,
the unit must be off-line while the fuel switching takes place. Therefore, the
state transits (from tcold1 to tcold2 or from tcold2 to tcold1 ). Fig. 5.1 illustrates the
state transitions of both the on-line and off-line switching. In this dissertation,
we focus on the off-line switching model.
70
x=ton
x=2
On-line Off-line
1
x=1
x=-1
x=-2
x=-toff
x=-tcold
1
1
x=-tcold
x=-toff
x=-2
x=-1
x=1
x=2
x=ton
2
2
2
Figure 5.1: A state transition diagram between two fuels (on-line and off-line).
71
5.1.4 Profit function of a fuel-switching unit
As in the previous chapters, the input-output characteristic of a generating
unit is captured by H(q) (MMBtu), which is a function described required to
generate q (MW) of power. Now this function is dependent on the fuel type
used, denoted by Hj(q) for fuel j. The profit at time t may be represented as
follows:
?t(xt;vt;qt;PEt ;PF1t ;PF2t )
=
8
>><
>>:
PEt qt ?H1(qt)PF1t vt ?H2(qt)PF2t (1?vt); if xt > 0;
0; otherwise:
(5.1)
where qt is the generation level at time t and we assume that qt is dispatched
instantaneously and optimally after the prices (PEt ;PF1t ;PF2t ) are revealed.
5.1.5 Operational constraints of a fuel-switching unit
The operational constraints are formulated as follows.
? Minimum up/downtime constraints:
ut =
8
>>>>
>><
>>>
>>>:
1; if 1 ? xt < ton1 vt +ton2 (1?vt);
0; if ?toff1 vt ?toff2 (1?vt) < xt ??1
0 or 1; otherwise:
(5.2)
? Switch constraints:
vt =
8>
><
>>:
1?vt?1 or vt?1; if xt = tcold1 or tcold2
vt?1; otherwise:
(5.3)
switch happens only when the unit is cold at time t.
72
? State transition constraints:
xt =
8>
><
>>:
min(ton;max(xt?1;0)+1); if ut = 1;
max(?tcold;min(xt?1;0)?1); if ut = 0
(5.4)
where
ton = ton1 vt +ton2 (1?vt) (5.4a)
toff = toff1 vt +toff2 (1?vt) (5.4b)
tcold = tcold1 vt +tcold2 (1?vt) (5.4c)
? Unit capacity constraints:
ut(qmin1 vt +qmin2 (1?vt)) ? qt ? ut(qmax1 vt +qmax2 (1?vt)) (5.5)
? Startup/shutdown cost:
St(ut;ut?1;vt) =
8
>>>>
>><
>>>
>>>:
Su1vt +Su2(1?vt); if ut = 1 and ut?1 = 0;
Sd1vt +Sd2(1?vt); if ut = 0 and ut?1 = 1;
0; otherwise:
(5.6)
where Su1 and Su2 represent constant startup cost for fuel 1 and fuel 2; Sd1
and Sd2 are constant shutdown cost for fuel 1 and fuel 2.
The operational constraints including the switch constraints have been fully
captured in the state transition diagram in Fig. 5.1.
5.2 Problemformulationandsolutionprocedure
The method to be introduced in this section can be viewed as an extension
of the method proposed in Longstaff and Schwartz (2001) for valuing American-
style options. We extend their approach to a more complicated situation involv-
ing multi-stage decision making and fuel switching options.
73
Let Jt(xt;ut;vt;qt;PEt ;PF1t ;PF2t ) be the so-called value-to-go function indi-
cating the total value of the unit for the remaining period at state xt at time
t, and assume a finite time horizon [0;T]. The asset valuing problem can be
formulated as the following recursive relation:
Jt(xt;ut;vt;qt;PEt ;PF1t ;PF2t ) = ?t(xt;vt;qt;PEt ;PF1t ;PF2t )+
maxu
t;vt
fEt[Jt+1(xt+1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)]?St(ut;ut?1;vt)g (5.7)
where Et denotes the expectation operator given the price information available
at time t.
5.2.1 Solution procedure
From (5.7), it can be seen at time t to make an optimal commitment decision,
one must know Et[Jt+1(xt+1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)], which implicitly is
a function of current price information, PEt , PF1t , and PF2t . The main idea of
the LSMC method is to approximate such a function by regression. In terms of
the states and the switching option, different functions are to be approximated
using regression. They are defined below.
If xt = xt+1 = ton,
h1;1t (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(ton;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)] (5.8a)
If xt = ton and xt+1 = ?1,
h1;0t (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(?1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)] (5.8b)
If ?tcold ? xt ??toff and xt=1 = 1,
h0;1t (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)] (5.8c)
74
If ?tcold < xt ??toff and xt+1 < 0,
h0;0t (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(xt ?1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)]
(5.8d)
If xt = xt+1 = ?tcold,
h0;0;nt (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(?tcold;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)]
(5.8e)
If xt = ?tcold and xt+1 = ?(tcold1 (1?vt)+tcold2 vt),
h0;0;st (vt;qt;PEt ;PF1t ;PF2t ) = Et[Jt+1(xt+1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1)]
(5.8f)
If the above regression functions ht(vt;qt;PEt ;PF1t ;PF2t ) are available at time
t, one could know the expected unit value for the next time period when the
uncertainty prices (PEt ;PF1t ;PF2t ) are revealed. Then, one could also know how
to make optimal decisions at t. Especially when the unit stay at the cold state
and h0;0;nt < h0;0;st , fuel switching may happen at this time period. Since analyti-
cal forms of ht(?) are nonexistent in general, we can only use numerical methods
based on Monte Carlo simulation to approximate ht(?). Through simulating a
set of random variables, the expected value yields the least square error. There-
fore, to approximate the above expected function, we generate N data samples
of prices based on the mean reverting uncertainty model (5.10). Thus, the ex-
pected value of Jt+1(xt+1;ut+1;vt+1;qt+1;PEt+1;PF1t+1;PF2t+1) can be approximated
by the function that best regressions Jt+1 on the data of price (PEt ;PF1t ;PF2t ) and
possible decision values of (ut;vt;qt). That means any realization of (ut;vt;qt)
at time t, one would know how to optimally make decisions for the next time
period based on the above regression functions ht(vt;qt;PEt ;PF1t ;PF2t ).
75
The expected value of Jt+1(?) can be approximated though forward-moving
simulation and backward-moving dynamic programming iterations from T ?1 to
T?2;???;0. Thus, theassetvaluecanbeobtainedbyJ0(x0;u0;v0;q0;PE0 ;PF10 ;PF20 ),
where (x0;u0;v0;q0;PE0 ;PF10 ;PF20 ) are determined by the initial conditions of the
unit. As to JT, it is determined by the boundary conditions as follows.
5.2.2 Boundary conditions
At time T, there is no commitment decision to make, because the power
plant value is only conditioned on the state xT as follows:
JT(xT;ut;vT;q?T;PET ;PF1T ;PF2T )
=
8>
><
>>:
PET q?T ?H1(q?T)PF1T vT ?H2(q?T)PF2T (1?vT); if xT > 0;
0; otherwise:
(5.9)
where q?T represents the optimal generation level in time T within the capacity
range [qminj ;qmaxj ] for fuel j, which is determined by vT.
At time T ?1, for the remaining two time periods, one can use the LSMC to
estimate JT?1(xT;uT?1;vT?1;qT?1;PET?1;PF1T?1;PF2T?1) for every data sample. The
decision maker can choose whether to switch fuel immediately or not and revisit
the exercise decision at the next time period when the unit is at cold state. The
value of JT?1(?) is maximized path-wise, and hence the value of fuel switching
option is greater than or equal to 0 unconditionally. This procedure can be
repeated to T-2,???;0. The last iteration, starting with the initial conditions at
time 0, provides the optimal planning and asset estimation for the whole time
horizon.
76
5.2.3 Price processes
In this paper, we assume that price of electricity PEt , price of fuel-1 PF1t ,
and price of fuel-2 PF2t are all functions of y1, y2, and y3, respectively, which are
governed by the following (mean-reverting) stochastic differential equations.
dyl = ??l[yl(t)?mt;l(t)]dt+ ldBl; (5.10)
where l=1, 2, and 3 represents electricity, fuel-1, and fuel-2 respectively; ?l is a
drift function;  l is a constant volatility and Bl is a Wiener process with correla-
tion ?lm (l;m=1, 2, 3). There exists a one-to-one transformation between y1 and
PEt , between y2 and PF1t , and between y3 and PF2t . Therefore, (PEt ;PF1t ;PF2t )
can be obtained through the corresponding (y1;y2;y3), and vice versa.
For the purpose of carrying out the simulation process, the time horizon of
fuel-switching options is divided into T subintervals of length ?t (=1 hour). The
discrete version of the process for yl is
?yl = ??l(yl ?mt;l)?t+ l?lp?t (5.11)
where ?yl is the change in yl in time ?t; ?l is a random sample from a stan-
dardized normal distribution. The coefficient of correlation between ?l and ?m is
?lm for 1 ? l;m ? 3. One simulation trial involves obtaining T samples of the
?l(1 ? l ? 3) from a multivariate standard normal distribution. These are sub-
stituted into equation (5.11) to produce simulated paths for each yl and enable
a sample value for the real option to be calculated.
In (5.11), to generate three correlated normal random variables, ?1, ?2, and ?3,
first we generate three mutually independent standard normal random variables,
77
Z1, Z2, and Z3. We then consider the following linear transformation:
?l =
lX
k=1
filkZk (l = 1;2;3) (5.12)
To meet the variances and covariances of ?l(l = 1;2;3), the following two con-
straints are imposed.
X
k
fi2lk = 1 (5.13)
and
X
k
filkfimk = ?lm (5.14)
The first sample ?1 is set equal to Z1. Then the above equations can be solved,
?2 is calculated from Z1 and Z2, ?3 is calculated from Z1, Z2 and Z3.
From (5.12), we have
?1 = fi11Z1;
?2 = fi21Z1 +fi22Z2;
?3 = fi31Z1 +fi32Z2 +fi33Z3:
(5.15)
In matrix form, it is
? = fiZ (5.16)
where ? = (?1;?2;?3)T, Z = (Z1;Z2;Z3)T and
fi =
0
BB
BB
BB
@
fi11 fi12 fi13
fi21 fi22 fi23
fi31 fi32 fi33
1
CC
CC
CC
A
Then, according to (5.13) and (5.14), we obtain
fi =
0
BB
BB
BB
@
1 0 0
?12
q
1??212 0
?13 ?23??12?13p1??2
12
r
1? ?213?2?12?13?23+?2231??2
12
1
CC
CC
CC
A
(5.17)
78
Define new uncertainty variables zl, l = 1;2;3 that satisfy the following linear
relation. 2
66
66
66
4
z1
z2
z3
3
77
77
77
5
= fi?1
2
66
66
66
4
y1
y2
y3
3
77
77
77
5
(5.18)
It can be shown that zl, l = 1;2;3 have been ?decoupled?. That is, given a real-
ization of zl, l = 1;2;3 at time t, their increments dzl, l = 1;2;3 are uncorrelated.
We generate sample path data (over time) for zl, l = 1;2;3 first, which are then
converted to yl, l = 1;2;3, and then PEt , PF1t , and PF2t to evaluate the payoffs.
This procedure preserves the correlation among the price data that is critical to
the value of the generation assets.
5.2.4 Algorithm development
Now, we can use the above regression functions and boundary conditions to
value the fuel switching unit through backward dynamic programming based on
the pre-generated price database. The detailed algorithm is as follows:
Data: Initial conditions (x0;u0;v0;q;0;PE0 ;PF10 ;PF20 ) are given, and data set
size N > 0 is also given.
Step 0: Sett ? T?1, k ? 1, j ? 1, i ? xt ? tonj , JT(xT;uT;vT;q?T;PET ;PF1T ;PF2T )
get from (5.9).
Step 1: Obtain a set of sample prices (PE(k)t ;PF1(k)t ;PF2(k)t ).
Step 2: Regress J(k)t+1 on (PE(k)t ;PF1(k)t ;PF2(k)t ) to obtain ht(?) .
Step 3: If xt = tonj ,
J(i;j;k)t ? ?t(xt;vt;qt;PEt ;PF1t ;PF2t )+max(h1;1t ;h1;0t ?St);
79
else if 0 < xt < tonj ,
J(i;j;k)t ? ?t(xt;vt;qt;PEt ;PF1t ;PF2t )+J(i+1;j;k)t+1 ;
else if xt = 0,
J(i;j;k)t ??1;
else if ?toffj < xt < 0,
J(i;j;k)t ? J(i?1;j;k)t+1 ;
else if ?tcoldj < xt ??toffj ,
J(i;j;k)t ? max(h0;0t ;h0;1t ?St);
else if xt = ?tcoldj ,
J(i;j;k)t ? max(h0;0;nt ;h0;0;st ;h0;1t ?St).
Step 4: If i ??tcoldj , i ? i?1, go to Step 3.
Step 5: If j < 2, j ? j +1, i ? tonj , go to Step 3.
Step 6: If t > 0, t ? t?1, j ? 1, i ? tonj , go to Step 1.
Step 7: Stop.
Note that the fuel switching will happen when xt = ?tcold, and h(0;0;n)t <
h(0;0;s)t . Now, according to the initial unit status (x0;u0;v0;q0), and initial prices
(PE0 ;PF10 ;PF20 ), the expected value of the fuel-switching unit is
J0(x0;u0;v0;q0;PE0 ;PF10 ;PF20 ) ?
NX
k=1
J(k)0 =N (5.19)
Among the above algorithm, the most difficult part is to obtain the regres-
sion function ht(vt;qt;PEt ;PF1t ;PF2t ). What remains to show is an appropriate
functional form for ht(?). Our experience shows that the following polynomial
form works well for the regression.
ht(vt;qt;PEt ;PF1t ;PF2t ) ? a1 +a2qt +a3q2t +a4q3t +a5q?qt +a6PEt +a7PFt
80
+a8q?PFt +a9(PEt )2=PFt (5.20)
where
q? = max(qmin1 ;min(qmax1 ;(PEt =PF1t ?c1;1)=2c2;1))vt
+max(qmin2 ;min(qmax2 ;(PEt =PF2t ?c1;2)=2c2;2))(1?vt) (5.21)
q? is determined by the optimal dispatch rule and the present fuel, PFt =
PF1t vt+PF2t (1?vt), and a1 to a9 are the parameters to be fitted in the regression.
Here we assume that the heat rate function of the unit follows the quadratic
function given in (15a) and c1;j and c2;j are the coefficients for different fuel j.
As a result, the multiple correlation coefficient R2 is around 0.89, which means
the regression on the above polynomial form is good.
Although ht(vt;qt;PEt ;PF1t ;PF2t ) is a highly nonlinear function in (vt;qt) and
(PEt ;PF1t ;PF2t ), and it may not be smooth everywhere because it involves q?,
ht(?) is still a linear function of the regression parameters a1;???;a9, which can
be figured out efficiently by solving a system of linear equations (a 9?9 linear
system in this case.)
5.3 Numerical results
5.3.1 Baseline: a non-switching case
Without considering the fuel-switching option, the valuation problem only
involves two uncertainties and can be solved using a two-factor lattice method
(Tseng 2000). This serves a baseline case, using which we can calibrate the
performance of the LSMC method.
81
Table 5.1: Mean reverting process coefficients of electricity, gas and oil
Coefficients  mu mt P0
Electricity 0.27 0.072 2.878 20
Gas 0.24762 0.010570 1.01945 2.2
Oil 0.10209 0.003704 0.48054 0.58
Consider a natural gas-fired generating unit with the following input-output
characteristics.
H1(qt) = c0;1 +c1;1qt +c2;1q2t (5.22a)
C1(qt) = H1(qt)?PF1t (5.22b)
where the cost function C1(?) is assumed to be a quadratic function of qt, H1(?)
is the heat rate function, PF1t is the fuel price at time period t. Assume PF10 is
$2:2=MMBtu, PE0 is $20=MW, and qmin1 = 225MW, qmax1 = 700MW, c0;1 = 540,
c1;1 = 9:223, and c2;1 = 0:00234. We also assume that ton1 = 5, and toff1 = tcold1 =
10 to fully capture the influence of the physical constraints. Let the startup cost
be $2300 and shutdown cost be $1000. Hourly electricity prices and gas prices are
generated by two mean reverting processes following (5.10). The corresponding
coefficients are in Table 5.1. The correlation coefficient between electricity and
gas is 0.078744. And electricity hourly prices also follow a certain on-peak vs.
off-peak pattern as Table 5.2.
To compare the algorithm performance of LSMC with the lattice method in
(Tseng 2000), seven cases are tested corresponding to seven operating periods
using the same gas-fueled generating unit, ranging from 1 day (24 hours) to 7
days (168 hours). The average CPU times are recorded in Table 5.3.
82
Table 5.2: Mean log Price of electricity: mt(t)
t 1 2 3 4 5 6 7 8
mt(t) 1.8874 2.6557 1.9348 2.3402 3.5027 3.8568 3.7583 4.6602
t 9 10 11 12 13 14 15 16
mt(t) 4.8613 4.71 5.8114 4.7363 5.044 5.7383 5.9166 4.7126
t 17 18 19 20 21 22 23 24
mt(t) 3.7233 1.4573 1.322 2.5106 3.6167 0.6446 1.6033 1.8328
Table 5.3: Average CPU time (seconds)
T (hours) 24 48 72 96 120 144 168
Lattice 0.78 1.64 2.83 4.22 5.86 7.86 10.09
LSMC 0.23 0.47 0.69 0.94 1.16 1.38 1.61
 0                   50                 100                150                200
Time(hours)
CPUTime(seconds)
12
10
8
6
4
2
0
Lattice(snds)
LSMC(snds)
Figure 5.2: CPU time of the lattice model and the LSMC approach.
83
0                   50                   100                 150               200
Time (hours)
Asset Value (dollars)
*10525
20
15
10
5
0
Lattice
LSMC
Figure 5.3: The asset value of the lattice model and the LSMC approach.
Fig. 5.2 shows that the LSMC method is much more efficient than the lattice
method. However, the LSMC method obtains 1 to 3% lower value than that from
the lattice method in Fig. 5.3. This discrepancy increases as the time horizon
increases. This is because the regression function is only an approximation, not
an exact fit. So there are errors in assessing the asset values. In addition, the
errors may add up during the forward and backward iterations. Nevertheless,
this test serves a calibration of the LSMC method for valuing a generation asset.
5.3.2 A fuel-switching unit
To value a fuel-switching unit, an additional (fuel) price uncertainty must be
considered. As mentioned previously, the lattice approach is prohibitive because
of huge memory space and the corresponding large CPU time required.
For simplicity, we assume that when the generating unit is fired by oil, the
84
Table 5.4: Asset value (dollars)
T (hours) 24 48 72 96 120 144 168
Lattice (w/o FSO) 221343 525641 835970 1145564 1453553 1759987 2065077
LSMC (w/o FSO) 218998 518436 821987 1122878 1420875 1715641 2006559
LSMC (w FSO) 229492 547244 873881 1202886 1535541 1868028 2201012
input-output characteristics remain the same as in (5.22a) and (5.22b), although
in reality the coefficients of the quadratic function in (5.22a) should vary. That
is,
H1(qt) = H2(qt) (5.23)
and
C2(qt) = H2(qt)?PF2t (5.24)
Hourly electricity prices, gas prices and oil prices are generated by three mean
reverting process following (5.10). The correlation coefficient between electricity
and oil is 0.033024 and the correlation between gas and oil is 0.19704.
In Fig. 5.4 and Table 5.4, it can be seen that the fuel-switching capability
can increase the asset value. There exist a 7% (when T=168) additional value
due to the fuel switching option, comparing with the baseline using the lattice
method. Since the LSMC approach underestimates the asset value (3%) in the
baseline case (compared with the lattice method), it may also underestimate the
asset value with the fuel-switching options. If this argument is true, than the
fuel switching option may increase the asset value as high as 10%. To verify this
conjecture, we build a three-factor lattice (with a small T, T = 12). We compare
the asset values using both the (3-factor) lattice method and the LSMC method,
the result of lattice method is 1% higher than that of the LSMC method. Since
85
Time (hours)
Asset Value (dollars)
*105
0                   50                 100                 150                200
25
20
15
10
5
0
Lattice (no fuel switching options)
LSMC (with fuel switching options)
LSMC (no fuel switching options)
Figure 5.4: The asset value with and without fuel switching options (FSO).
Table 5.5: Asset Value (dollars)
? 0.0 0.1 0.2 0.3 0.4 0.5
Asset value 2208745 2202111 2195412 2188820 2182207 2175539
the error increases over T, it is fair to estimate that the error in the 1-week case
(T = 168), the error (underestimate) is at least 3%.
5.3.3 Sensitivity analysis on ?gas;oil
Intuitively the value of the fuel-switching option increases as the correlation
between the fuel prices decreases. That means more chances for one fuel to be
in-the-money and the other out-of-the-money.
To study the impacts of fuel price correlation on the option value, we take
86
Correlation
Asset Value (dollars)
0               0.1             0.2              0.3              0.4              0.5
*1032215
2210
2205
2200
2195
2190
2185
2180
2175
2170
Figure 5.5: The asset value vs. ?gas;oil.
the same fuel-switching unit and repeatedly run the program with different ?
between gas and oil prices. The following results for one-week case (T=168) are
obtained.
It can be seen that the asset value decreases linearly as the correlation coef-
ficient ?gas;oil increases. For an example, under an extreme case, the correlation
between gas and oil price is -1. That is the increase of gas price will cause the
decrease of oil price correspondingly. Under this condition, the power producer
will make decisions in switching fuel from nature gas to fuel oil to cut down
fuel cost, so as to increase the asset value of the fuel-switching unit. In the
present energy market, changes in oil prices in this country are almost irrelevant
to natural gas. Our recent analysis based on futures price data, indicates that
the price correlation between the oil and gas is only 0.033024, which means the
fuel-switching units are still in great need in the current power market. This has
87
not considered the value as being emission abatement.
5.4 Conclusions
In this chapter, we use the LSMC method to value the fuel-switching option of
a generation asset considering the operational constraints. We estimate that the
option value is very significant (at 10% over a 1 week period). It provides another
evidence that operational flexibility should not be overlooked when valuing an
generation asset.
88
Chapter 6
Valuing Thermal Generation Units with
Overfire Options and Maintenance
Constraints
6.1 Problem statement
As the power industry moves toward deregulation, more and more small
investors are attracted to buy gas turbines (GTs) to participate the competitive
energy market. Compared with steam turbines (STs), GTs have the following
advantages:
? A GT has much lower installment cost than a ST.
? The construction time of a GT is much shorter than that of a ST.
? A GT may cause less environment pollution problems than any other ther-
mal units.
89
The above are also the reasons why a small or medium size GT working in
peak hour is an ideal choice of small investors, who may not wait for years to be
paid off.
In the current restructured market, the existence of stochastic electricity
prices allow each individual generator to be decoupled from that original col-
lective power pools and to optimize its own generation schedules based on the
available market information and its operating conditions without considering
whether the demand side is satisfied by the supply side or not. The main concern
of individual owners is profitability. For example, if turning off his generator is
profitable from the perspective of individual owner, he will do so without hesi-
tation regardless of how much the power is in need in energy market.
So the new challenge offered by the restructured market is how individual
market participants respond to the stochastic prices optimally considering vari-
ous maintenance constraints, such as crew availability, resource availability, sea-
sonal limitations, desirable schedule; and operating constraints, such as capacity
constraints, ramping constraints, overfire constraints and minimum up/down
time constraints.
Among these constraints, the capacity constraint remains the same as in the
previous chapters, except that qmax may be sensitive to the ambience tempera-
ture. In general, qmax decreases when the environment temperature increases.
As for the ramp constraints, they will be ignored in this chapter, because we
focus on gas turbines only, which can be turned on or shut down within minutes.
To the contrary of the ramp constraints that may limit power generation
(change), overfire process improves the production capacity of the unit, although
it may have adverse effect to the unit such that it may require more frequent
90
maintenance. There are two types of overfire process in thermal power generation
industry. The first is similar to fuel switching process. Two fuels can be burned
to generate power, and the second fuel is assumed to be considerably more
expensive and provides additional capability. In this sense, the fuel cost function
will also change correspondingly. The second type is simpler. Only one kind of
fuel is burned and additional capacity is provided by burning additional fuel.
The fuel cost function will not change because of overfiring. In this paper, for
simplicity we only consider the second type.
Although overfire can bring additional profit for the short run, it also cre-
ates problems. This is because overfiring a unit can cause the temperature
inside the combustor to be significantly higher than its normal value. Under
this condition, the unit?s hot section components are subjected to overstressing
and high-temperature corrosion, which may then create further damages, such
as degradation, deformation, and/or even cracks. Therefore, the duration for
overfiring a unit must be restricted based on metal characteristics of the gas
turbine.
Maintenance is an efficient way to correct/prevent such potential damages
due to overfire. During a maintenance process, the following steps are taken:
? Let the unit cool down;
? Clean all working parts;
? Test hot section components;
? Replace ineffective ones with new parts;
? Reassemble the unit and lubricate it.
91
Sometimes the above steps may take weeks to complete. After the maintenance,
the gas turbine can work efficiently and safely again.
Some basic definitions about maintenance are introduced here:
? A maintenance interval refers to the time of length required to finish main-
tenance.
? A operation period refers to the time period between any two maintenance
intervals that the unit is in operation.
? An outage refers to a period of power system non-function due to supply
failure or scheduled maintenance.
6.2 A valuation framework considering overfire
options and maintenance constraints
In this section, the following standard notation will be used to formulate
the asset valuation problem considering the overfire option and maintenance
constraints. Additional symbols will be introduced when necessary.
t : index for time (in hours), t = 0;???;T, where T is the number of hours of
the planning horizon.
ut : zero-one decision variable indicating whether the unit is up or down in time
period t.
vt : zero-one decision variable indicating whether the unit is overfired or not in
time period t.
92
wt : zero-one decision variable indicating whether the unit is shutdown for main-
tenance or not in time period t.
xt : state variable indicating the operation status of the unit in time period t.
?x0 : initial condition of xt at t = 0.
yt : statevariableindicatinghowmanyoperationhoursremainedattime tbefore
the next maintenance interval for the unit.
?y0 : initial condition of yt at t = 0.
zt : state variable indicating how many startup numbers remained at time t
before the next maintenance interval for the unit.
?z0 : initial condition of zt at t = 0.
ton : the minimum number of periods the unit must remain on after it has been
turned on.
toff : the minimum number of periods the unit must remain off after it has been
turned off.
tcold : the number of periods required to cool the unit from shutdown.
tover : maximum number of periods the unit can be overfired continuously.
qt : variable indicating the amount of the unit is generating in time period t.
qmin : minimum rated capacity of the unit.
qmax : maximum rated capacity of the unit.
qover : maximum rated capacity of the unit when it is overfired (qover > qmax).
93
Ct(qt;PFt ) : fuel cost for operating the unit at output level qt with fuel price at
PFt in time period t.
St(ut;ut?1) : startup/shutdown cost associated with turning on/off the unit in
time period t.
PEt : spot price at time t for electricity.
PFt : spot price at time t for fuel.
Tet : environment temperature at time t.
Td : designed operating temperature of this gas turbine.
?Td : designed operating temperature range of the gas turbine.
flef(Tet ) : fuel cost adjusting factor, which is dependent on environment temper-
ature Tet at time t.
fleq(Tet ) : qmax adjusting factor, which is dependent on environment temperature
Tet at time t.
Rf : fuel cost adjusting range (%) due to environment temperature variation.
Rq : qmax adjusting range (%) due to environment temperature variation.
nt(ut;ut?1;xt) : equivalent startup number at time t determined by the unit
status xt in time period t before turning on.
tmt : the minimum number of periods the unit must be shutdown for mainte-
nance.
94
Mmt : direct maintenance cost which are determined by the maintenance con-
tracts.
Nop : the maximal operating time periods between any two maintenance inter-
vals, which are determined by the maintenance contracts.
Nstart : the maximal number of startups between any two maintenance intervals,
which are determined by the maintenance contracts.
Xt : a state vector including xt, yt and zt indicating the status of the unit in
time period t.
Vt : a decision vector including ut, vt and wt indicating the decisions of the unit
in time period t.
Qt : an uncertainty vector including PEt , PFt and Tet indicating all the uncer-
tainties in time period t.
ft(Xt;Qt) : value function of the unit in time period t under state Xt and un-
certainty Qt.
6.2.1 The mathematical model
The objective is to value the thermal generation unit with overfire options and
maintenance contracts subject to environment temperature uncertainty. This
valuation is a typical multi-stage stochastic problem. Assume that at any time
t and state Xt, uncertainty vector Qt is observed. The operator can realize the
asset value in the current time period first of all, then maximize the expected
value of the unit for the rest time periods by taking suitable actions Vt. Let
Jt(Xt;Vt;Qt) be the so-called value-to-go function indicating the total value of
95
the unit for the remaining period at state Xt at time t, and assume a certain time
horizon [0;T]. The asset valuation problem can be formulated as the following
recursive relation:
Maximize the expected total profit:
(P0) Jt(Xt;Vt;Qt) = ?t(xt;qt;Qt)+
maxu
t;vt;wt
fEt[Jt+1(Xt+1;Vt+1;Qt+1)]?St(ut;ut?1)?Mmtwtg (6.1)
where
?t(xt;qt;Qt) =
8
>><
>>:
PEt qt ?Ct(qt;PFt ); if xt > ton;
0; otherwise:
(6.2)
Assume that qt can be dispatched instantaneously and optimally, when uncer-
tainty Qt is realized.
Ct(qt;PFt ) = flef(Tet )(c0 +c1qt +c2q2t)PFt (6.3)
flef(Tet ) = 1+
 Te
t ?T
d
?Td
?
Rf% (6.4)
In (6.3), fuel cost C(qt;PFt ) is dependent on the environment temperature Tet at
time t. Equation (6.4) shows that when the environment temperature deviates
from its designed temperature Td, the adjusting factor flef will have value and
apply to the fuel cost.
St(ut;ut?1) =
8>
>>>>
><
>>>>
>>:
Sup; if ut?1 = 0 and ut = 1
Sdown; if ut?1 = 1 and ut = 0
0; otherwise;
(6.5)
where Sup and Sdown represent constant startup cost and constant shutdown
cost.
The last term Mmtwt in the objective function represents a fixed maintenance
cost, incurred only when maintenance takes place. Finally, the above optimiza-
tion is subject to several constraints, each of which will be detailed next.
96
Maintenance contract
Proper maintenance can keep a GT to work efficiently and reliably. However,
it may not be economic for an owner to staff full-time crews to maintain the
units. This is true especially for owners of small GTs, who usually prefer to
sign maintenance contracts with some maintenance companies, responsible for
on-site unit maintenance.
A complete maintenance contact is normally complicated. Since frequent up
and down and violent temperature variation are the main causes for early fatigue
or outage of a unit, we consider a simplified contract such that maintenance
must be performed (therefore, the unit must be shutdown) if at least one of the
following conditions is met: (i) the aggregated unit operation hours (yt) exceeds
some prespecified level Nop; (ii) the aggregated unit startup numbers zt exceeds
some prespecified level Nstart. These two conditions are detailed next.
? The aggregated operation hours is tracked by yt, whose initial value is 0. A
normal operation hour refers to an hour during which the generation level
is within the rated capacities, i.e., [qmin;qmax]. As opposed to the normal
operation hour, an overfire hour is one in which the unit overfires. Since
overfiring a unit results in more fatigue than normal operation, an overfire
hour is considered equivalent to W > 1 normal operation hours (specified
in the maintenance contract). Therefore,
yt+1 = yt +(Wvt +(1?vt))ut: (6.6)
? The aggregated startup numbers is tracked by zt, initially set to 0. Similar
to the operation hours, different levels of startups are categorized depend-
ing on the temperature of turbines. They are: warm start, normal start,
97
cold start, and very cold start. From the perspective of maintenance, the
range of temperature variation is the less, the better. The startup of a
gas turbine is a typical process of increasing temperature. Generally, the
longer a unit has been shutdown, the lower the temperature of the tur-
bine is. A warm start causes less temperature variation and fatigue than
a normal start; and a cold and very cold starts cause more temperature
variation and fatigue than a normal start. The following is an example
how the startup number is considered, depending on how long the unit has
been down (xt < 0).
nt(xt) =
8>
>>>
>>>>
>>>>
>><
>>>
>>>>
>>>>
>>>
:
0:5; if xt > ?4 (warm start);
1; if ?4 ? xt > ?20 (normal start);
1:5; if ?20 ? xt > ?40 (cold start);
2; if xt ??40 (very cold start);
0; otherwise:
(6.7)
In (6.7), a warm start is considered a half normal start if the unit has been
down for less than 4 hours, and a cold start (down for 20 to 40 hours) is
considered one and a half normal start. Overall, the startup number is
aggregated as follows.
zt+1 = zt +nt(xt)(1?ut?1)ut; (6.8)
Asaforementioned, oncetheaggregatedoperationhoursoraggregatedstartup
numbers reaches some levels, specified in the maintenance contract, shutting
down the unit for maintenance (wt = 1) is enforced.
98
Maintenance condition
wt =
8>
><
>>:
1; if yt ? Nop or zt ? Nstart;
0 or 1; otherwise:
(6.9)
Maintenance interval constraints
Once a maintenance decision wt = 1 is made at time t, the unit goes into a
maintenance interval with a duration tmt time periods. That is, the unit must
stay off for at least tmt time periods (approximately two weeks in reality). That
is, if wt = 1 and wt?1 = 0, then
xt+tmt = ?tcold; (6.10)
yt+tmt = 0; (6.11)
zt+tmt = 0: (6.12)
A sample state transition diagram is shown in Fig. 6.1, in which it can be seen
that once a maintenance decision is made at t, the state is then transited to time
t+tmt, and the counters yt+tmt and zt+tmt are reset to 0. In (6.10), xt+tmt = ?tcold
implies that this generator can be viewed as staying at the cold status and ready
to put back on-line again.
Next we incorporate the maintenance constraints into the state transition
(see Fig. 6.1). Two phases are discussed: (i) operation phase (wt = 0); (ii)
maintenance phase (wt = 1).
State transition: operation phase (wt = 0)
xt+1 =
8>
>>>>
><
>>>>
>>:
min(ton +tover;max(ton;xt)+1); if ut = 1 and vt = 1;
min(ton;max(xt;0)+1); if ut = 1 and vt = 0;
max(?tcold;min(xt;0)?1); if ut = 0 and vt = 0:
(6.13)
99
and
ut =
8
>>>>
>><
>>>
>>>:
1; if 1 ? xt < ton and ton < xt ? ton +tover;
0; if ?toff < xt ??1;
0 or 1; otherwise:
(6.14)
vt =
8
>><
>>:
0; if xt = ton +tover or xt < ton;
0 or 1; otherwise:
(6.15)
Equations (6.14) and (6.15) represent the minimum uptime/downtime and over-
fire constraints, respectively. Equation (6.15) implies that the unit can be over-
fired only when after the minimal uptime constraint has been satisfied, i.e., after
at least ton hours of normal operation. This restriction can prevent significant
temperature variation within a short time period due to overfire. In addition,
the unit cannot overfire for more than tover hours continuously. When it is turned
back to normal operation status from overfire, it must remain normal operation
for at least an hour before it can overfire again.
State transition: maintenance phase (wt = 1)
xt+1 = max(?tcold ?1;min(0;xt)?1) (6.16)
yt+1 = 0 (6.17)
zt+1 = 0 (6.18)
and
ut = 0 (6.19)
vt = 0 (6.20)
Equations (6.16) to (6.20) describe the values of the states when the unit is in
the maintenance phase (i.e., shut down). Apparently, the unit cannot overfire in
a maintenance interval.
100
Overfire
   vt=1
Operation
On-line
   ut=1
xt=ton+tover
xt=ton+2
xt=ton+1
xt=2
xt=-1
t t+1 t+tmt
xt=ton
xt=1
xt=-2
xt=-toff
xt=-tcold
xt=-tcold-1
t+tmt+1
Maintenace
     wt=1
Figure 6.1: State transition diagram including operation and maintenance
processes.
101
Capacity constraint
As aforementioned, the production capacity of a unit may be dependent on
environment temperature. The capacity constraint is modeled below.
qmin ? qt ? (qmax(1?vt)+qovervt)fleq(Tet ) (6.21)
where
fleq(Tet ) = 1?
 Te
t ?T
d
?Td
?
Rq% (6.22)
Equations (6.21) and (6.22) state the maximum rated capacity can be increased
from qmax to qover. Regardless of overfire, both qmax and qover are sensitive to the
environment temperature Tet . For instance, when Tet increases, both qmax and
qover will decrease.
6.2.2 Temperature model
In the formulation, we have shown that GT?s operational characteristics (in-
cluding C(qt;PFt ), qmax, and qover) are sensitive to the environment temperature
Tet . It is, therefore, important to study temperature variation over time.
Cao and Wei (2000) suggested that future temperature deviation on day ?+1
can be forecasted based on temperature deviations over the three previous time
periods, ?, ? ?1 and ? ?2. Later Baldick et al. (2003) claim that the tempera-
ture deviations on ? ?2 are statistically insignificant to the future temperature
deviations on ? + 1. Thus, in their model the temperature deviation from the
historical average on ? + 1 is a function of temperature deviations on ? and
? ?1 only. The stochastic fluctuations around historical average can be further
described by the following equations:
?T?+1 = ?T1 ?T? +?T2 ?T??1 + T? ?T? (6.23)
102
Table 6.1: Value of the parameters of the temperature model
Parameters Value
?T1 0.831
?T2 -0.194
 T0 8.322
 T1;1 5.697
 T1;2 5.774
 T1;3 5.741
 T1;4 5.753
` -14.2
 T? =  T0 ? T1 jsin(?(? +`)365 )j (6.24)
where ?T? = Tt ? ?T?, T? is the actual temperature for day ? ?T? is the average
temperature for day ?, and ?T1 , ?T2 represent the autocorrelation coefficients for
deviations from average temperature on day ? and ? ? 1, respectively. The
magnitude of the random fluctuations is seasonal, with a fixed term  T0 and
a seasonal term of magnitude  T1 . Each ?Tt is a standardized normal random
variable.
Following the model of Baldick et al. (2003), we collect weather data (from
January 2000 through December 2002) at the National Climatic Data Center
website (www.ncdc.noaa,gov), and use which to calibrate the model. We fur-
ther categorize  T1 into seasonal values:  T1;1(spring),  T1;2(summer),  T1;3(fall) and
 T1;4(winter). The estimated values of the parameters are summarized in table
6.1.
103
6.2.3 Stochastic price process
In this chapter, it is assumed that the prices for electricity PEt and fuel PFt
follow some mean reverting processes and are functions of fi1 and fi2 respectively,
which are governed by the following stochastic differential equations.
dfil = ?l(fil;t)dt+ ldBl; (6.25a)
?l(fil;t) = ?mul[fil(t)?mtl(t)]; (6.25b)
where l = 1 and 2 represent the prices for electricity and fuel, respectively, ?l
is a drift function,  l is a constant volatility and Bl is a Wiener process with
correlation ?1;2. Assume that there exists one-to-one transformations between fi1
and PEt , and between fi2 and PFt . Therefore, (PEt ;PFt ) can be obtained through
the corresponding (fi1;fi2). Price samples are generated in the same way used
in Chapter 5.
6.3 Algorithm development
The problem (P) is a difficult mixed-integer multi-stage program. In order
to solve the problem (P), which is subject to all the above operating constraints
(6.6) to (6.22) including overfire and maintenance constraints, we need to find a
suitable method.
In this chapter, we use the LSMC approach described in the previous chapter
to solve the problem (P) based on the graphic network in Fig. 6.1.
6.3.1 Solution procedure
At any time t, one must know how to approximate Et[Jt+1(?)] before making
104
optimal decisions. The regression functions ht(?) of current uncertainty Qt and
production level qt are regressed as follows:
? Stay overfire
ho;ot (qt;Qt) = Et[Jt+1(min(ton +tover;xt +1);yt?W;zt;Vt+1;Qt+1)] (6.26a)
? From overfire to normal
ho;nt (qt;Qt) = Et[Jt+1(ton;yt ?1;zt;Vt+1;Qt+1)] (6.26b)
? From normal to overfire
hn;ot (qt;Qt) = Et[Jt+1(ton +1;yt ?W;zt;Vt+1;Qt+1)] (6.26c)
? Stay normal
hn;nt (qt;Qt) = Et[Jt+1(min(ton;xt +1);yt ?1;zt;Vt+1;Qt+1)] (6.26d)
? From up to down
hu;dt (qt;Qt) = Et[Jt+1(?1;yt;zt;Vt+1;Qt+1)] (6.26e)
? From down to up
hd;ut (qt;Qt) = Et[Jt+1(1;yt ?1;zt ?nt;Vt+1;Qt+1)] (6.26f)
? Stay down
hd;dt (qt;Qt) = Et[Jt+1(max(?tcold;xt ?1);yt;zt;Vt+1;Qt+1)] (6.26g)
? From cold to maintenance
hc;mt (qt;Qt) = Et[Jt+1(?tcold ?1;0;0;Vt+1;Qt+1)] (6.26h)
105
? Stay maintenance
hm;mt (qt;Qt) = Et[Jt+1(?tcold ?1;0;0;Vt+1;Qt+1)] (6.26i)
? From maintenance to cold
hm;ct (qt;Qt) = Et[Jt+tmt(?tcold;Nop;Nstart;Vt+1;Qt+1)] (6.26j)
The aforementioned expected value of Jt+1(?) can be approximated through
forward-moving simulation and backward-moving dynamic programming itera-
tions. Since analytical forms of ht(?) are nonexistent in general, we can only
use numerical methods based on Monte Carlo simulation to approximate it.
If the above regression functions ht(?) are available at time t, one could know
the expected unit value for the next time period when the uncertainty prices
(PEt ;PFt ) and environment temperature Tet are revealed. Then, one could de-
termine: (i)whether to do maintenance or not; (ii)whether to turn on or off the
unit; or (iii)whether to overfire or not. That means for any realization of Qt
at time t, one would know how to optimally make decisions for the next time
period based on the above regression functions ht(?).
6.3.2 Overfire options
Overfire may be viewed as a real option. However, when and how to exer-
cise the overfire option may not be an easy task. This is because that overfire
operation affects maintenance schedule of gas turbine. Therefore, optimally ex-
ercising the overfire option must be considered over the entire planning horizon.
Assume that the length of time horizon is T and all boundary conditions are
given. Whether one should overfire or not can be determined by the following
106
equations:
vt =
8
>>>>
>><
>>>
>>>:
1; if 1 ? xt < ton +tover and Jt+1(max(ton;xt)+1;yt ?W;zt;Vt+1;Qt+1)
> Jt+1(min(ton;xt +1);yt ?1;zt;Vt+1;Qt+1);
0; otherwise:
(6.27)
6.3.3 Maintenance options
From maintenance constraints (6.9), it can be seen that one may still decide
to shutdown the unit for maintenance even when any of the two conditions
specified in the contract is not met. Therefore, maintenance may also be viewed
as a real option. For example, one may intentionally maintain the unit even
when it is not required in order to make the unit available for some forecasted
heat wave in the near future. Since the maintenance requires shutting down
the unit for some period, it is not obvious whether early exercise the option is
optimal. At any time t when xt = tcold, one may have three options: (i) turn on
the unit; (ii) stay off; or (iii) do the maintenance. The optimal decision can be
determined based on the expected value of Jt+1 as follows:
wt =
8>
>>>
>><
>>>>
>>:
1; if xt = tcold;yt > 0;zt > 0; and Jt+1(?tcold ?1;0;0;Vt+1;Qt+1) >
max(Jt+1(?tcold;yt;zt;Vt+1;Qt+1);Jt+1(1;yt ?1;zt ?1;Vt+1;Qt+1));
0; otherwise:
(6.28)
6.3.4 Boundary conditions
Boundary conditions refer to the values of JT at time T. If T represents the
life time of a GT, JT must be zero for sure; otherwise, JT should be equal to the
107
rest value of the GT.
Once the boundary values of JT are known, one can use the LSMC to estimate
JT?1 for every data sample. The decision maker can choose whether to do
maintenance or not, whether to startup or not, whether to overfire or not, and
revisit the exercise decision at the next time period. This procedure can be
repeated to T ?2;???;0. The last iteration, starting with the initial conditions
at time 0, provides the optimal planning and asset estimation for the whole time
horizon.
6.3.5 Algorithm for the asset valuation
Next we show how to use the LSMC method to value the GT with overfire
capacity and maintenance contracts through backward dynamic programming
based on the pre-generated price database and temperature data. Two algo-
rithms will be presented. The first one is the generic algorithm, which, however,
requires a huge state space. The second one is an improved method.
Algorithm 1: Generic algorithm
Data: Initial conditions (x0;y0;z0;PE0 ;PR0 ;PF0 ;Te0) are given, and data set size
N > 0 is also given.
Step 0: Set t ? T ? 1, i ? ton + tover, j ? Nop, k ? Nstart, JT(?) get from
boundary conditions.
Step 1: Obtain a set of sample prices (PE(n)t ;PR(n)t ;PF(n)t ) and environmental
temperatures Te(n)t (n = 1;???;N).
Step 2: Regress J(n)t+1 on (PE(n)t ;PR(n)t ;PF(n)t ) to obtain ht(?) .
108
Step 3: If xt = ton +tover,
J(i;j;k;n)t ? ?t(?)+J(ton;j?1;k;n)t+1 ;
else if ton < xt < tover,
J(i;j;k;n)t ? ?t(?)+max(ho;ot ;ho;nt );
else if xt = ton,
J(i;j;k;n)t ? ?t(?)+max(hn;ot ;hn;nt ;hu;dt ?Sdown);
else if 0 < xt < ton,
J(i;j;k;n)t ? ?t(?)+max(J(i+1;j?1;k;n)t+1 ;hn;ot );
else if xt = 0,
J(i;j;k;n)t ??1;
else if ?toff < xt < 0,
J(i;j;k;n)t ? J(i?1;j;k;n)t+1 ;
else if ?tcold < xt ??toff,
J(i;j;k;n)t ? max(hd;dt ;hd;ut ?Sup);
else if xt = ?tcold,
J(i;j;k;n)t ? max(hc;mt ?Mmt;hd;dt ;hd;ut ?Sup);
else if xt = ?tcold ?1,
J(i;j;k;n)t ? max(hm;mt ;hm;ct ).
Step 4: If i > ?tcold ?1, i ? i?1, go to Step 3.
Step 5: if j > 0,
j ? j ?1, i ? ton +tover, go to Step 3;
else
J(i;j;k;n)t ? max(J(i;j;k;n)t ;J(i;Nop;k;n)t+tmt ).
Step 6: If k > 0,
109
k ? k ?1, j ? Nop, i ? ton +tover, go to Step 3;
else
J(i;j;k;n)t ? max(J(i;j;k;n)t ;J(i;j;Nstart;n)t+tmt ).
Step 7: If t > 0, t ? t?1, k ? Nstart, j ? Nop, i ? ton +tover, go to Step 1.
Step 8: Stop.
While in theory the above algorithm can work, it is not solvable from the
perspective of implementation due to the huge state space (I ? J ? K ? T)
required. For example, when the number of unit status xt is 10, the num-
ber of total operation hour yt is 1000, the number of total startup zt is 100,
and the number of total hours T (in a year) is 8760, the state space becomes
10?1000?100?8760 = 8:76?109. Further considering N sample paths of several
uncertainties and the least squares regression in each state, this problem cannot
be handled within reasonable time by the current computer hardware. One al-
ternative method is to absorb the state variables yt and zt into each regression
function so as to reduce the state space significantly. The algorithm is as follows:
Algorithm 2: An improved version
Data: Initial conditions (x0;y0;z0;PE0 ;PR0 ;PF0 ;Te0) are given, and data set size
N > 0 is also given.
Step 0: Set t ? T ?1, i ? ton +tover, JT(?) get from boundary conditions.
Step 1: Obtain a set of sample prices (PE(n)t ;PR(n)t ;PF(n)t ) and environmental
temperatures Te(n)t (n = 1;???;N).
Step 2: Regress J(n)t+1 on (PE(n)t ;PR(n)t ;PF(n)t ) to obtain ht(?) .
110
Step 3: If xt = ton +tover,
J(i;n)t ? ?t(?)+J(ton;n)t+1 ;
y(i;n)t ? y(ton;n)t+1 ?W;
z(i;n)t ? z(ton;n)t+1 ;
else if ton < xt < tover,
if y(i+1;n)t+1 > 0 and z(i+1;n)t+1 > 0;
J(i;n)t ? ?t(?)+max(ho;ot ;ho;nt );
y(i;n)t ?
8
>><
>>:
y(i+1;n)t+1 ?W; if ho;ot > ho;nt ;
y(ton;n)t+1 ?W; otherwise:
z(i;n)t ?
8>
><
>>:
z(i+1;n)t+1 ; if ho;ot > ho;nt ;
z(ton;n)t+1 ; otherwise:
else
J(i;n)t ? ?t(?)+ho;nt ;
y(i;n)t ? y(ton;n)t+1 ?W;
z(i;n)t ? z(ton;n)t+1 ;
else if xt = ton,
if y(i+1;n)t+1 > 0 and z(i+1;n)t+1 > 0;
J(i;n)t ? ?t(?)+max(hn;ot ;hn;nt ;hu;dt ?Sdown);
y(i;n)t ?
8>
>>>
>><
>>>>
>>:
y(i+1;n)t+1 ?1; if ho;ot > max(hn;nt ;hu;dt ?Sdown);
y(i;n)t+1 ?1; else if hn;nt > hu;dt ?Sdown;
y(?1;n)t+1 ?1; otherwise:
z(i;n)t ?
8>
>>>
>><
>>>>
>>:
z(i+1;n)t+1 ; if ho;ot > max(hn;nt ;hu;dt ?Sdown);
z(i;n)t+1 ; else if hn;nt > hu;dt ?Sdown;
z(?1;n)t+1 ; otherwise:
else if y(i;n)t+1 > 0 and z(i;n)t > 0;
111
J(i;n)t ? ?t(?)+max(hn;nt ;hu;dt ?Sdown);
y(i;n)t ?
8>
><
>>:
y(i;n)t+1 ?1; if hn;nt > hu;dt ?Sdown;
y(?1;n)t+1 ?1; otherwise:
z(i;n)t ?
8
>><
>>:
z(i;n)t+1 ; if hn;nt > hu;dt ?Sdown;
z(?1;n)t+1 ; otherwise:
else
J(i;n)t ? ?t(?)+hu;dt ?Sdown;
y(i;n)t ? y(?1;n)t+1 ?1
z(i;n)t ? z(?1;n)t+1
else if 0 < xt < ton,
if y(ton+1;n)t+1 > 0 and z(ton+1;n)t+1 > 0;
J(i;n)t ? ?t(?)+max(h(n;n)t ;hn;ot );
y(i;n)t ?
8>
><
>>:
y(ton+1;n)t+1 ?1; if hn;ot > hn;nt ;
y(i+1;n)t+1 ?1; otherwise:
z(i;n)t ?
8
>><
>>:
z(ton+1;n)t+1 ; if hn;ot > hn;nt ;
z(i+1;n)t+1 ; otherwise:
else
J(i;n)t ? ?t(?)+h(n;n)t ;
y(i;n)t ? y(i+1;n)t+1 ?1
z(i;n)t ? z(i+1;n)t+1
else if xt = 0,
J(i;n)t ??1;
else if ?toff < xt < 0,
J(i;n)t ? J(i?1;n)t+1 ;
y(i;n)t ? y(i?1;n)t+1
z(i;n)t ? z(i?1;n)t+1
112
else if ?tcold < xt ??toff,
if y(1;n)t+1 > 0 and z(1;n)t+1 > 0;
J(i;n)t ? max(hd;dt ;hd;ut ?Sup);
y(i;n)t ?
8
>><
>>:
y(1;n)t+1 ; if hd;ut ?Sup > hd;dt ;
y(i?1;n)t+1 ; otherwise:
z(i;n)t ?
8>
><
>>:
z(1;n)t+1 ?nt(i); if hd;ut ?Sup > hd;dt ;
z(i?1;n)t+1 ; otherwise:
else
J(i;n)t ? hd;dt ;
y(i;n)t ? y(i?1;n)t+1
z(i;n)t ? z(i?1;n)t+1
else if xt = ?tcold,
if y(1;n)t+1 > 0 and z(1;n)t+1 > 0;
J(i;n)t ? max(hc;mt ?Mmt;hd;dt ;hd;ut ?Sup);
y(i;n)t ?
8
>>>>
>><
>>>
>>>:
y(1;n)t+1 ; if hd;ut ?Sup > max(hc;mt ?Mmt;hd;dt );
y(i;n)t+1 ; else if hd;dt > hc;mt ?Mmt;
y(i?1;n)t+1 ; otherwise:
z(i;n)t ?
8
>>>>
>><
>>>
>>>:
z(1;n)t+1 ?nt(i); if hd;ut ?Sup > max(hc;mt ?Mmt;hd;dt );
z(i;n)t+1 ; else if hd;dt > hc;mt ?Mmt;
z(i?1;n)t+1 ; otherwise:
else if y(i;n)t+1 > 0 and z(i;n)t+1 > 0;
J(i;n)t ? max(hc;mt ?Mmt;hd;dt );
y(i;n)t ?
8>
><
>>:
y(i;n)t+1 ; if hd;dt > hc;mt ?Mmt;
y(i?1;n)t+1 ; otherwise:
z(i;n)t ?
8
>><
>>:
z(i;n)t+1 ; if hd;dt > hc;mt ?Mmt;
z(i?1;n)t+1 ; otherwise:
113
else
J(i;n)t ? hc;mt ?Mmt;
y(i;n)t ? y(i?1;n)t+1
z(i;n)t ? z(i?1;n)t+1
else if xt = ?tcold ?1,
J(i;n)t ? max(hm;mt ;hm;ct );
y(i;n)t ?
8>
><
>>:
Nop; if hm;ct > hm;mt ;
y(i;n)t+1 ; otherwise:
z(i;n)t ?
8
>><
>>:
Nstart; if hm;ct > hm;mt ;
z(i;n)t+1 ; otherwise:
Step 4: If i > ?tcold ?1, i ? i?1, go to Step 3.
Step 5: If t > 0, t ? t?1, i ? ton +tover, go to Step 1.
Step 6: Stop.
Based on the initial unit status (x0;y0;z0), initial prices (PE0 ;PR0 ;PF0 ) and the
initial temperature Te0, the asset value of the GT at t = 0 is
J0(x0;y0;z0;V0;Q0) ?
NX
n=1
J(x0;y0;z0;n)0 =N (6.29)
Since the analytical form of ht(?) is unavailable in general, we can only try to
find an appropriate functional form to approximate it. Based on our numerical
experience, the following polynomial form including state variable yt and zt works
well for the regression.
ht(qt;yt;zt;Qt) ? a1 +a2qt +a3q2t +a4q?qt +a5PEt +a6PRt +a7PFt +a8Tet
+a9q?(PEt )2=PFt +a10yt +a11zt +a12ytq? (6.30)
114
where
q? =
8
>>>>
>><
>>>
>>>:
max(qmin;min(ceq(Tet )qover; PEt =PFt ?c12c2 )); if xt > ton;
max(qmin;min(ceq(Tet )qmax; PEt =PFt ?c12c2 )); if 0 < xt ? ton;
0; otherwise:
(6.31)
q? is determined by the present status xt, and the current environmental tem-
perature Tet ; and a1 ? a12 are the parameters to be fitted in the regression.
6.4 Numerical results
Consider a small-size gas-fired turbine with the input-output characteristics
following (6.3) and (6.4). Assume that PF0 is $2:2=MMBtu, PE0 is $20=MW,
and qmin = 75MW, qmax = 200MW, qover = 230MW, c0 = 200, c1 = 8:149,
and c2 = 0:00452. We also assume that ton = 2, toff = tcold = 1, and tover = 1
to fully capture the influence of the physical constraints. The corresponding
state transition diagram is given in Fig. 6.2. Let the startup cost be $1000 and
shutdown cost be $500. Hourly electricity prices and gas prices are generated
by two mean reverting process following (6.25a) and (6.25b) The corresponding
parameters of the price models are given in Table 6.1 and Table 6.2. Assume
that the correlation coefficient between electricity and gas prices is 0.078744.
Forthemaintenancecontracts, weassumethatthemaximumnumberofoper-
ation hours Nop = 1600 hours and the maximum startup numbers is Nstart = 120
between any two maintenance intervals. Assume W = 4, i.e., an overfire hour
is equivalent to 4 normal operation hours. Assume the duration of each mainte-
nance interval Tmt is two weeks, i.e., 336 hours. As to the environment temper-
ature model, the corresponding parameters are showed in Table 6.1, calibrated
115
Overfire
   vt=1
Operation
On-line
   ut=1
xt=3
xt=2
xt=-1
t t+1 t+tmt
xt=1
xt=-2
t+tmt+1
Maintenace
     wt=1
Figure 6.2: The state transition diagram for this case.
Table 6.1: Mean reverting process coefficients of electricity and gas
Coefficients  mu mt P0
Electricity 0.27 0.072 2.878 20
Gas 0.2476 0.01057 1.0195 2.2
from real data. Assume the designed operating environment temperature Td to
be 66oF and the allowable variation range of environment temperature ?Td to
be 60oF. Both fuel cost adjusting range Rf and qmax adjusting range Rq are 2%.
6.4.1 Valuing a GT with overfire capacity and mainte-
nance contract
A set of price and temperatures scenarios are generated to estimate the ca-
116
Table 6.2: Mean log Price of electricity: mt(t)
t 1 2 3 4 5 6 7 8
mt(t) 1.887 2.656 1.935 2.340 3.503 3.857 3.758 4.660
t 9 10 11 12 13 14 15 16
mt(t) 4.861 4.710 5.811 4.736 5.044 5.738 5.917 4.713
t 17 18 19 20 21 22 23 24
mt(t) 3.723 1.457 1.322 2.511 3.617 0.645 1.603 1.833
pacity value of the same GT considering overfire capacity and maintenance con-
straints using Algorithm 2. Assume that the time horizon is 8760 hours (1 year)
and after which the remaining value of the GT is zero. (This does not mean
that the GT is worthless in a year, but a simplified ?mid-term? asset valuation
and planning.)
Asset value vs. time T
First we consider the capacity value of the GT vs. the length of the time horizon
T, ranging from one month to one year. The result is depicted in Fig. 6.3. It
can be seen that the capacity value of the GT with overfire capacity and mainte-
nance contract is around 150$=KW for one year. In general, the capacity value
increases with the length of time horizon T monotonically and approximately
linearly. The relation is bumpy when T is between 3 and 7 months. This is
because that maintenance intervals start to exist within such durations. Since
each maintenance interval takes two weeks, it impacts the overall asset value
and creates the bumpiness of the seemingly linear relation when T is not big.
However, as T exceeds 8 months, which is considerably much longer than the
117
0
20
40
60
80
100
120
140
160
0 2 4 6 8 10 12
Time (months)
Capacity Value (dollars/KW)
Figure 6.3: Capacity value of the GT over time.
duration of the maintenance interval, the asset value returns to an approximately
linear function of T.
Asset value affected by environment temperature
In the proposed model, a GT?s operational characteristics (including C(qt;PFt ),
qmax, and qover) are sensitive to the environment temperature Tet . To test how
the asset value is sensitive to the environment temperature, we design a baseline
test case, in which the environmental temperature Tet = Tdt for all t such that
flef = flqf = 1. That is, in the baseline case, these operational characteristics are
not temperature dependent. The baseline case is then compared with two cases
with uncertain temperatures following the model in Section 6.2.2. For simplicity,
we choose T to be 8 weeks to exclude the effect of maintenance. One test case
is in summer and one in winter. Generally, Tet > Tdt in the summer, and both
118
-2.30%
-2.20%
-2.10%
-2.00%
-1.90%
-1.80%
0 3 6 9
Time (weeks)
Asset Value Variation (%)
Figure 6.4: Asset value affected by environment temperature in summer.
qmax, and qover decrease. Therefore, the asset value also decreases. The situation
is reversed in the winter case. The result of the summer case is depicted in
Fig. 6.4. It can be seen that as T = 8, temperature uncertainty accounts for
approximately 2.2% decrease of the asset value (compared with the baseline.)
The result of the winter case is given in Fig. 6.5, where the asset value is higher
than that of the baseline.
6.4.2 Overfire option value
To extract the value of the overfire real option, we introduce an additional
constraint that limits the overall number of overfire hours. First, let ot be a new
state variable that tracks the aggregated overfire hours, which is reset to 0 after
a maintenance is performed. An upper bound Nover is then imposed to ot. The
119
1.20%
1.40%
1.60%
1.80%
2.00%
2.20%
2.40%
0 3 6 9
Time (weeks)
Asset Value Variation (%)
Figure 6.5: Asset value affected by environment temperature in winter.
new and modified constraints as follows.
vt =
8
>><
>>:
0 or 1; if 0 < xt < ton +tover and ot ? Nover;
0; otherwise:
(6.32)
ot+1 = ot +vt (6.33)
ot = 0 if wt = 0 and wt?1 = 1 (6.34)
We then run the algorithm for determining the asset value (T = 1 year)
repeatedly with the value of Nover increased gradually. The capacity value of
the GT vs. Nover is depicted in Fig. 6.6. Apparently, the asset value increases
as Nover increases, since overfiring the GT is a real option that has value. When
the value of Nover reaches 100 hours, the asset value is at a maximum and does
not increase even Nover is further increased. Therefore, Nover = 100 hours can
be viewed as the optimal number of overfire per year. Overfiring the GT less
120
144
145
146
147
148
149
150
151
0 100 200 300 400
Overfire Hour Limit (hours)
Capacity Value (dollars/KW)
Figure 6.6: Capacity value affected by overfire limit.
than 100 hours is equivalent to giving away this option value. On the other
hand, overfiring the unit more than 100 hours is not economical, because the
maintenance costs outweigh the benefit.
6.4.3 Maintenance option value
Note that (6.9) states that maintenance is mandatory if either one of the
two maintenance conditions is met. This equation, however, allows to perform
the maintenance even when any of the two conditions is not met. That is,
the maintenance is an (American style) option. To measure the value of such an
option, we manage to take away the option modify by modifying (6.9) as follows.
wt =
8>
><
>>:
1; if xt = ?tcold and yt ? Nop or zt ? Nstart;
0; otherwise:
(6.35)
In (6.35), a slight modification appears in the second line, which implies that
121
maintenance is performed only when it is required. We then run the algorithm
for determining the asset value (with T = 1 year) and compare it with the
original asset value with the maintenance option. The capacity value of the
GT is 146.7 $/KW without the maintenance option, and was 149.8 $/KW with
the option. That is, approximately 2 percent of capacity value is due to the
maintenance. This shows that maintenance can be part of a profitable strategic
plan to increase the asset value.
6.5 Conclusions
In this chapter, a general valuation framework for thermal units consider-
ing overfire option, maintenance constraints and environment temperature is
developed. The numerical results show that the overfire option can increase
the capacity value (about 3.3% per year) and the maintenance option can also
increase the capacity value (about 2% per year). We also show that the envi-
ronment temperature may affect the asset value, which tends to be decreased in
summer and increased in winter. The proposed model and the numerical results
provide some new insights in the valuation and operation of the GT.
122
Chapter 7
Conclusions and Further Research
Directions
This dissertation advocates that all relative operational options, constraints
and interdependent uncertainties should be considered when a thermal genera-
tion unit is valued in the competitive power market. Failing to do may signif-
icantly overestimate a power plant, which may result in stranded capital for a
long time period.
In Chapter 4, the optimal self scheduling of a thermal unit in an electric-
ity spot market was studied. When the spot prices are known with certainty,
a polynomial-time algorithm based on network graph is proposed for solving
the problem. Using the developed algorithm to evaluate the unit responses in
various price scenarios generated by the LSMC method, we obtain the optimal
commitment and dispatch rule under price uncertainty. The test results indicate
that the ramp constraints impact a thermal unit on its capability of responding
to price uncertainty by reducing its fuel economy, heat-electricity transformation
efficiency, and available generation capacity. The proposed method provides a
way to quantify these effects. Although the ramp-constrained self-scheduling
123
problem can be solved using the proposed two-stage approximation method, to
solve the multi-stage recursive equation directly with ramp constraints remains
very challenging. The major difficulty lies in the ramp constraints. Further
research direction may include new multi-stage recursive formulation and new
techniques for reducing state space.
In Chapter 5, a LSMC approach was proposed to value a power plant with
fuel-switching options. The numerical results show that the LSMC is much more
efficient than lattice model especially when time horizon is long and more than
two uncertainties are involved. Our test shows that the fuel-switching options
may increase the power plant value from 4 to 7% or even higher, depending on
the market condition. This shows that fuel-switching is an important operational
real option in determining the asset value. This, however, has not included the
fact that fuel-switching is also a useful emission abatement means. Although the
initial tests show that the LSMC approach is a useful tool for handling multiple
uncertainties, it remains unclear how a suitable regression functional form is
determined. This problem, however, is not unique to our case, but general to all
regression-based methods.
In Chapter 6, a general valuation framework for thermal units considering
overfire option, maintenance constraints and environment temperature has been
developed. The numerical results show that the overfire option can increase the
capacity value (about 3.3% per year). We also showed that the environment
temperature may affect the asset value, which tends to be decreased in summer
and increased in winter. The proposed model and the numerical results provide
some new insights in the valuation and operation of the GT. Further research
includes development of better temperature and price models.
124
In conclusion, this dissertation contributes a new methodology for fair genera-
tion asset valuation that accounts for multiple and interdependent uncertainties
and complex physical constraints. The proposed research will certainly help
unit operators achieving optimal operation and investors making appropriate
investment decisions. In the long run, customers also benefit from the improved
societal efficiency.
125
REFERENCES
Ajax, R. B. M, K. Rocha, and P. A. David, 2000, ?Effects of new Brazilian elec-
trical power regulatory framework on generation investment?, (www.puc-
rio.br/marco.ind/pdf/generation.pdf).
Allen, E. H., and M. D. Ilic, 1999, Price-Based Commitment Decisions in the
Electricity Market, Springer-Verlag, London.
Amaram, M., and N. Kulatilaka, 1999, Real Options: Managing Strategic
Investments in an Uncertainty World, Harvard Business School Press,
Bostion.
Arroyo, J. M. and A. J. Conejo, 2000, ?Optimal response of a thermal unit to
an electricity spot market,? IEEE Transactions on Power Systems, 15, pp.
1098 -1104.
Baldick, R., S. Kolos, and S. Tompaidis, 2003, ?Valuation and optimal for
interruptible electricity contracts,? working paper, University of Texas.
Baldick, R., 1995, ?The generalized unit commitment problem,? IEEE Trans-
actions on Power Systems, 10, pp. 465-475.
Bard, J. F., 1988, ?Short-term scheduling of thermal-electric generators using
Lagrangian relaxation,? Operations Research, 36, pp. 756-766.
Barlow, M. T., 2002, ?A diffusion model for electricity prices,? Mathematical
Finance, 12, pp. 287-298.
126
Bellman, R. E. and S. E. Dreyfus, 1962, Applied Dynamic Programming, Prince-
ton University Press, Princeton, NJ.
Birge, J. R. and J. M. Mulvey, 1996, ?Stochastic programming,? in Mathemat-
ical Programming for Industrial Engineers, Dekker, M. eds., New York,
NY., pp. 543-574
Birge, J. R., 1985, ?Decomposition and partitioning methods for multi-stage
stochastic linear programs,? Operations Research, 33, pp. 989-1007.
Boyle, P., 1977, ?Options: A Monte Carlo approach,? Journal of Financial
Economics, 4, pp. 323-338.
Breipohl, A.M., and F.N. Lee, 2000, ?Generation adequacy or asset valuation,?
the 33rd Annual Frontiers of Power Conference, Stillwater, OK, USA, 30-
31.
Brennan, M. J. and E. S. Schwartz, 1978, ?Finite difference method and jump
processes arising in the pricing of contingent claims,? Journal of Financial
and Quantitative Analysis, 13, pp. 461-474.
Cao, M., and J. Wei, 2000, ?Pricing the weather: an intuitive and practical
approach,? Risk, pp. 67-70.
Caroe, C. C., A. Ruszczynski, and R. Schultz, 1997, ?Unit commitment under
uncertainty via two-stage stochastic programming,? Proceeding of NOAS
97, UniversityofCopenhagen, (http://www.math.ku.dk/caroe/cccresearch.html).
Carpentier, A. G., G. C. Cohen, and A. R. Culioli, 1996, ?Stochastic optimiza-
tion of unit commitment: a new decomposition framework,? IEEE Trans.
127
on Power Systems, 11(2), pp. 1067-1073.
Carriere, J., 1996, ?Valuation of early-exercise price of options using simulation
and nonparametric regression,? Insurance: Mathematics and Economics,
19, pp. 19-30.
Chandler, W. G., P. L. Dandeno, A. F. Gilmn and L. K. Kirchmayer, 1953,
?Short-range operation of a combined thermal and hydroelectric power
system,? AIEE, Trans. Paper no. 53-326.
Chaton, C., j. A. Doucet, 1999, ?Uncertainty and investment in electricity gen-
eration: thecaseofhydro-Quebec,?(ideas.repec.org/p/lvl/laeccr/9914.html).
Cohen, A. I., and G. Ostrowski, 1996, ?Scheduling units with multiple operation
modes in unit commitment,? IEEE Trans. on Power Systems, 11, pp. 497-
503.
Cohen, A. I., and M. Yoshimura, 1983, ?A branch and bound algorithm for unit
commitment,? IEEE Trans. on Power Apparatus and Systems, 102(2), pp.
444-451.
Cox, J. S., S. Ross, and M. Rubinstein, 1979, ?Option pricing: A simplified
approach,? Journal of Financial Economics, 7, pp. 229-264.
Deng, S.J., B. Johnson, and A. Sogomonian, 1998, ?Exotic electricity options
and the valuation of electricity generation and transmissions,? Presented
at the Chicago Risk Management Conference, Chicago, IL.
Deng, S.J., B. Johnson, and A. Sogomonian, 1999, ?Spark spread options and
the valuation of electricity generation assets,? the 32nd Annual Hawaii
128
International Conference on System Sciences, Maui, HI, USA, 5-8.
Dillon, T. S. and V. R. Sherkat, 1978, ?Integer programming approach to the
problem of optimal unit commitment with probabilistic reserve determina-
tion,? IEEE Trans. Power Apparatus and systems, vol. PAS-97, no.6, pp.
2154-2164.
Dixit, A. K. and R. S. Pindyck, 1994, Investment Under Uncertainty, Prentice
Hall, Englewood Cliffs, NJ.
Edleson, M. E., and F. L. Reinhardt, 1995, ?Investment in pollution compliance
options: the case of Georgia power, Chapter 14 in the book,?in the book
real options in capital investment, edited by Lenos Trigeorgis.
Fine, C. H., and R. M. Freund, 1990, ?Optimal investment in product- flexible
manufacturing capacity,? Management Science, 36(4), pp. 449-466.
Ford, A., 1999, ?Cycles in competitive electricity markets: a simulation study
of the western United States,? Energy Policy, 29, pp. 637-658.
Ferreira, L.A., T.Andersson, C.F.Imparato, C.K.Pang, A.SvobodaandA.F.
Vojdani, 1989, ?Short-term resource scheduling in multi-area hydrothermal
power systems,? Electrical Power & Energy Systems, vol.11, no.3.
Freidenfelds, J., 1981, Capacity expansion: analysis of simple models with ap-
plications, North Holland, New York.
Frayer, J. and N. Z. Uludere, 2001, ?What is it worth? Application of real op-
tions theory to the valuation of generation assets?, The Electricity Journal,
14(8), pp. 40-51.
129
Fu, M. C., and J. Q. Hu, 1995, ?Sensitivity analysis for monte carlo simulation
ofoptionpricing,?Probability in the Engineering and Information Sciences,
9, 417-446.
Galiana, F. D. and M. Ilic, 1998, ?A mathematical framework for the analysis
and management of power transactions under open access,? IEEE Trans-
actions on Power Systems, 13, pp. 681-687.
Garcia, D., 2000, ?A Monte Carlo method for pricing American options,? work-
ing paper, University of California, Berkeley.
Gardner, D. and J. Rogers, 1999, ?Planning electric power systems under de-
mand uncertainty with different technology lead times,? Management Sci-
ence, 45(10), pp. 1289-1306.
Gardner, D. and Y. Zhuang, 2000, ?Valuation of power generation assets: a
real options approach,? ALGO Research Quarterly, 3(3), pp. 9-20.
Gill, P. E., W. Murray, and M. H. Wright, 1981, Practical Optimization, Lon-
don: Academic Press.
Gnansounou, E., A. Sxhmutz and J. Dong, 2003, ?Investment decisions with
flexibility in the liberalized electricity markets: an approach using Real
Options theory,? SAEE Annual Conference, ETH Zurich.
Grant, D., G. Vora and D. Weeks, 1997, ?Path-dependent options: extending
the Monte Carlo simulation approach,? Management Science, 43(11), pp.
1589-1602.
130
Griffes, P., M. Hsu and E. Kahn, 1999, ?Real options, ancillary services and
environmental risks,? in Jamson, R. (ed), The New Power Markets, Cor-
porate Strategies for Risk and Reward, Risk books.
Guan, X., P. B. Luh, H. Yan and J. A. Amalfi, 1992, ?An optimization-based
method for unit commitment,? Electrical Power & Energy Systems, 14, pp.
9-17.
Herath, H. S. and C. S. Park, 2002, ?Multi-stage capital investment opportu-
nities as compound real options,? The Engineering Economist, 47(1), pp.
1-27.
Hlouskova, J., S. Kossmeier, M. Obersteiner and A. Schnabl, 2002, ?Real op-
tion models and electricity portfolio management,? OSCOGEN discussion
paper no. 9.
Hobbs, B., M. Rothkopf, R. O?Neill and H.-P. Chao, 2001, The Next Generation
of Unit Commitment Models, Boston, MA: Kluwer.
Hobbs, W. J., G. Hermon, S. Warner and G. B. Sheble, 1987, ?Dynamic pro-
gramming approach to unit commitment,? IEEE Trans. Power Systems,
2, pp. 339-350.
Hsu, M., 1998, ?Spark spread options are hot!,? The Electricity Journal, 11(2),
pp. 28-39.
Huang, S. J. and C. L. Huang, 1997, ?Application of genetic-based neural
networks to thermal unit commitment,? IEEE Trans. on Power Systems,
12(2), pp. 654-659.
131
Hull, J. and A. White, 1994, ?Numerical procedures for implementing term
structure models II: two-factor models,? Journal of Derivatives, 2(2), pp.
37-48.
Hull, J. C., 1993, Options, Futures, and Other Derivative, 2nd edition, Prentice
Hall, Englewood Cliffs, NJ.
Hull, J. C., 1999, Options, Futures, and Other Derivative, 4th edition, Prentice
Hall, Englewood Cliffs, NJ.
Kazarlis, S. A., A. G. Bakirtzis, V. Petridis, 1996, ?A genetic algorithm solution
to the unit commitment problem,? IEEE Trans. on Power Systems, 11(1),
pp. 83-92.
Kojima, M., S. Mizuno and A. Yoshise, 1987, ?A polynomial time algorithm for
a class of linear complementarity problems. Research report,? Department
of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan.
Kulatilaka, N., 1993, ?The value of flexibility: the case of a dual-fuel industrial
steam boiler,? Financial Management, 22(3), pp. 271-279.
Kulatilaka, N., 1995, ?Operating flexibilities in capital budgeting: Substi-
tutability and complementarity in real options,? in Real Options in Cap-
ital Investment: Models, Strategies, and Application, Trigeorgis, L. eds.,
Praeger, New York, NY.
Kumar, R. L., 1995, ?An options view of investments in expansion-flexible
manufacturing systems,? International Journal of Production Economies,
38(2-3), pp. 281-291.
132
Lai, S. Y., and R. Baldick, 1999, ?Unit commitment with ramp multipliers,?
IEEE Trans. Power Systems, 14, pp. 58-64.
Lee, F. N., L. Lemonidis and K. C. Liu, 1994, ?Price-based ramp-rate model
for dynamic dispatch and unit commitment,? IEEE Transactions on Power
Systems, 9(3), pp. 1233-1242.
Lee, F. N., 1988, ?Short-term unit commitment: a new method,? IEEE Trans.
Power Systems, 3(2), pp. 421-428.
Longstaff, F. A. and E. S. Schwartz, 2001, ?Valuing American options by simu-
lation: A simple lease-squares approach,? The Review of Financial Studies,
14(1), pp. 113-147.
Louveaux, F. V., 1980, ?A solution method for multistage stochastic programs
with recourse with application to an energy investment problem,? Opera-
tions Research, 28, pp. 892-902.
Louveaux, F. V. and Y. Smeers 1988, ?Optimal investments for electricity gen-
eration: a stochastic model and a test-problem,? Numerical Techniques
for Stochastic Programming, Y. Ermovliev and R J-B. Wets eds., Springer,
Berlin.
Luenberger, D. G., 1998, Investment Science, Oxford, New York, NY.
Majd,S. and R.S. Pindyck, 1987, ?Time to build, option value, and investment
decisions,? Journal of Financial Economics, 18(1), pp. 7-27.
McClanahan, R.H., 2002, ?Electric deregulation?, IEEE Industry Applications
Magazine, 8(2), p. 11-18.
133
Min, K.J. and C. Wang, 2000, ?Generation planning for inter-related generation
units: a real options approach?, IEEE Power Engineering Society Summer
Meeting, 4, p. 2261-2265.
Monteiro, R. D. C. and I. Adler, 1989, ?Interior path following primal-dual
algorithms-Part II: Convex quadratic programming,? Mathematical Pro-
gramming, 44, pp. 43-66.
Murty, K. G., 1992, Network Programming, New Jersey: Prentice Hall.
Myers, S. C., 1996,?Fischer Black?s contribution to corporate finance,? Finan-
cial Management, 25(4), pp.95-100.
Papadimitriou, C. H. and K. Steiglitz, 1982, Combinatorial optimization: algo-
rithms and complexity, Prentice-Hall, Englewood Cliff, New Jersey.
Park, C. S. and H. S. B. Herath, 1999, ?Exploiting uncertainty-investment
opportunities as real options: A new way of thinking in engineering eco-
nomics,? The Engineering Economist, 45(1), pp. 1-36.
Peterson, W. L., and S. Brammer, 1995, ?A capacity based lagrangian relax-
ation unit commitment with ramp rate constraints?. IEEE Transactions
on Power Systems, 10(2), pp. 1077-1084.
Pereira, M. V. F. and L. M. V. G. Pinto, 1985, ?Stochastic optimization of a
multi-reservoir hydroelectric system?A decomposition approach,? Water
Resources Research, 21, pp. 779-792.
Pereira, M. V. F. and L. M. V. G. Pinto, 1999, ?Planning risks,? IEEE PICA
Tutorial.
134
Rendleman, R. J. and B. J. Barter, 1979, ?Two state option pricing,? Journal
of Finance, 34, pp. 1092-1110.
Schwartz, E. S., 1977, ?The valuation of warrants: implementing a new ap-
proach?. Journal of Finance Economics, 4, pp. 79-93.
Shahidehpour, M., and M. Marwali, 2000, Maintenance schedule in restructured
power systems, Kluwar Academic Publishers Norvell, Massachusetts.
Sharpe, W. F., 1978, Investment, Prentice Hall, Englewood Cliffs, NJ.
Sheble, G. B. and G. N. Fahd, 1994, ?Unit commitment literature synopsis,?
IEEE Transactions on Power Systems, 9, pp. 128-135.
Svoboda, A. J., C. L. Tseng, C. A. Li, R. B. Johnson, 1997, ?Short term
resource scheduling with ramp constraints,? IEEE Transactions on Power
Systems, 12, pp. 77-83.
Takriti, S., B. Krasenbrink, and L. Wu, 1996, ?A stochastic model for the
unit commitment problem,? IEEE Trans. on Power Systems, 11(3), pp.
1497-1508.
Takriti, S., B. Krasenbrink, and L. Wu, 2000, ?Incorporating fuel constraints
and electricity spot prices into the stochastic unit commitment problem,?
Operations Research, 48, pp. 268-280.
Thompson, M., M. Davision, and H. Rasmussen, 2004, ?Real options valuation
and optimal operations of electrical power plants in competitive markets,?
Operations Research, forthcoming.
135
Trigeorgis, L. and S. P. Mason, 1987, ?Valuing managerial flexibility,? Midland
Corporate Financial Journal, 5(1), pp. 14-21.
Trigeorgis, L., 1991, ?A log-transformed binomial numerical analysis method
for valuing complex multi-option investment,? Journal of Financial and
Quantitative Analysis, 26(3), pp. 309-326.
Trigeorgis, L., 1993, ?The nature of option interactions and the valuation of
investments with multiple real options,? Journal of Financial and Quan-
titative Analysis, 28(1), pp. 1-20.
Trigeorgis, L., 1996, Real Options: Managerial Flexibility and Strategy in Re-
source Allocation, the MIT Press, Cambridge, MA.
Tseng, C. L., 1996, On power system generation unit commitment problems.
Ph.D. Dissertation, Department of Industry Engineering and Operations
Research, University of California at Berkeley.
Tseng, C. L., G. Barz, 1999, ?Short-term generation asset valuation,? Presented
at the 32nd Hawaii International Conference on System Sciences, Maui,
Hawaii.
Tseng, C. L., G. Barz, 2002, ?Short-term generation asset valuation: a real
options approach,? Operations Research, 50, pp. 297-310.
Tseng, C. L., K. Y. Lin, 2004, ?A framework using two-factor price lattices for
generation asset valuation? (accepted by Operations Reseearch).
Tseng, C. L., 2000, ?Exercising real unit operational options under price un-
certainty,? IEEE Power Engineering Society Winter Meeting, Conference
136
Proceedings, pp. 436-40 vol.1, Piscataway, NJ, USA.
Tseng, C. L., 2001, ?A stochastic model for the price-based unit commitment
problem and its application to short-term generation asset valuation,? The
Next Generation of Electric Power Unit Commitment Models. Kluwer Aca-
demic Publisher, Boston, B. Hobbs, M. Rothkopf, R. O?Neill and H. Chao,
eds., 117-138.
Tsitsiklis, J., and B. Van Roy, 1999, ?Optimal stopping of Markov processes:
Hilbert space theory, approximation algorithms, and an application to pric-
ing high-dimensional financial derivatives,? IEEE Transactions on Auto-
matic Control, 44, pp. 1840-1851.
Valenzuela, J., M. Mazumadar and A. Kapoor, 2000, ?Influence of temperature
and load forecast uncertainty on estimates of power generation production
costs,? IEEE Trans. on Power Systems, 15, pp. 668-674.
Van Roy, B. and J. N. Tsitsiklis, 2001, ?Regression methods for pricing complex
American-styleoptions,? IEEE Transaction on Neural Networks, 12(4), pp.
694-703.
Wang, C., and S. M. Shahidehpour, 1993, ?Effects of ramp-rate limits on unit
commitment and economic dispatch?. IEEE Transactions on Power Sys-
tems, 8(3), pp. 1539-1545.
Wang, C., and S. M. Shahidehpour, 1994, ?Ramp-rate limits in unit commit-
ment and economic dispatch incorporating rotor fatigue effect?. IEEE
Transactions on Power Systems, 9(3), pp. 1539-1545.
137
Wagner, H., 1975, Principles of operations research, 2nd edition, Englewood
Cliffs, NJ:Prentice-Hull.
Wood, A. J., and B. F. Wollenberg, 1984, Power generation, operation and
control, John Wiley, New York.
Wood, A. J., and B. F. Wollenberg, 1996, Power generation, operation and
control, 2nd edition, John Wiley, New York.
Wu, R. W., 2002, ?Applications of Monte Carlo simulation in derivative securi-
ties pricing,? Ph.D. Dissertation, Business School, University of Maryland
at College Park.
Zhai, D., W. Snyder, J. Waight, J. Farah, A. Gonzalez and P. Vallejo, 2001,
?Fuel constrained unit commitment with fuel mixing and allocation,? IEEE
Trans. on Power Systems, 11, pp. 11-16.
Zhuang, F. and F. D. Galiana, 1988, ?Towards a more rigorous and practi-
cal unit commitment by Lagrangian relaxation,? IEEE Trans. on Power
Systems, vol. PWRS-3, no. 2, pp. 763-770.
138