THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING SCHEDULING IN POWER SYSTEMS John A. Muckstadt A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan Department of Industrial Engineering 1966 October, 1966 IP-752

Doctoral Committee: Professor Richard C. Wilson, Chairman Assistant Professor Hugh E. Bradley Associate Professor Anthony J. Pennington Professor Robert M. Thrall

PREFACE I wish to express my sincere appreciation to Professor Richard C. Wilson who has been a most stimulating advisor. Appreciation is also extended to the other members of my doctoral committee who provided valuable assistance in the development of this dissertation. I also wish to thank Mr. L. R. Stahl of the Detroit Edison Co. for his enlightening comments on the operation of a large power system. Particular thanks go to the United States Air Force for granting me the time and support to pursue this research. The Industry Program of the College of Engineering at the University of Michigan has provided help in the preparation of the manuscript for which I wish to express my appreciation. Finally, I thank my family for their encouragement and understanding. ii

TABLE OF CONTENTS Page PREFACE,.,............................00.....0.. ii LIST OF TABLES.............................................. vi LIST OF ILLUSTRATIONS.......... vii LIST OF APPENDICES...................e..e......6.... e Viii LIST OF BASIC SYMBOLS...................................... ix CHAPTER I. - INTRODUCTION..................... 1 1.1. The Problem..................................... 1 1.2. A Summary of the Dissertation........ 2 CHAPTER II. - A DISCUSSION OF THE FACTORS INFLUENCING POWER SYSTEM SCHEDULING AND RELEVANT LITERATURE......... 5 2.1. Introduction..............................O........... 5 2.2. Operating Costs................... o.......... 5 a) Fuel Costs..................................... 5 b) Maintenance Costs O... O.......O......O 7 c) Costs Due to Transmission Losses.. 8 d) Start Up Costs............................ 8 e) Other Costs...............,...o........o....... 10 2.3. Operating Restrictions....,..... 10 a) Capacity Restrictions..................Oo..... 10 b) Reserve Requirements................ e 6e * e@ @@ 11 2.4. A Review of the Scheduling Literature.................. 12 a) The Economic Dispatch Problem........ 12 b) Scheduling Methods....... 15 i) Priority List Scheduling..................... 15 ii) Other Approximate Scheduling Techniques..... 16 iii) Generation Scheduling by Dynamic Programming. 17 iv) Generation Scheduling by Integer Programming. 19 2.5. Some Results in Stochastic Linear Programming,......... 20 CHAPTER III.- AN INTEGER LINEAR MODEL FOR THE POWER SYSTEM SCHEDULING PROBLEM WHEN DEMAND FOR POWER IS UNCERTA IN..................... 22 iii

TABLE OF CONTENTS (CONT I'D) Page 3.1. Introduction,.................................... 22 3,2, A One Period Scheduling Model.,.O.,................ 22 a) Introduction................. 22 b) Basic Assumptions.................................. 23 c) The Demand Process................................. 23 d) The Constraints.................................... 26 i) Introduction............................. 26 ii) Start Up Constraints......................... 26 iii) Demand Constraints........................... 26 iv) Reserve Constraints,...................,,,,,, 27 v) Power Availability Constraints........... 27 e) The Objective Function...................... o...... 28 i) Introduction.... e......................... 28 ii) Start Up Costs..................... 29 iii) Minimum Level Fuel Costs.................... 29 iv) Incremental Production Costs................. 29 f) Summary................ o........ oo.............. 32 3.3. Extensions of the One Period Model..................... 33 a) Introduction,........................ o........ 33 b) Transmission Losses................................ 34 c) Manpower Constraints............................... 34 d) Geographical Reserve Constraints.......... e....... 35 e) Multiple Interconnections,........................o 35 f) Common Header Units...,.................... 36 g) A Q Period Model.............................. 36 CHAPTER IV. - THE STRUCTURE AND SOLUTION OF THE BASIC INTEGER LINEAR MODEL.................................. 41 4.1. Introduction........................................... 41 4.2. Partitioning In a Mixed Integer Continuous Linear Programming Problem.................................... 41 4.3. The Structure of the One and Q Period Models.......... 42 4.4. An Algorithm For a Mixed Integer Continuous Linear Programming Problem.................................... 50 4.5. A Solution Method For the Restricted Integer ProblemSubproblem One......................................... 52 a) Introduction.............. o....................6 52 b) Solution by Enumeration............................ 54 c) Rules For Excluding Vectors From Consideration..... 56 iv

TAB3LE OF COINTENTS (CONI'D) Page 4o6. The Inside Problem-Subproblem Two............. e.o 58 a) Introduction,.,,..... O h O 1. 58 b) The Problem minuID2U: U > W1 - Wo, U ~2 O} oo.e.....eo 59 c) The Problem min {Sj,t D3pt ~ SjtlnN+l = bt-m*(Wl), Sj t O ST < W~ Si t 2 O }................................. 59 4,7. The Generation of a New Constraint,....................... 63 a) Introduction,....................................... 63 b) The Dual Problem of minU {D2U' U > W1 - Wo, UOO}. 63 c) The Dual Problem of min {Sj,t D3 * Sjt lnN+l Sij,;t b mjt ST < W Sjt > 0O.................... 64 t m (Wl)., t - - Sj t = d) The New Constraint................................... 69 4,8, Some Comments On the Algorithm..,...........e 70 CHAPTER V. - AN EXAMPLE AND A FLOW CHART OF THE ALGORITHM oe.........oe 73 5. io Introduction........... o............ oo.................. 73 5, 20 The Example,.............................................. 73 CHAPTER VI. SUMMARY AND CONCLUSIONS. o............................ o o o 80 6, 1 The Model,,................................................ooOoo 80 a) Features of the Model,............................... 80 b) Structure of the Model and Dual Analysis............ 81 c) Some Practical Problems,,,,...................... 82 6,2, The Algorithm. oo................. o.......................... 0 83 a) A Review of the Algorithm.......,,......O........o... 83 b) Features of the Algorithm................. 84 c) Algorithmic Limitations.............................. 85 6,3a General Extensions and Future Research................... 87 B IBLIOGRAPHY o. oooo e Oooo*oo ooo............................o*..ed O... o 127

LIST OF TABLES Table Page I Cost Table.............................................. 74 II Summary of Calculations For the Case of No Initial Constraints................................... 8 III Summary of Calculations For the Case of Initial Constraints..O.OO..O.........e.oo e................. 79 vi

LIST OF ILLUSTRATIONS Figure Page 1. An Example of the Method Used to Describe the Demand Process................................................ 25 2. An Incremental Production Cost Curve For Fictitious Unit i.............................................. 30 3. A Descriptive Flow Chart of the Algorithm............. 74 vii

LIST OF APPENDICES Appendix Page I A Detailed Flow Chart.................................. 93 II Calculations for the Example......................... 106 viii

LIST OF BASIC SYMBOLS (O,T] is the scheduling horizon,,where T is measured in hours. N is the number of generating units considered in the problem. w?~ ~=1, if unit i is operating at time 0 O, otherwise. W1 =1, if unit i is operating in (O,T] 0, otherwise. Ui f1, if unit i is started at time 0 0, otherwise. mi is the output capability of generating unit i when operating at its minimum capacity level measured in mw. Mi is the output capability of generating unit i when operating at its maximum capacity level measured in mw. R is the minimum amount of operating capacity desired for the entire system measured in mw. N (W1) = i=l i' m* (W1) = Z mi iw. M is the maximum amount of power available through the interconnection in mw. Mi,k is the amount of power in mw generating unit i is capable of producing in step k. r is the number of subintervals considered in (O,T]. A = T/r. n is the number of steps in the incremental production cost curves for each generating unit. X; is the discrete random variable describing demand in subinterval j such that P(Xj = blj) > O,.,P(X = b ) > O, P(Xj = b ) +... + P(Xj = be.) = 1, and bl < <.. < b where btj is the t-th a I Ij c i') c demand level in subinterval j that has a positive probablity of occurring. ix

3= J {btj: P(Xj = btj) > 0} = {bl,...,b}, where bl,....,b are defined such that b1 <... < b~. 63 is then a set whose elements are the demand levels bt, t=l,...,~, having a positive probability of occurring in at least one subinterval j of (O,T], j=l,...,r. pj is the probability that Xj = bt Z et is the amount of power purchased from the interchange in subinterval j at the t-th demand level measured in mw. Si kj,t is the amount of power in mw produced by generating unit i at incremental production cost level k in subinterval j at demand level t. Ci is the cost in dollars of starting up unit i. ki is the cost of operating generating unit i at its minimum output level measured in dollars per hour. gi,k is the incremental production cost of unit i in step k measured in dollars per mw-hr. h is the incremental cost of power purchased from the interchange measured in dollars per mw-hr. D1 = [Tkl,...,TkN] is an N dimensional vector. D2 = [c1,...c N] is an N dimensional vector. D3 = [A gl,'''... gl1 n, gN,l'.. g,A n, h] is an nN + 1 dimensional vector. S 1,1,1,1.. S1.9nl N1,1 I... SNn,l,lI Zl,l 31,i S,l,r,l... Sl,n,r,l SN,l,r,l'1' SN,n,r,l Zrl Sr,l 1 S1lr 1 r.. Si1 nr I.~. SN lr,'' SN,n,r,I r, Sr, where Sjt is the jt-th row of the matrix S.

W1 = [w~.oo, w1] is an N-dimensional vector. W O W OO[W e.,, ] is an N-dimensional vector. Wi= [wl M 1,...wi Min] is an n-dimensional vector. W - [WW1 ~oW N,M]T is an (nN+1)-dimensional vector. U = [Ul,..,uN] is an N-dimensional vector. lnN+l = [1,1,. o o 1] is an nN+l-dimensional vector. xi

CHAPTER I INTRODUCTION 1.1 The Problem The problem studied in this dissertation is that of scheduling a fossil fuel power generation system over a short time horizon so as to minimize the total expected operating costs when demand for power is a random variable. Power system scheduling has been investigated for the past twenty years resulting in numerous scheduling techniques- most of which provide a solution for only the economic dispatch portion of the scheduling problem. "Economic dispatch" is allocating load among a given set of generating units designated to operate for a specified interval of time, called a period, so as to minimize operating costs. The question of how to determine which generating units to operate in each period of the horizon is not answered by economic dispatch. This aspect of power generation scheduling nevertheless is important since large costs are incurred when starting up generating units. Some effort has been devoted to solving this second aspect of power system scheduling, sometimes independently of economic dispatch. However, none of the present scheduling techniques permit the randomness of the demand process to be considered directly. As is shown, the fact that demand is a random variable can affect the choice of an optimum operating schedule for the horizon. In this dissertation we investigate selecting that combination of generating units to operate at economic dispatch in each period of a given short time horizon which minimizes the expected cost of meeting the demand, while satisfying certain operating constraints. -1

-2The main objectives of this dissertation are to provide a mathematical model of the power system scheduling problem, investigate the underlying structure of the model, indicate some properties of the solution, and provide a new computational procedure for solving the problem. 1.2 A Summary of the Dissertation1 The major factors that influence scheduling in power systems are presented in Chapter II. Current scheduling methods and some pertinent mathematical results are also discussed in Chapter IIL In Chapter III, a basic integer linear programming model for one period power system scheduling is introduced. In this model, demand for power is assumed to be a discrete random variable. This model includes the effects of starting generating units, system reserve requirements, the demand process, and generating unit capacity constraints as linear constraints. It is desired to find an operating schedule that minimizes the sum of the start up costs, the minimum level fuel costs and expected incremental production costs subject to the above linear constraints. We show how this one period model can be extended to include the additional effects of transmission losses, manpower availability constraints, multiple interconnections and common header units. Extensions of the basic one period model to Q periods, and to include time dependent start up costs are given. The Q period model is shown to be mathematically equivalent to Q copies of the one period model. Chapter IV contains a procedure for partitioning the one and Q period optimization problems introduced in Chapter III into two subproblems; 1 The terms used in this section are defined in Chapter II.

namely, subproblem one which is a (0,1) integer problem for the operational commitment status of the generating units and subproblem two which is a linear programming problem for economic dispatch and start up costs. We show that for a given solution to subproblem one. subproblem two is decomposable into many independent problems. Some of these, corresponding to the start up costs, have the following form: minimize the value of a continuous valued variable such that the value the variable assumes must be greater than or equal to a given finite constant. The remainder are independent transportation problems for economic dispatch. We demonstrate that all basic1 solutions to the power system scheduling problem are integer. A primal algorithm based on the partitioning procedure due to Bender45'6) is used. A special algorithm is developed for solving the primal and dual of subproblem two. The algorithm is shown to possess the following properties: each iteration yields a feasible solution; also, each interation produces upper and lower bound estimates of the optimal value of the objective function; approximate solutions can be obtained if desired, and prior experience can be used to generate constraints for subproblem one, that is, for the unit commitment problem. The algorithm is shown to terminate in a finite number of iterations. A descriptive flow chart of the algorithm and an example problem are given in Chapter Vo The algorithmic features discussed above are illustrated through this example, presented originally by Garver(20) who solved the problem using Gomory's all integer programming algorithm(25)0 Comparisons between the solution methods are given. Details of the calculations for the first two iterations of the algorithm are given in Appendix II. A detailed flow chart of the algorithm is presented in Appendix I. 1 Define a solution to be a basic solution to the power scheduling problem if and only if the portion of the solution corresponding to subproblem two is basic.

The model for the power system scheduling problem presented in this dissertation is the most general known to date. It allows the effects of randomness in the demand process and availability of power from interconnections to be directly evaluated for the first time. We also show how the expected selling price for power can be determined in order to obtain a specified expected profit per megawatt hour. The algorithm takes advantage of the simple structure of the problem in its computational procedure. The applicability of the algorithm, like that of other proposed solution methods, is shown to be limited by the number of integer variables in the problem structure, that is, the total number of generating units considered in the Q period horizon, Nevertheless, core storage requirements and computation time are estimated to be small compared to those required for Gomory's algorithm or a dynamic programming algorithm.

CHAPTER II A DISCUSSION OF THE FACTORS INFLUENCING POWER SYSTEM SCHEDULING AND RELEVANT LITERATURE 2,1 Introduction In the first portion of this chapter, the operating costs and operating restrictions related to the scheduling of a fossil fuel power generation system are presented. In the following section the literature related to the problem is discussed, The chapter is concluded with a discussion of some pertinent mathematical results. 2,2 Operating Costs a) Fuel Costs By far the greatest cost incurred when operating a fossil fuel generating system is the cost of fuel(15)o Therefore, in any scheduling procedure the fuel costs must be considered. Fuel costs are incurred in different wayso One type of fuel cost is incurred when a boiler is fired to start a generating unit, A second type of fuel cost that is incurred is the minimum level fuel cost, If a generating unit is operating, it is required to operate such that its output level is not less than its minimum capacity level(39), The minimum level fuel cost is defined to be the cost incurred when a generating unit is operating at its minimum capacity level, This cost is measured in dollars per hour. When a unit operates at a level above its minimum capacity level, an additional fuel cost is incurred. This cost is a function of the incremental fuel cost curve associated with the generating unit, The incremental fuel cost at a given output level is defined to be the increase in fuel cost

-6per unit increase in power output per hour at that output level. It is measured in dollars per megawatt hour (mw-hr). The fuel cost incurred when operating a unit above its minimum capacity is found by integrating its incremental fuel cost curve over the appropriate range1. Thus the total fuel cost per hour associated with operating a generating unit at a given level can be expressed as the sum of the minimum level fuel costs and the integral of the incremental fuel cost function over the appropriate range. The fuel costs associated with starting a generating unit are discussed in more detail in 2.2e). The minimum level fuel costs are adequately described above. However, further discussion related to the incremental fuel costs is necessary. The remainder of this subsection is devoted to this discussion. There are three types of performance curves calculated for each generating unit. The first curve discussed is the input-output curve. It indicates the amount of fuel input, measured in British Thermal Units (BTU) per hour, as a function of the output measured in megawatts (mw). A second curve is called the heat rate curve, It is obtained by dividing the input by the corresponding output. This curve is measured in BTU per kilowatthour (kw-hr) as a function of the power output of the unit measured in mw. The third curve is the incremental fuel rate curve, The incremental fuel rate for a given output is equal to the instantaneous rate of change of the input-output curve at the given output level assuming it exists, This curve is then measured in BTU per kw-hr as a function of the power output measured in mw. The incremental fuel cost for a given output is obtained by multiplying 1 It is usually assumed that the incremental fuel cost Burye is either cons tinuous or discontinuous at a finite number of points 39 so that the integral is either a Riemann integral or is a Riemann-Stieltjes integral which in this case can be written as the sum of a finite number of Riemann integrals.

-7the corresponding incremental fuel rate times cents per million BTU. It is possible that the cost per BTU for various units may differ since the cost of fuel delivered to different generating stations may not be the same. It is often assumed that the incremental fuel cost curve is a monotone increasing convex function(31'39) However, for typical multivalved generating units this assumption is incorrect(39). In fact, the slope of the input-output curve is approximately constant between valve points. Thus the incremental fuel cost curve is approximately constant between valve points. The resulting incremental fuel cost curve is a step function with increases occurring at those load points at which the valves are opened. In (39), this step function form for the incremental fuel cost curve is assumed to adequately describe the incremental fuel costs and is the for; assumed for this curve in this dissertation. b) Maintenance Costs Although fuel costs can be expressed, at least partially, as a function of the megawatt load placed on a generating unit, to date no method has been developed which allows maintenance costs to be charged in this manner. Steinberg(38), however, states that incremental maintenance costs are usually determined as a matter of judgment based on annual costs. These annual costs, determined from accounting records, are sometimes used to establish the incremental maintenance cost as a given value per mw-hr for each generating unit. G. V. Williamson, in a discussion following Steinberg's paper, demonstrates the usefulness of another method used for charging incremental maintenance costs presented in (38); namely, charging them as a fixed percentage of the incremental fuel costs. Steinberg points out that by using either of these methods, the obtained values will at best be approximations. Since maintenance costs account for only about 10% of the operating costs per

-8year(15), Steinberg says that either of these approximate techniques for charging incremental maintenance costs is adequate for scheduling purposes. In the remainder of this dissertation it is assumed that the latter of the two methods described above is used to generate the incremental maintenance cost curve for each unit. The incremental production cost curve is defined to be the sum of the incremental fuel cost curve and the incremental maintenance cost curve. Since the incremental fuel cost curves are assumed to be step functions, it is easy to see that the incremental production cost curves also are step functions. c) Costs Due to Transmission Losses The development of large power systems and interconnected systems has necessitated the consideration of not only the fuel costs incurred due to the relative efficiencies of the generating units, but also of the fuel costs incurred due to transmission losses. It has been demonstrated(31) that by considering the effect of incremental transmission losses on the economic dispatch of the generating units, savings in fuel costs of up to one hundred dollars per year per megawatt of installed peak capacity have been realized. Methods used for including the effect of transmission losses on the economic dispatch of a set of generating units are discussed in 2.4. d) Start Up Costs Another important cost which affects the choice of an operating scheduille is the cost of starting up the generating units. The cost of starting a unit is divided into two parts; namely, the cost of fuel and the costs of labor and maintenance(3'38). If a unit is shut down, the boiler is either shut down and allowed to cool or the boiler is banked in which case the boiler is kept operating but is disconnected from the turbines. If the boiler is banked, it is necessary

-9to supply the boiler with a sufficient amount of fuel to maintain at least minimum boiler pressure and temperature. On the other hand, if the boiler is not banked,then the temperature in the boiler drops exponentially as a function of time(3). In (3), the following equation is given to express the cost of starting a unit as a function of the time the unit has been shut down when the boiler is allowed to cool. cost = B[1-e-(t-l)] + K, t > 1 where t is the number of hours the unit has been shut down, B is the cost of starting the boiler when it is cold, a is the cooling constant of the boiler and K is the cost of starting the turbine plus maintenance and labor costs. If a boiler is banked, then a constant amount of fuel will have to be supplied in each hour. Thus the accumulated cost at start up when a boiler is banked is cost = Bl(t-l) + K, t > l where B1 is the cost of banking the boiler in dollars per hour, and t and K are defined as above. In (13), it was demonstrated that the optimum operating schedule is altered when start up costs are included in the objective function along with the incremental production costs and costs due to transmission losses. This occurs mainly due to the fact that in a typical weekday demand curve, a morning, an afternoon and an evening peak are present. See, for example, demand curves in (3). Between the peaks there may be an opportunity to shut down some units since the demand on the system has dropped. However, these units, although not needed to meet demand requirements during the period of

-10decreased demand, may be needed to meet the increased demand requirements placed on the system at the next peak. If the units were shut down, they would;have to be restarted. Whether or not it is economically desirable to shut down a unit during a period when its output is no longer required to meet demand requirements depends upon the cost of keeping the unit operating versus the cost of restarting the unit. Other factors, such as reserve requirements which are discussed in the next section, may take priority over these economic considerations however. The topic of startup costs is discussed in detail in (3). (e) Other Costs There are other costs which might be considered when determining an operating schedule. For example, the cost of supplies could be included. In (38), it is stated that the cost of supplies is not appreciably affected by the schedule and thereby may be omitted. In certain areas, for example West Texas, the cost of water could effect the schedule. These costs are excluded from consideration in this dissertation. 2.3 Operating Restrictions a) Capacity Restrictions There are maximum and minimum power output capacities for each generating unit. These levels are determined by the thermal constraints on the turbines and the capabilities of the boilers in each unit(39).'. In addition to these limitations, the operation of the generating units is restricted by the rate at which the units-can pick up load after being started up. The amount of time required to start up a unit is an important factor, too. Thus schedules must be determined far enough in advance to permit the units to be operational when needed.

-11There are also capacity restrictions on the amount of power available from interconnected, systems. The restriction may be due to the fact that the amount of power the interconnected systems have available for use is limited. This restriction may also be determined by the capacity of the tie lines with the interconnected systems. The general topic of the economics of interconnected systems is discussed in (32). The particular problem of determining the optimal tie line capacity is, for example, discussed in (41), In this dissertation, the interconnected companies are treated as additional generating units with specified capacity restrictions and incremental production costs. b) Reserve Requirements There is always a possibility of equipment failure, that is, of a forced outage, in a power system. Because forced outages occur at random times, it is necessary to schedule excess operating capacity to ensure that service is maintained, at least with some specified probability, in the event of an equipment failure. This excess capacity that is operated is called spinning reserve. A vast amount of literature is devoted to studying the question of how service reliability should be measured and how spinning reserve margins should be determined(1'2'7'1819'4042) These areas are outside the scope of this dissertation. It is assumed throughout that the spinning reserve margins are known. It is important, however, to examine some of the factors which need to be considered when determining spinning reserve margins and their effect on-the choice of an operating schedule. When an operating schedule is chosen, the effect of a possible transmission line failure must be considered, Such failures influence the amount of spinning reserve that is required, for it is necessary to have sufficient capacity scheduled in dispersed geographical regions to handle contingencies of this sort.

-12Reserve operating capacity is also necessary to provide protection against errors in the forecasted demand. Again, due to capacity restrictions on the transmission lines, it is necessary to schedule generating units to be operated in different geographical areas. 2.4 A Review of the Scheduling Literature a) The Economic Dispatch Problem The economic dispatch problem, as defined in 1.1, is that of allocating the demand for power among a given subset of operating generating units in order to minimize expected operating costs. The simplest method for obtaining an economic dispatch involves using only the incremental production costs for each unit to obtain the desired result. To use this technique, it is assumed the demand is known and the incremental production cost functions are monotone increasing, differentiable, and convex, The only explicit constraint imposed is that the demand be met, The economic dispatch occurs when the generating units are operated such that their incremental production costs are equal or such that some unit or units are operated at an operating limit(3l). The latter occurs only if a capacity constraint on a unit is violated in the optimal solution. This result is derived here for the sake of completehesso Suppose there are N generating units considered in the optimization- procedure. Furthermore,let Sn be the power output of unit n, Gn(Sn) be the production cost per hour for unit n when generating Sn mw of power, and D the known demand level. Then N Z Sn = D. (2.1) n=l The total production cost for the units is given by

13G Gn(Sn) The problem is solved using the Lagrangian multiplier technique. It is easy to see that the optimal solution occurs when N -~{G + X(D - Z Sn)} 0, (2.2) bsn n=l that is, when 6Gn dGn - - - =X, n=l,,..,N, where (2o3) asn dSn X is the Lagrangian multiplier. Equation (2.3) states that the optimum occurs when the incremental production costs of the units are equal. However, if the incremental production cost associated with some one of the generating units is less than X at its maximum capacity, then the unit is operated at its maximum output level. If, on the other hand, the incremental production cost of some generating unit is greater than X at its minimum output level, then that unit is operated at its minimum output level. As discussed in 2.2d), the economic dispatch of the generating units is altered when including the effect of transmission losses in the dispatching technique. In order to include this factor, a transmission loss formula expressing the total transmission losses in terms of the output of the generating units is required. Such a formula was first presented in 1943 by E. E. George(22) This formula is the following quadratic equation: L = Z Sm Bmn Sn, where m n L is the total transmission losses, Sm, Sn are the outputs of the generating units, and the Bmn are the transmission loss formula coefficients,

-14Since that time, much work has been done to improve the form of the transmission loss formula and to find more efficient methods of calculating the loss formula coefficients(l2'14'23'24'31,32,33,34) The economic dispatch technique discussed above can be altered to include the effect of transmission losses. Replacing (2.1) with D = Sn - L (2.4) and solving as before, it is easy to see that the optimal solution occurs when dGn L( -+ X-X X, n=l,...,N. (2.5) dSn 6Sn The Lagrangian multiplier X is interpreted as the incremental cost of received power. Many exact and approximate methods have been proposed for solving (2.5) (31 34) One such method, called the Penalty Factor Method (34, is discussed below, From (2.5), it follows that dGn 1 n { dS1 {~l-L/)Sn} (2.6) dSn l n dGn 6L {L 2 1 dSn {1 + an + +. } (2.7) If the incremental transmission losses for each n are very much less than 1, then, upon dropping the terms which are powers two and greater of aL/6Sn, X can be approximated by dGn L+ aT dSn En.

that is, Xdn {1+ + o (2.8) dSn n Thus it is easy to see that the Penalty Factor Method corresponds to charging the incremental transmission loss associated with unit n at a rate proportional to the incremental production cost associated with that unit. The penalty factor {1 + aL } is sometimes assumed to be a constant for a given period of time. If the incremental production cost functions for the generating units are step functions, then the following method is used to obtain the economic dispatch among a given subset of generating units. The optimum solution is obtained by loading up the steps of the incremental production cost curves in ascending order of these costs until the required output is attained. The Penalty Factor Method can be used to include the effect of transmission losses. It is easy to see that this method of obtaining the economic dispatch among the units is mathematically equivalent to the one described above. b) Scheduling Methods i) Priority List Scheduling The determining of the most economic combination of generating units to be operated at a given time is a difficult problem, One way to obtain an approximate solution to the problem is by using a priority list of the units, This list is used to indicate in what order the units should be placed into service and withdrawn from service, One method for determining a priority list is by ranking the units in ascending order according to their heat rates(31) This of course assumes the cost per BTU is the same

-16for all units. The priority list technique does not indicate when to place units into service or when to shut them down. This last question is partially answered by Kerr, Scheidt, Fontana, and Wiley(30). They assume a priority list is available from which the time to place the next unit on the list into service or the time to withdraw a unit is determined by minimizing a cost expression composed of start up costs, minimum level fuel costs, and incremental production costs. This scheduling method is limited by its dependence on a priority list. When a priority list scheduling method is used, the units are operated at economic dispatch once they are placed into service. ii) Other Approximate Scheduling Techniques Another scheduling technique is presented by Lowery(35). He uses a dynamic programming(28) approach for finding the optimum outputs of the different units for all loads between the minimum possible capacity of the system and the maximum capacity of the system when considering minimum level fuel costs and incremental production costs. The cost curves are constructed in the following manner. If one unit is to be operating, the cost curve of input as a function of output over the operating range of the unit can be constructed. If a second unit is considered, a similar cost curve can be constructed for it. It then could be found whether it would be more economical to supply various loads within the operating range of the two units using the first unit, second unit, or both units. A combined cost curve of input in dollars as a function of output from the minimum to maximum capacity of the two units could therefore be constructed. This resulting curve can be used in combination with a cost curve for a third unit to construct a composite cost curve for the three units in the same manner

-17as described above for the first two units. Continuing in this manner, a composite cost curve can be constructed for all available generating units. This technique of scheduling generalizes the economic dispatch technique by including minimum level fuel costs and more than a single load level. This technique, however, does not consider the start up costs and related problems. Other scheduling methods are suggested by Steinberg(39). One method suggested is that of successively loading generating units to their capacities in the order of their heat rates. Another method suggested consists of loading units, in an order corresponding to their heat rates, to their most efficient load determined from their heat rate curves. Once all units are operating at their most efficient load, they are then loaded to capacity in the same order. A third method is that of scheduling the loads placed on the units in proportion to their rated capacities. Each of these methods will, in general, yield a non-optimal solution to even the economic dispatch problem. They are, however, sometimes used in practice. iii) Generation Scheduling by Dynamic Programming The dynamic programming technique has been applied to the power system scheduling problem in another way. Osterle, Geiser, Dale, and DeSalvo(37) used dynamic programming to solve the problem of selecting the optimal combination of generating units to operate in each hour of a specified horizon so that the cost of supplying the required power to the system is a minimum. The costs considered were start up costs, minimum level fuel costs, incremental production costs, and the costs incurred due to transmission losses. The start up costs were considered to be independent of the length of time a unit had been shut down. The time horizon was divided into periods each of an hours duration. At the beginning of each hour, units could be placed into

or withdrawn from service. The demand was assumed known throughout the horizon and constant within each hour. Furthermore, the spinning reserve requirements were assumed known for each hour. The proposed scheduling procedure is as follows. A list of all possible combinations of operating units is made for each hour of the horizon which meets the specified demand and spinning reserve requirements. In hour one, the start up costs, the minimum level fuel costs, and the total incremental production costs associated with providing an economic dispatch for an hour are determined for each feasible combination of units. In hour two, the minimum level fuel costs and total incremental production costs are calculated for each feasible combination of units. Next the following question is asked: "For a given feasible combination of units to operate during hour two, what combination of units should be operated in the first period in order that the total minimum levCl fuel, co:bts' start tip, costs, and economic dispatch costs are minimum?". This question is asked for all feasible combinations in the second period. Once the calculations are made, the least cost path is known from hour zero to each feasible combinationr of generating units in the second hour. Using these cumulative costs the least cost path from hour zero to each feasible combination of units in the third hour can be calculated. This can be accomplished by considering the minimum cumulative costs for each feasible combinationin the second period as the cost of operating for the first hour and the costs for the third hour as the costs associated with the second hour and performing the optimization in the same manner as discussed for the two hour problem above. Continuing in this fashion, the minimum cost path can be calculated for the entire horizon. This path then indicates what combination of units should be operated during each hour of the horizon.

-19Instead of considering all the feasible combinations for each hour, DeSalvo and Dale(l3) propose to consider only a few possible combinations for each hour. They then apply the dynamic programming method, as described above, to this- reduced problem. They show that considering the effect of start up costs can result in considerable savings over an extended period of time even when using this approximate solution method. iv) Generation Scheduling by Integer Programming The unit selection problem including economic dispatch has been formulated as an integer programming problem by Dakin(8) and Garver(20) The basic models proposed by these authors are essentially equivalent. More specifically, the problem and model considered by Dakin, or Garver are the following. Consider a short time horizon divided into periods. The demand is assumed known throughout the horizon and is assumed constant within each period. Furthermore, the spinning reserve requirement is known for each period. It is desired to schedule a fixed set of generating units over the horizon such that the generating units can be placed into or withdrawn from service only at the beginning of a period. The objective is to minimize operating costs subject to certain constraints. The costs considered are the start up costs, the minimum level fuel costs, and the incremental production costs. It is assumed that the incremental production cost curves are step functions. It is required that demand and spinning reserve constraints be satisfied. Garver requires all variables in the problem formulation to take on integer values. Dakin requires that only the variables associated with starting up a unit and those variables indicating whether a unit is shut

-20down or operating to be integer. It is shown in this dissertation that these assumptions can be modified. Garver uses Gomory's all integer programming algorithm(25) to solve the problem. Dakin proposes Gomory's mixed integer algorithm(26) to solve the problem. Dakin uses a form of the decomposition technique due to Dantzig and Wolfe(l0) to investigate the structure of the model. He conjectures that there is a way of decomposing the model to prove that the variables are integer valued under suitable scaling. He, however, was unable to prove the conjecture. The proof is given in this dissertation, The use of Gomory's integer programming algorithm is somewhat questionable in this case, First, it is a dual method and thereby produces no feasible solution until the optimal solution is found, Thus approximate solutions are hard to obtain, Secondly, and probably most importantly, this method does not take advantage of the simple structure of this scheduling problem which is demonstrated in Chapter IVo Also, computational experience with Gomory's algorithm has not always been successful(4). 2.5 Some Results in Stochastic Linear Programming In each of the scheduling techniques discussed in 2.4 the demand for power is assumed to be known over the entire planning horizon. In (9), Dantzig shows that in general in a linear model, such as is considered in this dissertation, the demand random variable cannot be replaced by its expected value to obtain an optimal feasible solution. In an example (16) the expected value of the objective function corresponding to the optimal solution is $1,524,000, whereas the optimal value of the objective function is $1,000,000 when the demand random variable is replaced by its expected value,

-21Madansky(36), gives some inequalities resulting from replacing random variables by their expected values, In particular, he shows that when solving the deterministic problem obtained by substituting the expected values for the demand random variables, the resulting value of the deterministic objective function is less than or equal to the expected value of the objective function obtained when solving the problem as a stochastic programming problem. Furthermore, the expected value of the objective function obtained using the solution found by solving the corresponding deterministic problem is greater than or equal to the minimum expected value of the objective function for the stochastic problem. This follows since the expected value solution is a feasible but not necessarily optimal solution to the stochastic programming problem. In the example cited above, the expected value of the objective function inserting the optimal solution of the corresponding deterministic problem is $1,666,000o The "inside problem", as defined in Chapter IV,is a stochastic linear programming problem. In the literature discussed in this chapter, this problem is solved as a deterministic problem. In this dissertation, this problem is presented and solved as a stochastic programming problem for the first time.

CHAPTER III AN INTEGER LINEAR MODEL FOR THE POWER SYSTEM SCHEDULING PROBLEM WHEN DEMAND FOR POWER IS UNCERTAIN 3o1 Introduction A formulation of the power system scheduling problem when demand is uncertain is presented in this chapter. A mixed integer - continuous linear model is stated which includes the factors discussed in Chapter II. In certain respects the proposed model is similar to that of Garver(20O) and Dakin(8) which were discussed in the previous chapter. The differences between the proposed model and the aforementioned models are as follows. The demand for power is not assumed to be known exactly over the planning horizon, but rather is assumed to be described by a discrete random variable with a known probability distribution function. Interconnections with other power systems are included, Furthermore, the constraining conditions are somewhat different. A basic one period model is introduced first. It includes start up costs, minimum level fuel costs, and incremental production costs in its objective function. Demand constraints, reserve requirements and generating unit capacity constraints are considered. It is shown how transmission losses, manpower constraints, geographical reserve requirements, multiple interconnections, and common header units can easily be introduced into this one period model. A Q period generalization of the one period model is discussed. It is shown how time dependent start up costs can be introduced into the Q period problem. 3,2 A One Period Scheduli-ng Model a) Introduction In this dissertation, the one period scheduling problem is defined' -22

2>3 as follows. A decision must be made at a fixed time, say 0, as to what combination of generating units is to be operated during a fixed interval of time, say (O,T], given that a certain combination of generating units is operating at time 0 and that generating units can be started up or shut down at time 0 but at no time within (O,T]. The basic one period model is discussed first. In later sections, the additional features discussed above are introduced into the model. b) Basic Assumptions The following assumptions are made for the one period generating unit scheduling problem. 1) Any demand for power must be satisfied. 2) The interchange is considered as a generating unit with a specified incremental production cost, h o 3) The incremental production cost curve for each generating unit is a monotone increasing step function over its operating range. That is, for generating unit i, gil< a agin ~ 4) Xj is a discrete random variable. 5) The range of the function Xj is the set of possible demand levels that could occur in subinterval j 6) The reserve level plus the amount of power available from the interconnection is greater than the largest possible demand in (O,T], that is, R + M > b c) The Demand Process One reason that the scheduling of generating units is difficult is that demand is not known with certainty, that is, demand is not deterministic. In fact, the demand process is a non-stationary stochastic process. In practice, a single curve is forecasted as an estimate of the demand process. Moreover, demand is often assumed to be constant in (OT]

-24Instead of assuming the demand process is deterministic the following probabilistic method is proposed for describing the demand process. As before, let (O,T] be the period of time for which a schedule is to be determined, that is, the generating units are committed to either be operating or shut down for the entire time period (O,T] at time 0 Furthermore, the interval (O,T] is written as the union of a finite number of non-overlapping subintervals of equal length. For the duration of subinterval j, the demand for power, Xj, assumes one of a finite number of possible levels. The set of possible demand levels need not be the same in different subintervals. Each value that Xj could assume, blj,oo bij, has a positive probability associated with it, pJo. For example, suppose (O,T] is expressed as the union of five disjoint subintervals each of length A, that is, 5 (O,T] = U (tj-tj_l], where to = 0 and t5 = T and tj-tj_l=A, j=l,...,5 j=1 In subinterval (tj-tj_l], Xj can assume any one of several possible levels with a specified probability. The possible demand levels and probabilities need not be the same in (O,t1], (tl,t2],..., (t4,t5]. This example is displayed in Figure 1. The above method for describing the demand process is quite general. The subintervals can range from being arbitrarily small in length to being equal in length to the whole scheduling interval. In the latter case, the whole interval is the only subinterval. The number of demand levels that can be considered in each subinterval can range from one to an arbitrarily large number. If only one subinterval and only one demand level are considered for the interval, then the demand process is a deterministic process,

-25Demand in mw (p =1/8) (p = 1/5) (p9 1/8) 8 (P = 1/4) (p = 1/5) (pa = 1/4) b6~ ((P - 3/8) ( 3 1/5)8 ((pj = 1/2)/ L (p _1/8 (p =1/8) (p = 3/8) (p = 1/4). (P1 - 1/4) (Pl = 1/8) Time in Hours to=O t1 t2 t3 t4 t5=T Figure 1. An Example of the Method Used to Describe the Demand Process.

-26that is, demand is assumed to be a known constant throughout the whole interval. Hence the deterministic formulation of the demand process is a special case of the above description. On the other hand it is also possible to approximate a stochastic demand process that is continuous in both time and state space by letting the length of subintervals, A, approach zero and the number of demand levels considered become arbitrarily large. d) The Constraints i) Introduction In this section, the constraints considered in the basic power system scheduling model are developed. Constraints involving the start up variables, the demand process, reserve requirements and generating unit availability constraints are considered. ii) Start-up Constraints The effect of starting up a generating unit can be included using a very simple inequality. As defined earlier, ui is the startup variable for unit i, w1 indicates whether or not unit i is to operate in (O,T], and w~ indicates whether or not unit i is operating at time 1 O. The start up constraint for unit i is 1 o ui > wi -i. The non-negativity constraint is also imposed on ui, that is, ui > O 1 i o It is easy to see that depending on the values assumed by wi and w, u is either greater than or equal to one or zero. iii) Demand Constraints The assumption was made that demand for power is always

-27to be met. This can be accomplished in one of two ways. Either the total power requirements are met by using only power generated by units within the system or by using supplementalpower from the interchange. In each of the r subintervals demand can assume one of the levels blb2,...,,b with some probability. Hence for subinterval j the following demand equations must be satisfied. N n kl Si,k,j,t + Zj,t = bt - m*(Wl), 1 < t <, where Si,k,j,t is the amount of power in mw produced by generating unit i at incremental production cost level k in subinterval j at demand level bt and Zj,t is the amount of power in mw purchased from the interchange in subinterval j at the t-th demand level, iv) Reserve Constraints In order to ensure that adequate power is available if some equipment fails, reserve requirements must also be established. This can be accomplished by requiring the total system capacity be at least as great as some specified level, that is, by requiring, N M*(W1) > R, where M*(W1) = Z M-i i Mi i=l is the maximum output capacity of generating unit i, W1 = [wl,,...wNIT and R is the minimum capacity required for the system in (O,T] v) Power Availability Constraints If a particular generating unit, say unit i, is shut down, it clearly cannot be producing any power. If, on the other hand, it is operating, it can supply any amount of power within its operating range. One of the assumptions made was that the incremental production cost curves

-28are monotone increasing step functions. Hence for generating unit i, the amount of power available at rate gi l is Mi 1 and in general the amount of power available in step k is Mik. Furthermore, the Si, kjt variables are defined such that 0 < Si< k Kjt < Mi k when generating unit i is operating, that is, when w =- 1, for all j=l,o..,r and t=l,..., and such that Si kt = 0 otherwise, that is, when w1 = 0 Thus the power availability constraints for generating unit i can be written as 0 < Sik,j,t < Mi k wl This constraint is sufficient, for whenever wi = 1, the generating unit is operating and o < Si kj,t < Mi,k and whenever wi = 0, the generating unit is not operating so that Sik,j,t = 0 A similar constraint can be written for the amount of power available through the interconnection. Since the maximum amount of power available from the interconnection is M mw, the constraint can be written as Zj,t < M e) The Objective Function i) Introduction The objective of the optimization is to select the set of generating units to operate during (O,T] which minimizes the expected operating costs. The operating costs considered in this formulation are

-29the start up costs, the minimum level fuel costs and the incremental production costs. ii) Start-up Costs The cost of starting up generating unit i is ci dollars. If unit i is started at time 0, then ui = 1 and the start up cost incurred is ciui = c il= ci dollars. If unit i is not started, then ui = 0 and the start up cost incurred is ciui = 0 dollars. Thus Z ciui is the total cost associated with the starting up of generating units for any schedule. iii) Minimum Level Fuel Costs The cost of operating generating unit i at its minimum output level is ki dollars per hour. If generating unit i is operating in (O,T], then wl = 1 and the minimum level fuel cost kiwi = ki = k dollars per hour is incurred. Otherwise, w = and the cost kiO = O N dollars per hour is incurred. Thus T Z kiwi is the cost associated i=l with the minimum level fuel costs for any schedule. iv) Incremental Production Costs It was assumed that the incremental production cost curve for each generating unit is a monotone increasing step function, that is, for generating unit i, gi 1 < gi,2 <'' < gi n' The number of steps necessary to describe the incremental production cost curves depends on the characteristics of the individual units. It has been assumed that the number of steps for each unit is n. A typical incremental production cost curve is displayed in Figure P2 for the case n = 4. As discussed previously, the amount of power available in step k of the incremental production cost curve for generating unit i is Mik

-30Cost in Dollars per mw-hr gi, 4 gi,3 gi,2 gi, 1. Step 1 Step 2 IStep I Step 4 Output in rw -MM —i, m,2 Mi,3 ~ Mi, Minimum Maximum Output Output Level Level mi Mi Figure 2. An Incremental Production Cost Curve for Fictitious Unit i

31The associated cost for this step is gik i Thus the cost of producing Si, k,j,t mw of power for one hour is gi,k Silkj,t' where 0 Si,k,j,t 0 Mi,k wi for all j = 1,.o.,r and t = lJ.oGo Furthermore, h is the incremental cost of power purchased from the interchange. Consider demand level bt. The cost of producing this amount of power during subinterval j whose length is A is AhZj,t + A Z Z gi,k Si,k,j,t o i k t However, bt will be realized with probability pi. Hence this cost is weighted by the probability that bt occurso Summing the above cost expressions weighted by their corresponding probabilities over all possible values of t gives the expected incremental production cost for subinterval j The total expected incremental production cost for the horizon is obtained by summing the expected incremental production costs of each of the subintervals. This indeed is the correct total expected cost expression since the Lebesgue-Stieltjes integral of the sum of integrable functions is the sum of the integrals of the integrable functions. That these functions are integrable is obvious. Thus it has been shown that the total expected production cost is r N n E{ Z (AhZj,t + A i EZ gi,k Si,kjjt)} 9 j=l i=l k=l where E is the expectation operator.

-32f) Summary Combining the results of the previous subsections, the one period power system scheduling model can be stated as: N N minimize Z ciui + T Z kiwi i=l i=l (3.1) r N n + { Z [aLhZj t + L gik Sikjt]Pt } j=l t=l i=l k=l J subject to 1 0o wi - wi < Ui M*(W1) > R Sikj < Mik wi N n ~ Z- Si,k,j,t + Zj,t t- m*(W1), ui > 0 Zj,t > O i=l k=l i,k,j,t > O, and wi = 0 or 1, for i=loooN k=l, n, j=l~...,r, and t=l,...,2. Clearly this would be a linear programming problem if it were not for the fact that wi must be 0 or 1. It is shown later that the above- conditions are sufficient to guarantee that ui be either O or 1. Thus it is not necessary to include these additional constraints, In section 3.2e), the total incremental production costs were given as r N n E{ Z (AhZj t + A E E gi, Si,k,j,t)} j=l i=l k=l Since, as explained earlier, the expectation operator which is a Lebesgue-Stieltjes integral, and finite summation are interchangable,

-33r N n E{ Z (Ahzj t + A N n gi k Sikjlt)} j=l i=l k=l r N n =Z {E(Lh Zj t +A, FZ gi k Si k j t)}. But j=1 i=l k=l N n E(AhZj t +tZ g i,k Si i=l k=l ik 2a N n t =- [AhZjt +AZ gi,k Si,k,j,t] Pj t=l i=l k=l Thus the objective function presented in (3.1) follows. The model presented above expressed in matrix form is 1 2 I min D1W1 + D2U + S1,1D3P1 +... + S1), D3P1 +... + Sr, D3Pr subject to U > W1 - Wo M*(W) > R Sjt nN+l = bt - m (W1), (Sjt) <W, U >O Sjt > 0 and 1 > W1 >, W1 integer. The definitions of the symbols are given on pages ix, x, and xi. 3.3 Extensions of the One Period Model a) Introduction The one period model presented in the previous section can be extended to include additional factors such as transmission losses, manpower constraints, geographical constraints, multiple interconnections, and common-header units, that is, multiple boiler generating units. The basic one period model can also be extended to a multiple period model, These extensions are discussed in this section.

-34b) Transmission Losses The production costs associated with each generating unit can be modified to include the effect of incremental transmission losses. This can be accomplished using the Penalty Factor Method discussed in 2.4a). The results of a study(13) indicate that transmission losses are probably an unimportant factor when determining the optimum combination of generating units to operate. This is the case since generating units are required to be operated in dispersed geographical regions in order to ensure the desired system reliability thereby imposing a large portion of the transmission losses on the system. c) Manpower Constraints A certain schedule specifying a combination of units to operate may be optimal in a cost sense but infeasible due to the fact that the labor force at that time is not capable of carrying out the requirements of the schedule. That is, there may not be sufficient manpower in a given generating station to start up or shut down the units specified in the otherwise optimal schedule. Suppose I is the set of generating units in some particular generating station. Then the following constraint can be imposed. The total number of generating units started up and shut down must be less than some constant, say c. Thus the constraint can be written as ui + Z Vi < C icI icI where vi indicates whether or not generating unit i is shut down at time 0, that is, vi = 1 if unit i is shut down at time 0, and 0 otherwise.

-35d) Geographical Reserve Constraints Probably the most important factor affecting unit commitment mentioned in this section is that of requiring geographical reserves. As stated in 2.3, reserve capacity is scheduled in dispersed geographical regions due to transmission line capacities and to ensure that the regions are capable of meeting demands for power in case of a transmission line failure. The form of the geographical reserve constraints are the same as for the total system reserve constraint. If a system is divided into q geographical regions such that I1 is the set of generating units in region one, I2 is the set of generating units in region 2, etc., then the geographical reserve constraints are z M wL > R iI1. Miwi > Rq icIq where Ri is the minimum capacity required in region i e) Multiple Interconnections In the basic model only one interconnection was permitted. That is, Z;jt was defined to be the power purchased from a single interchange in subinterval j at demand level bt. However, this can be expanded to include multiple interconnections. Each interconnection can have a different cost per mw-hr and availability constraint associated with it. Thus if there are X interconnections, a generating unit can be assumed to be located at each point of interconnection. Each of these X fictitious units has an associated incremental production cost and capacity. The capacity is determined either by the physical capacity of the tie line or the amount of power available from the interconnection,

-36f) Common Header Units Common header units or multiple- boiler units can be included in the integer formulation in the following manner. For each multiple boiler generating unit a linear inequality constraint can be introduced requiring that the total power output from the turbine generator in the unit be less than or equal to the amount of boiler capacity being fired. Start up costs could then be split into two parts; one for the turbine and the second for the boilers. g) A Q Period Model The one period model required the decision maker to select a combination of generating units to operate during the entire time interval (O,T]. The Q period model, on the other hand, partitions (O,T] into Q periods. At the conclusion of each period a new combination of units can be selected to operate in the following period. At time 0 in the Q period model, it is desired to determine a schedule which indicates the combination of generating units to operate in each of the Q periods in (O,T]. The Q period model is almost Q copies of the one period model. To see this, each variable is given an additional subscript or superscript indicating to which period the variable applies. For example, wq is the variable indicating whether unit i is operating in period q, uq indicates whether unit i is started up in period q btq is the t-th demand level in period q, 1 < t < q, where 2q is the number of levels considered in period q, Si,k,j,tq is the amount of power produced by generating unit i at incremental cost level k in subinterval j at demand level bt,q in period q, etc. It is further assumed that costs and generating unit capacities remain constant over the Q periods.

-37The constraints for the basic Q period model can be written as follows. The start up constraints take the form w - wq < UJ for i=,...,N and q -1,,Q oI The reserve constraints can be written for each period. They are Mq(Wq) > Rq, q=,.o,Q The power availability constraints are S < M Wi - i,k w Zj,t,q < Mq i-l,...,N, k=l, 1 n j=l,..,rq, t=l,...,O q, and q=l,,,,,Q The demand constraints are given by N n Z Z Sik,j,t,q + Zj,t,q = btq - mq(Wq), i=l k=l j=l,...,rq, t=l,.eo.,q, q=le The non-negativity conditions for u Z t q also i' -jytyq and Siyk j,tq also hold and wi = 0 or 1. Thus it is clear that, except for the subscript q, the constraints for the basic Q period model are the same as for the one period model. The objective of the Q period model is to find that combination of units to operate in each of the Q periods which minimizes the total expected cost for the horizon. Since the costs are assumed constant throughout the horizon, it is easy to see that the cost expression for each of the Q periods is identical to the one presented earlier for the

-38one period model. Thus the objective for the Q period model is to minimize Q N N Z [Z ciu + Tq Z kiwi + q=l i=l i=l rq Y q N n t { [ qhqZi,t,q + Aq Z N gik Si,k,j,t,q}Pj,q. j=l t=l i=l k=l Thus it has been shown that the Q period model is like Q copies of the one period model presented in the previous section. This conclusion, of course, is based on the assumption that the assumptions, constraints, and cost structure are like the ones for the one period model. It is assumed that the start up costs are constant over time. This is not correct. In (3), as discussed in 2,2e), an exponential variation in the start up costs as a function of the time since the last shut down is assumed if the boilers are not banked. If the boilers are banked, a linear variation in start up costs is assumed. These time dependent start up costs could be included, too, if desired. One way to do this is as follows. Define vq to be the variable denoting whether or not unit i is shut down at the beginning of period q o In particular, q 1{, if unit i is shut down in period q Vi =, otherwise. The constraints involving v. which guarantee vq = 0 or 1 are vq > 0 1 -1 and v > wq - w. These are similar to the constraints on the ui variables. The justification for the fact that ui = 0 or 1 is given in Chapter IV and the proof that vq = 0 or 1 is the same. Also, define uq z to be 1 if unit i is started in period q after being shut down for z periods and O otherwise. The constraints for the time

dependent start up costs are then 0 < uq < vu-z and - Z - 1 q q 1, Z 1 That these are indeed the proper constraints can easily be seen, Suppose uq =. Then clearly uq =0 for all z Suppose u = 1 What i lz is desired is to have u = 1 for vq- = 1 and z* maxz: v = 1 1,z* 1 z z < q}. The start up costs can be calculated from the time dependent start up cost curves. These costs are strictly monotone increasing as a function of the length of time a generating unit has been shut down, Let ci,y be the time dependent portion of the start up cost for generating unit i:given that unit i was shut down y periods earlier, Redefine ci to be the fixed cost of starting unit i. Thus we have cil < *.. < Ci,y.... The objective function is then altered by the addition of the term C Z1ci, qz 1~i Z qi z To show the desired, it is obviously necessary to show only that the term E Ciq-z u1iz, Z that is, the time dependent start up cost for generating unit i in period q, is minimized when z* = max{z: v= 1 and z < q}, Let {vil, vi'2..viC} be the set of start up variables such that vqY = 1 and qy < q. Furthermore,assume q1 > q2 >... > qa o Then

-40z ci qz ui, z'ze{ql, o o e, 1qc} is to be minimized subject to 0 < u < 1 and Z uq - u 1 - 1,z - z:'ze ql*,...,}qc z 1 Thus it is desired to minimize a convex combination of the numbers in the set {ci, qql...,Ci,qqc}. Since any convex combination of the elements of this set is greater than or equal to the smallest element in the set, the answer to the problem is immediate. But ci qql must be the minimum of the set of costs {ciq-z: zc{qloo,.,qc}} since q-ql is minimum or ql = max{qy: viY = 1 and qy < q} and the costs are strictly monotone increasing as q-qy increases. Hence uq must equal 1. Thus the desired result has been demonstrated and it has been shown that the proposed constraints are the correct ones. In practice an additional constraint is often imposed in the Q-period problem. If a generating unit is shut down, it is often required to be kept shut down some minimum length of time. If this minimum time is greater than the length of one period, additional constraints are necessary. If generating unit i must be shut down for at least z periods, these q iq-c constraints can be written as uq. + vi < 1, for q=,.,,,,Q and c=l,oo.,z It is obvious that additional initial conditions must be included in order to make the constraints discussed in the previous two paragraphs meaningful.

CHAPTER IV THE STRUCTURE AND SOLUTION OF THE BASIC INTEGER LINEAR MODEL 4.1 Introduction The basic integer linear models for the one and Q period power scheduling problems presented in sections 3.2 and 3.3g), respectively, are explored in more detail in this chapter. A partitioning procedure is introduced to facilitate the study of the structure of these models. It is shown that the values of the variables in all basic feasible solutions to the one and Q period problems are integers under suitable scaling. The partitioning procedure also suggests a solution method for the problem. Algorithms due to Benders and Benders, Catchpole and Kuiken are cormbined and modified to provide an algorithm for solving the power generation system scheduling problem which takes advantage of the special properties of this scheduling problem. 4.2 Partitioning in a Mixed Integer Continuous Linear Programming Problem In this section, a partitioning method is discussed for mixed integer continuous linear programming problems. Some symbols are defined below. Their interpretations are limited to this section and are not to be confused with similar notation presented elsewhere unless so indicated. Let X be a p-dimensional vector, Y be a q-dimensional vector, C1 be a p-dimensional vector, C2 be a q-dimensional vector, B be an m-dimensional vector, Al be an m x p matrix, A2 be an m x q matrix, and S be the q-dimensional unit cube. -41

-42Suppose the following problem is proposed: find X 2 0 and YeS such that T T C1 X + C2 Y is minimized subject to A1X + A2Y > B It is easy to see that this problem is equivalent to the problem minyES {CT Y + minX {CT X: A1X > B - A2Y, X > 0}) 21rT The problem minxCT1 X: A1X > B - A2Y, X > O} is to be called the "inside problem". The inside: problem is a linear programming problem for any given value of the vector Y o 4.3 The Structure of the One and Q Period Models The partitioning procedure indicated in section 4~2 is applied to the one and Q period scheduling models. The structure of the one period model is studied in detail. That the structure of the Q period model is the same as that of the one period model will be shown, As stated earlier, the one period scheduling-problem is that of determining that combination of generating units to be operated during a fixed interval of time in order to minimize expected operating costs given that a certain combination of generating units is operational at the beginning of the fixed interval and that generating units can be started up or shut down only at the beginning of the interval. The model for the one period problem was presented in section 3o2f) as

-43minimize D1Wl + D2U + S1, D3P l + + + S1D3p1 + G' + S p +S D P (4.1) r,iD3pr + r, 3 r subject to U?Wi W1, M*(Wi) R Sj,t nN+l = bt - m (W1) T (Sj,t) W, U 0, Sj,t 0, and 1 ~W1 > ~ 0, W1 integer. Let F = {W1: M*(Wl) R and 1 _W1 20, W1 integer} Then, as indicated in the previous section, (4.1) can be equivalently written as 1 minWlCF {DlW1 + minu,Sj t {D2U + 1,S D3Pl +'' Sr, 3Pr T U > W1 - Wo, Sj,tlnN+l = bt - m*(Wi), Sj t < W U > 0,sj,t ~ o}} (4~2) Consider the inside problem minu N S t S DP U Sjt lnN+l = bt - m*(W1) 9 T Sj, t -_, U 0, Sj t 2 O}. (4~3) This is a linear programming problem for a given value of the vector W whose structure is of a special type. Consider the optimization problems minimize CT1 X + CT Y (44)

-44subject to A1X _ B1, A2Y > B2, X 0, Y 0, min CT X subject to A1X > B1, X 0, (4.5) and min CT Y subject to A2Y ~> B2 Y ~0, (4.6) where C1 is a p-dimensional vector, C2 is a q-dimensional vector, X is a p-dimensional vector, Y is a q-dimensional vector, B1 is a t-dimensional vector, B2 is a s-dimensional vector, Al is a t x p matrix, and A2 is a s x q matrix. It is clear that (X*,Y*) is an optimal feasible solution to (4.4) if and only if X* is an optimal feasible solution to (4.5) and Y* is an optimal feasible solution to (4.6). It also can easily be shown by a rigorous proof by induction that (X1, X2,.., X*) is an optimal feasible solution vector to the optimization problem min CT X1 +.+ C Xz subject to A1X1 > B, A2X2 > B2' AzXz > Bz, X1> 0,..., Xz ~0, if and only if Xj, j=l,...,Z, is an optimal feasible solution vector to the

-45minimization problem min CT Xj J subject to AjXj Bj Xj > Thus it is easy to see that min C1T +cIx +...T + C X = minX C1 X+ minX1 CT X 2 +...+''' 22 z z C1 in2 2 X' (X1,...,Xz) + minX CzT Xz Applying this observation to the inside problem,(4.3), it is clear that, for a given value for the vector W1, minUS 1''Sr S D {3D2U + Sll+... D3 U W1 W S1,1 lnN+l = b1 m (W1),...m SroQ lnN+l =bQ - m (W1) T T S1,1 l W,..., Sri _ W U > 0, Sl,l O,..., Sr, _ 0} (4.7) = minU {D2U U i W1 - Wo, U ~ O} + minS1.1 z1 m* T minS 1 {S1,lD3Pl S,1 1lnN+l bl - m (W1), Sj,1 < W S1,1 0} +... + minSr {Sr, r 3P: Sr,e lnN+l = b2 - m (W1), S,= < W, Sr,i O}, since the vectors U,S1,* 1,., Sr2. have no components in common and are not related in any of the constraints. Consider the minimization problem minbSt t T W minst {SjtD3p j Sj,t lnN+l=bt -m(W1), S j,t o }, S (4.8)

-46This problem can be written as min A{.. Si,k,j,t gi,k + hZj,t} P (4.9) = A p min Z Z (S-i,k,j,t gik + hZjt) ik subject to S 1lj, t +...+ SN+ N,n,j,t + Zj+ + Nn,t t = bt - m*(W1) Sl, )j~t. -< 1,1 w Sl,n,j,t M1 n wl 1 SN, l,j,t ~ MN,1 WN SN,n,j,t MN~n WN Zjt < M S > 0 i,kj,t zj,t n Thus this subproblem is of the form of a transportation problem with surplus having (Nn+l) origins and one destination(ll). This problem corresponds to the economic dispatch problem discussed earlier. Suppose the set of demand levels, bt, t=l,...,i, and the availability constraints mi, Mik, and M are scaled to be integers. In (4.9), under the above supposition, it is clear that the right hand side vector has integer components for a given value of the vector W1. It is well known that in a transportation problem the values of the basic variables are integers when the components of the right hand

-47side vector are integers(ll). The remaining variables, of course, are at a zero level. Hence the following observation can be made. Observation 1. All variables Sik,j,t and Z7jt take on integer values in any basic feasible solution to Problem (4.7) for a given value of the vector W1 Consider now the optimization problem minu{D2U: U > W1 - Wo, U 2 0), given the value of W1, that is, N min Z ciui subject to i=l 1 o Wi - Wi <Ui Ui > 0, i=,...,N. Again it is easy to see that (ul,..,u~) is an optimal feasible solution vector for Problem (4.10) if and only if ui is an optimal feasible solution to the minimization problem min ciui = cimin ui subject to ui > w1 - w(i ui > O, for i=l,...,N. 1 0 1 o It follows from the definitions of wi and wi that w - wi = l, O, or -1. If wl - wA~ = i1, then Problem (4.11) reduces to min ciui cimin ui subject to ui > 1. Thus min ui =1 and the minimum value of the objective function is ci. If w. - wi 0 or -1, problem (4.11) reduces to min ciui = cimin ui subject to ui 0 O. Hence the objective function is minimized when ui = 0, that is, min ciui =. Thus ui = 1 when w1 - wi = 1 and ui = 0 when wi- wO = 0 or -1. Therefore the following observation can be made.

-48Observation 2. All variables ui take on integer values in any basic feasible solution to -Problem (4.7) given the value of W1 The above observations can be combined to yield a general result. Observations 1 and 2 were made for the inside problem, that is, for any WlF, the minimization Problem (4.7) has the properties discussed above. Thus the following general observation can be made. Observation 3. All variables wi, ui, Si,k,j,t' Zjyt take on only integer values in any basic feasible solution to Problem (4.2).1 The Q period model can be partitioned in exactly the same way. The notation used for the one period problem is extended by adding a subscript indicating the period to which it refers. Thus Wq = (w,..., wN), Sq is a matrix like S for the q-th period, Sj,tq is the jt-th row of Sq, Uq is the vector of start up variables for period q, etc. The Q period problem is minimize Dl(W1 +... + WQ) + Sl,1,1 D3Pl,1 + *.. + S1,l,1 D3Pl,1 1 21 + + Sr,, D3Prl, + + Sr, i3Prl 1 2+ Si, i,2D3Pl,2+.. + S2,2D3P1, + *2 1 12 + Sr2,1,2D3Pr2,2 +''' + Sr2, 2,2D3Pr2,2 + 1 2Q + S1,1,QD3Pl,Q +... + SQ,QD3Pl Q +... 1 aQ + SrQ 1QD3PrQQ +.. + SrQ QQD3PrQQ + D2(U1 + U2 + *.. + UQ) subject to Uq > Wq - Wql, q=l,...,Q, 1 Recall that by definition, a solution is a basic solution to (4.2) if and only if the portion of the solution corresponding to the inside problem

-49M* (Wq), Rq, Sjt,q lnN+l = bt - mq(W),q (Wq,_qW Uq >O, S t q, 1 > >, Wq integer. (4.12) Let Fq = {Wq: 1 2 Wq 2 0 Wq integer, M*(Wq) Rq and F >< Fq, that is, F is the product space of the Fq q=l Problem (4.12) can be decomposed into two parts by writing it in the equivalent form: min {Dl(W1 +..o + WQ) + min {D2U1 + (W1,.,WQ )eF UqYS jt. q D2 U2 +... + D2 UQ + S D3Pl, 1 +'~ + Srl,, lD3p rl'1 +.'~ + S1,, QD3PI,Q + + SrQ QQD3rQ Ul>W1-W o,.., uQ >wQ-WQl,4 S1 1 NWl U= bt,1 - 4(1). Sj,t,llnN+l = btl - m'(W1),'.', Sj,t,QlnN+l = bt,Q - mQ(WQ), T T Sj t,1 < W. Sjt,e =, U1 0,..., UQ j t 1 > 0, o., Sj t Q 0}} (4.13)

-50Upon inspection, it is obvious that the inside: problem of (4.13) can be partitioned in exactly the same way the one period inside problem was partitioned. The same observations can be made for the components of Uq and Sj that were made for U - U1 and Sj t Sj t Thus observation 3 can be extended to all the variables wq uq, Si, kjtq, and Zj,tq in any basic feasible solution to (4.13). 4.4 An Algorithm for a Mixed Integer Continuous Linear Programming Problem1 In 4.2, the mixed integer continuous linear programming problem minyES {C2 Y + minX {C1 X: A1X B - A2Y, X 0 }} (4.14) was presented. It is well known that T A maxUi (B - A2Y) U: ATU < C, U > (4.15) is the dual of the inside problem of (4.14) and that min{C X: A1X >B-A2Y, X } maxU {(B - A2Y) U AT U ~ C1, U O } (11) (4.16) Assume that the optimal value of the inside- problem of (4.14) is finite for all YES, that is, there exists an optimal feasible solution vector T T* X1 such that C1 X1 is finite. Let G = {U AT U C, U > }. This is a convex polyhedral set which is independent of the values the vector Y assumes. Since the maximum of (4.15) must also be finite, an 1 The notation in this section refers to that defined in section 4.2, Any new definitions introduced in this section are not to be carried over to other sections.

-51optimal feasible solution vector U* to (4.15) must be an extreme point of G. But G has only a finite number of extreme points. Denote them by Uv, where veV, and V is a finite set containing the same number of elements as there are extreme points to G. Hence -Problem (4.14) can be written as T minyeS {CT Y + max (B - A2Y) (UV)}. (4.17) veV Furthermore, (4.17) can be rewritten as T T minycS {Yo' Yo > C2 Y + max (B - A2Y) (UV)}, (4.18) veV that is, (y*, Y) is an optimal feasible solution vector to (4.18) if and only if Y* is an optimal feasible solution vector to (4.17) and T * T * y = C2 Y + max (B - A2Y*) (UV) vcV Benders(5) has proposed an algorithm for solving problem (4.18). The proposed computationallprocedure consists of solving (4.14) by performing a sequence of iterations, each of which requires solving two subproblems. The first subproblem consists of solving the purely4 integer problem T~ 1T minyC {Yo Yo > C2Y + max (B - A2Y) (UV)} (4.19) where V'cV. Thus Problem (4.19) is solved over the restricted set V' Clearly (4.19) also has a finite optimal feasible solution. Let (y', Y') be that solution. The second subproblem consists of solving the inside problem of (4.14) given that Y = Y'. Let a(Y') be the resulting optimal value. By assumption a(Y') is finite. Let X' be an optimal feasible

-52solution to the inside problem and U' an optimal feasible solution to its dual, that is, to problem (4.15). Note that the optimal value to the dual problem is also a(Y'). Clearly (X', Y') is a feasible solution to Problem (4.14). However, if y + aY = + C2Y' - a() C2 2 X then (X', Y') is also the optimal feasible solution to (4.14). This is easily seen to be true, for (yo, Y') is a feasible solution to Problem (4.18) from which it follows that T Yo = minyeS {Yo yo > C2Y + max (B - A2Y) (UV)} = 2 EV' T CTY' + max (B - AT Y') (Uv) T < mis S {Y Yo o ~ C2Y + max (B - A2Y) (UV)} < o, that is, yo = vEV and Y' = Y. Suppose, on the other hand, that y' < CTY' + a(Y') Then at least one constraint in (4.18) must not be satisfied. Thus T T include yo > (B - A2Y) (U') + C2Y as a constraint for Problem (4.19). Return to subproblem one and repeat the procedure. The above two paragraphs describe a single iteration of the algorithm. That a finite number of iterations produces an optimal solution is guaranteed since the extreme points of G are finite in number. 4.5 A Solution Method for the Restricted Integer Problem-Subproblem One. a) Introduction The algorithm proposed in this section is a modification of one presented by Benders, et. al.(6) Modifications of the original algorithm

were made in order to take advantage of the feasibility constraints Mq > Rq. Subproblem one for the Q period model is min {D1W1 + D1W2 +.. + D1WQ + max (l, WTo.. W )Cv) (W1.,WQ) v{, 0 0 z} subject to M1 R1, M2 R2 e where Cv is a (QN + 1) dimensional vector whose components are associated with the values of the dual variables for the v-th generated constraint, that is, the constraint generated for the restricted integer problem after the v-th iteration of the algorithm. The exact method for determining the components of Cv is given in 4.8. Let T W = [WT,...,WT] be a QN- dimensional vector, T B = [R1,...,RQ] be a Q- dimensional vector, Di = [D1,D1,...,D1] be a QN- dimensional vector, and Ml M2 -- MN be a QxQN A = M1 M2... MN dimensional ~. matrix. M1 M2... MN Then the above problem can be written as minW {DI W + max (1,WT)Cv} (4.20) v subject to AW > B, where the components of W are equal to 0 or 1

b) The Solution by Enumeration The feasibility of W can be checked by seeing if y, defined by y = AW -B, satisfies the relation y > 0 o Define a sequence of sets Vj, j = O, l,...,QN, in the following manner: Vo contains the vector y() = Al - B, where T 1 = (l..oo,1), a QN dimensional vector, Vj+l contains the 2j vectors y(t) obtained from previously calculated vectors in sets Vo through Vj using the formula y(t) y (t-2) a j+l' for t = 2J 2j + 1-* )2J+l 1 (4.21) where a j+l is the (j+l)-st column of the matrix A. Once y(t) is calculated, the vector W(t) is found using the relationship W(0) - 1 W(t) = W(t-2j) - E(j+l) (4.22) for all y(t)c Vj+l, where E(j+l) is the unit vector in QN-dimensional Euclidean space for the (j+l)-st dimension. Next, define the functions Fv(W) and F(W) in the following manner: Fv(W) - D1W + (l,WT)Cv (4.23) and F(W) = max F (W) v Thus Fv(W(t)) W(t) + (1,(W(t))T)Cv

-55= Dl[W(t-2J) _ E(j+l)] + [l,(w(t-2j) - E(j+l)) ]C = D1 W(t-2j) - dj+l + [1, W(t-2J)]Cv - C:v,j+2 -Fv(W( ) - (dj+l + cj+2) (4.24) where t 2j 2j+l -, dj+l is the (j+l)-st component of D1, and cvj+2 is (j+2)-nd component Df Cv. Since only one element in each column of the matrix A is non-zero, only one calculation is required to compute y(t). In addition, one calculation is required to compute W(t) and two are required to calculate FV(W (t)). Hence for each element of Vj, 2+2z calculations need to be performed, where z is the number of vectors Cv considered in Problem (4.20). Using Formulas (4.21), (4.22) and (4.24),a computational procedure for solving problem (4.20), that is, subproblem one, is given as follows. (1) Find vectors y(t) and W(t) using (4.21) and (4.22), respectively, and then compute Fv(W(t)) using (4:.24) and F(W(t)) (2) Check whether F(W(t)) j min F(W(s)) (4.25) where the minimum is taken for all s ~ t such that y() > 0.

-56(3) Whenever (4.25) is satisfied, check whether y(t) 2 0 If y(t) > 0, record W(t) and F(W(t)) = D W(t) + max (l,(W(t))T)Cv Whenever (4.25) is not satisfied, calculate y(t+l), (t+l) and F(W(t+l)) Continue in this manner until all 2QN vectors y(t) have been calculated. Clearly, the optimal solution vector W* is that vector having the property that F(W*) = min F(W(S)) for all s such that y(S) > O. Since there are only a finite number of vectors y(S) > O, the vector W* is one of the set of vectors W(),where y(S) > 0 c) Rules for Excluding Vectors from Consideration It is clear that the size of the problem that can be investigated using the solution method presented in 4.5b) is indeed quite limited. In fact, it is easy to see that at least (2z+2)2QN calculations must be performed to solve the problem using that technique. However, as is shown shortly, not all vectors need be calculated. In fact, a large number of vectors do not have to be considered at all. The rules presented below indicate how vectors are excluded from the computational procedure. Suppose y(t~) E J Vi. Consider all vectors i=o QN t = to + i 2i i=j+l where bi = 0 or 1 for i > j and for at least one i, i = 1. Clearly there are 2QN-j - 1 such numbers t. To any vector y(t) and integer j, j=O,...,QN-l, a set Hj(y(to)) is defined as follows: Hj(y(to)) = yt): yt)c Vi (tt) y(to) QN = y.kyV y y - Z 5i a.i 5i = 0 or 1, i=j+l i=j+l 5i not all O }.

-57There are 2QN-j - 1 elements in the set Hj(y(tO)) Define M(W(t)) = min F(W(t)), where the minimum is taken over all t such that 0 < t < to and y(t) > 0. Also define (j+l) = max di + if ci>j m max di + Cv,i+l' Cv i+l + di <, i > j i>j = (di + Cv i+l) if Cv,i+l + di > 0 i>j for at least one i> j, where (di + Cv,i+l)+ = max(O, di + cvi+l) Now suppose y(t) C 9 Vi and t = to +.Z i 2i i=o i>j Then FV(W(t)) = DiW(t) + (1,(W(t))T)CV (t0 + ~N bi 2i) = DiW i=j+l (to + bN i 2i) T + (l,(W i=j+l ) )C D{W(to) QN = 1W ~) Z biEi} i=j+l + {(l,(W(to))T) - (o,( iEi) )}CV i=j+l QN = Fv(W(to)) - i(di + v,i+l) i=j+l > Fv(W(to)) - mv(j+l) Exclusion Rule 1. Let y(to) be the vector just determined using Equation (4.21). Suppose y(S)C ty(t)=H It: t _ to, Fv(W(t)) - mv(j+l) > M(W(tO)) for some v} Hj(y() - H Then F(W(S)) >M(W(to)) and therefore W(S) cannot be an optimal feasible vector. Hence all elements of H may be excluded from

-58optimality considerations. Thus this first rule excludes vectors from consideration whose corresponding objective functions are shown in advance to have values no less than the value of the objective function corresponding to some previously calculated vector. Now define h(j), a Q- dimensional vector, by hi(J) = min ai,i, where hi(j) is the i-th component of h(j) k> j+ 1 Thus y(t) y(tO) _ Z bi a < y(to) - h(j) (4.26) i>j + 1 This leads to Exclusion Rule 2. Suppose y(to) e Vi and Yi(to)- hi()< O for at least 1=0o one i. Let y(t)E Hj (y(tO)) o Then from (4.26) it follows that y(t) < y(to) - h(j) <. Consequently y(t) X 0 and therefore is infeasible. Hence all vectors in the set can be excluded from further consideration. Thus this second rule permits exclusion of vectors from consideration which can be shown in advance to be infeasible. By combining the method for generating the vectors y (t) W(t) and the associated cost functions F(W(t)) with the above exclusion rules, an algorithmic procedure has been constructed for solving the restricted integer problem. 4.6 The Inside Problem-Subproblem Two a) Introduction In this section, a solution method is discussed for the inside problem which takes advantage of its structure. Since it was shown in

-594.3 that the structure of this problem for the basic one and Q period models is identical, only the inside problem corresponding to the one period model will be discussed here. The methods presented are easily extended to the Q period case. The inside problem was shown in 4.3 Equation (4~7) to be decomposable into independent subproblems. The solution methods for these subproblems therefore can be considered independently. b) The Problem minu{D2U ~ U > W1 - Wo, U > O} In 4.3, this problem was shown to be decomposable into N subproblems each of the form cimin ui subject to 1 O wi - i' ui ~ < i In 4.3 it was shown that the optimal value for ui is ui = 1 1 o 1 o whenever wi - wi = 1 and ui = 0 whenever wi - wi = 0 or -1. Hence to -solve the problem minu{D2U: U > W1 - Wo, U > O}, given the value of the vector W1, the following simple rule can be applied. Set 1 0 jl, if wi -wi = 1 0 otherwise, for i=l,,,,,N e c) The problem min {Sj,t D3pj Sj,t lnN+l = bt - m*(W1), Sj t W Sj, Sj t In 4.3, this problem was written in its equivalent form pj min Z Z (Si,k,j,t gi,k + hZjt,) subject to Sj t lnN+l bt - m*(W1)

-60oT Sj,t < W Sj,t -0 This problem is also a particularly simple one to solve, Recall that the incremental production cost curve for each generating unit is assumed to be monotone increasing, that is, for unit i I gi l < gi 2 ~ < g Order the numbers hgisk, i=l,...,N, k=l,...,n, in ascending order. For a given vector W1, the capacity of the k-th step of the i-th generating unit is given by Mi k Wi - The optimal feasible solution is then obtained simply by loading the Si k, jt and Zjt, within their respective induced capacity ranges, that is, O _ Sijk,t - Mik wi, in the order corresponding to that placed on the numbers hgk i =l... N, k=l,...,n above until the requirement bt - m (W1) is satisfied. Note that if some wl = 0 and according to the ordering of the incremental costs, Sik,j,t is the next variable to be loaded, then 0 _ Si,k,j,t < Mi k w1 = 0 Thus S > 0 only if w = 1 The following simple observation is made. Let a be a positive number, and Al, X, C1, and B1 be defined as in section 4.2. Consider the optimization problem min CT X subject to A1 X _ B1 x 0. (4.27) Let X be an optimal feasible solution to (4.27). Now consider the problem

-61min CT X subject to A1 X > B1 X > O, where C = aC1. (4.28) It is clear that X* is an optimal feasible solution vector for Problem (4.28), too. The converse is also obviously true. Consider the optimization problems min Sj,t D3' Sjt lnN+l = bt - m (W1), jt W,S (4.29) jt and min {Sj,t(D3Pj): Sj, lnN1 = bt nN+(Wl), ST t St (43) Sjt From the observation made in the previous paragraph, it is easy to see that Sj, t is an optimal feasible solution to (4.29) if and only if Sj is an optimal feasible solution to (4.30)~ Let X1, X2 be p-dimensional vectors and Al, B1, C1 be defined as in 4.2. Consider the problems min CT X1 subject to A1 X1 ~ B1, (4.31) X1 2 0, and min CT X2 subject to A1 X2 ~ B1, (4.32) X2 ~ 0 It is clear that X1 can be an optimal feasible solution to (4.31) if and only if X2 X1 is an optimal feasible solution to (4.32).

-62From this observation, it is clear that S* can be an optimal j l~t can be anlot feasible solution to (4.29) with j = jl if and only Sj2,t Sj t is an optimal feasible solution to (4.29) with j = j2, j2E{1,.~,r} Combining these results, Sl is an optimal feasible solution to mm {S, p't lt nN+l = bt m (W1) I SJT t:> t} 8. 1 1 1' 1 (4.33) if and only if S* S t is an optimal feasible solution to min {Sj2,t D3P 2 Sj2t lnN+l = bt m (W1), ST2t = W, Sj2,t _ ~} Sj2,t ~~il~~~, j2e4l,...,r}J~.(4.34) Thus it is necessary to compute the optimal feasible vector S t to (4.29) for only one value of j, say j=l. The total expected incremental production cost for demand level bt can then easily be found by calculating the optimal value of the objective function to (4.29) and multiplying that number by Z pt, that is, the sum of the probabilities that bt is realized in subinterval j. This can be seen by noting that the total expected incremental production cost portion of the inside problem, (4.7), can be written as Z. Z min {Sjjt D3pj Sj,t lnN+l = bt - m*(W1), < S j,t O} t Sj t jej t T Z. Pi min {Sj,t D3: Sj,t lnN+l = bt - m (W1), Sjt < W. Sj t O} t j S j,t:= 7 pj rmin {Sl,t D3: Sl,t lnN+l = bt - m (W1), ST,t W Sl t > O} t j s = Z mmn {lt D3: 1,t 1l = bt m~(Wl), slt ~W, Sl t ~ O} Z a min { S, t D3 Sl,t inN+l: bt = m ( W1) y 1, t < W, S i t - 0}{ ~. p t Sit j (4.35)

-63Thus -to calculate the total expected incremental production costs for a given value of W1, only 2 minimization problems need be solved rather than ri minimization problems. 4.7 The Generation of a New Constraint a) Introduction To complete the description of how the various portions of the algorithm presented in 4.4 are calculated, a discussion is needed of how to generate new constraints for Problem (4.19). In the previous section the discussion centered around methods for solving certain primal problems. The new constraints for the restricted integer problem, as shown in section.4, are generated by using the optimal values of the dual variables to these primal problems. This section is concerned with how to calculate the optimal values of these dual variables and how to use them to generate new constraints. b) The Dual Problem of minu{D2U: U ~ W1 - W0, U > 0) The Dual Problem of minu(D2U: U:W1 - Wo, U > o) is T maxyl((WL - Wo) Y1:0 Y1 ~_D2)} This problem can be decomposed into N subproblems since the constraints are independent, These N problems have the form 1 o maxyl, (wi (wi)Y,i subject to 0 < Yls i ci (4.36) where Yl, i is the i-th component of Y1 and ci is the i-th component 1 o of D2. It is clear that if wi - wi = 1, the objective function is 1 o maximized by setting Yla i = ci T If w - w = -1,the maximum value the

-64objective function can assume is 0 for 0 _ Yl, i ci, that is, when Yli =. If wi - wi =, then Yl,i can take on any value between 0 and ci, for the value of the objective function is 0 no matter what the value of Yi, 1 In this case, choose Yli = 0 as the optimal feasible solution to (4.36). Note the following simple rule can be used to generate the optimal feasible solution to Problem (4.36). If ui = 1, that is, if w w = 1 set Yl, i = Ci If ui = 0, that is, if w - w~i = or -1, set Yl i = 0 o Thus, in either case Yl i = ciui c) The Dual Problem of in {S D3 nN+ = bt m (W1, j,t j,t Since the minimization problems for the expected incremental production costs are independent and identically structured for different pairs (j,t) 2 it is sufficient to show how to find only the values of the variables to the dual of min {Sjt D3: Sjt nN+l = bt - m*(W1), t, jt } (437) 5jt Recall that in section 4.3, (4.37) was shown to be a transportation problem with surplus having (nN+l) origins and one destination. Some properties of this type of transportation problem are discussed next. To reduce notational problems, let x(i-l)n+k, 1 - Sikjt XnN+l,1 - Zj,t, d(i-l)n+k,l - gi,k, dNn+l,l _ h, b = bt - m (W1) and a(i l)n+k be the ((i-l)n+k) -th coordinate of W o Thus (4.37) is rewritten as nN+ 1 min Z dil Xiil (4.38) i=l

-65subject to 0 < xi,1 < ai nN+ 1 xi,=b. i=l 1 nN+ 1 It is also known by assumption that Z ai > b. i=l The inequalities in the constraints can easily be converted to equalities by adding nN+l slack variables, xi 2, i=l,...,nN+l. The resulting optimization problem is nN+ 1 min Z di,1 xi 1 ial subject to xi 1 + 2 (4.39) nN+ 1 Z Xil =b, i=l nN+ 1 nN+ 1 i Xi, 2 ai - b = b' i — 1 i=l Xi,j > 0, assuming the costs associated with the slack variables are 0. Then the dual to (4.39) is nN+ 1 max Z aiY2,1 + bv1 + b-!v2 (4.4o) i=l! 1 subject to Vl + Y2, i -< di1' v2 + Y2,i - The dual to Problem (4,38) is nN+l max - aiY2, i + bl subject to (4.41) i=l V1 - Y2,i dil' Y2~i ~0.

-66Suppose (4,39) is solved using the computational procedure described by Dantzig(ll) We shall call this method the transportation array technique. Upon obtaining a solution of (4.39) using the transportation array technique, the optimal values of Y2,i' Vl' and v2 are available. It will be demonstrated how to use the optimal values obtained for and v to solve Y2, i vl for the optimal values of Y2 i and vl When finding any feasible solution to (4.40), one of the variables 1, v2, Y2, i can be set at an arbitrary value(ll) Suppose v2 O. Then Problem (4.40) becomes nN+ 1 max Z aiy2,i + bvi (4.42) i=l subject to V1 + Y2 i < dil, y2 <0. 2,i - Substituting Y2,i = -Y2,i, Problem (4.42) is identical to -problem (4.41). Using the observation made about Problems (4.31) and (4.32) in 4.6, it is seen that an optimal feasible solution to (4.41), Y2i' v2 with 2 = 0, can be used to obtain an optimal feasible solution to (4.41) by setting v1 = v1 and Y, i = -Y2 ~ Thus the optimal values of the variables to the dual of (4.38) can be obtained from the optimal values of the variables to the dual of Problem (4.39). In order to calculate the optimal values of the variables to the dual of Problem (4.39), the optimal feasible solution to (4.39) must be obtained. The optimal solution to (4.39) can be obtained using the following rules.

-67Let I be the set of indices i such that xi,1 > 0 or i = 0 and di, maxj{dj 1 xj > O The values of the xi,1 > 0 such that icI are found using the method discussed in 4.6c). By convention, it is assumed that I # ~. That is, it is assumed that the i corresponding to di,1 = minj{dj 1} is an element of I. Note that xi 1 = 0 and icI if and only if ai = 0 and icI or b = 0 and di 1 = minjfdjd. 1} Let L be the set of all i such that i/I. Then for icL, set x,2 = ai' Clearly Xil = ai, icI, except for possibly Xk,l 1 where dk,l = max{di.l} * If more than one di,1 max{di,1} l icI iE I iE I then xk,l is chosen to be the last variable that is required to be adjoined to I as discussed in 4.6c). Let L' = Lu{k}. If Xk,l = ak then set Xk,2 = 0 If Xk,l ak, let xk,2 = ak - Xk,l 1 The variables xi 1' icI, and xi 2, icL'1 form a basic optimal feasible solution to Problem (4.39). Justification of the above algorithm can be seen as follows, By the way the solution was constructed, it is seen to be feasible, That it is basic follows, since by permuting the rows of the corresponding transportation tableau, the proposed solution corresponds to a solution obtained using the Northwest Corner Rule(27) which is known to generate a basic solution(27). To show the proposed solution is optimal, it is sufficient to show that Vl - Y2,i ~ di 1, for all i, V1 - Y2i = di 1, for iEI Y2 i > O, for all i, o.-i = 0 for iLL' assuming vo = O (7)

-68-!! That Y2 i =0, iL',follows, since v2 + Y2 i = Y2 i = 0 and Y2, 1= Since Y i = -Y2 i Since Y2 k =, v = dk,l = maxidi, i Thus vl - di,1 >, iEI, that is, Y2 i > O, since = v1 -di 1 icI e Now consider the algebraic sign of di,1 - V1 + Y2,i, i/I For i/I, it was shown above that Y2 i = 0 Since i/I, di,1 maxicI{di,1} = dk,1 = v1,that is, d1 - v> 0. Thus the proposed solution satisfies the criteria for being a basic feasible optimal solution, In the above paragraph, a simple method of calculating the optimal values of the dual variables was given. This method is summarized as follows: for icL', set Y2 i = 0; set v1 = max di,; and set Y2, i = V1 - di,1' for icI As was the case for the primal problem, only I dual problems need be solved. It was observed in 4.6 that X* is an optimal feasible solution to minimize CT X1 (4.43) subject to A1 X1 > B1, X1 O 0, if and only if X1 is an optimal feasible solution to minimize (aCT)X1 (4.44) subject to A1 X1 > B1, X1 ~ 0, where a is a non-negative real number and the vectors are defined as in section 4.2. Now the dual to (4.43) is maximize B Y1 (4.45) subject to AT Y1 < C Y1 > 0O and the dual to (4.44) is

-69maximizey2 BT Y2 (4.46) Y2 1 Y2 subject to A1 Y2 ~ aC1 Y2 > O q where Y1, Y2 are m-dimensional vectors. It is easy to see that Y1 is an optimal feasible solution to (4.45) if and only if Y2 si aY1 is an optimal feasible solution to (4.46). Thus by solving (4.37) for the optimal values of the dual variables for j = 1 and t = 1,...,2, the optimal values of the dual variables for all (j,t) pairs are immediately available. d) The New Constraint The new constraint is found using the optimal values of the dual variables to the inside problem. The expression for the new constraint presented in 4.4 for the general case is presented here using the notation developed for the power scheduling problem. In particular, it is shown how the new constraint is generated for the one period problem. However, the new constraint for the Q period problem is generated in the same way. Let Y1 be an N-dimensional row vector of the optimal values of the variables in the dual of minu{D2U: 0 < U U W1 -Wo and Y2,j,t be an nN+2-dimensional row vector of the optimal values of the variables to the dual of minSj t{Sj,t D3pj: Sj,t lnN+l = bt - m (W1), S t 5 W Sjt ~ O} the first component of which is the dual variable associated with the constraint Sj,t lnN+l = bt - m (W1) and the remaining components correspond in order to the rows of the constraint ST t < W

-70Let Bt = [bt, 0, 0,...,0] be an nN+2 dimensional vector, aji = [0,...,0] be an n-dimensional vector, for i # j, ai,i = [Mi,...,Min] be an n-dimensional vector, ai = [mi, al,.,ai,, i,..., T aN, i ~0] be an nN+2 -dimensional vector, i = 1,...,N, aN+1 = [0,...,0,M] be an nN+2 - dimensional vector, A be an (nN+2) x (N+l) dimensional matrix with ai as the i-th column of Ao, INxN be the NxN identity matrix, T T B = [-WO, B1,...,BQ,...,B1,...,B] be an N + (nN+2)r2 dimensional vector, T ON = [0,0,...,0] be an N-dimensional vector, NxN, ON Ao =. A be an (N+(nN+2)re) x (N+l) matrix, and Y = [Y, and Y = [Y1, Y2,1,12.,12,''',Y2 1 ~,, Y2 r~l,ly''' be an (N + (nN+2)re) dimensional vector. Then the new constraint is given by y > YB - A [lj+ DW (4.47) The new constraint can also becwritten in the equivalent form yo > Y1(-Wo + W1) + Y2,j,t BT-A [1 + D t=l j=l... (4.48) 4.8 Some Comments on the Algorithm Each iteration of the algorithm produces an upper and lower bound estimat e of the optimal value of the objective function to Problem (4.18). This can be seen as follows, When solving subproblem one, a

lower bound estimate is found since the minimization in (4 19) is carried out over a restricted subset of the constraints in Problem (4.18). On the other hand, the optimal value to subproblem two yields a finite upper bound to the optimal value of (4o18) since a(Y*) is a finite which implies (X*, Y*) is a feasible solution to (4.14) with T * T * T T* C1 X + C Y = a(Y*) + CY ~ miny~s {CT Y + minx{CT X > B - A2 Y, X > 0}} ~~T T = minYS {Yo Yo ~ C2Y + max (B - A2 Y) (UV)} veV where X*, Y*, C1, C2, a(Y*), V, and Uv are defined as in section 4~4. It is important to recall that the algorithm is a primal method, that is, each iteration produces a feasible solution to the original problem. It may be desirable to terminate the computational procedure if it becomes too expensive or possibly if the best feasible solution calculated yields a value of the objective function within some specified distance of the lower bound estimate of the optimal value of the objective function. In any case, after each iteration a best feasible solution to the original problem is available together with an estimate of how far the corresponding value of the objective function is from the optimum. The algorithm, through the partitioning procedure, preserves the structure of the inside problem thereby allowing solutions to this inside problem to be easily calculated. In addition, it was shown in 4.6 that the number of problems related to the economic dispatch portion of the inside problem, that is, the portion involving the incremental production costs, that need to be solved in any iteration of the algorithm is directly related to the number of demand levels, Q, but is independent of the number of subintervals considered for (OT], that is, r o

-72Another important advantage of the algorithm is that it permits prior experience to be directly incorporated into the computational procedure. Suppose several feasible solutions to the problem are generated beforehand as likely candidates for the optimal feasible solution. Using the methods described in 4.7b) and 4.7c), the optimal values of the dual variables associated with the proposed feasible solutions can easily be calculated. A constraint for each proposed solution can then be generated as discussed in 4.7d). These constraints are included as initial conditions for solving the restricted integer problem, that is, their indexes are the elements of the set V' of Problem (4.19). The v-th constraint takes the form of the function Fv defined in 4.-5b) Equation (4.23) in which Cv, for the one period model, is an N+l - dimensional vector whose first component is Y B - Y aN+1 and whose j+l-st component is Y ~ + Tkj, where aj is the j-th column of A Y, A and B are defined as in 4.7d) and kj is defined on page x.

CHAPTER V AN EXAMPLE AND A FLOW CHART OF THE ALGORITHM 5.1 Introduction A descriptive flow chart of the proposed algorithm is given in Figure 3. A detailed flow chart is given in Appendix I. A numerical example originally proposed by Garver(20) is solved using the proposed algorithm. The details of the first two iterations are found in Appendix II. A rule for obtaining approximate solutions is illustrated. The effect of including feasible solutions as initial conditions on the restricted integer problem is also illustrated. Garver used Gomory's all integer programming algorithm to solve the problem. The relative computational advantage of the proposed algorithm is demonstrated. 5.2 The Example The power generation system scheduling problem proposed by Garver(20) is solved here using the proposed solution method. In review, Garver's problem is as follows. A decision is made as to which of two units to operate in each of two successive time periods. The schedule can be altered only at the beginning of each period. It is desired to obtain a two period schedule at the beginning of the first period, that is, it is to be determined which units are to be operated in period one and which units are to be operated in period two. The periods are assumed to each be of an hours duration". The demand for [power is assumed known in the two periods. It is assumed that both units are operating initially and the incremental production cost curves are monotone increasing step functions. -73

-74INPUTS Costs, Initial Constraints on the Restricted Integer Problem, Constants, Demand Levels and Associated Probabilities Solve the Restricted Integer Problem min yv subject to yV. >Fi(W), i=l,. -..,z and AW > B. Solve the "Inside Problem" for U, Sj,t, * and the Dual Vector Y. YI Is the Solution to the Restricted Yes Integer Problem Optimal (Does yV. = Yv)? Finished No Calculate the New Constraint for the Restricted Integer Ptoblem, | Fz+l(W = Y(s - [1]) + Tq k. i' l Update the Iteration and Constraint Counters, that is, v and z. Figure 3. A Descriptive Flow Chart of the Algorithm.

-75In addition to the variables presented in the formulation given earlier, Garver also considers the cost of shutting a unit down in each period. This variable is denoted by the symbol vq As stated above, Garver's problem assumes that demand is known in each of the periods. This is equivalent to assuming the demand is at the specified levels with probability 1. The variables as defined in the earlier formulation are somewhat modified for the present problem. In this problem r = 2 = 1. Therefore, the j and t subscripts can be eliminated. Thus Sikjtq is reduced to simply Si k q. A table is given below indicating the costs used in this problem. TABLE I Variable Generator 1 Generator 2 Mi (Maximum rating) 120 mw 80 mw mi (Minimum rating) 30 mw 20 mw ki (Cost at minimum rating) $85/hr $60/hi' gil(Cost at 1-st incremental step) $2,/mwhr $2,3/mwhr Mi,l(Power available at 1-st step) 20 mw 30 mw gi 2(Cost at 2-nd incremental step) $2.8/mwhr $3./mwhr Mi,2(Power available at 2-nd step) 70 mw 30 mw ci (Start up cost) $30 $20 Si (Shut down cost) $15 $10 Cost Table Using the modified notation, the example problem can be stated as 2 2 2 minimize Z Z {cu + sv + kiwi + Z gi,k Si,k,q } q=l i=l k=l

-76subject to M1wl + M2w2 > 65, Mlwl + M2W2 > 120 1 o 1 wi - Wi < ui, o 1 1 W. - W. <V. 1 1i - 2 1 2 Wi - Wi <Ui 1 2 2 Wi - Wi <vi Si,I,1 + S1,2,1 + S2,1 + S2,2,1 = 50 -ml(W), S +,2,2 + S1,2,2 + S2,2,2 = 100 - m(W2) i, k, q < Mi,k q > 0, and wkq 0 or 1 The initial conditions are w1 = w2 = 1 The problem is first solved without generating any initial constraints for the restricted integer subproblem. The following are input to the problem. 120 80 0 0 0 0 120 80 r11 2 2T W = W 1 W2 W1 W2 J T B = [65, 120], F1(W) = 85w1 + 85w1 + 60w2 + 60w2 G = {(1,1), (1,2), (2,1), (2,2)} W(O) I 1,l,z1,1] = W t = 1, z =1, v= 1, T1 = T2 = 1, k= 0,

-77T -1 0 0 0 -1 yll 1 0 -1 0 0 Y1 yl 1 0-1 0 0 y2 1)1 0 1 0 -10 2 Y1,2 1 0 0 0 1 1 1,2 0 1 0 0 1 yi94 -1 0 1 0 0 y 0 -1 0 1 0y2 m1 m2 0 0 50 10 y2 1O 0 ~0 0 B = 0 0 0 and Y = M1, 2~ Y2,1,2 1 0 M,10 0 0 A,2 o M2, 022 0 0 0 mAei 2 100 y2,1, 1 O O M0 0 2 10 M 0 2l 0 0 02 2,12 0 0 0 M2 0Q y22~1 0 0 0 0 2 The details of the first two iterations of the lgorithm are given in Appendix II. The algorithmin procedure terminates after four iterations with T 4 W = (1,1,1,1) as the optimal solution vector and y4 = 399 = y4 The results of all the iterations are given in Table II below.

-78TABLE IT Iteration Solution Number Vector yv The New Constraint T 1 (0,1,1,0) 145 410-35wl+24wl+15w2-21w2 449 2 (1,0,. 1, 1) 369 340+25wl-lOw2+lOwl+34w2 409 3 (1,0,1,0) 390 390+25w1+low2-15wl211w2 400 T 4 (1,1,1,1) 399 399 SUMMARY OF CALCULATIONS FOR THE CASE OF NO INITIAL CONSTRAINTS Suppose, however, that all that was desired was an approximate solution. Then the algorithm could have been terminated using a rule such as the following: whenever YV* _YV < d, Yv stop the computational procedure and retain the present feasible solution, where d is some real number. If d =.03, computation would have been terminated after three iterations of the algorithm. The actual difference between the value of the objective function of the approximate solution and that of the optimal solution is $1 or only a 1/4% difference. Suppose a set of initial feasible solutions is proposed beforehand. In an experiment performed on severalcolleagues, two feasible solutions were guessed to be the optimal feasible solution. These two solutions T T were (0,l,l,0) and (1,0,1,0). Using the dual variables corresponding to these two feasible solutions, two initial constraints for the restricted integer problem are generated. The constraints corresponding to (0,l,l,O)T T and (1,0,1,O ) are

-791 1 2 2 F1(W) = 410 - 35w1 + 24w2 + 15w1 - 21w2 and 1 1 2 2 F2(W) = 390 + 25w1 + lOw2 - 15w1 - 1lw2, respectively. The results of the iterations for solving the problem when the above initial constraints are included are summarized in the following table. TABLE III Iteration Solut ion Number Vector yv. The New Constraint Yv T 1 (1,0,1,1) 389 340+25wlI -lOw0+lOw2+34w2 409 T 2 (1,1, 1) 399 399 SUMMARY OF CALCULATIONS FOR THE CASE OF INITIAL CONSTRAINTS Thus by introducing the two initial feasible solutions, the number of iterations required to obtain the optimal feasible solution is halved. This problem, as mentioned earlier, was solved by Garver using Gomory's all integer programming algorithm, The solution took 15 iteration of algorithm to reach the optimal solution. Furthermore, after each iteration, except the last one, no feasible solution was available. Thus if an approximate solution was all that was required, it would have been difficult to obtain. In addition, Gomory's algorithm required more iterations to reach the optimum than there are feasible solutions to the problem.

CHAPTER VI SUMMARY AND CONCLUSIONS 6.1 The Model a) Features of the Model The extended model presented in Chapter III includes factors that are considered important in the scheduling of a fossil fuel power generation system over a short time horizon. In review, it is a multiperiod model which includes the effects of starting generating units, the demand process, system reserve requirements, generating unit capacity constraints, transmission losses, manpower requirements, geographical reserve requirements, multiple interconnections, and common header units. The costs considered in the objective function are the time dependent start up costs, minimum level fuel costs and the incremental production costs. Because the demand for power is considered to be a:random variable, the objective is to minimize the total expected cost expression over the specified time horizon. The proposed model for the short time - horizon power scheduling problem can theoretically be applied to a system consisting of any number of generating units. However, the number of generating units that can be considered in practice is limited due to computational problems which are discussed below. As far as we know, this is the first model for the short time - horizon power scheduling problem in which demand is considered as a stochastic process. In particular, stochastic processes discrete in both time and space can be described using the method presented in 3.2c). A special case of the above is the case in which demand is assumed known with probability one throughout the time horizon, that is, demand is assumed to be -80

deterministic. In the limit, it was shown that stochastic processes continuous in time and space having almost continuous paths can be approximated arbitrarily closely using the proposed method for describing the demand process. However, as will become evident later, computational problems occur when the number of states considered becomes large. Also, as far as is known, this is the first model for the short time - horizon power system scheduling problem which allows the effect of interchanges to be considered directly. b) Structure of the Model and Dual Analysis The partitioning procedure introduced in Chapter IV reveals for the first time the underlying simple structure of the scheduling problem. Consequently, we were able to prove that all basic feasible solutions to the scheduling problem are integer. In doing so, we demonstrated that the inside problem was decomposable into many independent subproblems some of which are transportation type problems; namely, the problems having the form min {Sj,t 3 j,t lnN+l = bt - m (W1), Sj t W W S t O} = ~jt t=l. 0 0, were shown to be transportation type problems. Using the values of the dual variables associated with the constraints Sj,t lnN+l = bt - m*(W1) found in the above problems, the expected "breakeven" selling price for power is easily calculated for each time period. Thus it is easy to determine what the selling price per mw-hr should be in each time period in order to obtain a specified expected profit per mw-hr. Such dual analysis has not been directly available in previous scheduling algorithms.

-82c) Some Practical Problems Certain practical problems are pointed out because of the comprehensive structure of the model. To apply this model, it is necessary to specify the appropriate time horizon and the times at which generating units are placed into or withdrawn from service. The scheduling techniques discussed in Chapter II also require these times to be known in advance. This partitioning divides the time horizon into periods which are in turn subdivided as described in 3.2c). For each subinterval of each period it is also necessary to forecast the possible demand levels and the corresponding probabilities in advance, that is, for each period q and every pair (j,t) it is necessary to forecast the demand levels blj,q,..., bje,q and probabilities pj' q At present only a deterministic demand curve is forecasted. Thus to apply the proposed model in its most general form it will be necessary to implement new forecasting techniques. Another practical problem encountered when applying the proposed model is the necessity of requiring the incremental production cost curves to be given in the form of step functions. In practice, as discussed in 2.2a), these curves are often assumed to be strictly monotone increasing differentiable convex functions over the operating range. In fact, it is often assumed these curves are quadratic functions, However, it is possible to extend the work of this dissertation to the particular case where the incremental production cost curves are strictly monotone increasing and piecewise quadratic functions over the operating range of the units, The independent transportation type problems within the inside problem can be replaced in a one to one fashion by independent quadratic programming

-83problems. Then using the Kuhn-Tucker theory(28), it is possible to determine the values of dual variables associated with each of the quadratic programming problems. These values are then used to generate new constraints for the restricted integer problem. The incremental production cost curves are required to be step functions in the integer programming models discussed in Chapter II. HowLver, the dynamic programming algorithm does not require these curves to be step functions. 6.2 The Algorithm a) A Review of the Algorithm In the previous section, it was noted that the basic structure of the scheduling problem is revealed through the partitioning procedure. The main reason for interest in the proposed algorithm is that it preserves this basically simple structure. In review, the model was partitioned into two subproblems~ namely, a purely integer problem and a linear programming problem, The purely integer problem was called the restricted integer problem. An algorithm, adapted from one presented by Benders, etal, ) was d(6scssed and proposed as a solution method for the restricted integer problem. The linear programming problem was called the inside problem, It was demonstrated that the inside problem is decomposable into many independent problems. Some of these problems were shown to have the following form~ minimize the value of a continuous variable such that the variable is restricted to be greater than or equal to a specified constant, The remainder of these problems were shown to be transportation type problems.

-84A simple algorithm was presented for solving the inside problem and its dual. Each iteration of the algorithm was shown to consist of obtaining a solution for the restricted integer problem, using this calculated solution to obtain a solution to the inside problem, and checking for optimality. If the combined solution was optimal, then the algorithm naturally termi:nated. On the other hand, if it was not optimal, then a new constraint was generated for the restricted integer problem and another iteration of the algorithm was performed. b) Features of the Algorithm Some of the properties of the algorithm were discussed in section 4.8-. The algorithm was shown to terminate in a finite number of steps. Each iteration was shown to produce a feasible solution and an upper and lower bound estimate of the optimal value of the objective function. Furthermore, it was demonstrated that approximate solutions could be obtained if so desired by terminating the computational procedure in accordance with some predetermined rule. Some such rules are the following: terminate the algorithmic procedure after a fixed number of iterations or terminate the computational procedure when the upper and lower bound estimates of the optimal solution differ by no more than some predetermined number. In addition, if the computational procedure is terminated before an optimal solution is obtained, it is possible to determine the remaining candidates for the optimal solution. It was also discussed that prior experience can be used to generate likely candidates for the optimal solution in advance and that these solutions can be used as constraints for the restricted integer problem. The effect of including these constraints on the computation time is discussed below,

-85c) Algorithmic Limitations To date little computational experience has been acquired uting Benders' algorithm. Thus it is difficult to estimate the maximum sized problem that can be solved using the proposed algorithm. Limitations in the size of the problem that can effectively be solved using the proposed algorithmic procedure depend on computation time and storage requirements. The restricting factor in terms of computation time is the total number of components in the vectors W1 through WQ. It has been estimated, however, that this number should not exceed 30 or 40(5). We conjecture that the maximum number of integer variables that can be considered is related to the maximum number of sets Vj, as defined in 4.5b), that need to be calculated when solving the restricted integer problem, and that if this maximum number is less than or equal to about 20, the problem can successfully be solved using the proposed algorithm. After geographical reserve requirements are included as constraints to the restricted integer problem and the components of the vectors W1 to WQ are carefully ordered so as to introduce the maximum possible number of feasible solutions in sets V1 through Vj, the number of integer variables that may be considered in the problem can be determined. The number of integer variables that can be considered is thus seen to be highly dependent on the particular system being modeled. The number of integer variables that may be considered in the scheduling problem may also be affected by the initial constraints generated for the restricted integer problem. Another integer programming (21) technique which shares many of the properties of the algorithm used to solve the restricted integer problem has been investigated in (17) for its computational effectiveness. In that study, it was demonstrated that by

-86introducing estimates of the optimal solution the computation time was drastically reduced. Thus it is hoped that the introduction of initial constraints on the restricted integer problem produces the same results for the proposed algorithm. These initial constraints correspond, of course, to feasible solutions which, based on past experience, are proposed as possible candidates for the optimal solution vector. The computational problems discussed above are shared by all the scheduling procedures discussed in Chapter II. In addition, computational experience with Gomory's algorithm has indicated that the number of iterations required to achieve the optimal solution varies greatly(4). This convergence problem seriously affects the usefulness of that algorithm. Applications of the proposed algorithm are also somewhat limited by the amount of core storage that would be required for use in a computer. It is difficult to estimate the storage requirements for the actual program of the algorithmic procedure. The number of core locations required for the program depends, for example, on the amount of output that is desiredand, even more importantly, on the skill of the programmer. However, it is possible to give an estimate of the amount of core required- for the input matrices and vectors and the number of addressable locations required to store the values of the variables determined in the computational procedure. Assuming that the maximum number of sets Vj that need to be calculated in any iteration of the algorithm is 15 and the computer is a 32 bit word length machine, approximately N(Q(4+I) + 3n) + Q(1 + max 2q ) + 500 (6.1) l<q<Q

-87core words would be required,where I = the number of initial constraints on the integer problem. Note that this sum is independent of rq, the number of subintervals in the q-th period. For example, if Q=4, N=10, n-4, max 2q = 20 and I - 15, this sum is less than 1500. In addition to the core requirements, however, at least one tape unit should be used. The vectors y(t), as defined in section 4.5, would be stored on this tape. This seems like an efficient storage method for the y(t) vectors9 since they are introduced sequentially into the computational procedure. Thus it would not be required to search the tape for the next piece of informationo However, these requirements do not appear to be excessive. We estimate that Gomory's algorithm and the dynamic programming technique both will require considerably more storage space. For a problem of the size mentioned above, approximately 1156 x 104 addressable locations are required to store the information needed to perform an iteration using Gomory's algorithm in addition to the program requirements. More than 220 addressable locations would be necessary to solve the problem using the dynamic programming technique. The estimate given in (6.1) is based on the assumption that the maximum number of sets Vj that need to be calculated in any iteration is 15. However, by slightly changing the restricted integer algoritahm this estimate is valid no matter how many sets Vj need to be calculated, 6,3 General Extensions and Future Research There are certain areas in which research should be performed in order to improve the effectiveness of the proposed model and algorithm. These areas can be divided into two groups~ research on the algorithm and research on the factors affecting the operation of the system.

-88As has been pointed out before, the proposed partitioning algorithm seems to be the logical way to solve the problem since the algorithm takes advantage of the basically simple structure of the problem. However, it may be possible to find additional exclusion rules for the restricted integer problem. When solving Garver's example, some of the feasible vectors could have been excluded from consideration in advance because corresponding values of the objective function had to be greater than or equal to the values obtained for certain of the remaining vectors. The author was unable to construct an exclusion rule covering.these cases. It has also been suggested that by cleverly programming the algorithm for the restricted integer problem, it may be possible to limit the search for the optimal vector to only admissible vectors, that is, vectors which have not been excluded by Rules 1 or 2 or have not been demonstrated to be infeasible. In the proposed algorithm it is necessary to check each vector in the sets Vj for admissibility until it has been demonstrated that there are no longer any admissible vectors to be considered. If this step could be removed, both computation time and storage requirements could be reduced. In the previous section, the effect of the inclusion of initial constraints on the restricted integer problem was discussed. The possibility of reducing the amount of computation time required to solve this problem by introducing these constraints was mentioned. However, the importance of the inclusion of the initial constraints needs to be studied further. In the numerical example, both the number of computations per iteration and the number of iterations were reduced. Furthermore, if the initial constraints do prove to significantly reduce computation time, it must

-89then be determined how many constraints should be introduced initially. It should be noted that storage requirements increase with the number of initial constraints. The number of iterations required to solve the problem may possibly be reduced in another way. After each non-optimal iteration of the algorithm one new constraint is generated for the restricted integer problem. Suppose instead of just one new constraint being generated, that P new constraints -are generated. To do this, the inside problem is solved for each of the P "best" solutions, that is, least cost solutions, to the restricted integer problem. Then after each non-optimal iteration it would be possible to obtain P constraints for the restricted integer problem. Since the computation time required to solve the inside problem is very small, the amount of time needed to perform an iteration would not be appreciably increased. However, the time required to perform an iteration -of- the algorithm..for the restricted integer- probler:: is relatively large. Clearly, the number of iterations that are performed to reach the optimum using this modified rule is not greater than using the original method. In fact, the number of iterations should be reduced. In the numerical example, setting P - 2 reduced the number of iterations to reach the optimum to 3. Further research is necessary to study the effect of this rule for various values of P Some,of the practical problems and algorithmic limitations discussed earlier resulted from incomplete information about factors influencing the economic operation of power systems. In order to apply the proposed model it is necessary to optimally partition the time horizon and specify the probabilities for the occurrence

-90of different demand levels throughout the horizon in advance. This, of course, assumes these factors are known. Further research is needed to determine the optimal length of the periods and subintervals. By experimenting using simulation, changes in schedules resulting from different rules for choosing the lengths of the periods and subintervals can be investigated. It is also necessary to investigate the sensitivity of schedules to the randomness of the demand process. Such investigations can also be carried out using a simulation technique. Furthermore, research in the area of forecasting demand for power is probably needed. In order to apply the proposed model in its most general form, it will be necessary to forecast what amounts to a finite ensemble of curves, each with an associated probability of occurrence, instead of a single demand curve. Since demand for power is highly dependent on weather conditions, the developments occurring in probabilistic weather forecasting may make it possible to devise probabilistic methods of forecasting demand. Another limitation discussed earlier was that the number of integer variables that could effectively be considered in the optimization procedure is limited. However, certain characteristics of the generating units themselves may make it possible to reduce the size of the optimization problems that need to be solved. In general, the newer and larger generating units are much more efficient than the older units. Thus depending on the system in question, it is probably possible to demonstrate mathematically a dominance relationship between some of the older and newer generating units. For example, in periods of rising demand, it may be possible to show in advance that some units should be placed into service before certain other units. Such relationships, if available, can help

-91to reduce the size of the integer problem and thereby make the proposed model more useful, A good approximate solution to the problem may be all that is desired. It is possible to limit consideration in each period to only certain "likely" generating units for operation. This would result in reducing the number of the integer variables that need to be considered, Experimentation should provide answers about the usefulness of this approximate technique. It may also be possible to decompose a system into several parts and solve the problem for each part separately. To do this, it is necessary to estimate the demand in each area in order to establish capacity requirements for each area. It would also be necessary to know the expected incremental production cost for power delivered to each of the other areas. However, by decomposing the system, the size of the problem that could be considered would be greatly increased, It seems as though system decomposition will be necessary to solve the scheduling problem for large interconnected systems. It is clear that experimentation is necessary to determine the effect of different methods for decomposing generation systems on operating schedules,

APPEND ICES -92

APPENDIX I A DETAILED FLOW CHART -93

The following is a list of symbols used in the flow chart. The actual values assumed by these variables are required as input to the flow chart. (1) A is a matrix as defined in 4o5a). (2) B is a vector as defined in 4.5a). (3) Fl(W),...,Fz(W) are initial constraints for the restricted integer problem determined as discussed in 4.8, where z > 1 (4) W(O) = 1 = W*, where 1 is QN dimensional vector whose components are all ones. (5) A is a matrix as defined in 4.7d). (6) B is a vector as defined in 4.7d). (7) G = {(ik): i=l,...,N, kl,.,n} {(N+ll)} (8) Tq is the length of the q-th period in hours. (9) Q, N, n, r, 2 are constants as defined in the list of symbols. (10) D1, D2, D3, W are vectors as defined in the list of symbols. (11) {pt q} is a set whose elements are probabilities as defined in the list of symbols. (12) qN+ 1 = h, where h is defined as in the list of symbols. (13) J = {0}, J' = 0, G' = ~, k=O, t=l, v=l, K = QN, and cost (t) =, t=l,..., a The following is a detailed flow chart of the proposed algorithmic procedure. The various portions of this flow chart are identified with their corresponding parts in the descriptive flow chart.

-95Start Initial Input Calculate y(O) - Al - B To 1 For a = 1 until a = z Calculate Fa(W(O)) Calculate M(W(O) ) = To 2 For a = 1 until = z / Calculate m(k+l)

-96__ ______ o 3 or a==1Set k=k+l For a:: 1 until a = Q F -Z~~~J'i Yes= "~- (h ~Y es~ Is yk = 1 = Calculate Set t ti + 2 I M(W(t)) No IF (W(t ) ) (t-) ~Is yt 2 EJ? - M(W S Calculate W(t) = W(t-2k) -aEk+1 3 No M(W(t)) Calculate o 4 Fa (W(t))

-97Calculate F(W(t)) raxa F (W(t)) Is F(W(t)) < M(W(t-N)3t M(w(t-1)) yes M(W(t)) "I F(w(t)) w* _ w(t) Set t = t + 1 Yes Is k + 1 No To 7 For all D 3 \ E J-J' No Is Fc,(W(P)) -m6 k+l) < M(W(t))? Yes Is a z? } (6

-987 $ E J - (k+l) No Is c >0? t To 10 For all I, (Is y - h > O? P Set cl = CY + 1 Is a> Q 7 No Yes Set -1 = M(Wot-1)) Set

-99r_ Ta To 1! 2For i =1 to i - N To 11 For q 1 To q = Q Set s Wq- wq1 1 _ 1 = I i i i Yl~i ) C No q = ~ 1 YWv i Set yq = 0!,i yj y* =y* v v + TqkiWi qI

-100To 13 For q - 1 u|lntil. q = Q To 13 For t - 1 unti t -- Set b --- btq - mq(W) Calculate m in {gr, s} - gi,k (r,s)EG - G' Set Cost(t) = Cost(t) Is Mi k wi > b? S tb,kSktq No l I | Set | [ -| Calclate i1,k,1,tq Mik WI Ccpt Cost (t) = Cost (t) Cost (t) + gkSi klt, T Cost (t) (C 1 I iq Cost (t) sl~~ b=01O~~0

-101Calculate gr s = max {g,ki' ( i,k).ea} Set q Y~,t, L) = grs To 15 For i - 1 until i = N To 15 For k 1 to k =n s~ ~ Set 2,l,t, i,k No gr,s' gi,k Set Yl,t,i,k = 0 To 15 For J = r to j = 1 Set 2,J,t,i,k (Y~, J,t, i,k)(Pt,q) Set yq = 2,J,t,1,0 (Y2 1sit. 0(P.1 ) m

-102Set Yq 1, t, N+, 11 = NO Igr~s. g N+1,1 Set Yq 2,1, t, N+I, 1 To 18 For,j = r until j - 1/ F L Set Y, J,, N+l 1 No se Calculate | I I +T k Ii Start

-103Start -_ Set Set J={ fo} Z = k=O W = W(O) V = V +10 Calculate v v + Y(O)=Al) ) Calculate Calculate M(W(O)) max{F1(W(O)),...,F (W(O)) Calculate (k+l) mz ----— ~t InI St e

-104Cal culate w(t) = w(t-2k) Calculate F.(W(t)) Ca I cul ate F(W(t))

-105Set ca =a+ 1 Is a > z? No Yes 27 E =1 I s ha' — > 0? "Is >? + Ay~~~es ~-No For all B j J No Is y ba(k+l) >_~ N E? Set a =pa + 1 t t + i y = M(W(tl )) v~, 8

APPENDIX II CALCULATIONS FOR THE EXAMPLE -106

-107The details of the first two iterations of the algorithmic procedure for the numerical example are presented in this appendix. ) ( 8 ce= 1 = z Fl(W(O)) = 290 M(W(0)) = 290 ml = 205 x= 1 hl = O = 1 + 1=2 =Q 2 V1 Is 1 < 21? Yes. Is 1 - 2X = OEJ? Yes. (l) y(o) _ (120) = (8o) Is y(l) > 0? Yes. J = Ju{1} W = (0,11,1,1) c(= 1 = z F,(W(1)) = F1(W(O)) - c1 = 290 - 85 = 205 F(W (1) = 205 Is 205 < 290? Yes. M(W(1)) = 205

-108T W = (oi~1li) Is k + 1 - 4? No. Is F1(W(O)) - 205 <20 5? Yes. Is F1(W )) - 205 < 205? Yes, a =a+ 1 = 2 Is 2 > 1? Yes. (= 1 Is hi > 0? No. c a c+ 1=2 Is 2 > 2? No. 1 Is h2 > 0? No. a= + 1 3 Is 3 > 2? Yes, t t + 1 = 2 Is 2 <2? No. k=k+ 1 1 Is k= 4? No, J = J J, J1 = Is J = ~? No. Is k + 1 = 4? No. c= 1 = z 2 ml = 145 a= 1 h = O 1~

-109= + 1 = 2 Q h22 80 V2 Is t = 2 < 4? Yes. Is 2 - 2eJ? Yes. y(2) = y(o) - (80) = (o5) Is y(2) > o? Yes. J = Jv{2} T c = 1 = z F1(W()) = 230 F(W(2)) = 230 Is 230 < 205? No. M(W(2)) = 205 Is k + 1 = 4? No. a = 1 Is F1(W(0)) - 145 < 205? Yeso Is F1(W(1)) - 145 < 205? Yes. Is F1(W(2)) - 145 < 205? Yes. = + 1 =2 Is c > 1? Yes. a = 1 Is hl > 0? No. =c + 1 =2 Is 2 > 2? No. Is h2>0? Yes. (0) Is Y2 -80 > 0? Yes.

-110Is y(1) - 80 > 0? Yes, Is y(2) - 80 > 0? Yes. Cx=c+ 1 =3 Is 3 > 2? Yes. t = t+ 1 = 3 Is 3 < 22? Yes. Is 3 - 2 = 1lJ? Yes. y(3) = y(l) _ (80)= (865 Is y(3) > 0? No. M(W(3)) = 205 t = t+ 1 = 4 Is 4 < 22? No. k=k + 1= 2 Is k = 4? No. J =J- =J JI = Is J =.? No. Is k + 1 = 4? No. a= 1= z m3 = 60 Cx= 1 h(3) = 0 a= + 1 = 2 Q h(3) = 80 v3 Is 4 < 23? Yes. Is 4 - 4 = OeJ? Yes.

-111(4) = y(O) _ (100) = (1 5) Is y(4) > 0? No. M(W(4)) = 205 t = t+ 1 = 5 Is 5 < 23? Yes. Is 5 - 4 = eJ? Yes. Y(5) = y(l) - (100) = (-40) Is y(5) > 0? No. M(W(5)) = 205 t = t + 1 = 6 Is 6 < 23? Yes. Is 6 - 4 = 2cJ? Yes. (6) = y(2) - (12O) = (-v) Is y(6) ~0? No. M(W(6)) = 205 t =t + 1 7 Is 7 < 23? Yes. Is 7 - 4cJ? No. M(W(7)) = 205 t = t+ 1 =8 Is 8 < 23? No. Set k = k + 1 = 3 Is k = 4? No. J =J - J' = 0 Is J= 0? No.

-112Is k + 1 = 4? Yes. V4 Is 8 < 24? Yes. Is OcJ? Yes. y(8) - y(o) - (80) - (135) Is y(8) > 0? Yes. J = J {8} T T W(8) = W(O) - (0,0,0,1) = (1,1,1,0) a = 1 = z F1(W()) = 230 Is 230 < 205? No. M(W(8)) = 205 Is 4 = 4? Yes. t = t+ 1 = 9 Is 9 < 24? Yes. Is 9 - 8 = l1J? Yes. x(9) = y(1) - (8~) = (lo) Is y(9) > 0? Yes. J = Ju{9} W(9) = (0o,,1,o0) c = 1 = z FJ(W(9)) = 145 F(W(9)) = 145 Is 145 < 205? Yes. M(W(9)) = 145 T W = (0,1,1,0) Is k + 1 = 4? Yes.

-113t = t + 1 = 10 Is 10 < 24 Y? es. Is 10 - 8=2cJ? Yes. (10) y(2) - (8~) = (5~) Is y(10) > o? es T W(10) = (i,O,i,O) c.= 1 = z F (W (lo)) = 16o F(W(10)) = 160 Is 160 < 145? No. M(W(10)) = 145 Is 4 = 4? Yes. t =t + 1 = 11 Is 11 < 16? Yes. Is 11 - 8 = 3GJ? No. M(W(11)) = 145 t =t + 1 = 12 Is 12 < 24? Yes. Is 12 8 = 4cJ? No. M(W(12) ) 145 t = t + 1 = 13 Is 13 < 2? Yes. Is 13 - 8 = 5EJ? No. M(Wt =t + 1 = 145 t —t + 1= 14

-114Is 14 < 16? Yes. Is 14 - 8 = 6eJ? No. M(W(14)) = 145 t = t + 1 = 15 Is 15 < 24? Yes. Is 15 - 8 = 7eJ? No. M( (15)) = 145 t = t + 1 = 16 Is 16 < 24? No. k =k+ 1 =4 Is 4 = 4? Yes. M(w(l )) = 145 Is01 1 Is wt - w= 1? No. u1 = 0 y 1=0 1 2 1 2 2 * Is 1 - wl = 1? Yes. ul = 1, Y1,1 = 30, y1 = 115 1 0 1 * Is w2 - w2 = 1? No. u2 = 0 Y12=0, = 175 Is w2 - w = 1? No. u 2 = 0, = I 2s w 2- w = 1? No2. = 0 Y1 = 0 Y = 175 o 1 1 1 * Is w1 - w1 = 1? Yes. v1 = 1, Y1,3 = 1, = 190 q=1,Y 2 2 2 = 30 Is WIwi 1 No, V( = 0 >Y1y3, 0?l90 Is 1 1 1 = CoIS Wt wNo.s = 0, Y1 = 190 1 2 2 2 * Is w2 - 2 1? Yes. v2 = 1, Y14 10, y 200 q = 1, b= 50 - 20 = 30 min {gr,s (r,s)eG - G'} = gl1, =2'= {(1,1)} Is (20) (0) = 0 > 30? No. S1,1,1 = 0 Cost (1) = 0

-115b = 30 Is b = 0? No. min {gr s: (r,s)~G - G'} = g2,1 = 2.3 Gt {(1,1), (2,1)} Is 30Q1 - 30 > 30? No. S2 1,1 — 30 Cost (i) = o0 + 69 b = 30 - 30 = 0 Is b = 0? Yes. Cost (1) - 69 l -= 69 + 200 = 269 Cost (1) - 0 g2, 1 = max {gi,k: (i,k)EG'} = 2.3 2g 10 = g2 1 2.3 i = 1i k = 1 Is (1 1)G' 7: Yes o k+ 1 = 2 = n Is (1,2)eG'? No. 1 - 0 i i + 1 = 2 = N k = 1 Is (2,1)EG'? Yes. y21 =23 - 23 = 0 k =k+ 1= 2 Is (2,2)CG,' Noo =O 2,2,2

-116G' =q = q+ 1 = 2 =Q b = 100 - 30 = 70 min {grs: (r,s)EG - G1} = 2o0 = gll G' = {(1,1)} Is 20.1 > 70? No. S1 1 2 = 20 Cost (1) = (2.)(20) = 40 b = 70 - 20 = 50 Is b = 0? No. min {gr, s: (r,s)eG - G'} = g2 = g2,1 2.3 G' = {(l,l), (2,1)} Is (30)(0) = 0 > 50? No. Set S212 = 0 2, 1,2 Cost (1) = 40 + 0 = 40 b = 50 - 0 = 50 Is b = 0? No. min {gr, s: (r, s)G - G'} = gl,2 2.8 Go = {(191), (2,1), (1,2)} Is (70)(1) = 70 > 50? Yes. S1,2,2 = 50 Cost (1) = 40 + (2.8)(50) = 180 yl = 269 + 180 = 449 Cost (1) = 0 2gr s= 2.8 y2,1,0= 2.8

-117i 1, k = 1 Is (1,1)eG'? Yes. 2 2.8 - 2.0 =.8 Y2 1 1 = 8 k = k+ 1 = 2 = n Is (1,2)eG'? Yes. 2 - 2.872o8 = O Y2,91,2 - i = i + 1 = 2, k = 1 Is (2,1)EG'? Yes. Y2 2 1 = 2.8 - 2.3 =.5 k= k+ 1=2 Is (2,2)eG'? No. Y2 2 = 02 Set G' 0 Is 449 = 145? No. 1 1 2 2 F2(W) = 410 - 35w1 - 24w2+ - 2w J = {o} k- 0 t 1 W W(O) g' 0 v =v + 1 = 2 z = z + 1= 2 vo y(o) = (135) F2(W(O)) = 393 M(W(0)) = 393 m2 = 39

-118V1 Is 1 < 21? Yes. Is 1 - 1 = 0 eJ? Yes. (1) _ y(o) (120) = (15) Is y(l) 0? Yes, J = Ju({} T w(1) = (0,1,1,1) F2(W ()) = 428 F(W(j)) ) 428 Is 428 < 393? No. M(W(1)) = 393 Is 1 = 4? No. cx= 1 Is F1(W(O)) - ml = 290 - 2Q5 < 393? Yes, Is Fl(W(l)) - ml = 205 - 205 < 393? Yes. a=ca+ 1 =2 Is >2? No. Is F2(W(0)) - 39 = 393 - 39 < 393? Yes. Is F2(W(1)) - 39 = 428 - 39 < 393? Yes. a = + 1 = 3 Is 3 > 2? Yes. a-= 1 Is hl > 0? No. ac=a+ 1 = 2 Is 2 >2? No. Is h4 > O? No. a=c+ 1 = 3

-119Is 3 > 2? Yes. t =t + 1 = 2 Is 2 < 21? No. k =k+ 1 = 1 Is 1 = 4? No. J = J - J Ji = ~ Is J = 0? No. Is 2= 4? No. m2 = 15 V2 Is 2 < 22? Yes. Is 2 - 21 = OEJ? Yes. y(2) (55) 80 Is y(2) > 0? Yes. J = J f{2} W() = (1,0,1,1) F2(W(2)) - 369 F(W(2)) = 369 Is 369 < 393? Yes. M(W() = 369 T W* = (1,0o1,1) Is 2 = 4? No. a= 1 Is F1(W(O)) - 145 < 369? Yes. Is Fi(W(1)) - 145 < 369? Yes. Is F1(W(2)) - 145 < 369? Yes.

-120a= a+ 1 = 2 Is 2 > 2? No. Is F2(W(0)) _ m2 = 393 - 15 = 378 < 369? No. Is F2(W(1)) - m2 = 428 - 15 = 413 < 369? No. leJ' Is F2(W(2)) - m2 = 369 - 15 < 369? Yes. c= + 1 =3 Is 3 > 2? Yes. Is h2 > 0? No. a=a-+ 1 =2 Is 2 —> 2? No. Is h > 0? Yes. Is y(2) -80 > 0? Yes., = cz+ 1 = 3. Is 3 > 2? Yes. t= t+ 1= 3 Is 3 < 22? Yes. Is 3 - 2 = c1J? Yes. y(3) (-65) Is y(3) > 0? No. M(W(3)) = 369 t =t+ 1=4 Is 4 < 2? No. k=k+ 1= 2

-121Is 2= 4? No. J = J J = {2} J = 0 Is J = 0? No. Is 3 = 4? No. m3 = - 21 V3 Is 4 < 23? Yes. Is 4 - 4 = OcJ? No. M(W(4)) = 369 t = t+ 1 = 5 Is 5 < 8? Yes. Is 5 - 4 = 1lJ? No. M(W(5)) = 369 t = t+ 1= 6 Is 6 < 23? Yes. Is 6 - 22 2eJ? Yes. y(6) (_5) Is y(6) >0? No. M(W(6)) = 369 t = t + 1=7 Is 7 < 23? Yes. 2 Is 7 - 2 = 3eJ? No. M(W?(7) - 369 t =t+ 1 =8 Is 8 < 23? No. k=k+ 1= 3

-122Is 3 = 4? No. J = J - J' Is J =? No. Is 3 + 1 = 4? Yes. V4 Is 8 < 24? Yes. Is 8 - 23eJ? No. M(W(8)) = 369 t = t+ 1 = 9 Is 9 < 2? Yes. Is 9 - 23 = leJ? No. M(W(9)) = 369 t = t + 1 = 10 Is 10 < 24? Yes. Is 10 - 23 = 2eJ? Yes. y(10) = (55) Is y(10) > 0? Yes. J = Ju {10} W(10) = (1,0,1,0) F2(W(10)) = 390 F(W(10)) = 390 Is 390 < 369? No. M(W(10 ) = 369 Is 4 —-= 4? Yes. t = t + 1 = 11 Is 11 < 24? Yes.

-123Is 11 - 23 J? No. M(W(11)) = 369 t = t + 1 = 12 Is 12 < 24? Yes. Is 12 - 23 = 4eJ? No. M(W(12)) = 369 t = t + 1 = 13 Is 13 < 24? Yes. Is 13 - 8 = 5eJ? No. M(W(13)) = 369 t = t + 1= 14 Is 14 < 24? Yes. Is 14 - 23 = 6eJ? No. M(W(14)) = 369 t = t + 1 = 15 Is 15 < 24? Yes. Is 15 - 8-7eJ? No. M(W(15)) = 369 t = t + 1= 16 Is 16 < 16? No. k=k+ 1 4 Is 4 = 4 - Yes. 2 *= 369 1 0 1 1 y Is Wi - W 1? No. u1 = 0 1 = 0 Y2 = 85 Is 1 wl = 1? No. u=2 2 _17 Is w - w0 = 1? No. u = 0, y1 = 0 Y2 = 170 w 2 2.,2

-1242 1 2 2 * Is w2 -w2= 1? Yes. u2 = 1 250 2 -NY, 2 = 20, yl) 2 = Y2 = 250 Is w - w = 1? No. v = 250 v 1 1 =0Y Y1,3 =!Oy Y2=25 1 2 2 2 * Is w1 - w1 = 1? No. v1 = 0, Y1,3 = Y2 = 250 I os 0 1 1 Ye 1 1 1 = Is w2 - w2 - 1? Yes. v2 = 1,,Y14 = 10, Y2 = 260 Is w2 - w2 = 1? No. v2 = 0, Y4 2 = 260 = = Yi4= 0, Y2 = 260 q = 1 b = 50 - 30 = 20 min {grs: (r,s)EG - G'} = gl, 1 = 2 G' = {(1,1)} Is 20 > 20? No. S1,1 = 20 Cost (1) = (2) (20) = 40 b = 20 - 20 = 0 Is b = 0? Yes. Y2 = 260 + 40 = 300 Cost (1) = 0 g!;, = max {gi k: (i,k)eG'} 1 Y2, 1, 0 = 2.0 i=1, k= 1 Is (1,1)eG'? Yes. 1 = (2.) -(2.) = k=k = k + 1= 2 Is (1,2)CG'? No. Y2,1,2 i = i+ 1, k = 1

-125Is (2,1e)G'? No. = 0 Y2 2, 1 k = k+ 1 = 2 Is (2,2)~G'? No. 1 =0 Set G' = q=l q+ 1 2 b = 50 min {gr, s ~ (r,s)EG - G') = 2.0 G' = {(1,1)} Is 20 > 50? No. S 1,12 = 20 Cost (1) = 40 b = 50 - 20 = 30 Is b = 0? No. min {gr s: (r, s)G - G' = g2,1 = 23 G = {(i,1), (2,1)} Is 30 > 30? No. S2, 1,2 = 30 Cost (1) = 40 + 69 = 109 b = 0 Is b = 0? Yes. Y2 = 300 + 109 = 409 Cost (1) = 0 max {gi k (i,k)G'} = g2, 1 2.3 2 = 2.3 Y2,l1O

-126i = 1, k= 1 Is (1,1)cG'? Yes. Y2,1,1 =.3 k=k+ 1 = 2 Is (1,2)cG'? No. Y2,1,2 = 0 i - i+ 1 = 2, k = 1 Is (2,1)eG'? Yes. y2, = 2.3 - 2.3 = O k= k+ 1= 2 Is (2,2)eG'? No. y2 y2,2,2 0 GI - 0 Is Y2 = Y* (369 = 409)? No. )1 L 2 2 F3(W) = 340 + 25w1 10w2 + low1 + 34w2

BIBLIOGRAPHY 1. AIEE Committee Report, "Application of Probability Methods to Generating Capacity Problems and References," AIEE Transactions, part III, Vol. 79 (1960), pp. 1165-1182. 2. Arnoff, E. L. and Chambers, J, C., "Operations Research Determination of Generation Reserves," AIEE Transactions, part III, Vol. 76 (1957), pp. 316-328. 3, Baldwin, C. J., Dale, K. M. and Dittrich, R. F., "A Study of the Economic Shutdown of Generating Units in Daily Dispatch," AIEE Transactions, part III-B, Vol. 78 (1959), pp. 1272-12840 4. Balinski, M. L., "Integer Programming- Methods, Uses, Computation," Management Science, Vol. 12 (1965), pp. 253-313. 5. Benders, J. F., "Partitioning Procedures for Solving Mixed-Variables Programming Problems," Numerische Mathematik, Vol. 4 (1962), ppo 238-252. 6., Catchpole, A. R. and Kuiken, C., "Discrete Variables Optimization Problems," RAND Symposium on Mathematical Programming, March 16.20, 1959. 7. Calabrese, G., "Generating Reserve Capacity Determined by the Probability Method," AIEE Transactions, Vol. 66 (1947), pp. 1439-1450o 8. Dakin, R. J., "Application of Mathematical Programming Techniques to Cost Optimization in Power Generating Systems," Technical Report No. 19, Basser Computing Department, School of Physics, The University of Sydney, December 1961. 9. Dantzig, G. B., "Linear Programming Under Uncertainty," Management Science, Vol. 1 (1955), ppo 197-206. 10., and Wolfe, P., "The Decomposition Algorithm for Linear Programs," Econometrica, Volo 29 (1961), pp. 767-778. 11., Linear Programming and Extensions, Princeton University Press, Princeton, No Jo, 1963. 12. Despotovic, S., "A Quick Method for Developing a Transmission Loss Formula," AIEE Transactions, part III, Vol. 79 (1960), ppo 707-711. 13. DeSalvo, C. A. and Dale, K. M., "Generating Unit Selection by Dynamic Programming," Report No. 60-175, Electric Utility Engineering Department, Westinghouse Electric Company, East Pittsburgh, Pa., 1960. -127

-12814. Early, E. D., Watson, R. E. and Smith, G. L., "A General Transmission Loss Equation," AIEE Transactions, part III, Vol. 74 (1955), PP. 510-520. 15. Federal Power Commission, "Statistics of Electric Utilities in the United States - Class A and B Privately Owned Companies," Washington, D. C., 1937-1955. 16. Ferguson, A. R. and Dantzig, G. B., "The Allocation of Aircraft to Routes - An Example of Linear Programming Under Uncertain Demand," Management Science, Vol. 3 (1956), pp. 45-73. 17. Freemann, R. J., Computational Experience with the Balas Integer Programming Algorithm, the RAND Corporation, P-3241, October 1965. 18. Gaver, D. P., Montmeat, F. E. and Patton, A. D., "Power System Reliability I - Measures of Reliability and Methods of Calculation," IEEE Transactions, part III, Vol. 83 (1964), pp. 727-737. 19.,, and, "Power System Reliability iI - Applications and a Computer Program," IEEE Transactions, part III, Vol. 84 (1965), pp. 636-643. 20. Garver, L. L., "Power Generation Scheduling by Integer Programming - Development of Theory," AIEE Transactions, part III, Vol. 81 (1962), ppo 730-735. 21. Geoffrion, A. M., Integer Programming by Implicit Enumeration and Balas' Method, The RAND Corporation, RM-4783-PR, February 1966. 22. George, E. E., "Intrasystem Transmission Losses," AIEE Transactions, Vol. 62 (1943), pp. 153e158. 23., "A New Method of Making Transmission Loss Formulas from Digital Power Flow Studies," AIEE Transactions, part III, Vol. 78 (1959), pp. 1567-1573. 24. Glimm, A. F., Habermann, R. Jr., Kirchmayer, L. K. and Stagg, G. W., "Loss Formulas Made Easy," AIEE Transactions, part III, Vol. 72 (1953), pp. 730-737. 25. Gomory, R. E., "All-Integer Programming Algorithm," Research Report RC-189, IBM Research Center, January 29, 1960. 26. _, An Algorithm for the Mixed Integer Problem, The RAND Corporation, RM-2597, July 1960. 27. Hadley, G., Linear Programming, Addison-Wesley, Reading, Mass., 1962. 28., Nonlinear and Dynamic Programming, Addison-Wesley, Reading, Mass., 1964.

-12929. Hayward, A. P., "Economic Scheduling of Generation by Valve Points," AIEE Transactions, part III, Vol. 80 (1961), ppo 963.965o 30. Kerr, R. H., Fontana, A. Jo Jr., Scheidt, J. L. and Wiley, J. Ko, "Unit Commitment," IEEE Transactions, part III, Vol. 85 (1966), pp. 417-421. 31. Kirchmayer, L. K.o Economic Operation of Power Systems, John Wiley and Sons, Inc., New York, N. Y.o 195o8. 32., Economic Control of Interconnected Systems, John Wiley and Sons, Inc., New York, No Y., 19=9. 33. 9 and Stagg, G. W., "Analysis of Total and Incremental Losses in Transmission Systems," AIEE Transactions, part I, Vol. 70 (1951), pp. 1197-1205. 34., and, "Evaluation of Methods of Coordinating Incremental Fuel Costs and Incremental Transmission Losses," AIEE Transactions, part III, Volo 71 (1952), pp. 513-521. 35. Lowery, P. G., "Generating Unit Commitment by Dynamic Programming," IEEE Transactions, part III, Volo 85 (1966), pp. 422-426. 36. Madansky, A., "Inequalities for Stochastic Linear Programming Problems," Management Science, Vol. 6 (1960), pp. 197-204. 37. Osterle, W. H., Geiser, J., DaleK. M. and DeSalvo, CO A., "Computer Selection of Generating Units to be Operated, Part IIo By Dynamic Programming on a Large Computer," AIEE-Conference'Paper CP 60-1399, PICA Conference 1960. 38. Steinberg, M. J., "Incremental Maintenance Costs of Steam-Electric Generating Stations," AIEE Transactions, part III, Vol. 76 (1957), pp. 1251.1255. 39.. and Smith, T. H., Economic Loading of Power Plants and Electric Systems, John Wiley and Sons, Inc., New York, N.o Yo 19430 40o Stewart, H. G,, "Probability Study Sets Economical Reserves for Uniform Reliability," Electric Light and Power, December 1965, pp. 91-95. 41. Szendy, Charles, "Economical Tie-Line Capacity for an Interconnected System," IEEE Transactions, part III, Volo 83 (1964), pp. 721-737. 42. Watchorn, C. W., "A Review of Some Basic Characteristics of Probability Methods as Related to Power System Problems," IEEE Transactions, part III, Volo 83 (1964), ppo 737-743.

UNIVERSITY OF MICHIGAN 3 901111111 034831 111 1111111112 111 3 9015 03483 1274