THE NEXT GENERATION OF ELECTRIC POWER UNIT COMMITMENT MODELS
INTERNATIONAL SERIES IN OPERATIONS RESEARCH & MANAGEMENT...
128 downloads
419 Views
11MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
THE NEXT GENERATION OF ELECTRIC POWER UNIT COMMITMENT MODELS
INTERNATIONAL SERIES IN OPERATIONS RESEARCH & MANAGEMENT SCIENCE Frederick S. Hillier, Series Editor Stanford University Saigal, R. / LINEAR PROGRAMMING: A Modern Integrated Analysis Nagurney, A. & Zhang, D. / PROJECTED DYNAMICAL SYSTEMS AND VARIATIONAL INEQUALITIES WITH APPLICATIONS Padberg, M. & Rijal, M. / LOCATION, SCHEDULING, DESIGN AND INTEGER PROGRAMMING Vanderbei, R. / LINEAR PROGRAMMING: Foundations and Extensions Jaiswal, N.K. / MILITARY OPERATIONS RESEARCH: Quantitative Decision Making Gal, T. & Greenberg, H. / ADVANCES IN SENSITIVITY ANALYSIS AND PARAMETRIC PROGRAMMING Prabhu, N.U. / FOUNDATIONS OF QUEUEING THEORY Fang, S.-C., Rajasekera, J.R. & Tsao, H.-S.J. / ENTROPY OPTIMIZATION AND MATHEMATICAL PROGRAMMING Yu, G. / OPERATIONS RESEARCH IN THE AIRLINE INDUSTRY Ho, T.-H. & Tang, C. S. / PRODUCT VARIETY MANAGEMENT El-Taha, M. & Stidham , S. / SAMPLE-PATH ANALYSIS OF QUEUEING SYSTEMS Miettinen, K. M. / NONLINEAR MULTIOBJECTIVE OPTIMIZATION Chao, H. & Huntington, H. G. / DESIGNING COMPETITIVE ELECTRICITY MARKETS Weglarz, J. / PROJECT SCHEDULING: Recent Models, Algorithms & Applications Sahin, I. & Polatoglu, H. / QUALITY, WARRANTY AND PREVENTIVE MAINTENANCE Tavares, L. V. / ADVANCED MODELS FOR PROJECT MANAGEMENT Tayur, S., Ganeshan, R. & Magazine, M. / QUANTITATIVE MODELING FOR SUPPLY CHAIN MANAGEMENT Weyant, J./ ENERGY AND ENVIRONMENTAL POLICY MODELING Shanthikumar, J.G. & Sumita, U./APPLIED PROBABILITY AND STOCHASTIC PROCESSES Liu, B. & Esogbue, A.O. / DECISION CRITERIA AND OPTIMAL INVENTORY PROCESSES Gal, T., Stewart, T.J., Hanne, T./ MULTICRITERIA DECISION MAKING: Advances in MCDM Models, Algorithms, Theory, and Applications Fox, B. L./ STRATEGIES FOR QUASI-MONTE CARLO Hall, R.W. / HANDBOOK OF TRANSPORTATION SCIENCE Grassman, W.K./ COMPUTATIONAL PROBABILITY Pomerol, J-C. & Barba-Romero, S. / MULT1CRITERION DECISION IN MANAGEMENT Axsäter, S. / INVENTORY CONTROL Wolkowicz, H., Saigal, R., Vandenberghe, L./ HANDBOOK OF SEMI-DEFINITE PROGRAMMING: Theory, Algorithms, and Applications Hobbs, B. F. & Meier, P. / ENERGY DECISIONS AND THE ENVIRONMENT: A Guide to the Use of Multicriteria Methods Dar-El, E./ HUMAN LEARNING: From Learning Curves to Learning Organizations Armstrong, J. S./ PRINCIPLES OF FORECASTING: A Handbook for Researchers and Practitioners Balsamo, S., Personé, V., Onvural, R./ ANALYSIS OF QUEUEING NETWORKS WITH BLOCKING Bouyssou, D. et al/ EVALUATION AND DECISION MODELS: A Critical Perspective Hanne, T./ INTELLIGENT STRATEGIES FOR META MULTIPLE CRITERIA DECISION MAKING Saaty, T. & Vargas, L./ MODELS, METHODS, CONCEPTS & APPLICATIONS OF THE ANALYTIC HIERARCHY PROCESS Chatterjee, K. & Samuelson, W./ GAME THEORY AND BUSINESS APPLICATIONS
THE NEXT GENERATION OF ELECTRIC POWER UNIT COMMITMENT MODELS
Editors Benjamin F. Hobbs The Johns Hopkins University Michael H. Rothkopf Rutgers University Richard P. O’Neill Federal Energy Regulatory Commission
Hung-po Chao Electric Power Research Institute
KLUWER ACADEMIC PUBLISHERS NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: Print ISBN:
0-306-47663-0 0-7923-7334-0
©2002 Kluwer Academic Publishers New York, Boston, Dordrecht, London, Moscow Print ©2001 Kluwer Academic Publishers Dordrecht All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America Visit Kluwer Online at: and Kluwer's eBookstore at:
http://kluweronline.com http://ebooks.kluweronline.com
CONTENTS Acknowledgments
vii
I. The Evolving Context for Unit Commitment Decisions
1. Why This Book?: New Capabilities and New Needs for Unit Commitment Modeling B. F. Hobbs, W. R. Stewart Jr., R. E. Bixby, M. H. Rothkopf, R. P. O'Neill, H.-p. Chao
1
2. Regulatory Evolution, Market Design and Unit Commitment R. P. O'Neill, U. Helman, P. M. Sotkiewicz, M. H. Rothkopf, W. R. Stewart Jr.
15
3. Development of an Electric Energy Market Simulator A. Debs, C. Hansen, Y.-C. Wu
39
II. New Features in Unit Commitment Models 4. Auctions with Explicit Demand-Side Bidding in Competitive Electricity Markets A. Borghetti, G. Gross, C. A. Nucci
53
5. Thermal Unit Commitment with a Nonlinear AC Power Flow Network Model C. E. Murillo-Sánchez, R. J. Thomas
75
6. Optimal Self-Commitment under Uncertain Energy and Reserve Prices R. Rajaraman, L. Kirsch, F. L. Alvarado, C. Clark
93
7. A Stochastic Model for a Price-Based Unit Commitment Problem and Its Application to Short-Term Generation Asset Valuation C.-L. Tseng
117
8. Probabilistic Unit Commitment under a Deregulated Market J. Valenzuela, M. Mazumdar
139
III. Algorithmic Advances
9. Solving Hard Mixed-Integer Programs for Electricity Generation S. Ceria
153
vi
The Next Generation of Unit Commitment Models
10. An Interior-Point/Cutting-Plane Algorithm to Solve the Dual Unit Commitment Problem -- On Dual Variables, Duality Gap, and Cost Recovery M. Madrigal, V. H. Quintana
167
11. Building and Evaluating Genco Bidding Strategies and Unit Commitment Schedules with Genetic Algorithms C. W. Richter, Jr., G. B. Sheblé
185
12. An Equivalencing Technique for Solving the Large-Scale Thermal Unit Commitment Problem S. Sen, D.P. Kothari
211
IV. Decentralized Decision Making 13. Strategic Unit Commitment for Generation in Deregulated Electricity Markets A. Baíllo, M. Ventosa, A. Ramos, M. Rivier, A. Canseco
227
14. Optimization-Based Bidding Strategies for Deregulated Electric Power Markets X. Guan, E. Ni, P. B. Luh, Y.-C. Ho
249
15. Decentralized Nodal-Price Self-Dispatch and Unit Commitment F. D. Galiana. A. L. Motto, A. J. Conejo, M. Huneault
271
16. Decentralized Unit Commitment in Competitive Energy Markets J. Xu, R. D. Christie
293
Index
317
ACKNOWLEDGMENTS This volume contains papers that were presented at a workshop entitled "The Next Generation of Unit Commitment Models", held September 2728, 1999 at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), Rutgers University, Piscataway, NJ. The editors gratefully acknowledge the financial support of the co-sponsors of the workshop: DIMACS (funded by the National Science Foundation under grant NSF STC 91-19999); and the Electric Power Research Institute (EPRI), which supported the publication and distribution of this book. The editors also thank Sarah Donnelly of DIMACS for her organizational support of the workshop and the subsequent book. The editors would also like the many speakers and other participants of the workshop for their ideas and hard work. All the papers were subjected to anonymous peer review by at least two referees and two editors. The referees included authors of other papers in this volume, along with Paul Sotkiewicz and Judith Cardell of the Office of Economic Policy of the Federal Energy Regulatory Commission. Technical editing for the volume was ably provided by Debi Rager of The White Cottage Company. Liz Austin of Johns Hopkins Unviersity compiled the index. Funding for B. Hobbs' involvement in the workshop and book came from NSF Grants ECS 96-96014 and 00-80577. Partial support for M. Rothkopf was provided by NSF grant SBR 97-09861.
This page intentionally left blank
Chapter 1 WHY THIS BOOK? NEW CAPABILITIES AND NEW NEEDS FOR UNIT COMMITMENT MODELING Benjamin F. Hobbs The Johns Hopkins University
William R. Stewart Jr. The College of William & Mary
Robert E. Bixby Rice University and ILOG
Michael H. Rothkopf Rutgers University
Richard P. O'Neill Federal Energy Regulatory Commission
Hung-po Chao Electric Power Research Institute
Abstract:
This book presents recent developments in the functionality of generation unit commitment (UC) models and algorithms for solving those models. These developments, the subject of a September 1999 workshop, are driven by institutional changes that increase the importance of efficient and market responsive operation. We illustrate these developments by demonstrating the use of mixed integer programming (MIP) to solve a UC problem. The dramatically lower solution times of modem MIP software indicates that it is now a practical algorithm for UC. Participants in the workshop also prioritized the features that need to be considered by UC models, along with topics for research and development. Among the highest research priorities are: market simulation; bid selection; reliability and reserve constraints; and fair processes for choosing from alternative near-optimal solutions. The chapter closes with an overview of the contributions of the other chapters.
2
1.
The Next Generation of Unit Commitment Models
PURPOSE OF THE BOOK
The unit commitment problem can be defined as the scheduling of production of electric power generating units over a daily to weekly time horizon in order to accomplish some objective. The problem solution must respect both generator constraints (such as ramp rate limits and minimum up or down times) and system constraints (reserve and energy requirements and, potentially, transmission constraints). The objective function should account for costs associated with energy production, ramping, start-ups and shutdowns decisions, along with possible effects upon revenues or customer costs of those decisions. The resulting problem is a large scale nonlinear mixed integer program. For many years, the electric power industry has been using optimization methods to help them solve the unit commitment problem. The result has been savings of tens and perhaps hundreds of millions of dollars in fuel costs. Things are changing, however. Optimization technology is improving, and the industry is undergoing radical restructuring. Consequently, the role of commitment models is changing, and the value of the improved solutions that better algorithms might yield is increasing. The purpose of this book is to explore the technology and needs of the next generation of computer models for aiding unit commitment decisions. Because of the unit commitment problem's size and complexity and because of the large economic benefits that could result from its improved solution, considerable attention has been devoted to algorithm development [1,2]. Heuristics such as priority lists have long been used by industry; but in the last three decades, more systematic procedures based on a variety of algorithms have been proposed and tested. These techniques have include dynamic programming, branch-and-bound mixed integer programming (MIP), linear and network programming approaches, and Benders decomposition methods, among others. Recently, metaheuristic methods have been tested, such as genetic programming and simulated annealing, along with expert systems and neural networks. The solution approach that has been most successful, and which is most widely used at present, is Lagrangian relaxation. This procedure decomposes the problem by multiplying constraints that couple different generators (such as energy demand and reserve constraints) by Lagrange multipliers and placing them in the objective function. Given a set of multiplier values, the problem is then separable in the generating units, and a dynamic program of low dimension can be used to obtain a trial schedule for each unit. A process of multiplier adjustment is used to search for feasible near-optimal solutions. Lagrangian relaxation has proven useful for quick development of good, if not optimal, generator schedules. Recent improvements in integer pro-
Introduction
3
gramming codes and other algorithms suggest, however, that it may be possible to find better solutions more rapidly. Further, such codes can more readily incorporate additional coupling constraints, such as transmission limits and emissions caps. Meanwhile, restructuring has sharpened the appetite of generation owners for more efficient operation. In the past, utilities sold power on a regulated cost-plus basis and so may not have put as much priority on squeezing out the last few percent improvements in the objective function. Furthermore, system operators realized that cost functions were approximate, so the operators were perhaps more likely to be satisfied with good solutions or marginal improvements that were technically suboptimal. Now, with restructuring, we have schedule coordinators making commitment decisions in a market environment, and independent system operators (ISOs) dealing with bids. Bids are precise, and small improvements in solutions can result in significant changes in payments to bidders. Further, the fact that optimization models are, in some cases, being used to determine which generators will be operated and thus paid implies that there is a greater incentive to get exact answers to make the bidding process fair and legitimate (and to disempower the bid-taker). In other words, electric markets are changing rapidly, as is the role of unit commitment models. How UC models are solved and what purposes they serve deserve reconsideration. The goal of the workshop that led to this book was to bring together people who understand the problem and people who know what improvements in algorithms are really possible. The papers in this book summarize the participants' assessments of industry needs together with new formulations and computational approaches that promise to make unit commitment models more responsive to those needs. In Section 2 of this chapter, we present an example to show how the capabilities of commercially available integer programming software to solve large unit commitment problems to optimality have dramatically improved in recent years. This example illustrates how improvements in software may make it possible to solve bigger problems in less time, while simultaneously including more of the complications that users want to represent. Section 3 then summarizes the results of a survey of workshop participants in which they were asked to identify what issues concerning unit commitment modeling are most in need of further research and development. Finally, in Section 4 we give an overview of the other chapters in this book. There, we describe how the papers contribute to our two goals of articulating the emerging needs of the restructured power industry and describing model developments that can make unit commitment models more responsive to those needs.
4
2.
The Next Generation of Unit Commitment Models
EXAMPLE OF NEW CAPABILITIES: SOLVING UNIT COMMITMENT PROBLEMS USING MIP
When formulated as a mixed integer program (MIP), the unit commitment (UC) problem is a large and complex mathematical programming problem. As a result, optimal solutions have been hard to obtain for practically sized problems due to the exponential behavior of solution times as problems grow larger. As a result, exact solutions to large UC problems have been unavailable, and approximate techniques are employed to produce solutions that are near optimal (within 0.5%-2%). In practice, Lagrangian relaxation methods have performed well, but the non-convexity and overall size of most practical problems have prevented solving such problems to optimality or even providing a bound on the optimal solution. Approximate solutions have two problems. First, since an approximate solution will be dispatching units that are slightly more costly than the ones that would have been dispatched had an optimal solution been available, the approximate solution almost certainly will be inefficient economically and a deserving facility may have been passed over by the approximate solution. The second, related problem consists of the political implications of passing over cost-effective units in a world in which generating units are owned by different competing entities, as opposed to the historical situation where all generation was centrally owned by a single, large regulated utility. The purpose of this section is to report on how the technology for solving MIPs to optimality (branch-and-bound, cutting planes, etc.) has improved computational times in the past several years, and the implications of those improvements for solving UC problems. Historically, MIPs have been notoriously difficult to solve due to the presence of multiple near-optimal solutions such as would occur when a system contained several generators with similar operating characteristics and costs. Traditional branch-andbound techniques would have to find all of these optimal solutions explicitly before an optimal solution could be verified. For this reason and because of the many near-optimal solutions in a typical large MIP, solution times grow very quickly with the size of the problem because of the large number of nodes in the branch-and-bound tree that must be fathomed. However, a number of theoretical improvements have been incorporated into commercial MIP codes, and further improvements are anticipated. Consequently, these codes can now solve to optimality problems thought impossible just a few years ago. As a concrete example of these improvements, we summarize the results of applying several recent generations of a widely used MIP code, CPLEX®, to a test problem. The problem comes from a paper by Johnson et al. [3]. It requires the scheduling of 17 generators to meet electricity demand over a
Introduction
5
seven-day (168-hour) period. The generators have different operating characteristics and the resulting MIP contains 25,755 variables (including 2,856 integer variables) and 48,939 constraints. While this may be a small problem by unit commitment standards, until recently it would have been considered intractable for direct solution by commercial MIP solvers using a linear programming/branch-and-bound/cutting plane technology. Recent advances have substantially accelerated these approaches, however; as a result, solution times for problems such as the one below are approaching the range where the MIP approach can be considered viable. Test UC Mixed Integer Linear Program: Minimize subject to:
where: is the MW of energy produced by generator i in period t, is a binary variable that is 1 if generator i is dispatched during t, is 1 if generator i is started at the beginning of period t, is 1 if generator i is shut down at the beginning of period t, is the MW of spinning reserves available from generator i in t, and are the fixed cost of operating ($/period), the cost of generation ($/MW/period), and the cost of start-ups ($), respectively, for generator i during t, and are the minimum and maximum MW capacities of plant i, and its maximum reserve contribution, respectively, and
6
The Next Generation of Unit Commitment Models and are the maximum ramp rates (in MW/period) for increasing and decreasing output, respectively, from unit i.
The seven-day MIP problem is non-convex, with one integer variable for each generator for each hour of the week. The rest of the variables are continuous. In addition to the formulation as shown in (1)-(10), the objective function coefficients for some of the generators grow with output level. These are approximated by piecewise linear cost functions. There is also a set of constraints not shown in (1)-(10) that controls for the minimum number of periods a generator can be up and running and the minimum number of periods that a generator must be shut down. The objective of UC is to choose a set of generators and operating levels so as to minimize the total cost of the dispatch (1) subject to meeting hourly demand (2), having sufficient spinning reserves (3) (arbitrarily set to 3% of demand in this problem), generation at each operating unit at or above its minimum run level and below its maximum output level (4)-(5), and spinning reserves below the maximum level for each generator (6). Constraints (7)-(8) force hour-to-hour changes in generation to respect ramp rate limits. Constraint (9) requires that a generator be started if it was not dispatched the previous period and will be this period, while (10) mandates that a unit be shut down this period if it is was dispatched the previous period and will not be used this period. The results for solving two related test problems are reported in Tables 1 and 2. The first problem is a one-day (24 time periods) problem and the other is the full seven-day problem. The one-day problem has one-seventh the number of continuous variables, discrete variables, and constraints that the week-long problem has. The main computational comparison is how the solution times for these problems improve as they are solved by later versions of a specific solver (CPLEX). In addition, we show the number of times a linear program is solved in the branch-and-bound portion of the algorithm (number of nodes).
Introduction
7
The marked improvement in times seen in Version 6.5 (Table 1) can be attributed to several factors: the inclusion of cutting planes eliminates a lot of extraneous fractional solutions that were previously explicitly considered; later versions of the dual simplex algorithm in CPLEX just solve the linear program faster (a couple of orders of magnitude faster on the seven day problem, see below); and the inclusion of pre-solve reductions substantially tightens the problem before branch-and-cut starts. The improvement of times from CPLEX 6.0 to CPLEX 6.5 of about an order of magnitude gives promise that this approach can be useful for solving UCPs in the future. The seven-day (168 time periods) problem was unsolvable in a reasonable amount of time in CPLEX 4.0; indeed, it took an hour just to get a solution to the linear programming relaxation. Yet, as Table 2 shows, that problem was solved in less than two hours using CPLEX 6.5 and under 30 minutes using a developmental version of CPLEX on a 500 MHz DEC Alpha. These results show that innovations in algorithms and their implementations will continue to have a strong impact on solution times for MIPs and that realistic unit commitment problems can be solved to optimality by off-theshelf software.
3.
NEW NEEDS: RESEARCH PRIORITIES
The potential of improved algorithms was one important focus of the workshop. The other was the functionality of unit commitment models. The workshop attendees participated in an afternoon meeting to evaluate the functions that unit commitment models should perform in restructured markets. The meeting was structured as a nominal group [4] to maximize the efficiency of information exchange and to ensure that all forty or so participants had a chance to voice their ideas. The steps of a nominal group exercise are as follows: participants silently write down ideas in response to one or more questions; the ideas are posted without attribution; the ideas are discussed in round robin fashion; and participants numerically rate the ideas either at the meeting or in a questionnaire after the meeting. The workshop participants performed the following tasks:
8
The Next Generation of Unit Commitment Models Identify features, characteristics, or requirements of system operation and bidding that are desirable to include in unit commitment models, and issues involved in representing these issues in those models. Describe the extent to which additional research is needed to incorporate those features in unit commitment models. This was done by grouping the features into three categories: I This feature/characteristic/requirement is modeled by existing models and software; II Models have been proposed for capturing this feature/ characteristic/requirement, but require development and implementation; and III There remain fundamental disputes or uncertainties as to how this feature/characteristic/requirement should be modeled. In this case, fundamental research is needed. Rate the importance of including each feature/characteristic/requirement on the following Likert scale: 1 Minor importance 3 Somewhat important 5 Very important 7 Crucial
Approximately 40 of the workshop attendees addressed the first two tasks during the afternoon session. Eighteen participants returned the follow-up questionnaire on importance rating. The latter group included nine industry representatives (primarily consultants, but also including generating company and EPRI representatives); eight university researchers; and a regulator. From the results of these tasks, a set of research priorities can be distilled. The following two tables summarize the results. Table 3 ranks the features by the mean importance rating given by the group, while Table 4 categorizes them in terms of whether further research is needed. Where participants disagreed concerning the category, a range is shown. Table 3 indicates near unanimity concerning the crucial importance of including the commodities of energy and ancillary services along with dynamic constraints and decision sequencing. The next most important issue was market prediction, interpreted as the projection of prices, and how the market might respond to alternative bidding strategies. Some importance ratings were mildly surprising. In particular, transmission issues were rated relatively low. It would seem that research on transmission is
Introduction
9
10
The Next Generation of Unit Commitment Models
Introduction
11
not a high priority with this group, as inclusion of AC representations fell in category II and received a moderate importance rating, while DC approximations were in I and received one of the lowest average importance ratings. Other features that received low ratings included distributed
12
The Next Generation of Unit Commitment Models
generation; emissions modeling; and particular stochastic methods for modeling reliability, uncertainty, and variability. Table 4 reveals that the group unanimously identified 11 features as requiring fundamental research (category III), of which nine received average importance ratings of 4.0 or more. These features are extremely diverse, ranging from risk and reliability modeling to strategic bidding, new product valuation, and dealing with the fairness and institutional implications of multiple near-optimal solutions. Another six features were thought by some but not all group members to be in category III and so are identified as being in category “II-III.” Several facets of market prediction were highly rated in that category. These facets include price prediction, bidding strategy assessment, and inclusion of priceresponsive demand. Meanwhile, in the “requires development” category (II), there are two very important topics: inclusion of ancillary services in unit commitment models and explicit accounting for the sequential nature of decisions (such as multi-settlement systems). Research of a more applied nature would seem to be justified in these cases.
4.
BOOK OVERVIEW
The chapters of this book are grouped into four sections. The first section includes this introduction and two other chapters that summarize the evolving institutional context that has motivated the functional and algorithmic developments described in the rest of the book. O'Neill, Helman, Sotkiewicz, Rothkopf, and Stewart (Chapter 2) review the recent history of short-term electricity markets in the U.S., focussing on alternative market designs and the implications for unit commitment modeling. They also suggest some principles for designing the next generation of UC market models. An alternative approach to presenting the evolving context of unit commitment is presented in Chapter 3. There, Debs, Hansen, and Wu present a general modeling framework that encompasses all the functions of short-term energy markets, including commitment, with a focus on whether the market participant is an ISO/RTO, generating company, market administrator, load serving entity, or even an energy service company. The other three sections of the book describe novel applications and features in UC models, new algorithms for solving those models, and modeling approaches that represent decentralized commitment by independent generating firms. Chapter 4 is the first chapter in the second section; there, Borghetti, Gross, and Nucci show how demand-side bidding can be included in Lagrangian-relaxation-based unit commitment models, and how such bidding can dampen price volatility and mitigate market power. Their formula-
Introduction
13
tion represents load recovery, hour-by-hour bids for demand reduction, and multiple bidders. Chapter 5 by Murillo-Sanchez and Thomas is the second chapter on new model features. They describe how a nonlinear AC power flow representation can be incorporated, with both active and reactive power sources. They also discuss a parallel processing implementation. The last three chapters of the second section concern the inclusion of price uncertainty in UC models. All use variations of a stochastic dynamic programming-based commitment model; when generators cannot individually influence price, the models neatly decompose into a single optimization model for each generator representing their self-commitment problem. In Chapter 6, Rajaraman, Kirsch, Alvarado, and Clark describe how uncertainties in both reserve and energy prices can be considered in such models. In Chapter 7, Tseng shows how such models can be used to quantify rigorously the worth of operating flexibility (“option value”) for a single generating asset. Finally, in Chapter 8, Valenzuela and Mazumdar present a model for single generator optimization that uses probability distributions of market prices directly derived from assumptions concerning demand variability and generator availability in the whole market. In the third section of the book, we turn our attention to improved algorithms for solving the UC problem. Four distinct approaches are represented in this section: mixed integer programming, Lagrangian relaxation, genetic algorithms, and aggregation approaches. Chapter 9 by Ceria, like Section 3 of this introduction, addresses the usefulness of MIP for UC, along with recent developments in MIP technology that have drastically improved solution times. He also briefly reviews two actual applications by utilities in Europe. Chapter 10, authored by Madrigal and Quintana, proposes an interior-point/cutting-plane algorithm to solve the Lagrangian relaxation problem and demonstrates its computational advantages over subgradient and other methods traditionally used to update Lagrange multipliers. They also offer some observations on several issues involved in using UC models to clear power markets, including duality gaps, cost recovery, and the existence of multiple solutions. Chapter 11, contributed by Richter and Sheble, reviews a range of considerations involved in creating bidding and commitment strategies. They then propose genetic algorithms and finite state automata-based simulations for strategy development and testing. Chapter 12 by Sen and Kothari shows how aggregation of generating units into a few sets of similar units can be exploited to improve solution times. The algorithm involves three basic steps: aggregation; solution of the simplified UC problem using dynamic programming or another optimization method; and disaggregation to create schedules for individual units.
14
The Next Generation of Unit Commitment Models
The fourth and final section of the book contains four chapters that address modeling and algorithmic issues associated with decentralized commitment decision processes. Important questions include opportunities for strategic manipulation of prices by market participants, coordination algorithms, and the ability of decentralized processes to approach optimality. The first two chapters of the fourth section focus on decision-making by individual firms. Baillo, Ventosa, Ramos, Rivier, and Canseco devote Chapter 13 to a model for committing a firm’s units while recognizing how commitment and dispatch decisions may affect market prices. Rival firms are assumed to behave according to price-elastic supply functions, which allows for derivation of total firm revenue as a function of its output. They use MIP to solve their model. In Chapter 14, Guan, Ni, Luh, and Ho describe two general approaches to bid development in decentralized markets. One is based on “ordinal optimization” for obtaining satisficing bidding strategies, and a second uses stochastic optimization to self-schedule and manage risks while considering interactions among different markets. The last two chapters of the fourth section turn to the issue of coordination of decentralized decisions. Galiana, Motto, Conejo, and Huneault (Chapter 15) propose a coordination process in which locational prices are announced, generating firms self-dispatch to maximize their individual profits, and prices are adjusted to ensure that demands and network constraints are satisfied. The authors use a Newton algorithm to update prices, and impose a “convexifying rule” to facilitate convergence. Case studies illustrate the process. In Chapter 16, Xu and Christie consider the interactions of strategic behavior by individual generating firms with a price-based coordinating mechanism. Firms optimize bidding strategies with the help of a simple price prediction model. The combined effects of multiple firms using that approach is explored with a market simulator, which reveals that convergence, feasibility, and price stability can be difficult to achieve, but that price cycling can be dampened with alternative price prediction models.
REFERENCES 1. 2. 3. 4.
G. Sheblé and G. Fahd. Unit commitment literature synopsis. IEEE Trans. Power Syst., 9(1): 128-135, 1994. S. Sen and D.P. Kothari. Optimal thermal generating unit commitment: a review. Elec. Power Energy Syst., 20(7): 443-451, 1998. R.B. Johnson, S.S. Oren, and A.J. Svoboda. Equity and efficiency of unit commitment in competitive electricity markets. Utilities Policy, 6(1): 9-20, 1997. A. Delbecq, A. Van de Ven, and D. Gustafson. Group Techniques for Program Planning — A Guide to Nominal Group and Delphi Processes. Glenview, IL: Scott Foresman and Co., 1975.
Chapter 2 REGULATORY EVOLUTION, MARKET DESIGN AND UNIT COMMITMENT
Richard P. O’Neill, Udi Helman, and Paul M. Sotkiewicz Federal Energy Regulatory Commission
Michael H. Rothkopf Rutgers University William R. Stewart Jr. The College of William and Mary
Abstract:
1.
In the context of competitive wholesale electricity markets, the unit commitment problem has shifted from a firm level optimization problem to a market level problem. Some centralized market designs use it to ensure reliability and determine day-ahead market prices. This chapter reviews the recent history of short-term electricity markets in the United States to evaluate the experience with alternative market designs and the implications for unit commitment modeling. It presents principles for the design of the next generation of unit commitment-based markets.
INTRODUCTION
Competitive wholesale electricity markets now operate in several major U.S. markets, confirming the analysis and recommendations of prescient economists, electrical engineers, and others over the past two decades.1 Since generation comprises approximately 75 percent of all electricity costs, com1
Seminal contributions on competitive wholesale electricity markets include [1,2]. As of January 1, 2000, regional markets with centralized wholesale electricity exchanges are operational in California, the Pennsylvania-New Jersey-Maryland (PJM) interconnection, New England, and New York.
16
The Next Generation of Unit Commitment Models
petition in generation promises large efficiency gains and cost savings to consumers. The unit commitment problem, the traditional method by which regulated utilities and power pools conducted internal scheduling of generation to meet demand at least cost over a multi-hour to multi-day time frame, is now embedded, in various ways, in competitive markets. Potentially, unit commitment models will be used by different market participants and institutions: individual firms, centralized auctioneers, decentralized aggregators of generation schedules, and transmission system operators. This environment presents a new set of modeling requirements and market design challenges.2 The market level unit commitment problem is typically much larger in scale than the firm level problem. Speed and accuracy are important if an auctioneer uses the solution by an auctioneer to determine market prices. Evaluating the characteristics of the solution, such as the presence of duality gaps (implying a lack of market clearing prices) and alternative optima, becomes of direct financial interest to market participants. The new electricity markets, and hence new applications of the unit commitment problem, are being developed within an evolving regulatory context. Indeed, an important driver of market designs is the guidance given by the regulator. The Federal Energy Regulatory Commission (henceforth “the Commission”) initiated regulatory reform of transmission in 1996, with the objective of encouraging competitive regional electricity markets that promote economic efficiency without compromising system reliability. The regulatory approach, embodied in a series of orders described below, has been to provide an open market architecture where alternative market designs are implemented, evaluated, and changed when necessary. Research into the unit commitment problem has largely been reactive to the new regulatory environment and the emerging issues in market design. A more proactive approach is needed. Among the issues that need consideration and research are the choices between simultaneous and sequential optimization of several energy and ancillary service products, alternative bidding rules for different products, different mechanisms for congestion pricing, and inter-regional coordination. In addition, unit commitment modeling now has to confront the issue of economic incentives in various market settings, which requires a more extensive familiarity with economics and game theory. In response to the regulatory evolution it has set in motion, the regulator also needs to adapt institutionally and develop its technical capabilities. This is imperative because the Commission is taking an oversight role in market design decisions across the United States. Several wholesale markets operate centralized unit commitment auction markets (e.g., PJM, New England, and 2
The literature on market design in electricity markets is extensive; for a survey, see the articles in [3].
Regulatory Evolution, Market Design, and Unit Commitment
17
New York), the market design of which is the focus of this chapter. These markets also allow bilateral trading and types of self-scheduling. Following approval of the basic design, the Commission provides oversight for a flood of subsequent adjustments and refinements in the search for well functioning markets. The underlying unit commitment model is often either an implicit or explicit matter in these market rule decisions. The objective of this chapter is to describe regulatory evolution and the market design challenges for unit commitment modeling. The chapter focuses on day-ahead markets, but much of the discussion is also applicable to realtime markets. Section 2 of the chapter describes the key regulatory developments and the design and recent experience of the major regional wholesale electricity markets. Section 3 focuses on principles that should guide the design of day-ahead energy and ancillary service markets. Finally, Section 4 offers conclusions.
2.
REGULATORY EVOLUTION AND THE ORGANIZATION OF ELECTRICITY MARKETS
The recent history of electricity regulatory reform in the United States began when the Commission issued Orders 888 and 889 in 1996 [4,5]. These orders required an open access transmission regime, based on nondiscriminatory transmission rates and transparent posting of available transmission capacity (ATC). Order 888 also included fairly broad organizational principles for an independent system operator (ISO), an institution which separates ownership from control of the grid and can perform market functions. Between 1997 and 2000, ISOs and power exchanges (PXs) were formed in California and in the three tight power pools of the eastern United States. These ISOs established day-ahead and real-time markets for energy, ancillary services, and transmission (in California, the day-ahead energy market is conducted by several separate scheduling coordinators, including the California Power Exchange). An ISO has also been established in the Midwest, but is not yet operational. Other regions of the country have been less successful or unwilling to centralize grid operations, and electricity trading remains bilateral, with a vertically integrated utility performing the balancing and reliability functions. By early 1999, a certain amount of inertia was evident in the development of wholesale markets. Electricity traders expressed dissatisfaction with the traditional methods of transmission grid management still employed in large parts of the United States. Specifically, there was substantial concern about
18
The Next Generation of Unit Commitment Models
frequent curtailments of transactions, justified on the basis of reliability but often questioned by parties to the transactions.3 On December 15, 1999, the Commission took a step toward clarifying the appropriate transmission access and market institutions with Order 2000, which requires the formation of regional transmission organizations (RTOs) [6]. The order establishes in the RTO many of the features that had emerged in the ISO markets as well as additional characteristics and functions that address unresolved issues in both ISO and non-ISO electricity markets. The RTO is required to serve a region of sufficient scope and configuration to provide for a reliable, efficient electricity market. With respect to the unit commitment problem, some of the important features of the RTO are that it must have exclusive authority for maintaining short term reliability, act as provider of last resort of ancillary services, address parallel path flows, provide real time energy balancing, and ensure development of market mechanisms for congestion management. In many ways, the functions assigned to the RTO are based on the principles of market design embodied in the better functioning ISOs that have emerged (in fact, RTOs will subsume existing ISOs). Section 2.1 surveys some of these ISO market design lessons; Section 2.2 discusses further the objectives of Order 2000 and some market design issues. Before considering the details of open access and market design, an important question is: Why should the regulator remain involved in the design and oversight of the emerging competitive markets? Recent experience has made clear that, in the near term, the Commission has a continuing role for at least three reasons: 1. There is the ongoing development of open access itself, including the provision of short-term reliability services linked to transmission and future expansion of the grid. There are public good aspects to reliability and transmission expansion.4 2. Where not currently available, there must be an efficient pricing mechanism for transmission congestion (i.e., pricing of the externalities created by parallel path flows). 3. There must be mitigation of market power in markets for electricity and ancillary services and in provision of transmission capacity. Market power is the ability of firms to raise prices above competitive lev3
Such curtailments are supposed to follow the North American Electricity Reliability Council’s (NERC) Transmission Loading Relief (TLR) procedures, which provide criteria for the management of congested transmission facilities.
4
A public good is a good that is non-rivalrous and non-excludable. In the case of reliability, a load’s or generator’s consumption of reliability in no way prevents others from enjoying the same reliability, and if all of the loads and generators are interconnected on the same system, they cannot be prevented from enjoying the benefits of reliability.
Regulatory Evolution, Market Design, and Unit Commitment
19
els. Firms can exercise market power in electricity markets because of both structural factors (e.g., firm concentration or transmission constraints) and opportunities offered by the market design (see [7,8] for a survey). The Commission’s policy heretofore has been to approve implementation of the markets (through more liberal standards for granting market-based rates) while at the same time evaluating the markets’ operational experience and providing guidance on market designs as a means to promote efficiency and competition. In addition, most of the responsibility for day-to-day monitoring and mitigation of market power has shifted to the ISOs and the future RTOs. The regulatory approach, then, seeks to balance the current reality some firms can exercise a degree of market power generally or under certain system conditions – with the expectation that entry of new firms and more efficient market designs will substantially mitigate future market power.5
2.1
Experience with ISO and Bilateral Markets
Order 888 outlined principles for, but did not require, a particular structure for competitive wholesale energy markets. Two broad types of market structures have developed. The first type consists of markets with ISOs, which may or may not include one or more scheduling coordinators or PXs.6 The ISO markets with PXs take the form of either a centralized ISO/PX or a decentralized ISO and PX(s). The centralized ISO/PX markets use unit commitment models for creating the day-ahead schedule (which incorporates bilateral transactions and self-schedules) while the decentralized ISO markets require self-commitment by the PXs. The second type of market has no ISO; rather, the transmission system and much of the generation continues to be operated by vertically integrated utilities. Power is traded bilaterally. This section focuses on the various market designs and performance of the existing ISO markets, as well as offer some conclusions and recommendations on what designs will work best. It also includes a brief review of the performance of the bilateral, non-ISO markets. Market Functions and Design of ISO Markets. Competitive wholesale 5
There is a large body of literature on market power due to both structural and market design characteristics of electricity markets. For analysis of regional energy and ancillary service markets in the United States, see [8-12].
6
Scheduling coordinators or power exchanges (PXs) are power trading operations functionally separate from the ISO. These terms will be used interchangeably.
20
The Next Generation of Unit Commitment Models
electricity markets can be complex, with multiple interdependent products sold on different time frames and differentially priced at different locations. Existing ISO markets can be characterized by the (1) number and types of different products (energy, ancillary services, capacity), (2) bidding and scheduling process, (3) relationship of temporal (forward and real-time) markets, (4) market clearing and settlement rules, and (5) type of congestion management and transmission rights. Each of the existing ISOs has also established market power monitoring and mitigation, but this function will not be examined here. The ISO carries out the basic function of assessing the feasibility of proposed generation schedules. The ISO also serves as the buyer, through contracted rates and bid-based auctions, of reliability services, including shortterm ancillary services (voltage support, operating reserves, and automatic generation control) and possibly longer-term capacity products. The PX facilitates and conducts a forward auction market for electric energy. PX functions can either be carried out by the ISO itself, as in New York, New England, and PJM, or by one or more separate, unaffiliated PXs, as in California. With the exception of the California ISO, the ISOs run a unit commitment model to determine which units will be scheduled to provide energy and ancillary services during the following day. In California, the ISO and PX (which is one of several scheduling coordinators) are separate, a decision intended to keep the transmission system operators (who may have been affiliated with an incumbent utility) functionally distinct from the market. In the California PX market, generation owners selfcommit their units through scheduling coordinators. This market structure has experienced certain disadvantages. One problem is that the scheduling coordinators’ submissions can be physically infeasible. The ISO must then engage in a time consuming iterative process with the scheduling coordinators to resolve the infeasibilities. The PX auction algorithm is such, however, that selfcommitted units are often asked to start-up and stop, disregarding minimum run and down times, with potentially adverse results.7 Another problem is that the separation of the ISO and PX raises the transaction costs for market participants. In addition, because the ISO’s decisions about congestion and purchases of ancillary services cannot be remedied by the PX, market participants may bid strategically into the ISO’s congestion market to ensure that profitable transactions are not curtailed. Bidding and Scheduling. The ISO markets began, largely, with only supply-side bidding for energy and certain ancillary services. While demandside bidding for energy is allowed in some markets (currently the California ISO and PX and New York, but planned for the other ISOs), the energy de7
Conversations with California ISO staff confirm this problem.
Regulatory Evolution, Market Design, and Unit Commitment
21
mand function is largely inelastic – that is, not price responsive – due to both technical limitations and historic rate designs. As more price responsiveness is introduced into demand bid functions (through installation of metering equipment and technological advances in distributed generation and information technology), there should be a reduction in both price volatility and the potential for exercise of market power, particularly during peak hours. The structure of bids is another market design issue that has attracted attention. Bids in current ISO energy markets vary in the number of cost components and required technical parameters, such as ramp rates, high and low operating limits, and so on. In the so-called “one-part” incremental energy bid, the bidder must factor its start-up, no load, and other costs into its dayahead energy bid for each megawatt-hour (MWh) offered.8 Even so, generators face the risk that they may not cover all of their costs in the auction. Onepart bids require generation owners to internalize this risk in some fashion, which in turn increases their costs (use of the real-time market to make adjustments can eliminate part of this risk).9 One-part bids also result in inefficiency if they are the only costs the dispatcher considers in commitment. In a three-part bid, the start-up and no-load costs can be separated out, allowing generators to bid actual operating costs more precisely and allowing for a more efficient unit commitment. In PJM and New York, generators are guaranteed to at least recover all of their bid costs if they are committed to run.10 This mechanism eliminates the uncertainty of whether a generator will be committed and dispatched only to lose money, and it allows for a more efficient dispatch. Market-Clearing and Settlement Systems. Market-clearing rules and settlement systems are the procedures that determine quantities produced and consumed, who pays, and who gets paid. As discussed above, ISOs typically operate multiple markets, including energy, several types of ancillary services, and transmission products. There are two basic ways to clear these different markets, sequentially or simultaneously, with variations on each method. In general, sequential auction markets clear each product separately 8
Currently, the California PX requires one-part energy bids without technical parameters, such as minimum run times, ramp rates, and so on. This could be called a pure one-part bid. New England currently requires one-part bids with technical parameters.
9
At its worst, the need to internalize risk in the one-part bidding system could lead to a greater incentive to internalize via bilateral contract or merger to avoid higher transactions costs. High market concentrations lead to market power concerns. Further, not being allowed to bid marginal cost is an easy defense to an inquiry on market power abuse.
10
Generators will receive an “uplift” payment to recover their costs only if the revenues they receive from the energy and ancillary services markets are less than their total bid costs.
22
The Next Generation of Unit Commitment Models
in a sequence, even though several of the products may be alternative (substitute) uses of the same generator. Variations of this approach were adopted initially in California and in the interim New England market. In contrast, a simultaneous auction, adopted in PJM and New York, clears the relevant markets at the same time, minimizing the joint bid cost of providing energy and ancillary services. This method explicitly takes into account that some products are substitutes. One of the clearest market design lessons from ISOs is that sequential market clearing without product and/or quantity substitution is economically inefficient and offers opportunities for strategic behavior. In California, energy, regulation, 10-minute spinning reserves, 30-minute non-spinning reserves, and replacement reserves are cleared in the order given.11 It has sometimes been the case that the price for ancillary services with lower production costs exceeds the price of ancillary services (and energy) with higher production costs (for example, providing spinning reserve requires using some fuel, whereas providing non-spinning reserve requires simply being on stand-by). The reason for some of these “price inversions” is that generators can strategically bid high prices in the last markets knowing that there will not be much capacity remaining after the other markets clear. Hence, the ISO must take these high price bids. To combat this design flaw, the California ISO has instituted a pre-processing algorithm, called the Rational Buyer Protocol, which will allow it to substitute higher quality services for lower quality services if and only if it reduces its ancillary service procurement cost. New England also initially used sequential market clearing and experienced problems similar to California; temporary solutions have included rolling over of bids between substitute services, as in California, as well as price caps. Experience with simultaneous market clearing is limited. The simultaneous market clearing method will largely, but not entirely, avoid the price inversions seen in the California ISO and New England markets because the software used to clear the markets automatically clears all remaining arbitrage opportunities. In addition, generators which bid strategically, as in California, would be far less likely to be selected to provide ancillary services at the higher price due to the greater substitution possibilities in the simultaneous market clearing. While more complex computationally, simultaneous marketclearing appears to be emerging as the better system from an efficiency standpoint. 11
In California, regulation refers to automatic generation control, but is defined in terms of whether generation output is increased (regulation up) or decreased (regulation down). Spinning reserves is reserve capacity available in a specified time period from a generator synchronized with the grid. Non-spinning reserves are reserve capacity available in a specified time period from a generator not synchronized with the grid. Replacement reserves are reserves that can be available within 60 minutes.
Regulatory Evolution, Market Design, and Unit Commitment
23
The settlement systems can be characterized as either single settlement or multi-settlement based on the number of temporal markets the ISO runs. In California, there are three temporal markets: day-ahead, hour-ahead, and realtime with a financial settlement for each. New York and PJM run two temporal markets: day-ahead and real-time. New England currently has only realtime markets (bids are due day-ahead but financial settlement only takes place at real-time prices), but is scheduled to implement day-ahead markets with financial settlement. A clear market design lesson is that single-settlement systems, which require generators to submit bids and stand-by day-ahead while awaiting financial settlement at real-time prices, create problems in scheduling and often require additional rules to constrain generator incentives to change their bids. The multi-settlement system has been adopted by all the ISOs in recognition of the value of the forward market as a financial hedge for real-time conditions. Also, the forward market should facilitate demand-side responses by giving demand that has bid to reduce load more time to react to price signals. Congestion Management and Pricing. In the ISO context, there are two general ways to manage congestion: locational pricing and non-locational pricing. Locational pricing can be sub-divided into approaches defined by the level of aggregation used to calculate the price. In the typical “nodal pricing” method, an energy price is calculated at each generation and load bus (node). The transmission congestion price between any two busses is the difference in energy prices at the busses. At higher levels of aggregation, the busses in the system operated by an ISO can be gathered into one or more congestion zones. Zones are intended to be indicative of the historical pattern of congestion in the system on the presumption that congestion will take place between the zones with little or no congestion within a zone. The price of congestion between zones is the difference in energy prices between the zones. If congestion occurs within a zone, the costs of managing it (typically through generator re-dispatch) are shared by all market participants inside the zone using a system of subsidies.12 This intrazonal congestion management method could be considered a type of nonlocational pricing.
12
Several ISOs have attempted to operate as single zones (PJM, New England), but have subsequently made the transition to locational pricing. If the single zone system has consistent congestion between sub-regions (that is, should be at least two zones), this can create opportunities for generators to leave the spot market and use bilateral contracts to take advantage of the system price. This was the experience in PJM before it implemented a nodal system; the ISO was required to adopt administrative measures to curtail the bilateral transactions.
24
The Next Generation of Unit Commitment Models
The zonal approach has been adopted in California, which currently has two (soon to be three) congestion zones but is experiencing congestion that should trigger new zones (also, each import point effectively creates a new zone). The California ISO manages inter-zonal congestion through adjustment bids submitted by generation and load. These bids indicate the price at which the market participant is willing to be ramped up or down in order to alleviate congested lines. If this fails to relieve the congested lines, then the ISO must call on generators with cost-based contracts to relieve congestion.13 California manages intra-zonal congestion by re-dispatch (which incorporates the transmission constraints into the original, transmission unconstrained dispatch) with the resulting costs averaged over load in the zone. Persistent intrazonal congestion indicates that the zones are not properly defined; in addition, the averaging of congestion costs within the zone is inefficient, since the congestion costs are also paid by participants not causing the congestion.14 In the long run, zonal pricing as practiced in California can lead to price signals that distort decisions on siting new generation and transmission assets.15 Neither maintaining fixed zones in the face of intrazonal congestion nor continuous re-zoning are efficient methods of congestion management. Zonal market design in California has been instituted in part under the rationale that it lowers market power. Both in theory and practice this assumptions has been proved wrong. Market power cannot be reduced by the declarations of large zones. If this were so, there would be no market power problem. Transmission constraints and generation costs determine the size of the market, not the declaration of zones. The California ISO rules recognize this by providing for dispatch orders and out-of-market payments to generators in the same zone separated by constraints. In contrast, despite opposition from some generators and marketers, nodal pricing has been adopted in New York and PJM and approved for New England (these systems actually use nodal prices for generators and zonal averages for loads). Nodal pricing eliminates the problem of properly defining 13
These are called Reliability-Must-Run (RMR) contracts. RMR contracts are intended to ensure that the ISO has sufficient generation capacity to meet various system contingencies, such as congestion relief and voltage support.
14
The California ISO can create a new congestion management zone if the cost to alleviate congestion over the previous 12 months exceeds 5 percent of the approximate annual revenue requirement of the transmission operators. In order to be considered an active congestion zone, the markets on either side of the congested interface must be “workably competitive” for significant portions of the year.
15
For example, the Commission has rejected a California ISO proposal (Tariff Amendment No. 19, filed June 23, 1999) that new generators upgrade transmission capacity to alleviate intrazonal congestion which might arise from their entry on the grounds that it could create further barriers to entry and market distortions. A similar New England proposal was also rejected.
Regulatory Evolution, Market Design, and Unit Commitment
25
zones and the need to average the costs of any intrazonal congestion. In the short run, load receives the proper price signals about how much to consume, and the long-run decisions can be made much more easily. Even though loads pay a zonal price, the nodal price information remains available for decision making. For financial markets, nodal prices for a region can be aggregated into fewer “hub” prices, which are weighted averages of the underlying nodal prices. For example, PJM has two hub prices. Transmission Rights. Transmission rights have traditionally been used to reserve access to the transmission system and to ensure that energy transactions would be curtailed only in extreme circumstances. These rights were physical rights – the right to transmit physically a specific amount of power over the system for the access charge paid. With the advent of congestion pricing (whether zonal or nodal), most ISOs have provided both physical rights and financial rights that can be used as a hedge against congestion costs (the stochastic nature and potentially high cost of congestion makes financial hedging necessary).16 In all the markets with locational congestion pricing, payment of congestion prices is essentially a physical right to transmit between nodes or zones (although not a right that is bought in advance). On the other hand, financial rights are typically purely financial mechanisms that provide revenues but confer no physical priority. They can be traded on a secondary market. For example, in New York and PJM, financial transmission rights give the holder the right to collect congestion rents between a designated point of injection and point of withdrawal, so that if a transaction incurs congestion costs, those costs would be offset by the revenues from the financial right. Auctions for these rights are typically held regularly. The California ISO has implemented a similar type of zone-to-zone right, but which also confers some physical priority.17 Performance of ISO Markets. As discussed above, none of the ISO markets has reached a stable point in terms of market design; some are undertaking major market re-designs while others are in the process of implementing major components of their market design. There is a convergence in market design in many areas: all the ISOs have implemented either sequential auctions with substitutions or simultaneous auctions for energy and ancillary services; most ISOs have established multi-settlement systems or will shortly. Most ISOs offer some form of financial transmission right; in the East coast 16
Transmission rights can take the form of either options or obligations.
17
If the California energy markets fail to clear, the holder of a transmission right usually gets a better position in the curtailment queue than a generator not holding a right.
26
The Next Generation of Unit Commitment Models
ISO markets, nodal pricing is used for generation or is planned for future implementation. Given these ongoing changes, the preliminary performance of the markets varies by product and time period. In transmission, the ISOs have recorded few curtailments. There has been some concern, however, that the number of bilateral transactions has decreased in nodal congestion management systems (because point-to-point congestion may be difficult to hedge with the available transmission rights). The energy markets seem to be functioning fairly well, although prices under certain system conditions reflect varying levels of market power [8-13]. Entry of generation, transmission capacity expansion, and demand-side bidding should lower prices and lessen volatility. The ancillary service markets have been more problematic. Reserve markets in particular have experienced price spikes and price inversions, reflecting the greater vulnerability of these markets to market power and to market design flaws that exacerbate strategic behavior [9,12]. Temporary price and bid caps and more permanent market re-designs should help solve some of these problems. Other general market problems include limitations in software implementation and technical capabilities (such as using telephone rather than electronic communications for dispatch), and conflicts that emerge when system operators depend on rules of thumb to dispatch the system rather than the outcomes of the auction. In general, however, many market design or implementation problems are amenable to satisfactory resolution, some through admittedly short-term “band-aid” solutions, but most with a longer term fix available. Business confidence is not equally robust in each ISO market (PJM appears to be the market with the fewest problems to date), but should increase as the markets mature. Performance of Bilateral (Non-ISO) Markets. The largely bilateral markets, especially those in the Midwest, have experienced many potential reliability problems as evidenced by the frequency of curtailments under Transmission Loading Relief (TLR) procedures. These may also be attributable to the lack of independence of the system operator and market participants.18 Market participants have complained that they could not get access to the transmission system even when capacity appeared to have been available. As described below, Order 2000 requires the implementation of more efficient congestion management practices.
18
The curtailment of transactions in the presence of prices 10 to 100 times the annual average, due to TLRs and voltage reductions concurrent with power outages, indicate markets are not working in harmony with reliability constraints. For example, in the summer of 1999 the ECAR region with bilateral trading called 87 TLRs and the adjacent PJM ISO called three. For a general review of these complaints, see [6].
Regulatory Evolution, Market Design, and Unit Commitment
2.2
27
Order 2000 and RTOs
A Regional Transmission Organization (RTO) is a transmission system operator that is independent of market participants, controls transmission facilities within a region of appropriate scope and configuration, and is responsible for operating those facilities to provide reliable, efficient, and nondiscriminatory service. All transmission owners must file a proposal to participate in a RTO or provide reasons for delaying or avoiding participation. Order 2000 explicitly notes that the designs for bid-based markets in the four ISOs operational before the year 2000 should form a basis for the design of RTO markets. Yet the open architecture adopted in Order 2000 does not propose a single market model and offers sufficient leeway for further experimentation within the RTO design principles. With respect to the unit commitment problem, the RTO has certain relevant functions. The RTO must have exclusive authority for maintaining shortterm reliability. To fulfill this function, Order 2000 makes clear that the RTO requires knowledge of the operational status of generators and load.19 This includes control over interchange schedules, the authority to require redispatch of generation connected to the grid, and approval over scheduled outages. The RTO will determine the required amount of each ancillary service and the location where the service is to be provided. It will also act as provider of last resort of ancillary services. That is, market participants can selfsupply or purchase ancillary services from third parties, but the RTO must have the capability to provide any residual. The RTO or a third party unaffiliated with market participants must provide real time energy balancing. With regard to transmission, the RTO must ensure development of market mechanisms for congestion management and must develop procedures to take into account parallel path flows. The RTO will sell physically feasible, shortand long-term, tradable transmission rights. The RTO may choose to expand the transmission system and/or invest in advanced technology to increase capacity.20 19
Such knowledge includes technical information supplied by generators such as ramp rates, upper and lower operating limits, whether the unit is running or not, start-up times and time between start-ups. In real-time and for day-ahead planning, the RTO must have information on generator injections and load withdrawals of energy in order to balance the system. 20 In the comments on Order 2000 [6], various policy suggestions were made regarding increasing transmission capacity, including overbuilding the transmission system (see Joskow comments) and/or investing in the high tech Flexible AC Transmission System (FACTS) and Wide-Area Measurement System (WAMS) to allow more robust competition to develop.
28
The Next Generation of Unit Commitment Models
Finally, the RTO is required to monitor for market power abuses and market design flaws. It should also evaluate and implement potential efficiency improvements in the markets it operates. Beyond these requirements and guidelines, specific market designs are left to the RTO market developers (subject to the proviso that they not limit the RTO’s ability to improve efficiency further). The remainder of this section discusses some issues about the conceptualization of the role of the RTO with respect to financial and physical transactions as well as the relationship of RTO-operated auction markets in relation to other energy markets. In addition, some pressing market design issues are reviewed, including pricing of reserves and inter-regional coordination. Section 3 then draws on the ISO experience and other sources to outline some principles for the design of dayahead RTO markets. Relationship Between Physical and Financial Transactions. An issue that has remained contentious in the preliminary design and operation of ISO markets is the relationship between physical and financial markets – specifically, the concern that the centralized ISO markets and nodal congestion pricing would inhibit development of the decentralized financial markets.21 An important principle underlying the future RTO markets is that wellfunctioning physical markets promote robust financial markets. For our purposes, physical trades are trades that the RTO has registered as feasible, considering all other physical trades and required ancillary services. This includes bids into the ISO markets, bilateral transactions and self-schedules that have been cleared in the ISO day-ahead schedule (even though these day-ahead transactions are actually financial contracts until physical delivery). Financial trades are trades that are not physical trades, but take the form of forward contracts, futures contracts, or options contracts. They are not considered physical trades until they are confirmed as physically feasible by the RTO. Indeed, the RTO should be concerned primarily with physical market transactions; it would not operate purely financial markets and need not be involved in any financial markets unless the transaction goes to delivery. Financial markets can and must exist in harmony and equilibrium with physical reliability markets. If not, the financial markets’ ability to reduce risk is diminished. Multiple PXs and bilateral trading can fit easily into this market velop. The latter appears more promising because it promises not only more capacity and less greenfield construction, but also better system control (see EPRI and EEI comments). 21
One argument has been that uncertainty over nodal congestion prices, calculated hourly in real-time, increases the risk of bilateral deals concluded prior to the hour. Another is that some rules regarding three-part bids, in which the start-up payments made by the ISO are averaged over all electricity load in the system (e.g., in New York), effectively amounts to a subsidy to generators in the ISO auction market.
Regulatory Evolution, Market Design, and Unit Commitment
29
framework. Each PX would act as a single scheduler, submitting schedules and technical information for generation and load to the RTO. The market design of the physical market should allow full, but optional interaction with financial markets. To become physical transactions, a market participant need only self-schedule, that is, submit quantities to the day-ahead market. If the transaction includes the necessary transmission rights and ancillary services, no charges will be assessed. This allows for fully hedged financial transactions. In addition, payment would be received for any additional service provided. Otherwise, the market participant will be billed for congestion, losses, and ancillary services caused by the bilateral transaction. If not self-supplied, a bilateral trader can place price limits on what it is willing to pay for transmission and ancillary services. If the price limits are not met, the transaction will not be scheduled. If all voluntary adjustments are tried and reliability constraints are still not met, the transaction will be canceled in the day-ahead market. This gives ample time for parties to make adjustments. This cancellation avoids a potential TLR and the resulting schedule is very likely to be physically feasible. Physical markets provide real-time price signals and additional liquidity. Without good price signals from the physical markets, the financial markets can become unstable and encourage more speculation and less hedging. Even though bilateral trading may be highly discriminatory (that is, sellers may charge different prices for the same delivered product to different buyers), the opportunity for buyers to participate in an efficient, nondiscriminatory RTO auction market will tend to discipline the bilateral market. RTO auction markets create options for all buyers and sellers and thereby allow for a light-handed approach to the regulation of these transactions. In sum, the benefits of well-designed RTO markets include lighter-handed regulation of financial markets, more liquidity, less gaming and risk, more visible prices, lower transactions costs, fewer curtailments, and compatibility with financial markets. Reserves Markets. The establishment of efficient ancillary service markets is an ongoing market design challenge. As the cost of reliability increases and in the absence of a way to represent willingness to pay for ancillary services, the RTO system operator can relax reserve margins and transmission constraints. This is, in fact, written into the market rules in some ISOs; it remains a contentious issue, largely because it has involved system operator discretion that results in changes in market prices. The relaxation of these constraints increases the probability of a system failure; as such, it should be part of the operational parameters of the auction decided in advance of the day-ahead auction so that actions of the system operator are not seen as arbi-
30
The Next Generation of Unit Commitment Models
trary. To be effective, reserves must be able to respond to loads that need them. If transmission is congested between generation and load, reserves on the generation side are of little help to the load side. Both transmission and generation can be used to meet reserve requirements. They have substitute characteristics (strengthening transmission connections within a region can lower the total generation reserves needed in a region) and complementary characteristics (if the reserves for a load are not located at the same node, transmission capacity between the reserves and load will also need to be set aside). This set-aside is similar to the capacity benefit margin (CBM) concept. The auction algorithm would set aside transmission capacity to allow reserves to respond. The modeling of this process is very similar to the modeling of the energy market itself. Prices for reserves would have a locational component and the transmission price would reflect the set aside transmission capacity. Using this locational method of allocating reserves, it could appear that transmission capacity is being withheld. One method to deal with this is to have a “use or lose” requirement of transmission rights. The set-aside “use” of transmission for reserves markets would be considered a “use,” not withholding, and is under the control of the auction process and the operator. Dealing with the combination of congestion constraints and soft reserve constraints simultaneously requires operator independence and transparency in the market environment, as a means to promote trust in the market. Over time, as demand becomes more responsive to price, generation reserve margins can decline as offers to reduce demand can substitute for reserves. Currently the costs of reserves are averaged among all end users. Some of these costs can be more directly assigned to specific generating units and individual customers. For example, a unit with a good reliability record should be responsible for a lower reserve margin or be charged less for reserves based on size and the historic probability of unit failure. Payments or discounts that differentiate more reliable from less reliable generators should be handled in the pre-day-ahead markets. RTO and Expanded Inter-regional Coordination. Spatial boundary conditions – also called the “seam” or interface problem – are becoming an important design issue as trading between ISOs increases. ISO coordination efforts on this matter are in the nascent stages. In terms of system representation, some ISOs have included a reasonably detailed representation of the interconnection with control areas outside the ISO as part of the boundary conditions. Approaches to the seam problem have included proposed interface auctions for inter-control area exchanges [16,17]. In day-ahead markets, there is some time to coordinate these interfaces offline via iterative trading rules. Research into this problem generally is in its infancy. PJM, New York, New England, and Ontario are examining a broad set of inter-regional market de-
Regulatory Evolution, Market Design, and Unit Commitment
31
sign and procedural issues, and these markets have signed a memorandum of understanding on inter-regional coordination (on the need for such coordination generally, see [6]). Order 2000 anticipates that RTOs will assist in creating larger regional markets in which seams issues are resolved.
3.
DESIGN PRINCIPLES FOR DAY-AHEAD RTO AUCTIONS
In the early phases of electricity market design and implementation, the various disciplines – notably economics and electrical engineering – have not undertaken adequate inter-disciplinary research or sufficient professional exchanges. For example, ISOs have several times misunderstood the incentive issues in electricity and ancillary service auction designs, as evidenced in the remedial actions and market re-designs described in Section 2, above. At the same time, market design has sometimes proceeded with the economics basically correct but without an adequate consideration of reliability and technical constraints. As a result, there is sometimes little understanding of what basic principles ought to underlie these complex markets. This section attempts to elaborate such principles for day-ahead markets. These principles can be compared with the market design principles in [14]. This section addresses the prospective RTO day-ahead market, which is defined as the market in which the initial bidding to provide energy and ancillary services for reliability, congestion management, and energy balancing takes place. As is done currently in ISO markets, this market would be conducted on the day prior to the dispatch day. The dual objectives of the dayahead market are to achieve economic efficiency and ensure system reliability. The day-ahead market is a physical market where all expected balancing/ancillary services are scheduled. The design for the day-ahead market is discussed below and it assumes that there is a real-time market, in which adjustments are made to energy and ancillary services reflecting the differences between day-ahead expectations and real-time conditions.22 22
The real-time market will not be examined in depth here. Efficient market design requires, however, that most principles be adhered to with respect to the relationship of the real-time and day-ahead markets. Bids should be submitted separately into the real-time market, and market prices based just on those bids. Deviations from the day-ahead market should pay the real-time price unless there is a reliability problem. If a bidder does not deviate from the day-ahead schedule, there are no additional costs to pay based on the real-time market. Finally, the market operator needs to keep the system in balance at the nodal level using bids to the extent possible.
32
The Next Generation of Unit Commitment Models
The following is a list of recommended design principles derived from the foregoing analysis and experience to date, with short explanations and clarifications. Principle 1: Maximize economic efficiency. The RTO auction objective is to maximize economic efficiency through voluntary market bids, bilateral transactions, and self-scheduling, given the physical and reliability constraints. Not all current ISOs adopt this principle. For example, the California ISO cannot adjust power schedules submitted to it by the California PX to improve economic efficiency. This principle requires that if market participants use the RTO markets, the resulting prices are efficient. The market-clearing procedure will balance the system and the purchase of ancillary services using the bids it has received. If the financial markets are efficient, there may be few additional trade gains in this market and this market becomes a reliability check. Efficiency requires that prices be consistent (e.g., no price inversions due to market design flaws) and that arbitrage opportunities reflected in the bids be exhausted. Principle 2: Ensure physical feasibility of market transactions and system reliability. Without physical feasibility, reliability problems cannot be fully addressed. For ancillary services, the market design should require that generators committed to provide these services are located so that their capacity is available when and where they are needed. Principle 3: Remove disincentives to market participation. Participation in an RTO market should involve low transaction costs and create minimal additional risks. Minimal participation in the market is the submission of generation and consumption quantities (that is, bids which are taken at any price, or “at market”). Any unit dispatched should be guaranteed bid-cost recovery. Principle 4: Bidding protocols should promote flexibility of participation. All market participants should be allowed, but not required, to submit multi-part bids that reflect short-term marginal costs. Market participants should be allowed to self-schedule, that is, allowed to submit quantity-only bids. This principle requires that all resources have the option to bid a reasonable approximation of their short-term marginal cost function, including start-up, no load, and energy costs (in addition to technical parameters, such as minimum and maximum load limits, ramp rates, and minimum shutdown time). Although a bid function will seldom serve as a perfect match for
Regulatory Evolution, Market Design, and Unit Commitment
33
actual marginal (incremental or going forward) costs, a good approximation should be available. This principle will require changes in some current unit commitment auctions, which allow only one-part energy bids (of course, in a multi-part bidding rule, generators can still submit one-part bids, by bidding zero for start up and no load). As discussed above, there are technical, financial, and economic reasons for adopting multi-part bidding. While the multi-part bid allows for more accurate representation of marginal costs and thus, in the absence of market power, should result in a more efficient solution, it also results in a non-convex supply function. In turn, this makes the market equilibrium and prices harder to derive. This complication can be addressed and made manageable with some simplifying assumptions about which generators are allowed to bid non-convex costs, whether some parameters should be fixed for a specified period (such as ramp rates, maximum and minimum output), and what should be fixed in the bid function. Demand bid functions are essentially the mirror images of generator bid functions but will not be discussed in detail here. Consumers need more explicitly defined contracts to participate properly in the market and should be allowed bid functions similar to the generators. Principle 5: Make clear the distinction between financial and physical commitments. If accepted, bids are financially binding. If needed for reliability, bids are physically binding. The RTO schedules are physical and financial commitments subject to liquidated damages. That is, if market participants deviate from their commitments, they are liable for making the affected market participants whole. Under emergency conditions, the RTO may exact other penalties for nonperformance and/or issue perform-to-contract orders. Principle 6: Minimize opportunities for arbitrage between different product markets. This principle addresses generally the problems that arise when generators can bid into different product markets (energy and ancillary services) that are sequentially cleared. As discussed above, simultaneous markets eliminate opportunities for arbitrage. If the market design allows opportunities for lower quality products to be priced higher than high quality products, then there may be cases where generating units are paid more for not generating than for generating. Preferably, this should not be the case. The New England ISO attempted to establish this principle administratively by proposing that the energy price always act as a cap for operating reserves prices. This proposal was rejected by the Commis-
34
The Next Generation of Unit Commitment Models
sion; administrative measures should be at best transitions to market designs which can efficiently reach the same outcome. As discussed above, the simultaneous auction design will automatically allocate energy and reserves efficiently, but cannot guarantee the elimination of price inversions in the presence of market power. Principle 7. Prices should be unbundled where possible to minimize averaging (i.e., socializing) of costs. Averaged prices (whether for congestion, reserves, or other costs) do not send the correct price signals for the entry of new generation. Uplift charges, the mechanism used for passing through costs of energy and ancillary services not covered by market prices, should be coupled with incentives for the RTO to minimize the use of such charges. Principle 8. Market-clearing information should be made available as soon as possible. Fuller information on bids should follow with a suitable delay.23 Market-clearing prices and quantities are the basic results of the bid acceptance process. They enable market participants and potential future market participants to assess the market and plan their businesses efficiently. They also allow market participants to spot and correct obviously erroneous bid acceptance and rejection decisions. Disclosure of individual bids should be made eventually, but not immediately. Such disclosure will allow detection of subtle bid acceptance errors and it will also allow study of the market by independent analysts and market participants. It may lead to the exposure of the exercise of market power. Immediate disclosure of individual bids is undesirable because it might facilitate collusion by the market participants. Immediate disclosure might reveal information about market participants who wish to keep their costs confidential. After 6 months or a year, the information on individual bids has essentially no value for collusion and discloses little new about any bidder’s current costs, but the information would have high value for auditing and independent analysis. The auction software should be available to the market participant or public at a reasonable cost. Improvements to the software are desirable, and the best way to accomplish this is by making the software available with a set of test problems. 23
The California ISO, PJM, and New England appear to set the benchmark with updated prices every five minutes. At a minimum, prices and aggregate quantities should be available before the next round of bids with enough lead time to allow a reasonable response to the new information.
Regulatory Evolution, Market Design, and Unit Commitment
35
Principle 9: Minimize the incentives for market participants to engage in strategic behavior. The design should not favor market participants with market power. Market designs can only imperfectly address structural sources of market power. An auction does not eliminate the ability of a large firm to withhold capacity profitably. Auctions have been devised to “pay-off” market power, but these require significant computation and may not be revenue sufficient.24 Hence, absent a market design solution, the basic problem of structural market power has to be addressed using both structural remedies (vertical and horizontal dis-integration, encouragement of entry) and regulatory remedies, such as market power monitoring and mitigation. Of course, structural remedies may be wrapped up in market design issues. For example, an ISO may seek to promote rules on transmission interconnection for new generation which appear to favor incumbent generators. While market design cannot necessarily mitigate structural market power, it can certainly exacerbate it; market design can also create opportunities for strategic behavior by generators other than the obvious large players. An example, discussed above, is the sequential clearing of energy and ancillary service markets without substitution in both the initial California and New England markets. Even a small generator can try to take advantage of shortages of certain types of reserves in this type of market to raise prices.
4.
CONCLUSIONS
The considerable developments in the design of electricity markets over the past few years have provided the groundwork for the next generation of short-term markets. This chapter has emphasized that unit commitment models are now embedded in a variety of market contexts governed by an evolving regulatory framework that presents new requirements for modeling, including incorporation and understanding of market design issues. The open architecture promoted by the Commission allows for continued experimentation with RTO market design, but within parameters reflecting lessons learned heretofore from the ISO markets as well as the non-ISO bilateral markets. The market design principles presented in the paper are intended to reflect those lessons.
24
The Vickrey-Clark-Groves (VCG) mechanism, which has been applied to electricity auctions by [15], is a method to elicit truthful bids from players with market power.
36
The Next Generation of Unit Commitment Models
The other primary argument in the chapter is that a well-designed RTO day-ahead auction market with unit commitment complements “decentralized” financial markets. The computer does the work of resolving reliability constraints and will ensure that no offered trade gains are missed. Financial markets are free to create whatever innovative deals they can. The only restriction is that if they go to delivery they must satisfy any reliability constraints. Also, the opportunity for buyers to participate in an RTO auction market will tend to discipline the financial market. This will allow for lighterhanded regulation of financial transactions. The paper identified several other benefits of well-designed RTO markets: fewer curtailments, more visible prices, lower transactions costs, and less gaming and risk. The open architecture also allows for continued progress in efficient pricing, so that causality has financial consequences – prime candidates are transmission rights and reliability. Over time, as price signals are sent and acted on in real-time, accurate pricing can allow the public good aspects of these markets to shrink in importance and the private good aspects to grow.
ACKNOWLEDGEMENTS This paper reflects ongoing discussions among the authors and Carolyn Berry, Judith Cardell, Benjamin Hobbs, Thanh Luong, David Mead, William Meroney, and Roland Wentworth.
REFERENCES 1. 2. 3. 4.
5.
6. 7. 8.
P. Joskow and R.M. Schmalansee. Markets for Power. Boston: MIT Press, 1983. F.C. Schweppe, M.C. Caramanis, R.E. Tabors, and R.E. Bonn. Spot Pricing of Electricity. Norwell, MA: Kluwer Academic Press, 1988. H. Chao and H.G. Huntington, eds. Designing Competitive Electricity Markets. Boston: Kluwer Academic Press, 1998. Federal Energy Regulatory Commission. “Promoting Wholesale Competition Through Open Access Non-discriminatory Transmission Services by Public Utilities and Recovery of Stranded Costs by Public Utilities and Transmitting Utilities.” Order No. 888, 61 FR 21, 540, May 10, 1996. Federal Energy Regulatory Commission. “Open Access Same-Time Information System (formerly Real-Time Information Networks) and Standards of Conduct.” Order No. 889, 61 FR 21,737, May 10, 1996. Federal Energy Regulatory Commission. Regional Transmission Organizations. Order No. 2000, 89 FERC 61,285, December 20, 1999. C.A. Berry, B.F. Hobbs, W.A. Meroney, R.P. O’Neill, and W.R. Stewart. Analyzing Strategic Bidding Behavior in Transmission Networks. Utilities Policy, 8(3): 139-158, 1999. S. Borenstein, J. Bushnell, and C.R. Knittel. Market Power in Electricity Markets: Beyond Concentration Measures. Energy J., 20(4): 65-88, 1999.
Regulatory Evolution, Market Design, and Unit Commitment 9. 10 .
11. 12. 13. 14. 15. 16 . 17.
37
California ISO. “Annual Report on Market Issues and Performance.” Prepared by the Market Surveillance Unit, California Independent System Operator, June 6, 1999. R.E. Bohn, A.K. Klevorick, and C.G. Stalon. “Second Report on Market Issues in the California Power Exchange Energy Markets.” Prepared for the Federal Energy Regulatory Commission by The Market Monitoring Committee of the California Power Exchange, March 9, 1999. S. Borenstein, J. Bushnell, and F. Wolak. “Diagnosing Market Power in California’s Deregulated Wholesale Electricity Market.” PWP-064, Univ. of Cal. Energy Institute, Berkeley, CA, Revised, March 2000. P. Cramton and J. Lien. “Eliminating the Flaws in New England’s Reserve Markets.” Working Paper, Department of Economics, University of Maryland, College Park, MD, March 2, 2000. J.E. Bowring, W.T. Flynn, R.E. Gramlich, M.P. Mclaughlin, D.M. Picarelli, and S. Stoft. “Monitoring the PJM Energy Market: Summer 1999.” PJM Market Monitoring Unit, undated draft. R.D. Wilson. “Design Principles.” In [3]. B.F. Hobbs, M. Rothkopf, L. Hyde, and R.P. O’Neill. Evaluation of a truthful revelation auction in the context of energy markets with non-concave benefits. J. Regulatory Econ., 18(1): 5-32, 2000. M.D. Cadwalader, S.M. Harvey, W.W. Hogan, S.L. Pope. “Coordinating Congestion Relief Across Multiple Regions.” PHB Hagler Bailly Inc., Navigant Consulting Inc., and J.F.K. School of Government, Harvard University, Cambridge, MA, October 7, 1999. B.H. Kim and R. Baldick. Coarse-grained distributed optimal power flow. IEEE Trans. Power Syst., 12(2): 932-939, 1997.
This page intentionally left blank
Chapter 3 DEVELOPMENT OF AN ELECTRIC ENERGY MARKET SIMULATOR
Atif Debs and Charles Hansen Decision Systems International
Yu-Chi Wu National Lien-Ho Institute of Technology and Commerce
Abstract:
1.
The paper outlines the development of an electricity market operation simulator (EMOS) that can be used by competing market participants as well as independent system operators and independent market operators such as power exchanges. The uses include training personnel to make control and operating decisions and to assess bidding strategies by energy trading entities for energy and ancillary service products. We base the simulator is based on the power system model used in the operator training simulator. In the EMOS, market participants use unit commitment to assess bidding strategies and/or to schedule generation in a pool-type electricity grid. The EMOS provides a framework for users to implement their own applications with minimal effort and to model their competitors in a generic manner.
INTRODUCTION
This chapter reports on efforts to develop a realistic electricity market operation simulator (EMOS) for the emerging electric energy market. Several key features of the market are: (a) An independent system operator (ISO) coordinates supplies and demands with a focus on system security and reliability; (b) A market clearing entity determines which bids by market participants are accepted. In some cases this entity is an independent power exchange (PX), such as the California Power Exchange. In other
40
The Next Generation of Unit Commitment Models
cases, the ISO and the market clearing entity are integrated into one organization (e.g., the PJM Interconnection); and (c) Market participants (MPs) consist of a mix of unregulated and average-cost regulated entities. The unregulated entities compete against each other and submit daily, hourly, and even real-time bids to the market clearing entities and/or the ISO. They are generally generation companies (GENCOs), energy service companies (ESCOs), or scheduling coordinators (SCs). The regulated entities are mainly distribution companies whose aim is to purchase the energy through the market at competitive prices. In order to compete, each MP has to follow the rules of the market area involved and make appropriate “bids” to meets its goals. The bidding is normally based on the MP’s estimates of market prices and other factors associated with various risks involved. The purpose of the EMOS is to simulate the overall market composed of the entities just mentioned for very short-term operations (one day ahead, up to real-time). The working tool is the power system model (PSM) of the EPRI-operator training simulator (OTS) [1-7]. Each MP may have its own model of the system, but with outputs consisting of its bids into the market. The market clearing entity generates market clearing prices (MCP) and also most of the information needed to schedule system operation. The ISO does the final balancing of the market and the provision of needed “ancillary services” for system balancing, security, reliability, and real-time control [8-10]. Through the use of many existing software packages, standard application program interfaces, and communication protocols, the EMOS can be realized in a variety of configurations. It is, therefore, usable by any of the entities mentioned above. How do unit commitment (UC) and other forms of system optimization fit into the overall scheme of things? The approach given here uses UC at both the MP level and the market clearing entity level, whenever applicable. The EMOS also recognizes the fact that network optimization through the optimal power flow (OPF) is essential for such market considerations as: congestion management, reactive power/voltage scheduling, maximization of transfers, and others. Section 2 of this chapter provides a background summary of the emerging electricity market with a focus on short-term scheduling. Section 3 provides a conceptual framework for the development of MP models. Section 4 describes the overall market model, and Section 5 contains concluding remarks.
An Electric Energy Market Simulator
2.
ELEMENTS OF EMERGING ELECTRICITY MARKETS
2.1
Generation Scheduling in the Competitive Electricity Market
41
The traditional approaches of UC scheduling, hydro scheduling (HS), or a combination thereof (so-called hydro-thermal coordination (HTC)) [11] are being replaced rapidly by various forms of short-term competitive bidding schemes [8]. The majority of such schemes are based on a 24-hour, day-ahead scheduling process – a Forward Day-Ahead Market in the new jargon. In all the new schemes of electric utility restructuring, the generation component, as compared with the transmission and distribution components, is strictly market-driven and competitive. As a result, the central dispatcher plays the role of implementing the rules of generation scheduling as obtained through a market auction (bidding) mechanism. The main differences between the traditional and the “market-driven” approaches for generation scheduling consist of the following [11-13]: (a) Market prices are the result of the market design and associated rules and regulations under consideration. These rules may vary from one system to another. What complicates the picture is that the “products” being traded are many – starting with MWH energy and continuing through a host of ancillary services (A/S) and interconnected operation services (IOS). Some bidding schemes require full “multi-part” bids. Others require single-part bids for energy, and either simultaneous or sequential bids for the ancillary and IOS services. (b) Individual for-profit MPs aim to improve their short- and long-term market positions through various strategies for increasing their profits, controlling their market share, and/or other objectives. In the area of short-term (e.g., day-ahead and same-day) scheduling their main focus is on profit maximization. For the long-term strategies, they tend to use different mixes of tools including financial ones (futures, options, and swaps), or strategic ones (mergers and acquisitions, investments in other markets, etc.). (c) The new markets can become more or less effective through the existence of catalysts such as a power exchange, scheduling coordinators, energy brokers, service providers, e-commerce, and independent system operators.
42
2.2
The Next Generation of Unit Commitment Models
Network and Other “System” Issues in the New Environment
Principles that have been followed in restructuring transmission include: 1. In order to allow generating companies – as well as customers and distribution companies – to compete effectively, an open-access requirement has been suggested and implemented. The functions of generation scheduling have been “separated” from those of network access and control. 2. Certain markets (e.g., the PJM Interconnection, New Zealand, NYISO) use locational marginal prices (LMP). These depend on a solution of both a resource scheduling program (unit commitment, hydro-scheduling, or hydro-thermal coordination) and a securityconstrained optimal power flow (SCOPF). The resulting locational prices reflect a combination of “charges,” such as transmission losses, congestion, reactive support, reserves and, others [14,15]. (See Figure 1.) Even in markets that do not use LMPs (or equivalent), network information and the ancillary services protocols can be of great value for all market players, e.g., the California ISO [8].
An Electric Energy Market Simulator
43
In short, different market players will have to adapt to the operating rules for the systems served by different types of ISOs. In many cases, knowledge of real-time and forecasted network conditions can be critical in assessing various risk exposures and in evaluating hedging instruments.
2.3
Market Prediction is a “Learning Process”
Competitive markets do not behave like centrally dispatched systems. Price discovery is attained through the auction mechanism, which has its own dynamics [12]. Prices tend to be uncertain with a random component and a systematic component. The random component stems from external uncertainties (unpredictable weather, forced outage of a unit, system disturbance, fluctuating fuel prices and interest rates, etc.). The systematic component is related to physical constraints, market rules, auction clearing mechanisms, etc. It is also related to “gaming” and market strategies by various players (e.g., to manipulate prices and increase prices). Within this systematic component of market price prediction, a “learning process” becomes necessary to predict the behavior of the competition. Since energy markets clear prices very frequently, the learning process can be formally analyzed [13]. In most cases, however, it becomes the purview of “experts,” like skilled traders who earn their income from being very good learners.
2.4
Rationale of a Simulation-Based Approach
The foregoing discussion points to the fact that various analytical models may not provide the full answer to all the questions. Given the complexity of the power system and hence the electric energy market, there is a need in our opinion for a simulation tool to help in the learning process. Such a tool must by necessity represent both the systematic and random parts of the process. From a modeling viewpoint, we have considered the following to be critical [1-8,13]: The power system under consideration should be modeled realistically. Control and decision mechanisms by the main dispatcher (ISO, TSO, etc.) should be customized in accordance with the rules of the system under consideration. The market bidding and price clearing mechanisms should also be modeled for each respective market.
44
The Next Generation of Unit Commitment Models
The transitions from one market regime to the next (i.e., day ahead to hour ahead to real-time) should be clearly modeled and accommodated, The various tools used by individual market participants to play the market should be modeled. The simulation should have a growing library of such tools as one learns about the bidding strategies of various players. The simulation should explicitly model random and systematic risk exposures.
3.
MARKET-PARTICIPANT MODELS
The simulation model recognizes that the power system is run as a result of decisions made by groups of various market participants (MPs). At a minimum, these MPs would represent the following entities: Generating companies (GENCOs) who are competing against each other, Demand-side entities, Independent System Operators (ISOs) Energy Service Providers (ESCOs) Figure 1 gives the functional structure of MP models. This structure is in turn specialized for each of the categories of market participants as given in Figure 2. Figure 3 in Section 3.6 displays the ESCO functional structure.
3.1
Generating Companies (GENCOs)
GENCOs comprise a variety of entities: (a) the generation component of an integrated utility that is required to have functional separation of generation trading from other services, (b) a pure generating company with resources scattered over several geographic areas, or (c) an independent power producer (IPP). All these entities share similar needs and requirements. As a result, we designed the GENCO model to consist of three basic modules: (1) input module, (2) bid optimization module and (3) post-mortem analysis module. These are now presented in some detail as they form the core of the overall model.
3.1.1
Input Module
The GENCO will not be able to compete successfully unless it is able to forecast energy and ancillary service prices. Other inputs are related to spe-
An Electric Energy Market Simulator
45
cific market rules for the clearing of bids. We discuss these in some detail below. The GENCO should be able to forecast market-clearing prices based on historical information and its relative market position [12]. The approach used in our modeling is a regression model, which relates market-clearing prices to: (a) overall system demand and (b) available generation by the GENCO. Given the system demand forecast, the GENCO can then predict the corresponding price forecast. Several price-forecast scenarios are provided based on uncertainties in the demand forecast. At a minimum, these are expected, pessimistic, and optimistic scenarios with associated probabilities of occurrence.1 Price forecasts are done for both energy (MWh) prices as well as ancillary service prices. A given GENCO sits somewhere between the two extremes of being (a) a pure price leader or (b) a pure price follower [12]. Furthermore, the GENCO may be constrained by socio/economic/regulatory factors, which would limit its ability to manipulate price, even if it has market dominance.2 The output 1 2
An alternative to this is fuzzy modeling of the uncertainty. For example, the GENCO may be concerned with anti-monopoly laws or excess profit regulation, which may arise out of aggressive practices.
46
The Next Generation of Unit Commitment Models
of this sub-module consists of: (1) limits on market share and (2) sensitivity of market prices and energy supply to GENCOs bid prices. Both of these are to be used in the bid optimization module.
3.1.2
Bid Optimization Module (BOM)
The BOM consists of two components, described below. Component 1: Deterministic bid optimization based on specific input scenarios The optimization is performed for two specific markets: (a) day ahead and (b) hour ahead markets.3 The market rules vary from market to market. Our approach models initially two types of market rules – (1) those which are based on LMP considerations, e.g., the PJM Interconnection, and (2) those based on bidding by scheduling coordinators4 using a PX, e.g., the California ISO. Thus, there are four basic sub-modules to consider. Day Ahead/LMP-Based. The bidding system for LMP-based day-ahead markets consists of a multi-part bidding process whereby the generation (and load) bidders are required to submit typically the following: Energy multi-block price curves which are piecewise constant No-load price bids Operating range (min and max MW) Minimum up-time Minimum down-time The ISO control center as a result performs a combination of unit commitment and contingency-constrained optimal power flow computations to yield an optimal solution. The performance criterion is the minimization of overall price to meet customer demand. When combined with elastic demand bids, it is possible to use the same software to maximize social welfare. Ideally, if every generation bidder submits his marginal cost data (plus a specified mark-up for profit), the result would be almost the same as that of a fully integrated utility system. The constrained OPF would minimize system losses. In case the ISO would pay for reactive power production, then the OPF would attempt to maximize profit from the use of reactive power production. From the perspective of the GENCO, the objective is to submit a bid that maximizes profit – at least at this initial deterministic level. Thus for each 3
4
It is possible to extend the functionality of this module to cover both real-time bids and longer-term forward market bids. Scheduling coordinators (SCs) are allowed to submit strictly balanced generation/load bids for the energy part of the market.
An Electric Energy Market Simulator
47
forecasted scenario, the control variables consist of the above bid parameters, as long as they do not violate technical limitations (such as bidding minimum up-time which is always greater than or equal to the technical minimum uptime). One of the key issues here is to ensure that the GENCO MarketParticipant is able to model its own cost information, including their nonconvex price incremental cost curves. Hour-Ahead/LMP-Based. Under this regime, the basic bidding process consists of incremental/decremental bids to allow for adjustments of schedules based on deviations from the day-ahead schedules. The main tool is strictly the OPF with an objective function to maximize market surplus. From the bidder’s perspective, the goal is to maximize profit. Day-Ahead/SC/PX5-Based. In the SC/PX-based market, the typical bidding process is decomposed into hourly energy price bid curves and other bids for congestion management and ancillary services. However, there is a distinction between a scheduling coordinator (SC) and the power exchange (PX). In California, the SCs are exposed to network congestion and ancillary service risks (and opportunities). Their main bid parameters to improve profitability consist of incremental/decremental (INC/DEC) bids for congestion management and ancillary service bids. In the simulation model the focus is strictly on congestion management bids. For GENCOs bidding through the PX, the main objective is to optimize hourly energy price bid curves. Furthermore, there is a question here whether portfolio bidding should be allowed. If portfolio bidding is permitted, then the GENCO has to perform optimization at two levels: one that uses a single curve for the entire company and a second that provides generation schedules at the cleared market prices. Again, the GENCO has the opportunity to bid into the congestion management and ancillary services market. Hour-Ahead/SC/PX-Based. This is similar to the day-ahead bidding system with the exception that portfolio bidding may not be allowed. Component 2: Bid optimization through risk management For each of the four bidding regimes, the GENCO optimization is performed for a set of scenarios. In the input module, there is a probability associated with each scenario. The key output here is a profit probability profile. The analysis would select a scenario that yields bid prices for the best profit/risk trade-off.
5
PX = Power exchange, whether independent or part of the central market clearing organization.
48
3.2
The Next Generation of Unit Commitment Models
Demand-Side Entities
For the purposes of the model under consideration, we distinguish the following demand-side entities: (a) Major Load Serving Entities (LSE) (e.g., distribution company, or commercial or industrial loads): An LSE may be able to bid a declining multi-block purchase price curves based on the composition of its load and the demand-side management systems in place (typically interruptible loads). The objective here for the LSE is to reduce the cost of purchases based on its price forecasts (and contracts already in place). (b) Pumped Storage Power Plants: These plants try to combine their generation bids with their demand bids (for pumping). The result is a composite optimization.
3.3
Independent System Operators (ISOs)
In our model, the ISO represents the component that implements the results of the bidding process to create a full schedule of system operation that meets regulatory reliability and security requirements. Normally, the ISO controls only its own area of responsibility (control area). Again, we distinguish between two types of ISOs: LMP-based and SC/PX-based.
3.3.1
LMP-Based ISO
The model of the LMP-based ISO permits the following functions to be performed: Issuance of ISO-demand forecast for the day-ahead and hour-ahead markets: The demand forecast is a net forecast for all demands to be met by participants in the day-ahead and hour-ahead markets. In essence, the forecast is adjusted by subtracting any bilateral contracts and export/import contracts, which are also bilateral in nature. Hourly optimization of the generating system and the network through a combination of unit commitment and contingencyconstrained OPF, as described above, based on the totality of the bids by the market participants. The optimization would yield LMPs, which are published and released to the market. Computation of congestion charges and firm transmission rights (FTR) payments.
An Electric Energy Market Simulator
49
Similar functions for (1,2, and 3) the hour-ahead market (no unit commitment is involved, however). Real-time system control through automatic generation control (AGC). The AGC utilizes an economic dispatch component which is based on the hour-ahead bid prices, or alternative bid prices for system regulation as an ancillary service
3.3.2
SC/PX-Based ISO
In this case, the following functions are supported: Demand forecast similar to the one in the previous section for the LMP-based ISO Congestion management for interzonal congestion as well as intrazonal congestion for both the day-ahead and hour-ahead markets Simultaneous and sequential ancillary services bid clearing Automatic generation control based on ancillary service bids for system regulation and load following
3.4
Power Exchange (PX) Model
There is no need for a separate PX model for the LMP-based system, simply because the ISO in this case clears the market using the various multipart bids. The PX model for the SC/PX-based market is quite simple as it just matches supply and demand curves. The PX, however, may engage in ancillary service markets and options/futures markets and these have to be taken into account.
3.5
Energy Service Provider (ESCO)
For the purposes of the market simulation model, the ESCO is a combination of a GENCOs and LSEs. A large ESCO may be bidding in multiple markets and these have to be modeled separately. The trading performed by the ESCO may combine a portfolio of contracts/bids to manage risk.
3.6
Overall Market Model
Figure 3 shows the resulting EMOS overall market model. We have designed the model for the following uses:
50
The Next Generation of Unit Commitment Models
(a) Studies and training by each market participant entity described above to improve its performance and meet its own needs. (b) Studies at regional or national levels to evaluate different market designs. (c) On-line activities by MPs, including energy bidding strategies, ancillary services bidding, market surveillance, etc., whenever the system is linked to real-time data sources. Again, a given market participant should be able to model its own activities using its own proprietary systems.
3.7
Note on Implementation
The EMOS is implemented using standard software applications developed primarily by EPRI and other developers. These include:
An Electric Energy Market Simulator
51
EPRI-OTS by EPRI for the primary PSM modeling EPRI-DYNAMICS unit commitment program for various market participant modules EPRI ANN-STLF for short-term load forecasting DSI-OPF for the multi-area optimal power flow interfaced with EPRI-DYNAMICS Other components of the EMOS are still under development. The overall system uses an effective database system which is compliant with EPRI’s common information model [1].
4.
CONCLUDING REMARKS
The development of an overall market model for the electric energy industry under restructuring is a major challenge mainly because the electric physical system is highly complex, changes constantly, and creates a significant amount of physical risk to market participants (MPs). The overall market model consists of an interacting population of MPs. Market rules and designs are aimed at coordinating all efforts through ISO’s. The model implementation is based on such developments to allow for effective interoperability and plug-compatibility among various applications. We expect that the developments reported here can be used in a variety of ways by each MP type: GENCOs, LSEs, ISOs, PXs and ESCOs. The main uses consist of: Just-In-Time training of personnel – traders, dispatchers, operations engineers and managers Enhanced mechanisms for improving competitive positions by traders Ability of ISOs and market designers to analyze the behavior of market participants and test improvements in market rules and overall market design Unit commitment as such is used as a tool whenever applicable. The main users of UC are the GENCOs, ESCOs, and some ISOs with multi-part bidding market rules.
ACKNOWLEDGEMENTS The developments reported in this chapter are under the sponsorship of the National Science Foundation (NSF) under SBIR Phase II Grant, DMI-980 10161. The EPRI-OTS developments and related enabling technologies have been partially sponsored by EPRI, Palo Alto, California.
52
The Next Generation of Unit Commitment Models
REFERENCES 1.
2.
3.
4. 5.
6.
7. 8.
9.
10. 11. 12. 13.
14.
15. 16.
17. 18.
A. Debs, Y.-C. Wu, and C. Hansen. “Enhancement of the EPRI-OTS for the Restructured Electric Utility,” Project Reports, Decision Systems International, Atlanta, Georgia, under Small Business Innovations Program of the National Science Foundation. A. Debs and C. Hansen. “The Total Power System Simulator: A Comprehensive Tool for Operation, Control and Planning.” In Proc. Arab Electricity ’97 Conference & Exhibition, PennWell Europe and DSI, Bahrain, 1997. A. Debs and C. Hansen. “The EPRI-OTS as the Standard for Training and Studies in the New Era: Strategy for Global Application.” Presentation at the First Asia Pacific Conference on Operation and Planning Issues in the Emerging Electric Utility Environment, sponsored by EPRI, Kuala Lumpur, Malaysia, 1997. M.K. Enns, et al. Considerations in designing and using power system operator training simulators. EPRI EL-3192: 1984. V. Calovic and A. Debs. “The Fully Integrated DTS for ESB, Dublin. ” In Proc. EPRI First European Workshop on Power System Operation and Planning Tools, Amsterdam, The Netherlands, 1995. C. Hansen and M. Foley. “Power System Model Enhancement at ESB, Dublin.” In Proc. EPRI First European Workshop on Power System Operation and Planning Tools, Amsterdam, The Netherlands, 1995. S. Lutterodt and A. Debs. “Issues in Use of Operator Training Simulators.” Paper presented at the CEPSI Conference, Kuala Lumpur, Malaysia, 1996. A. Debs and F. Rahimi. “Modern Power Systems Control and Operation in the Restructured Environment.” Class notes for intensive short course by Decision Systems International, San Francisco, CA, 1999. A. Debs, P. Gupta, C. Hansen, A. Papalexopoulos, and F. Rahimi. “System Planning in the Context of Competition and Restructuring.” Class notes for intensive short course by Decision Systems International, San Francisco, CA, 1996. M. Ilic, F. Graves, L, Fink, and A. DiCaprio. Operating in the open access environment. Elec. J., 9(3): 61-69,1996. A. Debs. Modern Power Systems Control and Operation. Norwell, MA: Kluwer Academic Publishers, 1988. B. Sheblé. Computational Auction Mechanisms for Restructured Power Industry Operations. Boston, MA: Kluwer Academic Publishers, 1999. A. Papalexopoulos. “Design of the Wholesale Market in the USA.” In Proc. EPRI Second European Conference – Enabling Technologies and Systems for the Business-Driven Electric Utility Industry, Vienna, Austria, 1999. Y.C. Wu, A.S. Debs, and R.E. Marsten. A direct nonlinear predictor-corrector primal-dual interior point algorithm for optimal power flows. IEEE Trans. Power Syst., 9(2): 776-883, 1994. H. Kim and R. Baldick. Coarse-grained distributed optimal power flows. IEEE Trans. Power Syst., 12(2): 932-939,1997. A. Debs. “The OPF in the Deregulated Environment.” Lecture notes for intensive short course by Decision Systems International: Modern Power Systems Control and Operation, San Francisco, CA, 1996. A. Papalexopoulos, et al. Cost/benefits analysis of an optimal power flow: The PG&E experience. IEEE Trans. Power Syst. 9(2): 796-804, 1994. Y.C. Li and A.K. David. Optimal multi-area wheeling. IEEE Trans. Power Syst., 9(1): 288-294, 1994.
Chapter 4 AUCTIONS WITH EXPLICIT DEMAND-SIDE BIDDING IN COMPETITIVE ELECTRICITY MARKETS A. Borghetti University of Bologna, Italy
G. Gross University of Illinois at Urbana-Champaign
C. A. Nucci University of Bologna, Italy
Abstract:
1.
This paper focuses on the development of a model for and the simulation of electricity auctions with demand-side bidding (DSB) explicitly considered. We generalize the competitive power pool (CPP) framework developed in [1] to include DSB. In order to allow customers to play a proactive role in the price determination process, the DSB provides the opportunity for them to submit bids for load reductions in specific periods. We study the behavior of DSB inclusion in electricity auctions simulations obtained with a specially developed Lagrangian relaxation scheme that effectively takes advantage of the structure of the problem. We present some numerical results for a 24-hour simulation on a small system. This case study is effective in illustrating the various economic impacts of DSB including system efficiency effects, changes in the system marginal price and the load recovery effects.
INTRODUCTION
This paper deals with the development of a model for the simulation of electricity auctions with demand-side bidding (DSB) explicitly considered. The model is a generalization of the competitive power pool (CPP) framework developed in [1] to include DSB. Such a mechanism has been used at times in the England & Wales Power Pool by large industrial consumers who can offer their ability to reduce load directly to the Pool and receive a payment for actually making such a reduction possible [2,3].
54
The Next Generation of Unit Commitment Models
In the CPP with only supply-side offers, the point of intersection of the aggregate supply curve and the fixed forecasted load determines the marketclearing price. To improve competition, the consumers may be allowed to participate in the market price definition process by providing them the opportunity to submit bids. Without DSB, the system marginal price (SMP) is determined by constructing the supply curve from the offers submitted by the supply-side bidders and determining the uniform price paid to all bidders who are selected to serve the fixed forecasted load demand. The basic idea in the application of DSB is to use the demand profile to lower SMP by cutting load during peak periods. DSB may take advantage of large industrial customers who can cut load or shift load to benefit from lower electricity prices. Since industrial customers are not expected to reduce significantly their daily energy consumption, the overall effectiveness of DSB depends on the how, the how much, and the when of the energy recovery. Clearly, the more flexibility such a customer has, the more possible it becomes for him to participate in DSB. The demand recovery is typically a function of the weather, of the economic conditions as well as of the number of reduction periods, and the amount of load cut in each period. In [4] an analysis has been presented of data relevant to a four-year period for a regional electricity company (REC) in the United Kingdom that quantifies the extent of intertemporal substitution in electricity consumption across pricing periods within the day for five groups of different industries. Every industry shows electricity substitution possibilities with its own firm-specific characteristics. We have constructed an econometric model from the results of this analysis. This model is for the use of the REC to formulate its demand-side bids and as such takes into account the specific pricing scheme and rules adopted in the England & Wales Power Pool. There are additional data available on the characteristics of the load recovery from experiences gained with the application of commercial/industrial and residential load control programs [5-7]. In this case, there is electricity substitution only across adjacent load periods, i.e., the energy is recovered in the periods that follow right after the reduction periods. In this paper, we simulate and study the inclusion of DSB in electricity auctions to examine various economic and policy aspects in DSB. The simulation tool implements a Lagrangian relaxation-based scheme, which takes advantage of the problem structure with the inclusion of DSB. The sufficiently detailed representation of the supply-side bidders allows the modeling of the unique physical characteristics of the power generation system. In particular, it takes into account the main operating considerations including the operational limits and up- and down-time constraints. The supply-side bidders are also allowed to include in their bids a separate price for start-up in addition to the price for the MWh commodity. In the simulation tool, the impact of DSB is taken into account by incorporating specific energy con-
Auctions with Explicit Demand-Side Bidding
55
straints and load recovery into the Lagrangian relaxation algorithm. Researchers have applied Lagrangian relaxation methods widely in recent years for the solution of unit commitment problems for large-scale systems due to their ability to include a more detailed system representation than would be possible with other techniques [8]. Some aspects of DSB have been analyzed in [9,10]. The studies indicate that the specific characteristics of the demand-side bidders have a substantial impact on the system economies. However, additional work is required to better quantify such impacts. This chapter aims to bring additional insight to the study of DSB. The principal combinations are the development of a generalized framework for the analysis of various aspects of DSB and the illustration of the salient characteristics through the simulations obtained with the tool developed for the implementation of this framework. The chapter is organized as follows. In section 2, we present the generalization of the CPP structure with the inclusion of DSB into the CPP framework and a description of the Lagrangian relaxation-based algorithm for its solution. In section 3 we present some numerical results obtained for a 24hour simulation on a small system. We compare costs and price signals obtained from DSB in addition to supply-side bidding (SSB) to costs and price signals obtained from the use of only supply-side bidders. The paper provides an analysis of the numerical results. Section 4 offers final thoughts on this research, and the Appendix presents details concerning the implemented code and the power system data.
2.
GENERALIZATION OF THE COMPETITIVE POWER POOL FRAMEWORK FOR INCLUSION OF DEMAND SIDE BIDDING
We start with the extension of the CPP framework developed in [1] to include DSB in addition to SSB. With the addition of DSB, the CPP dispatcher problem is to select the winning bids and offers from the set of both supply-side offers and demand-side bids. We use henceforth the term bid to refer to both the supply-side offer and the demand-side bid and we refer to each player as a bidder. Each bid has three components: the bid variable price which describes the per hour price as a function of MW provided/reduced. The function is here assumed to be a quadratic or piece-wise linear function; the bid start-up price which is charged whenever the bidder is committed; and the bid offered capacity
which is a vector whose
56
The Next Generation of Unit Commitment Models
component is the maximum capacity offered by the bidder for use in period t, expressed as a fraction of the maximum output. The supply- and demand-side bids have different characteristics. In particular, for the case of SSB, we have made the assumption that the operational data1, including the minimum and maximum output and and minimum up- and down-times and need to be provided by each bidding plant i. Moreover, the bid start-up price which is charged whenever unit i is started in period t, is assumed to be a function of the down time of unit i at period t-1
where is the thermal time constant of unit i, I is the number of supply side bids, is a constant related to the cold start charge, and is a constant related to the fixed operating and maintenance charges [11]. The characteristics of the demand-side schemes require the specification of the following information for each demand-side bid j,j=1, ..., J: the bid start-up price that is considered a constant value the subset of the operator-designated load-reduction periods that is the subset of the periods dertake load reduction the minimum and maximum demand
in which bidder j may unand
that can be re-
2
duced by bid j the subset of the operator-designated load-recovery periods
that
is the subset of the periods in which bidder j may undertake a load recovery load recovery at period h, that is related to all the load reductions in each reduction period of by the following expression
1
2
We do not take ramp and network constraints into account in the model discussed in this chapter. Note that a requirement is introduced in the problem formulation to ensure that the sum of the maximum load reductions of all the demand-side bids in a period t cannot exceed the load forecasted for that period.
Auctions with Explicit Demand-Side Bidding
where
57
represents the load recovery ratio in period h of the load
reduction
in period t.
The above representation of load recovery is similar to that used in [9]. It allows the representation in a flexible and simple way of the electricity substitution characteristics of consumers who may participate in load modification. It allows, moreover, load recovery to occur both in pre- and post-load reduction periods. In [9] it is pointed out that the beneficial effects of DSB are greatly attenuated if some bidders recover their load in the same periods in which others are reducing it. Therefore, we shall assume that there are no overlapping periods in which the load reductions and the load recoveries may cancel each other out. By taking into account both load reductions and load recoveries, the actual load in reduction period t is given by
and the actual load
where
and
in recovery period h is given by
are the forecasted loads in period t and h, respectively.
The additions of the relations for the DSB participation do not change the basic structure of the framework in [1]. Consequently, we can extend the Lagrangian relaxation framework developed in [1] to the more general model described here. For this purpose, we use the following notation:
I: J: T: D:
the number of supply-side bidders the number of demand-side bidders the number of time periods the T-dimensional vector of the load demands in each period t in the scheduling horizon the T-dimensional vector of the zero-one variables indicating whether supply-side bidder i is committed in period t or not the T-dimensional vector of the zero-one variables indicating whether demand-side bidder j is committed in period t or not the T-dimensional vector of the amount of power that the supplyside bidder i is producing in period t the T-dimensional vector of the amount of power that the demand-side bidder j is reducing in period t.
58
The Next Generation of Unit Commitment Models
The CPP dispatcher problem determines the most economic commitment that satisfies the forecasted demands D without violating physical and operating constraints of the generation equipment and demand specifications.
subject to initial conditions and, by taking into consideration equations (2) and (3), subject to
We refer to the optimization problem in equations (4)-(7) as P. While the demand-side bids are defined similarly to supply-side offers, problem P differs from problem with only supply-side bidding. In fact, the incorporation of DSB adds the two decision variables w and y that are characterized by specific constraints specified in (7). The solution approaches with and without DSB are similar. Also with the introduction of new DSB decision variables w and y, the Lagrangian relaxation approach allows the decomposition of P into I+J sub-problems associated with each supply-side and demand-side bid. With the inclusion of DSB, we use the following Lagrangian dual function
or, more explicitly, taking into account (4),
Auctions with Explicit Demand-Side Bidding
59
subject to the specified initial conditions and to constraints (6) and (7). t= l,...,T, are non-negative Lagrange multipliers. The dual function is rearranged as
where, for supply-side bid i
and, for demand-side bid j, by explicitly taking into consideration equations (2) and (3),
subject to the specified initial conditions and to the constraints (6) and (7). Problems (10) and (11) are the I + J sub-problems, one for each bidder, that need to be solved. In order to find the optimal values of the multipliers to use in equations (10) and (11) the following dual problem is solved
60
The Next Generation of Unit Commitment Models
In fact, L * provides a lower bound of the final solution of the primal problem P [12]. As a by-product of the process of maximizing L we obtain the optimal Lagrange multipliers and a system schedule {u, w, p, y} resulting from the solution of the Lagrangian relaxation for In certain cases, this system schedule does not satisfy the conditions imposed by the demand constraint and, therefore, a practical approach for computing a near-optimal schedule has to be implemented [13]. It may be useful to note that the optimal schedule, obtained with the solution of the proposed framework, is the one that minimizes the total “production” costs, i.e., the costs paid to satisfy the forecasted demand, on the basis of the bids of the supply-side and demand-side bidders. The solution can differ, in general, from the schedule that minimizes the consumer payments, for the various reasons cited in [14].
3.
NUMERICAL RESULTS
We implemented the solution approach based on the extended framework for the inclusion of DSB as a software package. Some of the salient aspects of this package are summarized in Appendix A. This package has been used to perform many numerical studies to assess the characteristics and the impacts of DSB in a competitive power pool. To illustrate the application of the generalized framework, we present some typical results of our simulation studies. We use the 10-unit system in [13] as the supply side of the resources. The operational data and the bid functions used for the supply-side bidders are given in Appendix B. The behavior of the power pool is simulated for the 24-hour period load profile of Table B.1 in Appendix B. Figure 1 plots the hourly loads. The load reductions are dispatched on the basis of the demand-side bids that represent the prices at which the bidders wish to reduce their consumption by the specified amounts. The bidder that is scheduled to reduce its consumption in a certain period is also allowed to recover its load partially or totally in other periods. The model specifies the periods in which load reduction and load recovery are allowed. These periods have been defined in the previous section as the operator-designated load-reduction periods and load-recovery periods To show the influence of such a constraint, the results of a sensitivity study are presented. The study was carried out by varying only the following two triggering levels: the load-reduction triggering level as a fraction of the peak load, specifies the load level above which the load reductions are allowed; and
Auctions with Explicit Demand-Side Bidding
61
the load-recovery triggering level as a fraction of the difference between the peak and the base load, specifies the load level below which the load recoveries are allowed. For each given and values, the corresponding permitted reduction and recovery periods, and respectively, are then established. The load recovery is considered uniform throughout the recovery period. We discuss the results of several simulations on this system with a single demand-side bidder in addition to the ten supply-side bidders. The demandside bidder limits are and The demand-side bid is 1 $/MWh with 1 $/h being the no-load bid. These values were selected specifically to provide a lower cost per unit of energy to the CPP dispatcher on the demand side than the supply-side. We start out with a case in which, the DSB is allowed whenever the load exceeds For this case is set at 0.5. The periods when load reductions are allowed, are The corresponding recovery periods
are
and the recovery is implemented to spread the recovery of load in equal amounts in each of the periods in
62
The Next Generation of Unit Commitment Models
To assess the impact of DSB, we use the no-DSB case as the reference basis. We show in Figure 2 the modified loads as a result of DSB under different levels of load recovery. These levels of load recovery are indicated by the recovery fraction value, that is the total amount of load recovery over the total amount of reduced load. In Figure 3, we depict the corresponding impact on the system marginal prices (SMP). For the supply-side bidding strategy used, the system marginal prices track closely the modified system demands Furthermore, DSB, in effect, acts to “smooth” out the price variations across periods. We now evaluate the impacts of varying some of the parameters in DSB implementation. One parameter that has a major impact on deployment of DSB is the load reduction recovery factor. This parameter is the ratio of the recovery energy to the cut energy. As this factor decreases from 1 to 0, the savings increase with respect to the costs for the case without DSB (what we shall call reference costs). Figure 4 shows results for the test system. The assessment of DSB on the variability of the SMP is important. DSB tends to impact prices in different periods lowering the prices in periods with higher loads and increasing them in periods with lower loads. We evaluate the hourly average SMP, as well as the volatility impacts in terms of the standard deviation as a function of recovery fraction. Figure 5 gives these results with the no-DSB case as reference. While there is a reduction in the volatility, a reduction in the average value of the SMP is not obtained for all
Auctions with Explicit Demand-Side Bidding
63
recovery fractions. The reason is that the schedule is obtained without a minimization of consumer payments. In the case of DSB without load recovery, the reduction of the volatility is only due to the reduction of the SMP in the peak periods. Therefore, the reduction in the volatility is lower in this case than for the case in which there are both the reduction in the price in the peak periods and the increase of the price in load recovery periods. We note that at the higher fraction of load recovery, DSB is committed in only a limited number of periods, and as such both the savings and the reduction in price volatility are limited. An important aspect to examine is the impact of different triggering levels for the definition of the operator-designated load-reduction and recovery periods. For the test system we evaluate the savings with respect to the reference DSB case for sixteen different triggering levels under the fixed load recovery fraction of 0.8. Table 1 gives the data, and Figure 6 presents the plots as a function of the reduction triggering levels for different values of Due to the fewer number of periods in which the demand-side bidder may be committed, higher reduction triggering levels result in lower savings. On the other hand, the effect of the recovery triggering level is less uniform: as the recovery triggering level increases, the number of recovery periods increases and the recovery of the load decreases in each recovery period. In the case of the higher recovery triggering levels, the recovery periods are in the shoulder load periods resulting in a decrease in the savings compared to the lower values of
64
The Next Generation of Unit Commitment Models
Auctions with Explicit Demand-Side Bidding
65
We examine the impact on loads and SMPs for as a function of Figure 7 shows the load modifications, and Figure 8 depicts the impact on the SMPs. These plots make more concrete the observations in the previous paragraph on the impacts of different We next discuss the impacts of a single-supply unit’s bidding strategy on the market. We focus on the unit 9, and we obtain the results in Figures 2-8 with the bid of unit 9 declaring unavailability in periods 10 to 21. A supplyside bidder for various reasons or market objectives may select such “strategic” behavior. When unit 9 changes its bid and declares availability for the periods 10-21, the total costs without DSB change $537,271. This change
66
The Next Generation of Unit Commitment Models
Auctions with Explicit Demand-Side Bidding
67
represents a saving of $3,186 with respect to the reference case of no-DSB without the participation of unit 9 for the periods 10-21. From Figure 4, we can see that such a saving is lower than the saving obtained with DSB recovering the entire energy. We may, therefore, interpret the impacts of DSB to include its ability to mitigate the market power on the supply-side. Thus far, we have concentrated on displaying the salient characteristics of DSB through a single demand-side bidder. The rationale for this was to provide a good insight into the interaction of the DSB with the electricity market. We next study the case with multiple DSB bidders. To illustrate the behavior of DSB with multiple demand-side bidders, we consider two cases: (i) five DSB bidders and (ii) nine DSB bidders. We compare the behavior in these two cases to that in the case of the single bidder discussed above. For these cases, the demand-side bidders have and the load recovery fraction is 0.9. Recall that for the single DSB bidder, the bid is 1 $/MWh with 1 $/h being the no-load amount and In case (i) the bids are 1, 2, 3, 4, and 5 $/MWh, respectively, with 1 $/h the no-load amount for each bidder. In case (ii) the bids are 1, 1.25, 1.5, 1.75, 2., 2.25, 2.5, 2.75, and 3 $/MWh with 1 $/h the no-load amount for each bidder. In the two cases is 200 MW for each DSB bidder. Figures 9 and 10 provide plots of the results obtained with the five and nine demand-side bidders together with the results obtained with the single DSB bidder. Figure 9 gives the impacts on the load modification, and Figure 10 displays the impacts on the hourly SMPs. The number of demand-side bidders has been chosen to exceed the number that is committed in the multiple-bidder cases: in (i) only two are committed, and in (ii) only five are committed with the fifth being committed only for a single period in the hour 10.
4.
CONCLUSIONS
This chapter focused on the integration of DSB into electricity markets. We discussed the development of a general framework for the inclusion of DSB in addition to supply-side bidders. We used the Lagrangian relaxation based solution approach to examine the impacts of DSB. The tool we developed for simulation is very useful for investigating a wide spectrum of policy issues. In our case, we have used this tool to examine the ability of DSB to mitigate the potential for exercise of market power by the supply-side bidders. In addition, the impacts of DSB on smoothing system marginal prices and on mitigating price volatility are important attributes as indicated by the numerical results.
68
The Next Generation of Unit Commitment Models
Auctions with Explicit Demand-Side Bidding
69
The numerical studies of the paper provide good insights into various aspects of DSB. In particular, it is important that load reductions and load recoveries do not cancel each other out. Therefore, the specification of permitted load reduction periods and permitted load recovery periods has been added to the model. The results of a sensitivity analysis show that the specification of appropriate triggering levels, that define the permitted load reduction periods and permitted load recovery periods, is particularly critical to make effective use of DSB. In the chapter, we provide a simple example to study multiple DSB players. The impacts of competition and possible collusion among DSB players need to be investigated in more depth. Also, there are many additional policy issues that remain to be examined. One key issue for further study is that of DSB remuneration, including the needs for such incentives and the levels at which to set them. The changes in supply-side bidder behavior brought about by the inclusion of DSB are another key issue that requires investigation.
ACKNOWLEDGMENTS We are grateful for the financial support for the research reported here from the Italian National Research Council. George Gross received support from the Power System Engineering Research Center administered by Cornell University.
REFERENCES 1. 2. 3. 4. 5. 6. 7.
G. Gross and D.J. Finlay. “An Optimization Framework for Competitive Electricity Power Pools.” In Proc. PSCC, 815-823, 1996. F.A. Wolak and R.H. Patrick. The impact of market rules and market structure on the price determination process in the England and Wales electricity market. Working Paper PWP-047, University of California Energy Institute, 1997. D.W. Bunn. Demand-side participation in the electricity pool of England and Wales. Decision Technology Centre report, London Business School, 1997. R.H. Patrick and F.A. Wolak. Estimating the customer level demand for electricity under real time pricing. Working Paper, Department of Economics, Stanford University, 1997. D.V. Stocker. Load management study of simulated control of residential central air conditioner on the Detroit Edison Company system. IEEE Trans. Power Apparatus Syst., 4: 1616-1624, 1980. A.I. Cohen, D.H. Oglevee, and L.H. Ayers. An integrated system for residential load control. IEEE Trans. Power Syst., 3: 645-651, 1987. C.N. Kurucz, D. Brandt, and S. Sim. A linear programming model for reducing system peak through customer load control programs. IEEE Trans. Power Syst., (11)4: 18171824, 1996.
The Next Generation of Unit Commitment Models
70 8. 9.
10. 11.
12. 13. 14. 15. 16.
A.J. Svoboda and S.S. Oren. Integrating price-based resources in short-term scheduling of electric power systems. IEEE Trans. Energy Conversion, (9)4: 760-769, 1994. G. Strbac, E.D. Farmer, and B.J. Cory. Framework for the incorporation of demand-side in a competitive electricity market. In IEE Proc. – Generation, Transmission and Distribution, (143)3: 232-237, 1996. G. Strbac and D. Kirschen. Assessing the competitiveness of demand side bidding. IEEE Trans. Power Syst., (14)1: 120-125, 1999. J. Gruhl, F. Schweppe and M. Ruane. “Unit Commitment Scheduling of Electric Power Systems.” In System Engineering for Power: Status and Prospects, LH Fink and K. Carlsen eds., Henniker, NH, 1975. A. Geoffrion. Lagrangian relaxation for integer programming. Math. Prog. Study, (2): 82-114, 1974. J.F. Bard. Short-term scheduling of thermal-electric generators using Lagrangian relaxation. Oper. Res., (36)5: 756-766, 1988. S. Hao, G.A. Angelidis, H. Singh, and A.D. Papalexopoulos. Consumer payment minimization in power pool auctions. IEEE Trans. Power Syst., (13)3: 986-991, 1999. R. Fourer, D.M. Gay and B.W. Kernighan. A modeling language for mathematical programming. Manage. Sci., (36): 519-554, 1990 B.A. Murtagh and M.A. Saunders. “MINOS 5.1 User’s Guide.” Technical Report SOL 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, 1987.
APPENDICES A.
Development of a Computer Program for Validation of the Proposed Approach
We have developed a computer program incorporating both supply-side and demand-side bidding. The program allows multiple demand-side bidders and supply-side bidders to interact for meeting a load profile over a specified period. The generality of the program allows us, in particular, to study the characteristics of the demand-side bidders and the influence of their parameters on the results. For the Lagrangian relaxation implementation we have followed the procedure proposed in [13]. To solve subproblems (10) and (11), the values of are, at first, considered assigned as well as the values of the zero-one decision variables and It follows that these subproblems, for supply-side bid i and demand-side bid j, respectively, become
Auctions with Explicit Demand-Side Bidding
71
subject to upper/lower limits specified in equation (6) (without the minimum up/down constraints) and in equation (7). These problems are piece-wise or quadratic problems (it depends on how the bid variable price function is defined), and can be solved with a linear or quadratic programming technique. These optimizations give the values of power productions and load reductions To find the optimal values for the decision variables and we solve subproblems (10) and (11) using the values of and in a forward dynamic programming, taking into account the start-up prices and the minimum up-/down-time constraints. In the case of demand-side bidder problem (11) the dynamic programming approach differs from that of supply-side bidders. In particular, to take into account the load recoveries, we add the following term to the values corresponding to the states in which demand-side bid j is committed at period t
This term represents the contribution to the function of all the load recoveries due to the scheduled load reduction at period t that has to be minimized in equation (11). Because of the presence of this additional term, the solution of the problem (A.2) and the dynamic programming procedure are included in a loop that ends when two consecutive solutions result in the same commitment, i.e., in the same values of the zero-one decision variables To find the maximum value L * of equation (12), we use a standard subgradient technique [12]. With this technique, the solution process is iterated, starting from a set of tentative values of multipliers and at each iteration k the multipliers are updated using
where, taking into consideration equations (2) and (3),
72
The Next Generation of Unit Commitment Models
and denote the current solution (iteration k) of the dual problem and the lowest available solution of the primal one, which represent the lower and upper bound of the final solution at iteration k, respectively. is a scalar parameter that is progressively reduced whenever the solution of the dual problem is not improved. To implement such a technique, we need to find a feasible solution for the primal problem P at each iteration. This is accomplished by adopting the priority-list heuristic procedure proposed in [13], based on the calculation of the marginal costs associated with each supply-side bidder and each period. The heuristic procedure is implemented in such a way that it does not change w, i.e,. the commitment of the demand-side bidders. The procedure here described is stopped when the relative duality gap (defined as is lower than a specified value. We implement the program in the algebraic modeling language for mathematical programming called AMPL [15]. This language is particularly useful for the piecewise linear representation of the cost functions. A major advantage of the modular structure resulting with the AMPL implementation is the ability to use a library of solvers. In this paper the MINOS [16] solver has been used to solve the problems (A.1) and (A.2).
B.
Case Study System Data Table B.1 gives the load profile.
Ten generators, considered as supply-side bidders, compose the supply system. Tables B.2, B.3, and B.4 show the supply-side bidder data and have been adapted from those used in [13]. Table B.1 shows the values of the minimum and maximum power outputs the minimum up- and down-times and the initial status of the units i.e., the number of
Auctions with Explicit Demand-Side Bidding periods the unit had been up
73
or down
In Table B.3 the quadratic expression of the cost data of [13] is converted into piecewise linear form so that the bid variable price is specified by 6 parameters: the no-load price three incremental prices two elbow points respectively.
and
Table B.4 displays the values of the components of the bid start-up price defined in equation (1).
74
The Next Generation of Unit Commitment Models
Chapter 5
THERMAL UNIT COMMITMENT WITH A NONLINEAR AC POWER FLOW NETWORK MODEL Carlos E. Murillo-Sánchez and Robert J. Thomas Cornell University
Abstract: This chapter presents a formulation of the thermal unit commitment
problem that includes nonlinear power flow constraints, thus allowing a more accurate representation of the network than is possible with DC flow models. This also permits potential VAr production to be used as a criterion for commitment of otherwise expensive generators in strategic locations. We use a Lagrangian relaxation framework with duplicated variables for each active and reactive source, permitting the exploitation of the separable structure of the dual cost. Results for medium-sized systems in a parallel processing environment are available.
1. INTRODUCTION The central theme surrounding the use of Lagrangian relaxation for the unit commitment problem is that of separation. Ever since the early papers [1, 2] this separability was the objective and for a good reason: the unit commitment problem, as a mixed-integer mathematical program, suffers from combinatoric complexity as the number of generators increases. This is what dooms other algorithms intended for solving it, such as dynamic programming: the combined state space of several generators in a dynamic program is too large to be able to attack many realistic problems, even with limited memory schemes. Classical Lagrangian relaxation permits the decomposition of the problem into several one-machine problems at each iteration; the coupling to other constraints involving more machines is achieved by sharing price information corresponding to the relaxed constraints, which is updated from one iteration to another. The complexity of a given iteration becomes linear in the number of discrete variables. The price to pay is that of switching to an iterative method
76
The Next Generation of Unit Commitment Models
rather than a direct method, as well as giving up certainty of global optimality if there is a duality gap. This last drawback is not as bad as it seems, however; very small duality gaps are routinely obtained using Lagrangian relaxation. The unit commitment problem can be formulated generally as:
where
Length of the planning horizon Number of generators to schedule Real power output for generator at time Reactive power output for generator at time On/off status (one or zero) for generator at time
The total production cost The sum of any startup costs A set of dynamic generator-wise constraints A set of static instantaneous system-wide constraints A set of nonseparable constraints. The production cost function F is assumed to be convex (in fact, quadratic) and separable over each generator and time period:
For our purposes, the constraints in the problem have been classified into three kinds. Category groups constraints that pertain to a single generator, but may span several time periods. These include minimum up or down times and ramping constraints. Category groups constraints that span the complete system but involve only one time period, such as load/demand matching, voltage limits, reserve constraints, and generation upper/lower limits. Finally, category groups constraints that involve more than one generator and more than one time period. A typical example is the infeasibility of turning on more than one unit at a time in a given location because of crew constraints. To show the specific type of separation achieved by means of Lagrangian relaxation, we take a look at the work of Muckstadt and Koenig [2]. They considered a lumped one-node network with losses modeled as fixed penalty factors. They also considered reserve constraints. We write an example formulation including demand and reserve constraints, the relaxation of which yields the Lagrangian
Thermal Unit Commitment with Nonlinear AC Power Flow
77
where is the real power demand in period is the desired minimum total committed capacity for the same period, and is the upper operating limit for the ith generator. Consider the dual objective
and the corresponding dual problem
which can be written explicitly in the following form after collecting terms on a per generator basis:
Thus, for fixed and evaluation of amounts to solving single-generator dynamic programs of the form
separate,
The dynamic programs can readily accommodate constraints such as minimal up or down times. Transition costs can easily include cold start or warm start costs, derived from either banked or total shut-downs. Ramp-rate constraints can also be introduced by discretizing the generation domain for the unit, though the dynamic program grows considerably. For a detailed description of a dynamic programming graph including most of these constraints, see reference [3]. After confirming that the evaluation of the dual functional is simple, a dual maximization algorithm can be readily applied to since the sub-gradient is easy to compute from Equation (3). A method as simple as a Poljak’s subgradient ascent or as sophisticated as a bundle method [4] can be utilized. A proper algebraic constraint structure is the key to the separability of the dual functional. Note that the step from Equation (3) to Equation (6) was possible due to the fact that the constraints are affine in the optimization variables. We want to separate the variables on a per-generator basis, so, failing affinity, we need at least separability into sets of variables related to a single generator each. The unit commitment problem has such separability as long as the system-wide constraints are separable by generator. Thus, general nonlinear constraints cannot be readily included in the model, at least not directly. We will show a way around this later.
78
The Next Generation of Unit Commitment Models
2. THE CASE FOR AN AC POWER FLOW MODEL In the past 20 years, many advances have been made, enhancing the number and type of constraints that can be treated, addressing convergence issues when the production costs are not strongly convex, and so on. In particular, transmission line constraints have been included by using the so-called DC power flow network models. These constraints, being linear, can be relaxed with appropriate multipliers and the dual functional will still be separable by generator. There are, however, genuine engineering considerations for including a nonlinear AC flow model. These considerations stem from the fact that some very important system constraints can only be modeled accurately with a full-blown AC power flow model. For example, in an actual transmission line the limit is best expressed as a limit in the current, whereas a transformer’s capacity is best described by its MVA rating. Both actual MVA loading and current depend on its orthogonal active and reactive components. The DC flow model can only predict (and even then, only for relatively small angle deviations and under a nominal voltage assumption) the active component, and therefore it is easy to find situations in which it does a poor job of modeling important constraints. Active branch limits inextricably tie together active and reactive dispatch restrictions; if the reactive component is large, the dispatch obtained by the DC flow-based unit commitment algorithm may have to be altered to comply with actual line limits, or conservative limits may have to be used. Other limits that cannot be modeled accurately via linear approximations are voltage limits. Appropriate voltage levels are crucial to the operation of most electrical apparatus, and it is not uncommon to find so-called “must run” generators that are needed not so much because of their actual power generation capacity, but because of their reactive power capacity. In order to raise the voltage to levels that are adequate for consumers, sometimes large amounts of reactive power are needed at specific locations in the network, even if the only sources are generators that are costly to operate. Granted, common practice to this day is to use linear network models for constrained economic dispatch, and in many cases accuracy is good enough. The reason why they work, however is that usually the only branches that are modeled are tielines, which tend to have controllable reactive compensation in order to keep power factors near unity. Linear congestion models work best if unity power factor is maintained. They become inaccurate if used to approximate thermal limits over broad ranges of voltage and reactive and active injections, especially if the branch being represented does not have dispatchable reactive compensation. In summary, current Lagrangian relaxation algorithms using DC flow-based network constraints or other linear approximations may do poorly enforcing voltage limits and true current or MVA limits in grids requiring large reactive injections. As a result of the limited accuracy of this network representation, it is quite possible that a solution obtained by such an algorithm is actually infeasible, requiring additional generators to be committed in order to meet voltage or congestion constraints.
Thermal Unit Commitment with Nonlinear AC Power Flow
79
We find some of the works that have followed the DC flow formulation in their incorporation of line limits to the dual maximization in [5, 6, 7, 8, 9, 10, 11]. In [12], the authors use linear approximations to include the voltage constraints in the formulation, but it is not clear that a linear approximation will work under large excursions in the reactive dispatch. Baldick [8] uses a general formulation that could in principle be used to address AC flow constraints, and he elaborates a little more in the speculative paper [13], although the authors do not seem to have actually implemented their scheme. The formulation proposed in this work was first reported in [14]. It uses fewer multipliers and, by explicitly employing an augmented Lagrangian, should have improved convergence properties.
3.
FORMULATION AND ALGORITHM
Our approach has its origins in the variable duplication technique credited to Guy Cohen in [6] by Batut and Renaud. Baldick [8] later used this technique in his more general formulation of the unit commitment problem. The principal achievement of this work is the inclusion of reactive power output variables to the formulation, so that better loss management may be performed and generators that are necessary because of their VAr output but not their real power are actually committed. This is the logical next step in the development of Lagrangian relaxation techniques. At this point, when typical algorithms reduce the duality gap to figures close to 1% [15, 10], it is important to recognize that a better handling of the reactive power considerations at the unit commitment stage may have a payoff that is higher than those last few percentage points in the duality gap. The variable duplication technique exploits the fact that the problem
is equivalent to
Notice that the last constraint is linear and therefore amenable to relaxation. We start by defining two sets of variables. The dynamic constraints will be posed in terms of the dynamic variables, whereas the static or system-wide constraints will be posed in terms of the static ones: Dynamic variables: Commitment status {0,1} for generator at time Real power output for generator at time VAr output for generator at time
80
The Next Generation of Unit Commitment Models
Static variables: Real power output for generator at time VAr output for generator at time
We define the optimization problem as:
subject to: (1.) constraints
(2.)
constraints
(3.) and the following additional constraints
Thermal Unit Commitment with Nonlinear AC Power Flow
81
where is the minimum combined capacity that is acceptable for the zone in the period and is the set of indices of generators in the zone. A word about the representation of the minimum up-time or down-time constraints is in order. While it is perfectly possible to state these restrictions in terms of additional state variables obeying state transition rules that reflect these constraints (see [10]), we have chosen not to include any more variables because of the already overburdened notation. These constraints can readily be incorporated in the structure of the dynamic programming graph used to solve the resulting subproblems, as in [3]. Thus, it will be assumed that we can enforce the constraints (9–11) on the D variables and the constraints (12– 14) on the S variables, so that we only relax the three last constraints (15–17), which leads to the following Lagrangian:
where are multipliers on the relaxed equalities of the two kinds of variables, is the multiplier associated to the zone’s reserve requirement at the period, and returns the index of the zone to which generator belongs.
82
The Next Generation of Unit Commitment Models
The separation structure of the Lagrangian is obvious upon looking at equations (19) and (20). It makes it possible to write the dual objective as
By looking again at (19) and (21), we see that the first term can be computed by solving dynamic programs again; the second term separates into optimal power flow (OPF) problems with all generators committed but with special cost curves for generator at time Notice that also has a price. We assume that the solutions of the dynamic programs meet the constraints and that the solutions of the optimal power flows meet the constraints. It would be tempting to apply a dual maximization procedure to the dual objective as stated, but there are some issues that prevent us from doing that without some modification of the Lagrangian. The first issue is that the cost of reflected in the dynamic programs, being linear, is not strongly convex; this can cause unwanted oscillations in the prescribed by the dynamic program [6]. Therefore, we set out to fix this before addressing any other problems by augmenting the Lagrangian with quadratic functions of the equality constraints. This will introduce nonseparable terms. At this stage, we will invoke the Auxiliary Problem Principle described by Cohen in [16] and [17]. This principle is a rather general formalism characterizing optimality in an implicit manner for convex programming, and an algorithm of the fixed point type can be inferred from it. Convergence for the convex case with affine constraints has been proved by Cohen. We proceed to write the new augmented Lagrangian as
Thermal Unit Commitment with Nonlinear AC Power Flow
83
Within the context of the auxiliary problem principle, it is possible to substitute the augmentation terms by the following at iteration (see [17] for the general technique and [6, 7] for the first documented application to unit commitment):
where and are the values obtained at the iteration. Since (22) is separable, we can collect terms of the augmented Lagrangian on a per-generator basis, so that at the iteration we are faced with
84
The Next Generation of Unit Commitment Models
Notice that (24) has the same separation structure of (19). Now that the separability issue has been resolved, we propose the following Algorithm: AC Augmented Lagrangian relaxation Step 0: Step 1: Initialize to the values of the multipliers on the power flow equality constraints at generator buses when running an OPF with all units committed. Initialize to zeros. Initialize a database of tested commitments to be empty; it will later be filled with the commitment schedules obtained in the course of the algorithm and their corresponding feasibility status. Step 2a: Compute
by solving
one-generator dynamic programs.
Step 2b: Compute by solving OPFs in which all generators are committed, their generation range has been expanded to include and the special cost is used. Note: all tasks in steps 2a and 2b can be solved in parallel. Step 3: If the commitment schedule Û is not yet in the database of tested commitments, perform a cheap primal feasibility test. If the results are not encouraging (i.e., not enough committed capacity), store the schedule in the database and label it as infeasible, then go to Step 6. Step 4: Perform a more serious primal feasibility test by actually attempting to run OPFs with the original constraints. If all OPF’s are successful in finding a feasible dispatch, store the commitment in the database, together with the primal cost including startup costs. Else label the commitment as infeasible, store it in the database, and go to Step 6. Step 5: If the mismatch between the two sets of variables is small enough, and there is already a set of feasible commitment schedules, stop. Step 6: Update all multipliers using sub-gradient techniques, and
Thermal Unit Commitment with Nonlinear AC Power Flow
85
Step 7: Go to Step 2. The proposed algorithm is very OPF-intensive: the major computational cost is that of computing OPFs for every iteration in order to solve the static subproblems, plus extra OPFs in selected iterations when a given commitment is promising in terms of primal feasibility. Thus, every effort possible must be made to try to alleviate the burden of OPF computation. The first thing that can be done is to use as a starting point for the OPF the result of the previous iteration for the same time period. Most of the times, the only difference in the data for the OPF would be a small change in the costs (reflected by the change in from one iteration to another). This, in theory, should result in fewer iterations needed for the OPF. Another drawback of the algorithm is that a different set of OPF computations must be performed to compute the value of the dual objective and to compute the value of the primal. Thus, before even trying to compute the value of the primal objective, one should make sure that such a costly computation is worth doing. Some of the cheap tests include verifying that the reserve constraint is met and that the mismatch between the S and the D variables is small, since feasibility is a given if the mismatch is zero. With respect to the latter, we have found that if a smaller mismatch should be specified as requisite to feasibility than if More costly feasibility tests would involve power flow problems starting from appropriate initial values. Currently a constrained power flow is being performed at this stage.
4.
COMPUTATIONAL RESULTS
An implementation of the algorithm has been written in the MATLAB™ environment. The dynamic subproblems can accommodate minimal up or down times, warm start and cold start-up costs and are solved using forward dynamic programming. We solve the static subproblems using a version of MINOS [18] that has been incorporated in the MATPOWER package [19] by the first author. It incorporates box constraints on the generator’s active and reactive output, piecewise-linear or polynomial cost functions for both P and voltage constraints, line MVA limits, and, of course, the power flow equations. Additionally, any linear constraint on the optimization variables can be imposed. A preconditioner for MINOS that performs a constrained power flow is used if necessary. It implements a Levenberg-Marquardt-like minimization of the sum of squares of the power flow constraints, with penalty functions on some other box contraints and constrained variables in the case of voltage limits. Thus, each iteration involves the solution of a problem rather than a Newton step. We solve the problem using a MEX-file version of BPMPD [20], an interior method solver. The specific sub-gradient technique being used at this point is a simple Poljac step size schedule, with an iteration-dependent weight that is inversely proportional to iteration number. We chose simplicity initially because convergence conditions for Poljac’s method are “mild” and well documented: it is advanta-
86
The Next Generation of Unit Commitment Models
geous to be able to blame any convergence problems on the formulation itself and not on the particular kind of sub-gradient update. The obvious drawback to this decision is that the convergence of the dual iteration process may not be very fast. More sophisticated gradient updates will be investigated once the basic features of the algorithm are well understood. The program was originally tested on a modified IEEE 30-bus system [21] with six generators and a planning horizon of length six. We modified the test case so that generator #4, located at bus #27, is needed for voltage support for many load levels even though it is most uneconomical to operate. For comparison purposes, we also wrote a version of the Lagrangian relaxation algorithm with DC flow-based relaxed line limits. The AC-based algorithm correctly identified this unit as a must-run for those time periods, even providing some price information on the MVArs that this unit produced by means of the corresponding The number of iterations required was usually in the vicinity of one hundred. In contrast, the DC flow-based algorithm failed to commit unit #4 for any period, producing a commitment schedule that was infeasible in light of the AC power flow constraints. The importance of proper selection of the parameters was apparent from the beginning. After several trial runs, we obtained good results with and Values very different from these, however, tended to produce somewhat smooth, damped oscillations in the values of some of the To highlight one of the new features found in the algorithm, we show the evolution of versus iteration number for a typical run in Figure 1. The multipliers with the higher values are all P-type multipliers. Those with the smaller values correspond to the Most of them settle to zero, indicating that is essentially free almost always. Yet, a few of them actually have high prices: these belong to generators and time periods where the OPF tries to use their MVArs in order to force feasibility or guided by economic considerations, but the generators are not actually committed. In the course of the algorithm, these may grow so large that they trigger the respective unit on. Once this happens, such multipliers tend to approach zero again, since is now plentiful. In Figure 1 there are two clear examples of this behavior, corresponding to unit 4 being committed for certain time periods. As the multiplier approaches zero, the static copy will approach the dynamic
A slightly more ambitious test has been performed using the IEEE 118-bus system, with 54 generators and a time horizon of 24 periods, corresponding to two “weekdays” and one day of the weekend, each with 8 three–hour periods. The total variation of the load relative to the base case is –50% and +40%. Figure 2 shows the behavior of the norm of the active and reactive mismatches between the two sets of variables. Figure 3 depicts the evolution of the multipliers in this case.
Thermal Unit Commitment with Nonlinear AC Power Flow
87
88
5.
The Next Generation of Unit Commitment Models
PARALLEL IMPLEMENTATION
One of the purported advantages of separation by Lagrangian relaxation is that it allows for simultaneous solution of all of the static and dynamic subproblems in a given dual iteration, making the computation amenable to parallelization. Profiling of the algorithm has indicated that more than 95% of the computation time in this particular implementation is allocated to the solution of the optimal power flows. In order to test larger systems, a parallel implementation was deemed not just convenient, but in fact necessary since running times were already several hours long. Fortunately, MultiMATLAB, a parallel processing toolbox for MATLAB is being developed at Cornell University by John Zollweg (see [22] and the original work of Trefethen et. al. [23]); this allowed us to take advantage of much of the existing code. Although the dynamic programs are also parallelizable, their time-granularity is much smaller than that of the OPFs, so communications overhead is likely to reduce the efficiency of their parallelization. We have opted to parallelize only the OPF computation at this time. MultiMATLAB works by having several copies of MATLAB, each running in a different node, communicate by means of a subset of the Message Passing Interface (MPI) library [24]. The calls to the MPI functions are implemented by means of MEX (MATLAB-Executable) files. A master node performs the main algorithm and the dynamic programming subproblems and when a set of OPFs need to be carried out it sends the OPF data to the other nodes,
Thermal Unit Commitment with Nonlinear AC Power Flow
89
working in a master/slaves configuration. The workers’ only task is to receive OPF input data, run the OPF solver and report the results back to the master. Two parallel scheduling strategies have been programmed so far. The first one is a straightforward round-robin scheme in which the master cycles through the workers, receiving the results of any previously assigned OPF by means of a blocking receive (MPI’s Recv function), which ties the master until data does arrive. Then the master sends the worker data for the next OPF and turns its attention to the next worker. Clearly, having the master wait for the worker is not optimal, but it has the advantage of employing only MPI’s Send and Recv calls, whose implementation is stable in MultiMATLAB. A second, more sophisticated parallel scheduling strategy makes use of MPI’s Irecv non-blocking receive function. Immediately after sending data to a worker, the master node posts a non-blocking receive, setting aside an incoming message reception area. The master can then turn its attention to other workers and assign further work. Every now and then the master calls MPI’s Testany function, which informs the master if any pending Irecv’s have been completed. If so, the master reads the data from the corresponding buffer and assigns more work if needed. This strategy promises the most efficient use of the workers. In limited experiments with up to seven workers, the master is actually free most of the time, testing for incoming data. This means that it is efficiently keeping the workers busy. The efficacy of this scheduling strategy can be further improved by performing the OPFs in order of decreasing expected execution time. Unfortunately, as of now the Testany implementation is not sufficiently stable to allow running a complete problem. The round-robin strategy has been tested using the 118-bus system with a much longer time horizon (168 periods) and longer start-up and shut-down times on the generators. Figure 4 shows a plot of the evolution of the mismatches.
6. FUTURE WORK Historically, the best justification for using Lagrangian relaxation has been the regular achievement of small relative duality gaps in larger problems. So far, our algorithm seems to behave correctly with proper tuning of parameters, but there is a need to test much larger (i.e., more than 300 generators) systems to verify whether small duality gaps are also routine. At that point, comparison to the results obtained using a DC-flow or linear network model formulation should also be performed, with special attention to the cost of any commitment corrections needed to make the schedule generated by the linear network model algorithm to be AC-feasible. It would be worth it to incorporate other kinds of constraints and continue improving the robustness of the optimal power flow subsystem, which has been the weakest link so far. Three major efforts are being undertaken. First, John Zollweg is implementing several changes that should make the non-blocking receive implementation
90
The Next Generation of Unit Commitment Models
in MultiMATLAB more stable, allowing the use of improved parallel scheduling strategies. Secondly, work is being done to improve the robustness of the OPF solver. While MINOS has been found to do a good job of finding optima given a good starting point, the early stages of the Lagrangian relaxation algorithm, when prices are being adjusted with larger steps, result in OPF problems where the solution lies far away from the starting point. We have found MINOS not to behave as well in these cases, especially for larger (i.e., 3000 buses) systems, even with the constrained power flow preconditioner. So the preconditioner is being turned into a first-stage optimizer intended to locate binding constraints and provide a better, feasible starting point. Finally, work is being done on how to include ramping constraints into the formulation. There are two basic variations in the literature: the first one involves discretizing the generation range for the dynamic copy of the active sources and disallowing transitions that violate ramping constraints in the dynamic program. While relatively straightforward, this approach would result in much larger dynamic programs. The second method involves relaxing the linear ramping constraints and adding them to the Lagrangian. There is, however, some concern about the speed of convergence of the corresponding multipliers, and special updating strategies may be part of the solution. Finally, there remains the question about whether such an algorithm is useful anymore. Lagrangian relaxation methods have not been used to clear energy markets that also produce commitment schedules due to fairness problems: since the cheapest commitment schedule obtained may depend on parameter tuning, a Lagrangian relaxation solution may lack the clarity and uncontestability required in a method used to clear a market. In addition, the issue of computation time also arises, since the algorithm requires the solution of many
Thermal Unit Commitment with Nonlinear AC Power Flow
91
complex AC OPFs; a method used to clear a market should be expeditious due to practical considerations. This second consideration is actually an issue that will become moot in time, given the exponential growth of typical computing capacity and the algorithm’s amenability to parallel computation. The first issue is more serious, and inherent in Lagrangian relaxation methods for unit commitment. So at this point it is difficult to advocate the use of the algorithm for market clearing. However, it is still a tool that can be used by ISOs for location-based market power studies as well as transmission capability assessment and expansion. Lastly, from an experimental economics viewpoint, the best way to assess the performance of a market is to compare its efficiency to that of the maximum social welfare solution. This algorithm can provide this solution (the modifications for elastic demand are trivial) and help to make market efficiency comparisons.
ACKNOWLEDGEMENTS We wish to thank Ray Zimmerman and Deqiang Gan for providing us with their package MATPOWER [19] for the initial tests of the algorithm. We would also like to thank Csaba Mészáros, whose QP program [20] BPMPD we use in several of our programs, and finally, John Zollweg, principal developer of MultiMATLAB.
REFERENCES 1. J.A. Muckstadt and R.C. Wilson. An application of mixed-integer programming duality to scheduling thermal generating systems. IEEE Trans. Power Apparatus Syst., 87(12):1968–1978, 1968. 2. J. A. Muckstadt and S.A. Koenig. An application of Lagrange relaxation to scheduling in power-generation systems. Oper. Res., 25(3):387–403, 1977. 3. G.S. Lauer, D.P. Bertsekas, N.R. Sandell, and T.A. Posbergh. Solution of large– scale optimal unit commitment problems. IEEE Trans. Power Apparatus Syst., 101(1):79–85, 1982. 4. C. Lemarechal and J. Zowe. A condensed introduction to bundle methods in nonsmooth optimization, in Algorithms for Continuous Optimization, E. Spedicato, Ed., Kluwer Academic Pub., 1994. 5. and A new approach for solving extended unit commitment problem. IEEE Trans. Power Syst., 6(l):269–277, 1991. 6. J. Batut and A. Renaud. Daily generation scheduling optimization with transmission constraints: a new class of algorithms. IEEE Trans. Power Syst., 7(3):982–989, 1992. 7. A. Renaud. Daily generation management at Electricité de France: from planning towards real time. IEEE Trans. Autom. Cont., 38(7):1080–1093, 1993. R. Baldick. The generalized unit commitment problem. IEEE Trans. Power Syst., 8. 10(l):465–475, 1995. 9. J.J. Shaw. A direct method for security-constrained unit commitment. IEEE Trans. Power Syst., 10(3): 1329–1339, 1995.
92
The Next Generation of Unit Commitment Models
10. S.J. Wang, S.M. Shahidehpour, D.S. Kirschen, S. Mokhtari, and G.D. Irisarri. Short-term generation scheduling with transmission and environmental constraints using an augmented Lagrangian relaxation. IEEE Trans. Power Syst., 10(3):1294–1301, 1995. 11. K.H. Abdul-Rahman, S.M. Shahidehpour, M. Aganagic, and S. Mokhtari. A practical resource scheduling with OPF constraints. IEEE Trans. Power Syst., 11(1):254–259, 1996. 12. H. Ma and S.M. Shahidehpour. Unit commitment with transmission security and voltage constraints. IEEE Trans. Power Syst., 14(2):757-764, 1999. 13. X. Guan, R. Baldick, and W.H. Liu. Integrating power system scheduling and optimal power flow. In Proc. 12th Power Systems Computation Conference, Dresden, Germany, August 19–23, 1996, pp. 717–723. 14. C.E. Murillo-Sánchez and R.J. Thomas. Thermal unit commitment including optimal AC power flow constraints. In Proc. 31st HICSS Conference, Kona, Hawaii, Jan. 6–9 1998. 15. D.P. Bertsekas, G.S. Lauer, N.R. Sandell, and T.A. Posbergh. Optimal shortterm scheduling of large-scale power systems. IEEE Trans. Autom. Cont., 28(1):1–11, 1983. 16. G. Cohen. Auxiliary problem principle and decomposition of optimization problems. Optim. Theory Appl., 32(3):277-305, 1980. 17. G. Cohen and D.L. Zhu. Decomposition coordination methods in large scale optimization problems: the nondifferentiable case and the use of augmented Lagrangians. In Advances in Large Scale Systems, Vol. 1; J.B. Cruz, Ed., JAI Press Inc, 1984, pp. 203–266. 18. B.A. Murtagh and M.A. Saunders. MINOS 5.5 user’s guide. Stanford University Systems Optimization Laboratory Technical Report SOL 83-20R. 19. R. Zimmerman and D. Gan. MATPOWER: A Matlab power system simulation package. http://www.pserc. Cornell.edu/matpower/. 20. Cs. Mészáros. The Efficient Implementation of Interior point Methods for Linear Programming and Their Applications. Ph.D. Thesis, Eötvös Loránd University of Sciences, 1996. 21. O. Alsac and B. Stott. Optimal load flow with steady-state security. IEEE Trans. Power Apparatus Syst., 93(3):745–751, 1974. 22. J. Zollweg. MultiMATLAB for NT Clusters. Cornell Theory Center Software Documentation, http://www. tc.Cornell. edu/UserDoc/Intel/Software/ multimatlab/. 23. A.E. Trefethen, V.S. Menon, C.C. Chang, G.J. Czajkowski, C. Myers, and L.N. Trefethen. MultiMatlab: MATLAB on Multiple Processors. Cornell University Computer Science Technical Report 96TR239. 24. W. Gropp, E. Lusk, and A. Skjellum. Using MPI: Portable parallel programming with the Message Passing Interface. MIT Press, 1994. 25. A.I. Cohen and V.R. Sherkat. Optimization-based methods for operations scheduling. Proc. IEEE, 75(12):1574–1591, 1987. 26. G.B. Sheblé and G.N. Fahd. Unit commitment literature synopsis. IEEE Trans. Power Syst., 9(1):128–135, 1994.
Chapter 6 OPTIMAL SELF-COMMITMENT UNDER UNCERTAIN ENERGY AND RESERVE PRICES
R. Rajaraman and L. Kirsch Laurits R. Christensen Associates
F.L. Alvarado University of Wisconsin
C. Clark Electric Power Research Institute
Abstract:
1.
This paper describes and solves the problem of finding the optimal self-commitment policy in the presence of exogenous price uncertainty, inter-product substitution options (energy versus reserves sales), and different markets (real-time versus day-ahead), while taking into consideration intertemporal effects. The generator models consider minimum and maximum output levels for energy and different kinds of reserves, ramping rate limits, minimum up- and down-times, incremental energy costs and start-up and shut-down costs. Finding the optimal market-responsive generator commitment and dispatch policy in response to exogenous uncertain prices for energy and reserves is analogous to exercising a sequence of financial options. The method can be used to develop bids for energy and reserve services in competitive power markets. The method can also be used to determine the optimal policy of physically allocating generating and reserve output among different markets (e.g., hour-ahead versus day-ahead).
INTRODUCTION
Unit commitment refers to the problem of deciding when to start and when to shut-down generators in anticipation of changing demand [1]. In traditional utility systems, the problem of unit commitment was formulated and solved as a multi-period optimization problem. In the traditional problem formulation, the anticipated demand was an input variable. The problem was solved for multiple generators, generally owned by the same entity (a utility). The start-up, shut-down and operating costs of the generators were assumed known. The standard way to analyze and solve this problem was by dynamic programming, and within this category of problems, the most popular solution
94
The Next Generation of Unit Commitment Models
method in recent years has been the use of Lagrangian relaxation [2,3]. Recently, a new method of decommitment has also been proposed [4,5]. Several things change in a deregulated market. Generators generally have to self-commit their units optimally. Since in most power pools, no single merchant owns all the generating assets, the need to meet system load is replaced with the need to optimize profits of the merchant’s generating plants based on the uncertain market prices at the locations where the generators are located. Of course, the forecasts of markets prices depend upon a number of factors, the most important of which include demand, system-wide generation availability and cost characteristics, and transmission constraints. We pose the problem of finding the profit-maximizing commitment policy of a generating plant that has elected to self-commit in response to exogenous but uncertain energy and reserve price forecasts. Typically, one generator’s output does not physically constrain the output of a different generator1, so this policy can be applied to each generator in the merchant’s portfolio separately and independently. Therefore, for ease of exposition, we assume the case of a single generator. Generator characteristics such as start-up and shut-down costs, minimum and maximum up- and down-times, ramping rates, etc., of this generator are assumed known. The variation of prices for energy and reserves in future time frames is known only statistically. In particular, the prices follow a stochastic rather than deterministic process. We model the process using a Markov chain. The method is applicable to multiple markets (e.g., day-ahead, hour-ahead) and multiple products (energy, reserves). Other researchers have modeled the effect of energy price uncertainty on generator valuation. In [6], the author models the effect of the spark spread on short-term generator valuation. In [7], the authors propose mean reverting price processes and use financial options theory [9] to value a generating plant. In both [6] and [7], however, the authors neglect the effect of realistic operating constraints such as minimum start-up and shut-down times. In [8], the authors improve upon this work to more realistically include the effect of operating constraints to find the short-term value of a generating asset; yet they neglect the effect of ramping rates. All these papers make assumptions about the risk-neutral price process in order to value the power plant. This chapter focuses not on generator valuation, but on finding the general principles for generator self-commitment in the presence of exogenous price uncertainty and market multiplicity. We derive the basic mathematical principles from dynamic programming theory [10]. We consider energy and reserve markets, although the method can be extended to include additional market choices, such as day-ahead versus real-time markets. Section 2 of this 1
Exceptions include multiple hydroelectric units connected in series and restrictions on aggregate emission levels from multiple generators within an area.
Self-Commitment Under Uncertain Prices
95
chapter defines the problem. Section 3 gives the dynamic programming solution to the problem, and Sections 4 and 5 illustrate the features of the optimal commitment policy using simple illustrative examples. Section 6 gives a more detailed numerical result for a peaking generator, and Section 7 concludes the paper. Appendix A is a technical section that solves the single-period optimal generator dispatch problem given exogenous prices of energy and reserves.
2.
THE PROBLEM
We begin by describing the exogenous inputs to the problem. Generator capability and cost characteristics. At any given time t, generator G is assumed to be in state where is a member of a discrete set X={state 1, state 2, ..., state K} of possible states. Intertemporal constraints are represented by state transition rules that specify the possible states that the generator can move to in time period t+1, given that the generator is in a state at time t. Generally, there is a cost associated in moving between different states. In a simple representation, two states are sufficient: “in service” (or “up”) and “out of service” (or “down”). In general, however, many more states may be needed to represent the various conditions of the start-up and shut-down process. The degree to which a generator can participate in providing reserves depends on its ability to respond to the reserve needs in a timely manner. For regulating and spinning reserves, the generator must be already be in service; the amount of MW of reserves that a generator can offer must be consistent with its ramping rate. Generators that are already at a maximum in terms of energy provision are unable to also participate in the reserves market. Thus, to participate in the reserves markets, the generator cannot simultaneously sell all of its capability in the energy market. The parameters that describe a generator include: Minimum and maximum output levels Ramping rates Minimum up- and down-times for the generator Incremental energy costs and no-load costs Start-up, shut-down, and banking costs. Generator states and state transitions. Generators can be in any of a number of several possible UP, DOWN, or transitional states. For example, for a generator with total capacity of 200 MW, and ramp rate of 100 MW/hour, we could define two UP states: and The state would cover the operating range [0 MW, 100 MW], while the state would cover the operating range [101 MW, 200 MW]. Likewise, minimum down times
96
The Next Generation of Unit Commitment Models
can be enforced by defining multiple DOWN states. Only certain transitions among these states are permissible. Furthermore, transition between states generally involves a cost. For example, going from a cold shutdown to an online state will involve a start-up cost. Generator dispatch constraints. A generator may have additional dispatch constraints that restrict its operation. For example, the generator may need to be offline (in the “off” state) during certain periods for scheduled repairs. These restrictions are modeled as time-dependent constraints on generator states. Exogenous price forecast of energy. A discrete Markov process models the exogenous price for energy. In each time period, a discrete price state represents a price range. The price at time is probabilistically related to the price at time t via a price transition matrix. That is, is a known quantity. One can think of a price forecast at any time t to be a baseline price point plus a random uncertainty around the baseline forecast. Since the exogenous price forecast is an important input of the problem, we digress a little to discuss how one may obtain estimates of this input. We consider two ways in which price forecasts can be made: One possible method is to use historical data. For example, to obtain a price forecast for next week, one could use past week data and data from other weeks with similar load/weather patterns as that predicted for next week. This would be a statistical data-mining problem. Another way to forecast prices would be to use numerous Monte Carlo iterations of structural computer models (such as optimal power flow models and production cost models) to model the uncertainty of prices. The physical spot markets for energy include real-time, hour-ahead, dayahead, and possibly week-ahead markets2. Each of these spot markets is a different market, e.g., energy prices for a particular hour could be different in day-ahead and real-time markets and could have very different characteristics in terms of price volatility. A generator will often have a choice as to which market to use to sell its energy. Exogenous price forecast of reserves. Operating reserves are distinguished by the speed with which they become available and the length of time that they remain available. In the nomenclature of the Federal Energy Regulatory Commission, the primary types of reserves (from fastest to slowest) are regulating, spinning, supplemental, and backup reserves. For example, regulating reserves need to be available for following moment to moment fluctua2
It is doubtful whether forward prices quoted month-ahead (or more) will influence an individual generator’s commitment and dispatch decisions.
Self-Commitment Under Uncertain Prices
97
tions in system demand and can generally be offered by generators on automatic generation control (AGC). As another example, to offer 10 MW of spinning reserves, a generator must be online and must be capable of producing 10 MW within 10 minutes. Supplemental reserves and backup reserves are slower reserve types. For generators who provide reserve services, there are two types of reserve costs (see [11] for more details). These are reserve availability costs, which are the costs of making reserves available even if they are not actually used, and reserve use costs, which are the costs incurred when the reserves are actually used. Generally, reserve use costs are compensated at the spot price of energy3. Reserve availability costs are the opportunity costs of generators, i.e., they include off-economic dispatch costs, and costs of starting up or shutting down generators. In California, New York, New England, and the Pennsylvania-Jersey-Maryland (PJM) system, there is currently a competitive market-clearing process for setting the reserve availability costs of some or all of the above reserve types. Reserve availability prices are modeled similarly to energy prices, i.e., as a discrete Markov chain. We allow, however, the reserve availability prices to be correlated with the energy prices. One particularly simple way to model reserve uncertainty is to assume perfect correlation between energy prices and reserve availability prices. Exogenous fuel price forecasts. Fuel prices can be modeled similarly to reserve availability prices. Since most practical commitment periods are less than a week and fuel prices typically show much less volatility than energy prices over this interval, it is a not a bad approximation to keep these inputs constant. For ease of exposition, therefore, we assume fixed fuel prices throughout the paper. It is fairly straightforward to also include uncertainty in fuel prices; see, for example, [8]. Start and end time periods. We will assume that the start time period is at time 1 and that the end time period is at time T. For most practical problems, T will be between one day and one week. Next, we define some notation; explicit functional dependencies are often omitted for clarity. Given generator state and a vector of energy and reserve availability prices, at time t, 1. (or simply defines the commitment policy for time t, i.e., it signifies a particular valid rule to move the generator from state at time t to a new state at time t+1.
3
In general, reserve use costs could also include the wear-and-tear costs of ramping up and down to follow system demand. The current custom is that, in competitive markets for reserve services, these costs are not directly compensated and must somehow be internalized by the generators.
98
The Next Generation of Unit Commitment Models
(or simply defines the dispatch policy for time t, i.e., it represents a particular dispatch of energy and reserves for the generator at time t, given that the generator is in state 3. denotes single-period profits at time i.e., the profits realized by the dispatch 4. denotes the cost of transitioning (e.g., start-up or shut-down costs) from state at time t to state at time t+1 due to the commitment policy used in time period t. The problem can now be posed as: [PROBLEM] Find the best commitment and dispatch policy (u*, d*) that maximizes expected total profits over all possible commitment policies and all possible dispatch policies where E denotes the expected value over the uncertain price forecasts5. Before we proceed further, it is useful to summarize the essential features of the problem: Inter-product substitutability. Market participants have a choice between sales in the energy versus sales in the reserve markets. These markets operate simultaneously (though the markets for energy and reserves may clear sequentially, as they currently do in California). Moreover, market participants have a choice of offering their products in different markets (e.g., day-ahead versus hour-ahead markets). Price uncertainty. The future prices of energy and of reserves at the location of the generator of interest are unknown but follow a known random process. The general characteristics of the random process are estimated by the generator wishing to self-commit. Intertemporal ffects. Intertemporal constraints affect the generator’s operations. This may lead to situations when a market participant can elect to remain on during certain periods when operation will be at a loss in return for likely (but not certain) profits in later periods. We are interested in finding both the optimal commitment and the optimal dispatch policy. We stress that the problem is complicated by the fact that at the time the commitment decision is made, future prices are uncertain. The next section addresses this problem. 2.
4 5
Current period profits do not include transition costs. This objective function assumes that the generator is risk-neutral. If the generator is riskaverse, the objective function should reduce the expected outcome according to some measure of risk. For example, the objective might be to maximize where “V” is the variance of net profit and “a” is a risk aversion coefficient. As another example, the objective function could be an exponential utility function with constant relative risk aversion [12]. Now the objective function would be multiplicative in nature, but we can take natural logarithms to convert the objective function to the form shown in this chapter.
Self-Commitment Under Uncertain Prices
3.
99
OPTIMAL COMMITMENT AND DISPATCH POLICY
We now present the optimal commitment and dispatch policy. The optimal dispatch policy is fairly straightforward: given an exogenous price forecast for time period t, the generator takes its current state as given and dispatches energy and reserves in an optimal manner for time period t, without regard to other time periods. Appendix A describes the single-period optimal dispatch. The profit-maximizing commitment decision for transitioning to the next time period is more complicated, however, because actions taken now affect future time periods. The backward dynamic programming (DP) method for solving this problem starts at the final time period T and works backward using the following steps. The backward DP method [3,10] is as follows6: Step 1. Let over all possible commitment policies and dispatch policies Let the optimal dispatch policy be denoted by and the optimal commitment policy by must be computed for each possible state and each possible price level Step 2. Let over all possible commitment policies and dispatch policies The expectation E is taken over all possible price levels given that the price in time T–l is is probabilistically related to via the Markov chain. The state at time T, is related to by the commitment policy Let the optimal dispatch policy be and the optimal commitment be must be computed for each possible state and each possible price level Step T. Let over all possible commitment policies dispatch policies and price levels The expectation E is taken over all possible price levels given that the price in time 1 is The state at time 2, is related to the previous state by the commitment policy i.e., Let the optimal dispatch policy be and the optimal commitment policy be must be computed for each possible state and each price level If the generator is in state and sees price level at time t=l, the profit-maximizing schedules are represented by the commitment actions and the dispatch decisions where for t=1,2,...,T-l, and is related probabilistically to via the Markov chain, and the maximum expected profits are Actual profits and actual 6
For ease of exposition, we have ignored the boundary condition at time T+l.
100
The Next Generation of Unit Commitment Models
schedules depend upon actual price levels encountered in the different time periods. The algorithm for finding the optimal commitment policy is similar to the problem of determining the value of an option using a tree approach [9]. Therefore, we can characterize the problem of finding an optimal commitment policy as a generalized tree approach that values and exercises a sequence of complicated options in each time period. The options involve decisions such as whether to commit or not, whether to ramp up or ramp down, whether to participate in the energy or reserves markets, etc.
4.
ILLUSTRATIVE EXAMPLE 1
This section illustrates the concept. For simplicity we assume only one product, energy, and one three-period market, i.e., T=3. Suppose that the generator parameters are as shown in Table 1. For this example, the generator at time t can be in one of two states, “UP” or “DOWN," i.e., X={UP,DOWN}. There are no intertemporal constraints. The generator can move from any state at time t to any state at time t+1.
A shut-down cost is incurred when the generator moves from an UP state to the DOWN state. A start-up cost is incurred when the generator moves from the DOWN state to the UP state. All other transitions result in zero costs. In each time period, an exogenous price forecast may be described by two possibilities: is HIGH or is LOW, each having a specified probability of occurrence. The HIGH and LOW prices in each time period are allowed to vary, as Table 2 shows. Further assume that the prices at time t+1 depend probabilistically upon the prices at time t. The probability of a HIGH-HIGH transition is and the probability of a LOW-LOW transition is These are exogenous, with assumed values and
Self-Commitment Under Uncertain Prices
101
The backward DP algorithm finds the profit-maximizing commitment and dispatch policy. Tables 3(a)-(c) depict the solution. Columns in these tables correspond to time periods. The entry in Table 3(a) that corresponds to a “time period t” column and a “state” row represents the maximum total expected profits for time periods t to T, given that the state at time t is and the price is
Similarly, given state and price at time t, the corresponding entries in Tables 3(b)-(e) show respectively: 1. The optimal dispatch for time t. 2. The optimal commitment policy for time t, i.e., the next state to move to at time t+1. 3. The maximum profits obtained from the optimal dispatch at time t. 4. The cost of the optimal commitment policy, or the cost to move from the current state to the new state at time t+1. Table 3 illustrates the results of a standard Backward DP computation. These results are obtained, as is standard practice, by solving for the respective entries in the table from right to left.
102
The Next Generation of Unit Commitment Models
Self-Commitment Under Uncertain Prices
103
Suppose that, at time t=l, the price level is HIGH and the generator is UP. The maximum expected profits are $415.4 over the three time periods. Since the current price level is HIGH and the generator is UP, the optimal commitment policy is to stay UP at t=2 (from Table 3(c)), in spite of the possibility of net losses over the three periods. The actual profits and the commitment policies at other times would, however, depend upon the actual price levels that occur in those time periods. For example, if the price level stays HIGH for both t=2 and t=3, the optimal commitment policy is to stay UP at t=3, realizing total profits of –5+500+50=$545. If, on the other hand, the price level becomes LOW for t=2, and LOW for t=3, the optimal commitment policy is to go DOWN at t=3, realizing profits of –5–10–22= –$37. In other words, the generator loses money under some price patterns, even with the optimal policy. The expected profits are maximized, however. The optimal schedules given by the backward DP are not static. Instead, they depend upon the exogenous prices in each time period. Thus the DP method does not merely give an optimal schedule. Rather, it gives an optimal scheduling policy corresponding to different conditions.
5.
ILLUSTRATIVE EXAMPLE 2
In this section, we describe the “optionality” features of the generator self-commitment problem, and show that it has features analogous to financial options. We also make additional three points: 1. Assuming a single average price forecast generally understates the value of the optionality, and could severely understate expected generator profits. 2. Running Monte Carlo methods without taking care to ensure that future prices are always uncertain (at the time the commitment is made) generally overstates the value of the optionality and overstates expected generator profits. 3. Not considering reserve products (and multiple markets) tends to lower expected generator profits, because these additional products increase generator optionality. First, we consider the optionality due to price uncertainty. Assume a single time-period horizon and a single product – the energy service. Assume that the generator for which we want to find the optimal commitment and dispatch policy has no start-up or shut-down costs and no intertemporal constraints. Assume that generator has a capacity of 100 MW, no minimum generation constraint, and constant incremental costs of $30/MWh over this range.
104
The Next Generation of Unit Commitment Models
Table 4 shows five different price forecast scenarios. Two possible price states, HIGH and LOW, each with a 50% probability of occurrence, represent each price forecast. The expected value of the prices for all price forecasts is $30/MWh. The optimal policy for the generator is to produce 100 MW whenever the energy price exceeds its incremental costs and to produce 0 MW whenever the energy price is below its incremental costs. For example, for forecast #3, the generator will produce 0 MW when the price is LOW (or $20/MWh), and will make no profits. When the price is HIGH ($40/MWh), the generator will produce 100 MW and make a profit of 100*(40-30) = $1000. Since both price scenarios are equally likely for this forecast, expected profits are 0*0.5+1000*0.5 = $500. Table 4 shows that expected generator profits increase with increasing price volatility8. This is analogous to the value of a financial option that increases in value when price volatility increases [9]. On the other hand, if one uses an average price of $30/MWh to find a commitment policy for the generators, then one will estimate that the generator will make no profit for any price forecast because the generator incremental costs will not exceed the expected energy price. Therefore average price forecasts fail to calculate the value of optionality and understate generator profits. Next, we examine a potential pitfall associated with Monte Carlo methods. One possible way of finding the expected generator profits to capture the optionality value could be to generate a large number of random price scenarios for the time interval [0,T] by Monte Carlo methods. Using the ensemble 7 8
Price volatility here is defined as the ratio of the standard deviation to the expected price, expressed in percent (and rounded). All other factors (e.g., expected energy price) remaining constant.
Self-Commitment Under Uncertain Prices
105
of all generated price scenarios one could then use a deterministic model to solve for the optimal commitment and dispatch over this period for each member of the ensemble and then average over different Monte Carlo runs. This is, however, not always correct. To see this, consider the following example. Assume a two-period system, with each period having a 50% chance of HIGH price ($35/MWh) and a 50% chance of having a LOW price ($10/MWh), regardless of the previous period. The generator has the same characteristics as the above example, except that there is a minimum generation limit of 90 MW, and an additional intertemporal constraint that, once online, the generator has to stay online for two consecutive periods. The boundary condition is that the generator is offline initially and must be offline at the end of two periods. It can be verified that the optimal policy is not to commit the generators regardless of what the period 1 price is9. Therefore, the expected profit under the optimal commitment policy is zero. On the other hand, suppose that we first generate all the price scenarios (using a Monte Carlo method), and then run a deterministic optimal unit commitment on each possible price sequence. The four equally possible price sequences in the two periods are {HIGH, HIGH}, {HIGH, LOW}, {LOW, LOW}, and {LOW, HIGH}. If we make four deterministic unit commitment runs on these four price sequences, the deterministic unit commitment will only run the generator at maximum output (100 MW) for both time periods when the price sequence is {HIGH, HIGH}. The profit for this price sequence is $1000. For all other price sequences, the generator will not run, and the profit will be zero. Hence, expected profits using this method will be 0.25*1000+0.75*0 = $250, which clearly overstates the expected profits of zero under the true optimal commitment policy. The reason for this is that in each Monte Carlo run, the generator “peeped ahead” and “knew” the future prices and therefore chose the commitment accordingly. Models for commitment based on the traditional approach are likely to follow a variant of this deterministic optimization method. This approach would result in overestimation of generator profits. Monte Carlo methods are very efficient when one needs to simulate a large number of different random outcomes and find the expected value (or some other statistic) of some function based on these random outcomes. They
9
If period 1 price is HIGH, and the generator decided to commit, then the generator would produce 100 MW in period 1 to make a profit of $500. There is a 50/50 chance, however, that the period 2 price is HIGH or LOW. If the period 2 price is HIGH, the generator’s twoperiod profit will be $1000. If period 2 had a LOW price, the generator would produce the minimum 90 MW and lose 90*30=$2700 in period 2 for a net two-period loss of $2200. Therefore, if the generator commits to be online when the period 1 price is HIGH, the expected two-period payoff is 1000*0.5 – $2200*0.5 = ($600), for an expected loss of $600.
106
The Next Generation of Unit Commitment Models
are much more complicated to implement10, and prohibitively expensive, when the value of a function at any given time t itself depends on what may happen in the future, as in optimal commitment policy problems that have intertemporal constraints11. For example, using the finance analogy, Monte Carlo methods are used for European style options and for those other types of options when one does not have to worry about when it is optimal to exercise the option. American style options, however, are much more difficult to solve for using Monte Carlo methods [12, pp. 685]. Consider a final example to show the optionality value of multiple products (or multiple markets). Assume a single time-period problem and a single reserve product. Consider a generator whose incremental cost is $30/MWh, maximum capacity is 100 MW, minimum capacity is 0 MW, and maximum reserve capacity of 30 MW. Assume that the price of energy is $45/MWh and reserve availability costs of $20/MW/h. If the generator offers 100 MW of energy only, it will make profits of 100*(45–30) = $1500, on revenues of 100*45=$4500. On the other hand, if it maximizes its profits12 and offers 30 MW of reserve and 70 MW of energy, its profits are 30*20+ 70*(45–30)=$1650 on revenues of 30*20+70*45=$3750. (Shifting more of the generator output to reserves increases profits, even though total revenues decrease relative to the energy-only sale. This is typical.) In summary, the more optionality that a generator has, the higher its expected profits will be. Conversely, the more the operational constraints reduce this optionality (e.g., intertemporal constraints), the lesser will be its expected profits, all other factors being equal.
6.
ILLUSTRATIVE EXAMPLE 3
We now consider a slightly more realistic example.13 Assume a peaking generator with the characteristics illustrated in Table 5. The start-up and shutdown times for the generator are assumed to be zero. Figure 1 shows the base10
See reference [8] for the correct way to implement Monte Carlo methods for such problems. In [8], however, the Monte Carlo method becomes prohibitively expensive as the number of generator states and price uncertainty states increase. See also Section 6 for how to use Monte Carlo methods once the optimal self-commitment policy is known. 11 The Monte Carlo method discussed in this section will work correctly on the problem described in Table 4, because the optimal self-commitment policy does not have intertemporal features. 12 Appendix A shows how one may approach the problem when there are more than one reserve type. In this example, while there is profit to be made on the sale of both energy and reserves, the generator sees a higher profit margin in reserves and so maximizes the sale of reserves (30 MW). The remainder is offered as energy (100-30=70 MW). 13 The results of this section were derived using EPRI’s PROFITMAX model.
Self-Commitment Under Uncertain Prices
107
line energy price forecast. Figures 2 and 3 illustrate the anticipated baseline prices for 4 types of reserves: regulating, spinning, supplemental, and backup.14 The total number of time periods is one week (168 hours).
14
Spinning reserves are defined to be the capability that can be offered in 10 minutes (if online). Supplemental reserves are the amount of MW available in 20 minutes, and backup reserves are the amount available in 60 minutes.
108
The Next Generation of Unit Commitment Models
We model price uncertainty using a three-node Markov process. We assume that prices can be at one of three levels: HIGH, BASELINE, or LOW. The BASELINE prices are as illustrated. The HIGH price for energy and re-
Self-Commitment Under Uncertain Prices
109
serves is 115% of the corresponding baseline price, and the LOW price is 85% of the baseline price. We assume that there is perfect correlation between energy and reserve availability prices; e.g., when the energy price is HIGH, so are the reserve availability prices. For simplicity, we assume that the probability of transition between any one price state to any other price state is 1/3. That is, it is equally likely for the price to change states regardless of the present state of prices. Using the backward DP methods described in Section 3, we derived the optimal commitment and dispatch policy. The optimal commitment and dispatch policy at any time t is a function of the state that the generator is in, and a function of the uncertain price forecast for future time periods as observed at time t. Future prices are always considered uncertain. We then applied the optimal policy15 in numerous Monte Carlo runs to simulate different profit outcomes. From the Monte Carlo prices, we then calculated the actual eventual profits and generator outputs. Using these outcomes, we then illustrate the probability distribution of different generator outputs: generator profits, optimal generator dispatch of energy and reserves, etc. When we use the optimal policy found by the DP to simulate a number of possible states, we obtain a distribution of possible outcomes. Figure 4 illustrates this distribution. There is no assurance that the distribution will be neatly “bell-shaped” as in this example. In other examples it is possible to have distributions that are skewed or bimodal, particularly when we consider start-up and shut-down costs. The effects of the optimal commitment policy on the state transitions are shown in Figure 5. For a large number of scenarios, all transitions between states that result from the optimal policy are recorded. For some times, the state is unique (either UP or DOWN), but for other times the system could end up in either state, depending on the price sequence. This is because it is not known which state the generator will be at a future time t. Figure 5 shows that, depending on the prices that are actually realized, the generator could be in any of the different states at a future time. The ball “size” represents the probability of ending up in a particular state. The “thickness” of a transition line indicates the likelihood that the particular transition will take place.
15
We stress that the optimal policy was an input (not an output) in the Monte-Carlo runs.
110
The Next Generation of Unit Commitment Models
During the interval depicted in Figure 5, the optimal policy has the option to take several transitions, depending on the actual price realized. Only hours 93, 94, and 104 to 106 have a certain state (OFF in this case). For other periods the relative probability of being in either state is represented by the size of the “ball” and the relative transition probability is represented by the thickness of the transition “line.” During certain periods there is both an up transition probability and a down transition probability in the optimal policy.
Self-Commitment Under Uncertain Prices
111
For comparison, Figure 6 illustrates the optimal commitment policy when there is no uncertainty, i.e., the baseline price forecast is the perfect forecast. It can be seen that the effect of price uncertainty recognizes the possibility that the generator will either begin producing output (periods 104 through 108) or will turn off (periods 94 through 104) during certain periods according to what prices are actually realized. That is, a quick-responding generator has the luxury of producing when the prices are high, and going offline when the prices are low. Thus high price volatility tends to be beneficial for the expected profits of the peaking generator. When prices are higher than its incremental costs, the peaking generator will maximize its output (and increase profits), while when prices are below its incremental costs, the generator will shut down (and have zero profits). Since profits are bounded from below at zero, and monotonically increase as a function of price (above the generator’s incremental costs) the generator’s expected profits will increase. Figure 7 illustrates this notion. It shows that when expected prices are held constant among scenarios, expected profits increase as price uncertainty increases. This again shows that committing and dispatching a generator is analogous to exercising a financial option. The option value generally increases when uncertainty increases.16 This is because a peaking generator is able to follow changes more readily than other plant types. Thus, price volatility is beneficial to peaking units, a result that may be familiar to many readers. In Figure 11, we are able to precisely quantify this benefit. 16
An intermediate or cycling generator has less optionality features because inter-temporal constraints affect its profits, and it has features similar to Asian options [9]. A baseload generator has even less optionality features (excepting for the important question of which market to sell into), usually because its incremental costs are generally well below the market prices and is analogous to forward contracts [9].
112
The Next Generation of Unit Commitment Models
Figure 8 illustrates the expected sales of energy and reserves as a function of time. Note the striking fact that the generator in question offers energy only during certain periods, but derives income from making reserves available during many more periods.
7.
CONCLUSIONS
The contribution of this chapter is to describe the multi-period multimarket uncertainty framework within which decisions for unit commitment and dispatch will have to take place for many units that operate in a deregulated market. The chapter applies directly to the problem of optimal generator self-commitment. It describes a method for finding the most profitable market-responsive commitment and dispatch policy that takes into full account the optionality available to a generator: reserve market opportunities, multiple markets, price uncertainty, and intertemporal constraints. The model uses backward dynamic programming, and the algorithm in the model can be thought of as a generalized tree that values and exercises a sequence of complicated options. This algorithm can be used to obtain optimal power market bids for energy and reserve services in markets that integrate both these needs. The method can also be used to profitably allocate output in different physical forward markets, e.g., hour-ahead versus day-ahead.
Self-Commitment Under Uncertain Prices
113
ACKNOWLEDGMENTS We thank EPRI PM&RM for support of this work, with special thanks to Victor Niemeyer of EPRI for his support and encouragement. In particular, the work on the PROFITMAX model developed by Christensen Associates was sponsored by EPRI and initiated in 1997. We thank Blagoy Borissov of Christensen Associates for his help in simulating some of the results in this paper. We also thank Fritz Schulz for his help with the original implementation of PROFITMAX.
REFERENCES 1. A.J. Wood and B.F. Wollenberg. Power Generation Operation and Control, Wiley 1984. 2. A. Merlin and P. Sandrin. A new method for unit commitment at Electricite De France. IEEE Trans. Power Apparatus Syst., PAS-102(5): 1983. 3. D.P. Bertsekas et al. Optimal short-term scheduling of large-scale power systems. IEEE Trans. Autom. Cont., AC-28(1): 1983. 4. C.A. Li, R.B. Johnson and A.J. Svoboda. A New Unit Commitment Method. IEEE Trans.. Power Syst., 12(1): 1997. 5. C.L. Tseng, S.S. Oren, A.J. Svoboda, and R.B. Johnson. A unit decommitment method in power system scheduling. Elec. Power Energy Syst., 19(6): 1997. 6. M. Hsu. Spark spread options are hot! Electricity J., 11(2): 1998.
114
The Next Generation of Unit Commitment Models
7. S. Deng, B. Johnson, A. Sogomonian. “Exotic Electricity Options and the Valuation of
8. 9. 10. 11. 12. 13.
Electricity Generation and Transmission Assets.” Research Report #PSERC 98-13, 1998 (also available in the limited access http://www.pserc.wisc.edu/index_publications.html). C.L. Tseng and G. Bartz. “Short Term Generation Asset Valuation.” Research Report #PSERC 98-20, 1998 (also available in the limited access website http://www.pserc. wisc.edu/index_publications.html). J.C. Hull. Options, Futures, and Other Derivatives, Prentice Hall, 1997. D.P. Bersekas. Dynamic Programming and Optimal Control, Volumes 1 and 2, Athena Scientific, June 1995. L. Kirsch and R. Rajaraman. Profiting from operating reserves. Electricity J., March: 1998. H.R. Varian. Microeconomic Analysis, W.W. Norton & Company, Edition, 1992. P. Wilmott. Derivatives: The Theory and Practice of Financial Engineering, John Wiley & Sons, 1998.
APPENDIX A This appendix describes how a profit-maximizing generator would dispatch energy and reserve availability services given exogenous market prices for a given hour, and given that it is committed to be online. Assumptions Consider the output choice faced by a generator that can offer, in any given hour, energy and four reserve services. Assume that the energy price is PE, and that the availability prices for the four reserves are PR1, PR2, PR3, PR4, respectively. Suppose that the generator has maximum output level ME, and that, because of ramping limitations, the generator can provide the maximum quantities of the reserve XR1 for reserve 1, XR2 for reserve 2, XR3 for reserve 3, and XR4 for reserve 4. Further suppose that the generator’s production cost function is: where a, b, and c are constants and XE is the generator’s quantity of offered energy. What quantities of energy and reserves should the generator offer if it is maximizing profits? The Optimization Problem The generators problem is to maximize profits17:
subject to the constraints that all energy and reserve quantities must respect maximum limits: 17
When a generator offers reserves, there is a certain probability of these reserves being called. When reserves are called to produce energy, they will receive the market energy price. One can easily include this effect in the objective function (A-2).
Self-Commitment Under Uncertain Prices
115
For simplicity and without loss of generality, we ignore the constraints that all reserve quantities must be non-negative, and that the energy quantity have a minimum limit. Although equations (A-2) and (A-3) make the reserves all appear to be mathematically identical, they are not because we assume (reasonably) that reserve prices have a particular order18: Because production costs (A-l) depend only upon energy output, the generator will prefer to sell Reserve 1 first and Reserve 4 last. The Solution The Lagrangian for the optimization problem is:
The solution to the foregoing problem is:
Note that the shadow value of capacity use the generator to its full capacity, and that The solution to the above problem is:
18
only if energy and reserves only if XRj=Mj for j=1,2,3.
Theoretically, the reserve availability prices must be highest for the “highest” quality reserve (regulation) and lowest for the “lowest” quality reserves (backup). The reasoning is that generators that can offer “higher” quality reserves can always offer “lower” quality reserves, but not necessarily vice-versa. Therefore, the availability prices for “higher” quality reserves must be higher than the “lower” quality reserves. Because of market imperfections, however, this relationship is not always obeyed; e.g. see historical ancillary service prices from the California ISO website (http://www.caiso.com). Note that in equation (A-4), we do not necessarily assume that the highest quality reserves will have the highest price, i.e., we allow market imperfections.
116
The Next Generation of Unit Commitment Models
If Reserve 1 is (optimally) offered in a positive quantity that is less than its limit, then But if Reserve 1 is (optimally) offered to its limit, then In general: if Reserve j is offered at all, then all reserves <j are at their limits; if Reserve j is offered in a positive quantity that is less than its limit, then and all reserves >j are not offered at all.
Chapter 7 A STOCHASTIC MODEL FOR A PRICE-BASED UNIT COMMITMENT PROBLEM AND ITS APPLICATION TO SHORT-TERM GENERATION ASSET VALUATION
Chung-Li Tseng University of Maryland
Abstract:
1.
In this paper, we model the unit commitment problem as a multi-stage stochastic programming problem under price and load uncertainties. We assume that there are hourly spot markets for both electricity and fuel consumed by the generators. In each time period, the operator needs to determine which units are to be scheduled so as to maximize the profit while meeting the demand. Assuming that the price and load uncertainties can be represented by a scenario tree, we develop a unit decommitment method using dynamic programming to solve this problem. When there is only one unit under consideration, we show that a scenario tree can be converted to a lattice that allows branch recombination, which may greatly reduce the size of state space. This one-unit problem can be used to value a generation asset over a short-term period. In conclusion, we present our numerical results.
INTRODUCTION
Unit commitment is a problem to schedule generating units economically to meet forecasted demand and operating constraints, such as spinning reserve requirements, over a short time horizon. The unit commitment decision determines which units will be used in each time period. It is a mixedinteger programming problem and is in the class of NP-hard problems (e.g. [1]). Because of its problem size and the NP-hardness, the optimal solution of the unit commitment problem is normally difficult to obtain. Many optimization methods have been proposed to solve the unit commitment problem. These methods include the priority list method [2], the dynamic programming approaches (e.g. [3-5]), the branch-and-bound methods [6-8], and
118
The Next Generation of Unit Commitment Models
the Lagrangian relaxation methods (e.g. [9-11]). Among them, the Lagrangian relaxation methods are the most advanced and widely used approaches. Although the unit commitment problem has been widely studied during the past decades, most of the approaches do not consider uncertainties. The traditional unit commitment problem aims to schedule generation units to meet the forecasted demand. When the actual demand is not equal to the forecasted value, the discrepancy can be handled by system spinning reserve to some extent. In [12], we present a stochastic model for the unit commitment problem in which the demands are not known with certainty. We then use a scenario tree to capture the demand uncertainty and the apply Lagrangian relaxation to decompose the problem into scenario subproblems using progressive hedging [13]. Carpentier et al. in [14] propose another decomposition scheme using the augmented Lagrangian method. In these two approaches, the unit commitment decision is modeled as a multi-stage problem. Carøe and Schultz develop a two-stage stochastic programming model for the unit commitment problem, in which the authors emphasize the planning decision over the entire planning horizon rather than multi-stage implementation of the operating decision [15]. With the evolution of deregulation in the electricity industry and the introduction of spot markets for both electricity output and fuel input, incorporating uncertainties to the unit commitment problem becomes a necessity for utilities or power generators. In this chapter, from the perspective of a firm owning generating units, we model the unit commitment problem as a multistage stochastic programming problem under price and load uncertainties. We assume that there are hourly spot markets for electricity and the fuel consumed by the generators. Our research uses a scenario tree to represent the uncertainties as in [12]. However, we develop a new method using unit decommitment to solve this problem. Li et al. [16] and Tseng et al. [17] proposed independently the method of unit decommitment for the traditional unit commitment problem. In [16], the authors propose a solution procedure, which initially turns on all available units at all hours and then performs only decommitment. The authors view their method as a Lagrangian relaxation-like method and take the multipliers from economic dispatch instead of sub-gradients. On the other hand, in [17] the authors propose using unit decommitment as a post-processing tool for existing solution procedures for solving the unit commitment problem. They consolidate these two approaches as a unified unit commitment algorithm [18], in which they also conduct extensive numerical tests. Their results show that the unit decommitment method on average obtains solutions almost as good as the Lagrangian relaxation approaches, but with much less CPU times. In this chapter, we extend the unified approach presented in [18] to solve the stochastic unit commitment problem. Assume that the price and
A Stochastic Model for a Price-Based Unit Commitment Problem
119
load uncertainties can be represented by a scenario tree. Initially, all generating units are committed in all scenarios and in all time periods, to the best extent. Each unit’s schedule (in all scenarios) is then tentatively improved in turn with other units’ schedules fixed. At each iteration, only one unit’s tentative schedule is selected and updated. The iteration proceeds until no improvement can be made. Initial numerical tests seem to suggest that the unit decommitment approach applied to the stochastic unit commitment problem retains the properties when applied to the traditional deterministic case, as reported in [18]. When there is only one generating unit under consideration, the problem can be used to value a generation asset over a short-term period (e.g. [19]). This problem appraises the flexibility of a power plant’s real options, e.g. committing or decommitting a unit, in a competitive environment (e.g. [20]). We will show that in this special case we can convert a scenario tree to a lattice that allows branch recombination, which may greatly reduce the size of state space. In Section 2, we establish the mathematical model for the stochastic unit commitment problem. Section 3 presents a special case in which the uncertainties of the problem are perfectly known. Through this deterministic special case, we derive the method of unit decommitment. Section 4 extends the unit decommitment method to the stochastic case. We then discuss a shortterm generation asset valuation problem in Section 5. Section 6 gives numerical test results, and we present future directions in Section 7.
2.
THE MATHEMATICAL MODEL
In the model development, we introduce the following standard notation, with additional symbols introduced when necessary. : index for the number of units : index for time : zero-one decision variable indicating whether unit is up or down in time period : state variable indicating the length of time that unit has been up or down in time period : the minimum number of periods unit must remain on after it has been turned on : the minimum number of periods unit must remain off after it has been turned off
120
The Next Generation of Unit Commitment Models : the number of periods required for the boiler of unit to cool down
: decision variable indicating the amount of power unit in time period : minimum rated capacity of unit
is generating
: maximum rated capacity of unit : reserve available from unit in time period : system demand (MW) in time period : system reserve (MW) in time period (assumed to be a function of ) : amount of power transaction in time period (power input) or negative (power output). : electricity price ($/MWh) in time period
Its value can be positive
: fuel price ($/MMBtu) in time period : the heat (MMBtu) required for unit to generate (MW) of power (assumed strictly convex, increasing, and smooth) : start-up cost associated with turning on unit at state : shut-down cost associated with turning off unit
2.1
Operational Constraints
The operational constraints to be discussed in this paper can be described in terms of state transition. Let be the set of unit commitment state space for unit the on-line states, and
is composed of two subsets of the states: for the off-line states.
The operational constraints include: Minimum up-time/down-time constraints, for
and
for
A Stochastic Model for a Price-Based Unit Commitment Problem
State transition constraints, for
and
Equation (4) also implies the following relation between
Capacity constraints for Initial conditions on
2.2
121
and
and for
at
A Multi-Stage Stochastic Programming Formulation
This research considers the problem from the perspective of a firm that owns generating units. We assume that there are hourly spot markets for both electricity and fuel consumed by the generators. Each generating unit is viewed as a cross-commodity instrument. That is, each generator buys fuel from the fuel market, converts it to electricity, and sells the electricity to the electricity market. The uncertainties considered in this model are the prices for both electricity and fuel and the quantity of the electricity sold. The quantity of electricity sold in the market , called load or demand in this paper, may be contingent upon time (e.g. peak or non-peak hours) or may be price-elastic. The firm may also involve option-type transactions, such that the amount of transactions may depend on the price of electricity. For example, a customer may tend to call an option of quantity (e.g. swing options) when the price of electricity is high and vice versa. The firm would like to maximize its expected profit while meeting its load and transactions. In the proposed stochastic model, the timing of the event occurrence is as follows. In time period , the uncertainties are revealed. Based on the states of all units from the previous hour, , the operator needs to schedule the units to achieve maximum profit while satisfying the demand. The operator’s decision is not only based on the information obtained in the current period, but also the expectation of future return. Any commitment decision made in the current period will then become the
122
The Next Generation of Unit Commitment Models
initial condition for decision-making in the following hour and will constrain the availability or flexibility of the unit commitment in the subsequent hour(s). In addition, there are start-up and shut-down costs associated with the commitment decision. In this paper, both costs are generalized in the following function. Let
be the decision problem to be made in time pe-
riod , given the initial conditions
and
and the observed elec-
tricity and fuel prices The dynamic programming type recurrence equations can be formulated as follows:
where denotes the expectation operator, and the subscript indicates that the expectation is based on the price information available at time . The last term in (8) with the expectation operator defines another stochastic program to be considered in the subsequent time period, which is also called a recourse function. Since the fist term on the right-hand side of (8) is a constant that can be pulled out from the maximization, can be decomposed to two terms as follows.
Equation (10b) is subject to the physical constraints (3) to (6) and the following constraints. Demand constraints for
Reserve constraints for
A Stochastic Model for a Price-Based Unit Commitment Problem
where and unit i. In (9), accounts for revenue, and The terminal condition of (9) is as follows
123
is the maximum reserve for represents cost minimization.
subject to (11) and (12) at time The optimal value representing the maximum expected profit that the operator can make over the period can be obtained from the last step of the recursive relation as Finally, note that in the formulation the fuel price
directly affects a
generator’s cost characteristics, and the electricity price is correlated to the transaction amount and the load , which are uncertain per se. All of these uncertainties influence unit commitments from different perspectives.
2.3
Economic Dispatch
The minimization problem on the right-hand side of (10b) represents scheduling generating units over a single period with generating costs minimized. The scheduling decisions include the determination of what units will be on (i.e. the commitment) and the generation levels for on-line units. Given a commitment, the economic dispatch problem is to allocate electricity generation economically to on-line units while satisfying the demand and system reserve constraints. At time given state variable and for each unit, let be the index set of on-line units at time (Note that in this chapter a variable with a tilde hat will denote a realization of the variable.) The economic dispatch problem at time denoted by rced is defined below.
124
The Next Generation of Unit Commitment Models
Note that rced stands for “reserve-constrained economic dispatch.” In [18] the optimality condition of rced is interpreted as follows: the units in are divided into two sets, one set of units with “cheap reserve” but “expensive generation” (relatively), and one is the counterpart. The units with cheap reserve but expensive generation are operated with the same marginal costs (or as close as possible), which are the Lagrange multipliers corresponding to (15b). The units with expensive reserve but cheap generation are operated such that their marginal costs for reserve equal (or are as close as possible) to the Lagrange multipliers corresponding to (15c). Proposition 1. The solution of rced following conditions hold.
3.
exists if and only if the
THE DETERMINISTIC CASE
In this section we discuss a special case with certainty. An algorithm will be developed, and will be extended to handle stochastics in a later section. Assume that the future prices for electricity and fuel as well as the load and transaction , are fully and perfectly known. Equation (8) reduces to the following deterministic price-based unit commitment formulation.
subject to constraints (3) to (6), (11) to (12), and initial conditions on at for The first term in (17b) is a constant, and the minimization term is a traditional unit commitment problem, which can be solved using the methods reviewed in the introduction of this paper, such as the Lagrangian relaxation method. In this section, we focus on the unit decommitment method proposed in [17, 18] for solving the cost minimization problem in (17b). First we review the unit decommitment method.
A Stochastic Model for a Price-Based Unit Commitment Problem
3.1
125
Unit Decommitment
The unit decommitment method was proposed in [17] as a postprocessing tool to improve solution quality for methods solving the traditional unit commitment problem. Given and a feasible schedule consider the problem of optimally improving one unit’s schedule by decommitment. That is, in the time periods when the unit under consideration is already off-line, the unit remains off-line. The unit may be turned off in some on-line periods only if doing so is cost-saving and would not cause infeasibility. While we are improving a unit’s schedule, say determining for unit by decommitment, the commitments of units other than are kept fixed. However, their generation levels in some time period may change in order to balance demand and reserve if unit is decommitted in the same time period. The decommitment rule is summarized below.
Constrained by the decommitment rule, the optimal decommitment problem for a unit, say is formulated below.
subject to additional constraints such as (3) to (6) and (11) to (12), where captures the total cost changed from units other than if unit were turned off in time period
The exact value of
tained by solving the dispatch problem twice, one with unit time and the other without.
can be obcommitted at
is a 0-1 integer programming problem, and can be solved using the following dynamic programming recursive equation.
with boundary condition
126
The Next Generation of Unit Commitment Models
where
can be interpreted as the minimum cost for op-
erating unit
over a period starting from time to
The optimal solution of
is obtained from the last step of the dynamic
programming algorithm as tion of
with initial state
In this research, we call the solu-
the tentative commitment of unit
In the following algorithm, superscript denotes the the algorithm. Let be the total cost for unit the schedule
and
iteration of associated with
be the optimal objective
value of solved with respect to bold faces are vectors. For example,
(Note the variables in
The unit decommitment algorithm Prices given. Set Step 0:
for
Data:
and a feasible solution
and evaluate
Step 1: Solve Step 2: Select a unit
are
for
with respect to
and obtain
such that
for
If there is no such unit,
stop; otherwise update the commitment of unit the tentative commitment obtained in
in
by
The resultant unit
commitment is assigned to be Step 3: Perform dispatch on for go to Step 1. Step 4: Set
to obtain
and evaluate
Although the unit decommitment method starts with an initial feasible solution of the unit commitment problem, it can be used as a complete algorithm for solving the unit commitment problem. Initially, as many units as possible are turned on in all hours without violating the minimum downtime constraints at the initial hours. This resultant unit commitment serves as an initial commitment, to which the unit decommitment algorithm is then applied. There are, however, minor modifications required in order to make this approach work. First, the commitments in the early iterations tend to be
A Stochastic Model for a Price-Based Unit Commitment Problem
127
seriously overcommitted such that the first inequality in (16a), the minimum load condition, is violated. In other words, the dispatch phase in Step 3 of the unit decommitment algorithm may not be feasible. When the infeasible situation occurs, the algorithm would dispatch the units to satisfy the optimality condition to the best extent, in the sense of matching the units’ marginal costs for both fuel cost and reserve to the corresponding multipliers and , respectively, as closely as possible (see [18]). By doing this, as the decommitment procedure proceeds, the commitment obtained eventually satisfies the minimum load condition, and the algorithm starts to produce feasible schedules. Instead of obtaining the exact value as in (20), may also be approximated. In [18] the first order approximation of
is derived.
where and are the multipliers associated with rced With (23) plugged into (19), it is shown in [18] that starting from an economically dispatched schedule performing either the unit decommitment step with respect to or the Lagrangian relaxation subproblem with respect to to any unit would result in the same (tentative) commitment. However, these two approaches differ in the commitment updating (the unit decommitment updates one unit at a time, while the Lagrangian relaxation approach updates all units at once) and the multiplier updating (the unit decommitment performs economic dispatch, while the Lagrangian relaxation approach uses sub-gradients). In [18], based on their numerical testing results on randomly generated instances, the authors report that the error between the solutions obtained by the unit decommitment method and Lagrangian relaxation approach is within 0.2%, and the unit decommitment method takes at least 50% less CPU time than the Lagrangian relaxation approach on average. In the following section, we extend and apply the unit decommitment method to the stochastic unit commitment problem.
4.
SOLVING THE MULTI-STAGE STOCHASTIC MODEL USING UNIT DECOMMITMENT
The multi-stage stochastic model formulated in (8) appears to be intractable generally. A popular approach is to summarize the future realization of uncertainties by a finite number of possible scenarios. We represent scenarios by the nodes of a tree such that given any node in the tree, there exists a
128
The Next Generation of Unit Commitment Models
unique path leading to it from the starting node. A (directed) arc in a tree connecting two nodes represents the evolution from one scenario to the other. Consider a scenario tree T(N, A), where N is the set of nodes, and A is the set of arcs in the tree. Let
where
is an ordered set
of nodes in the tree corresponding to time period t, and notes the set of the descendents for node at time t such that Assume the scenario at node and a descendent
de-
is . For each node there is a branching (conditional) prob-
ability associated with this arc denoted by . Given a scenario tree T(N, A) , the stochastic unit commitment formulated in (10) reduces to the following equations for a node
and
subject to the demand constraints for
and the reserve constraints for
and (3) to (5) with an appropriate superscript in each variable to denote the node in the tree. Next, we will show that we can extend the unit decommitment method to solve (25). Given a scenario tree T(N, A) , and a feasible schedule for similar to the development in Section 3.1, we discuss what the best strategy is to improve the generating cost from unit with other units’ strategies fixed in all scenarios (cf. (21)).
with boundary condition (cf. (22))
A Stochastic Model for a Price-Based Unit Commitment Problem
for
Again
129
is subject to the decommitment
rule,
and the minimum up-time and down-time constraints between in (3), and the state transition constraint for the
5.
last
step
of
and
defined in (4), for
We obtain the optimal solution of from the dynamic programming algorithm as (Note contains only the start node.)
SHORT-TERM GENERATION ASSET VALUATION
In this section, we consider a special case in which there is only one generating unit (say unit Solving this problem can determine the expected profit for a generation asset over a short-term period (e.g. [19]). This problem appraises the flexibility of a power plant’s real options, e.g. committing or decommitting a unit, in a competitive environment (e.g. [20]). We will show that, in this special case, a scenario tree can be converted to a lattice that allows branch recombination, which may greatly reduce the size of state spaces. Recall the general formulation of the stochastic unit commitment in (8) to (10). With employment of a scenario tree, these equations are reduced to (24) and (25). In (28), the unit subproblem (for unit using unit decommitment is presented. Although each unit subproblem (28) is solved independently, the commitment status of units other than are also required, which are implicitly accounted through That is, the value of depends on the states of all other units. However, at each node
to evaluate
at
all possible unit commitments is virtually impossible. The approach suggested here is to incorporate a scenario tree such that for each node there is one corresponding commitment state for each unit i to be determined,
130
The Next Generation of Unit Commitment Models
as described in Section 4. In a tree there exists a unique path leading to any given node from the starting node, and the commitment of all units can be tracked in each path. By doing this, the tree size is inevitably large, an exponential function of the number of times that the tree branches. For example, if we would like to design a scenario tree such that each node branches into two new nodes at each hour, for a 24-hour period the tree would contain ,more than 16 millions paths. When there is only one generating unit (say j) under consideration, the situation changes because Equation (28) reduces to
It is now possible to evaluate all possible states at each node are only
states of
If
is evaluated at all possible
since there we
would not rely on the unique path leading to to track the history of unit j’s commitment. Therefore, we can merge a scenario tree to a lattice that allows branch recombination without losing any information. The following section gives numerical results, along with an example of constructing a scenario lattice.
6.
NUMERICAL RESULTS
6.1
General Case with Multiple Units
The presented algorithm has been implemented in Fortran and applied to a test problem on a Pentium II PC (400MHz). In the test problem, 10 generating units are considered. The heat requirement of each generator is modeled as a quadratic function. The start-up cost for
is modeled as follows.
Table 1 summarizes the parameters of the generators.
A Stochastic Model for a Price-Based Unit Commitment Problem
131
Starting from a current electricity price at 25 ($/MWh), a scenario tree is used to represent the variability of the electricity prices over the period [1,24]. This 24-hour period is equally divided into 4 subperiods (1 to 6, 7 to 12, 13 to 18, and 19 to 24). For the first and the fourth subperiods, there are two price scenarios indicating high (H) and low (L) price cases; for the second and the third subperiods, there are three price scenarios indicating high (H), medium (M) and low (L) price cases. Notations and i= 1,2,3,4 and i=2,3 are used to represent the high, low, or medium price scenarios in the i-th subperiod. Figure 1 illustrates the price tree, and Table 2 gives the data of scenarios. Table 3 presents the conditional probabilities between scenarios. For simplicity, assume that hourly demand follows the following relation (including the effect of transaction where
can be considered as some base load, and
represents some
“mean” prices for the electricity. When is deviated from , assume the demand will also deviate from . The load deviation is proportional to . This may be due to some options the firm has sold, which may be exercised at different price levels. Table 4 summarizes the data of and
,
,
132
The Next Generation of Unit Commitment Models
We apply the proposed unit decommitment method to the test problem and obtain a near-optimal solution within 2.3 seconds of CPU time. Table 5 reviews the algorithm performance. In all, we performed eight iterations. Initially, at iteration k=0, all units in all scenarios are turned on at all hours, to the most extent. The economic dispatch is then performed, and then the expected profit of each unit is summarized under the column of Note that at this point the system may be overcommitted, and the dispatch may not exactly match the demand. In the first iteration (k=1), we perform subproblem to each unit and obtain the tentative schedule. One unit m whose tentative schedule can yield the most improvement on the expected profit, is selected. This value is recorded under the column of for each unit. In the first iteration, unit 1 yields the most improvement for the expected profit. Its tentative commitment that completely shuts down the unit in all periods replaces its original one. Economic dispatch is performed to the new unit commitment, and the expected profit of each unit is recorded under The iteration goes on in a similar manner until no improvement can be made. We can observe the following: 1. The expected total profit is strictly increasing as the iteration increases. 2. Once a unit has been selected for improvement at some iteration, its (new) commitment remains “optimal” in the subsequent iterations. For example, we select unit 1 at the first iteration. The improvement that can be made through decommitment (under the column of remains 0 for unit 1 in the subsequent iterations. We can adopt this observation to improve the algorithm performance, because once a unit has been selected at some iteration, it can be exempted from further consideration. Therefore, the number of iterations required by the algorithm is bounded by the number of units.
A Stochastic Model for a Price-Based Unit Commitment Problem
3.
133
It can be verified that the following relation:
starts to hold when That is, after iteration 4, the algorithm has produced a feasible unit schedule. Therefore, solution feasibility is maintained after the 4-th iteration. Finally, to verify how good the solution obtained from the proposed method is, the dual problem using Lagrangian relaxation has been established. We created a simplistic version of dual optimization to obtain an estimate of the
134
The Next Generation of Unit Commitment Models
dual optimum, which can serve as an upper bound of the primal optimum. Without much effort spent to fine-tune dual iterations, we obtain an approximate dual optimum of $1,100,339. Compared with the primal optimum obtained from the proposed method of $1,089,819, the duality gap is within 0.96%. This implies that the obtained solution is fairly close to the true optimum.
A Stochastic Model for a Price-Based Unit Commitment Problem
6.2
135
Short-Term Generation Asset Valuation
Assume that the electricity and fuel prices follow some Ito processes. As an example, consider the following two processes advocated in [21].
and where and are two Wiener processes with instantaneous correlation In the price models above, captures the seasonal average price. The parameter captures reverting speed when the price deviates from and is the price volatility. We characterize the above commodity price models by mean reversion and log normally distributed, seasonal prices. Let equivalently We devised a two-dimensional price lattice to encompass both electricity and gas prices. Each price node in the plane is designed to branch out into a 3×3 grid of 9 price nodes in the plane corresponding to the following time period (see Figure 2). To form a lattice, the plane of each time period is divided into a predetermined grid such that branching is only allowed from grid nodes to grid nodes of the following time period. How to select the nine nodes to which to map, as well as their corresponding (conditional) probabilities, is discussed in [22]. Basically each branching must match (discrete-time) price movement characteristics (mean, variance, and correlation) implied by (36a) and (36b). We apply the branching process to each mapped grid node and repeat the process until time period T is reached. Figure 2 illustrates one such lattice. Note that the size of the lattice grows quadratically (linearly in each variable) as time increases. Furthermore, at each node we assume
Equation (37) essentially assumes that the operator would sell to the market at the amount of electricity that optimizes profit, and that the market has infinite capacity. Note that (37) ignores the reserve constraint (27), and the transaction is set to zero. Remember that Table 1 give the proposed method as applied to unit 1. Consider a 7-week (168-hour) period. Assume that the electricity prices and fuel prices both follow the processes described by (36a) and (36b). We obtain the parameters of the price processes are by fitting the historical price data series of Nymex natural gas prices and electricity prices from the California Power Exchange, taking the logarithm of these prices as our basic
136
The Next Generation of Unit Commitment Models
data series. For gas we obtain ity we obtain
and
and
For electric-
Refer to [22] for detailed
val-
ues. At time 0 suppose prices and are observed. We assume that the instantaneous correlation coefficient between electricity and natural gas is Figures 3 and 4 depict the relation between the expected profit of the power plant and the length of planning horizon T and the volatility respectively. We see that the expected profit for the power plant increases as either T or increases. The expected profit is extremely sensitive to the price volatility. From Figure 4, we can estimate that a 1% increase in the value of would result in roughly a 1% increase of the expected profit for the power plant. An intuitive interpretation of these results is to view owning a power plant as holding a series of spark spread call options [20]. The value of these options increases when (i) the number of options increases (as T increases) or (ii) the price volatility increases.
A Stochastic Model for a Price-Based Unit Commitment Problem
7.
137
CONCLUSIONS AND FUTURE DIRECTIONS
In this chapter, we present and model a general formulation of a pricebased unit commitment problem as a multi-stage stochastic programming problem under price and load uncertainties. We extend the method of unit decommitment using dynamic programming to solve this problem. The unit decommitment method is very efficient in computation and does not require a fine-tuning process for algorithm parameters like in the Lagrangian relaxation method. Preliminary numerical test results are promising. When we use a scenario tree to describe the evolution of uncertainties as presented in this research, it can be fully and efficiently integrated with a dynamic programming approach such as the proposed unit decommitment method. The establishment of scenario trees remains an open problem. Statistical methods can be used to measure the correlation of random variables such as prices and loads at different hours. Also, the scenario trees seem to suffer the curse of dimensionality. We demonstrate, using the example of short-term generation asset valuation, that under some problem structure the dimensionality curse can be relieved. How to model the stochastic unit commitment problem such that it can provide a nice structure to cope with the dimensionality problem, and can still reflect real operational restrictions, seems to be a new direction of research.
REFERENCES 1.
C.L. Tseng. On Power System Generation Unit Commitment Problems, Ph.D. Thesis, University of California at Berkeley, 1996.
138 2.
3. 4.
5. 6. 7. 8.
9. 10.
11. 12. 13. 14.
15.
16. 17. 18. 19. 20. 21. 22.
The Next Generation of Unit Commitment Models W.G. Chandler, P.L. Dandeno, A.F. Gilmn, and L.K. Kirchmayer. Short-range operation of a combined thermal and hydroelectric power system. AIEE Trans., 733: 1057-1065, 1953. C.K. Pang and H.C. Chen. Optimal short-term thermal unit commitment. IEEE Trans. Power Apparatus Syst., 95(4): 1336-1342, 1976. C.K. Pang, G.B. Sheble, and F. Albuyeh. Evaluation of dynamic programming based methods and multiple area representation for thermal unit commitments. IEEE Trans. Power Apparatus Syst., 100(3): 1212-1218, 1981. A.J. Wood and B. F. Wollenberg. Power Generation, Operation and Control. New York: Wiley, 1984. A. Turgeon. Optimal unit commitment. IEEE Trans. Autom. Control, 23(2): 223-227, 1977. A. Turgeon. Optimal scheduling of thermal generating units. IEEE Trans. Autom. Control, 23(6): 1000-1005, 1978. T.S. Dillon. Integer programming approach to the problem of optimal unit commitment with probabilistic reserve determination. IEEE Trans. Power Apparatus Syst., 97(6): 2154-2164, 1978. J.A. Muckstadt and S. A. Koenig. An application of Lagrangian relaxation to scheduling in power-generation systems. Oper. Res., 25(3): 387-403, 1977. D.P. Bertsekas, G.S. Lauer, N.R. Sandell Jr., and T.A. Posbergh. Optimal short-term scheduling of large-scale power systems. IEEE Trans. Autom. Control, 28(1): 1-11, 1983. J.F. Bard. Short-term scheduling of thermal-electric generators using Lagrangian relaxation. Oper. Res., 36(5): 756-766, 1998. S. Takriti, J.R. Birge, and E. Long. A stochastic model for the unit commitment problem. IEEE Trans. Power Syst., 11(3): 1497-1508, 1996. R.T. Rockafellar and R.J.-B. Wets. Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res., 16(1): 119-147, 1991. P. Carpentier, G. Cohen, J.-C. Culioli, and A. Renaud. Stochastic optimization of unit commitment: a new decomposition framework. IEEE Trans. Power Syst., 11(2): 10671073, 1996. C.C. Carøe and R. Schultz. A Two-Stage Stochastic Program for Unit Commitment under Uncertainty in a Hydro-Thermal Power System. Working paper, University of Copenhagen, Institute of Mathematics, Denmark, 1998. C.A. Li, R.B. Johnson, and A.J. Svoboda. A new unit commitment method. IEEE Trans. Power Syst., 12(1): 113-119, 1997. C.L. Tseng, S.S. Oren, A.J. Svoboda, and R.B. Johnson. A unit decommitment method in power system scheduling. Elec. Power Energy Syst., 19(6): 357-365, 1997. C.L. Tseng, C.A. Li, and S.S. Oren. Solving the unit commitment problem by a unit decommitment method. J. Optimization Theory Appl., 105(3), 2000 (in press). C.L. Tseng and G. Barz. “Short-term generation asset valuation.” In Proc. 32nd Hawaii International Conf. Syst. Sci. (CD-ROM), Maui, Hawaii, Jan 5-8, 1999. M. Hsu. Spark spread options are hot! Electricity J., 11(2): 28-39, 1998. G. Barz. Stochastic Financial Models for Electricity Derivatives. Ph.D. Thesis, Stanford University, 1999. C.L. Tseng. Valuing the operational real options of a power plant using discrete-time price trees. Submitted to Elect. Power Energy Syst.
Chapter 8 PROBABILISTIC UNIT COMMITMENT UNDER A DEREGULATED MARKET Jorge Valenzuela and Mainak Mazumdar University of Pittsburgh
Abstract:
1.
In this paper, we propose a new formulation of the unit commitment problem that is suitable for the deregulated electricity market. Under these conditions, an electric power generation company will have the option to buy or sell from a power pool in addition to producing electricity on its own. We express the unit commitment problem as a stochastic optimization problem in which the objective is to maximize expected profits and the decisions are required to meet the standard operating constraints. Under the assumption of competitive market and price-taking, we show that the unit commitment problem for a collection of M generation units can be solved by considering each unit separately. The volatility of the spot market price of electricity is represented by a stochastic model. We use probabilistic dynamic programming to solve the stochastic optimization problem pertaining to unit commitment. We show that for a market of 150 units the proposed unit commitment can be accurately solved in a reasonable time by using the normal, Edgeworth, or Monte Carlo approximation methods.
INTRODUCTION
In the short-term, typically considered to run from twenty-four hours to one week, the solution of the unit commitment problem (UCP) is used to assist decisions regarding generating unit operations [1]. In a regulated market, a power generating utility solves the UCP to obtain an optimal schedule of its units in order to have enough capacity to supply the electricity demanded by its customers. The optimal schedule is found by minimizing production cost over a time interval while satisfying demand and operating constraints. Minimization of the production costs assures maximum profits because the power generating utility has no option but to supply the prevailing load reliably. The price of electricity over this period is predetermined and unchanging; therefore, operating decisions have no effect on the firm’s revenues. As various regions of the United States implement deregulation [2], the traditional unit commitment problem continues to remain applicable for the
140
The Next Generation of Unit Commitment Models
commitment decisions made by the Independent System Operator (ISO). The ISO resembles very much the operation of a power generating utility under regulation. The ISO manages the transmission grid, controls the dispatch of generation, oversees the reliability of the system, and administers congestion protocols [3,4,5]. The ISO is a non-profit organization. Its economic objective is to maximize social welfare, which is obtained by minimizing the costs of reliably supplying the aggregate load. Under deregulation, the UCP for an electric power producer will require a new formulation that includes the electricity market in the model. The main difficulty here is that the spot price of electricity is no longer predetermined but set by open competition. Thus far, the hourly spot prices of electricity have shown evidence of being highly volatile. The unit commitment decisions are now harder and the modeling of spot prices becomes very important in this new operating environment. Different approaches can be found in the literature in this regard. Takriti et al. [6] have introduced a stochastic model for the UCP in which the uncertainty in the load and prices of fuel and electricity are modeled using a set of possible scenarios. The challenge here is to generate representative scenarios and assign them appropriate probabilities. Allen and Ilic [7] have proposed a stochastic model for the unit commitment of a single generator. They assume that the hourly prices at which electricity is sold are uncorrelated and normally distributed. In [8] Tseng uses Ito processes to model the prices of electricity and fuel in the unit commitment formulation. The purpose of this chapter is to present a new formulation to the UCP suitable for an electric power producer in a deregulated market and consider computationally efficient procedures to solve it. We express the UCP as a stochastic optimization problem in which the objective is to maximize expected profits and to meet operating constraints such as capacity limits and minimum up- and down-times. We show that when the spot market of electricity is included, the optimal solution of a UCP with M units can be found by solving M uncoupled sub-problems. We obtain a subproblem by replacing the values of the Lagrange multipliers by spot power prices. The volatility of the spot market price of electricity is taken into account by using a variation of the stochastic model proposed by Ryan and Mazumdar [9], The model, which is referred to as the probabilistic production-costing model, incorporates the stochastic features of load and generator availabilities. It is often used to obtain approximate estimates of production costs [10,11,12]. This model ignores the unit commitment constraints and assumes that a strict predetermined merit order of loading prevails. This implies that a generator will be dispatched only when the available unit immediately preceding it in the loading order is working at its full capacity. We believe that this model provides a good approximation to the operation of an electricity market, such as the California market, in which no centralized unit commitment decisions are taken. The model cap-
Probabilistic Unit Commitment
141
tures the fundamental stochastic characteristics of the system. At any moment, a power producer may not be fully aware of the exact characteristics of the units comprising the market at that particular time. But it is likely to possess information about the steady state statistical characteristics of the units participating in the market. Ryan and Mazumdar’s probabilistic production costing model can be used to provide a steady-state picture of the market. We determine the hourly spot market price of electricity by the marketclearing prices. The market-clearing price can be shown to be the variable cost or bid of the last unit used to meet the aggregate load prevailing at a particular hour. This unit is called the marginal unit. We determine the probability distribution of the hourly market-clearing price based on the stochastic process governing the marginal unit, which depends on the aggregate load and the generating unit availabilities. We model the aggregate load as a GaussMarkov stochastic process and use continuous-time Markov chains to model the generating unit availabilities [10,13]. We assume that the information is available on mean time to repair, mean time to failure, capacity, and variable operating cost of each unit participating in the market required to characterize these processes. We use probabilistic dynamic programming to solve the stochastic optimization problem pertaining to unit commitment. We also report results on the accuracy and computational efficiency of several analytical approximations as compared to Monte Carlo simulation in estimating probability distributions of the spot market price for electric power.
2.
FORMULATION
We consider the situation in which an electric power producer owns a set of M generating units and needs to determine an optimal commitment schedule of its units such that the profit over a short period of length T is maximized. Revenues are obtained from fulfilling bilateral contracts and selling electric power, at spot market prices, to the power pool. It is assumed that the electric power company is a price-taker. If at a particular hour the power supplier decides to switch on one of its generating units, it will be willing to take the price that will prevail at this hour. We also assume that the power supplier has no control over the market prices and the M generating units will remain available during the short time interval of interest. In determining an optimal commitment schedule, there are two decision variables, denoted and The first variable denotes the amount of power to be generated by unit at time and the latter is a control variable, whose value is “1” if the generating unit is committed at hour and “0” otherwise. The cost of the power produced by the generating unit depends on the amount of fuel consumed and is given by a known cost function
142
The Next Generation of Unit Commitment Models
where is the amount of power generated. The start-up cost, which for thermal units depends on the prevailing temperature of the boilers, is given by a known function The value of specifies the consecutive time that the unit has been on (+) or off (-) at the end of the hour In addition, a generating unit must satisfy operating constraints. The power produced by a generating unit must be within certain limits. When the generating unit is running, it must produce an amount of power between and If the generating unit is off, it must stay off for at least hours, and if it is on, it must stay on for at least hours.
2.1
Problem Formulation
The objective function is given by the sum over the hours in the interval [0,T] of the revenue minus the cost. The revenue is obtained from supplying the bilateral contracts and by selling to the power pool at a price of per MWH the surplus energy produced in each hour t. The cost includes the cost of producing the energy, buying shortfalls (if needed) from the power pool, and the start-up costs. Defining the supply amount stipulated under the bilateral contract by and by R ($/MWH) the price, the objective function (maximum total profit) is given by:
A positive value of indicates that megawatts hour are bought from the power pool and a negative value indicates that megawatts hour are sold to the pool. Since the quantity is a constant, the optimization problem reduces to:
subject to the following constraints(for Load: Capacity limits:
and
Probabilistic Unit Commitment
143
Minimum down-time: Minimum up time: where and
unrestricted in sign
After substituting in the objective function the value of obtained from Equation 4, we re-write Equation 3 as follows
which after removing constant terms is equivalent to:
subject to the operating constraints. Because the constraints (5) to (7) refer to individual units only, the advantage of Equation 9 is that the objective function is now separable by individual units. The optimal solution can be found by solving M de-coupled subproblems. Thus, the subproblem for the unit
subject to operating constraints of the unit. Equation 10 is similar to the subproblem obtained in the standard version of the UCP [14] excepting that the value of the Lagrange multipliers are now replaced by the spot market price of electricity.
2.2 Stochastic Formulation of the Subproblem We next consider the spot market price of electricity, which is determined by the market-clearing price, as a random variable. When the optimization subproblem is being solved for a particular unit, we assume that the mar-
144
The Next Generation of Unit Commitment Models
ket, which includes the M-1 units owned by the power producer solving the problem, consists of N generating units (N>>M). The generating unit for which the subproblem is solved is excluded from the market. We assume that the unit commitment decisions for any one unit have a negligible effect on the determination of the marginal unit of the market for a given hour. To model the market-clearing price, we assume that the generators participating in the market are brought into operation in an economic merit order of loading. The unit in the loading order has a capacity (MW), variable energy cost ($/MWH), and a forced outage rate Under the assumption of economic merit order of loading, the market-clearing price at a specific hour is equal to the operating cost (S/MWH) of the last unit used to meet the load prevailing at this hour. The last unit in the loading order is called the marginal unit and is denoted by The market-clearing price, is thus equal to The values of and depend on the prevailing aggregate load and the operating states of the generating units in the loading order. We write the objective function of the subproblem for one of the M generating units as follows:
subject to the operating constraints: capacity limits, minimum up-time, and minimum down-time.
2.3
Probabilistic Dynamic Programming Solution
The maximum profit over the period T (Equation 11) is a random variable because the hourly market-clearing price is a random variable. We assume that at the time of the decision, hour zero, the marginal unit and the load for all the hours before hour zero are known. We denote the marginal unit at time zero by and solve the subproblem by maximizing the conditional expected profit over the period T. We express the objective function as:
This equation is subject to the same operating constraints described earlier. We use probabilistic dynamic programming to solve this optimization problem. We define the function by the following equation:
Probabilistic Unit Commitment
145
This function denotes the maximum profit at hour given that at this hour the unit is determining the market-clearing price and the generator to be scheduled is in the operating state We also define the recursive function to be the optimum expected profit from hour to hour T of operating the generator that is in state at time Thus, the expression for hour zero is
For hour
the expression is given by the following recursive relation:
Setting the expected incoming profit at time T+1 to be zero we obtain the boundary condition for the last stage
The initial conditions are given by the initial state of the generator and and the marginal unit at hour zero Consequently, the optimal schedule is given by the solution of To solve the problem, the following conditional probabilities need to be computed:
Thus, the joint probability distribution of probability distribution of are needed.
3.
and
and the marginal
STOCHASTIC MODEL FOR THE MARKETCLEARING PRICE
The stochastic model of the market-clearing price uses the productioncosting model proposed by Ryan and Mazumdar [9]. This model has been used in estimating the mean and variance of production cost [12] and marginal cost [15] of a power generating system.
146
3.1 1.
2.
3.
4.
5.
The Next Generation of Unit Commitment Models
Stochastic Model of the Market
The assumptions of a market model with N generating units are: The generators are dispatched at each hour in a fixed, pre-assigned loading order, which depends only on the load and the availability of the generating units. Operating constraints such as minimum up- and down-times, spinning reserve, and scheduled maintenance are not considered. The unit in the loading order has capacity (MW), variable energy cost (S/MWH), mean time to failure mean time to repair and forced outage rate, After adjusting for the variations in the ambient temperature and periodicity, the load at time is assumed to follow a Gauss-Markov process [16,17] with and where and are assumed to be known. (An analysis given in [13] validates this assumption.) The operating state of each generating unit follows a two-state continuous-time Markov chain, with failure rate and repair rate The forced outage rate equals For and are statistically independent for all values of and Each is independent of for all values of
3.2
Probability Distribution of the Marginal Unit
To derive an analytical expression for the probability mass function of the marginal unit at time first note that and that the events
and
are equivalent. Thus,
the following equality holds:
3.3
Thus, to obtain the probability mass function of
the probability that
is greater than zero for all values of
needs to be computed.
Bivariate Probability Distribution of the Marginal Unit
An analytical approximation for the bivariate probability mass function of and needed for evaluating Equation 17, requires the following development. Writing
Probabilistic Unit Commitment
147
and