Risk management system for electric utilities6021402Abstract A computer implemented risk-management system schedules the generating units of an electric utility while taking into consideration power trading with other utilities and the stochastic load on the utility system. The system provides the user with a tool that generates multiple load forecasts and allows the user to vary the fuel price between the different scenarios and the different periods of the planning horizon. The tool allows the user to model accurately the uncertain trading transactions and the changing fuel prices to meet the electric demand of customers at a minimal cost while making the maximum profit possible from power trading. The tool also allows the user to apply any set of linear constraints to fuels. A mathematical model of the problem is solved to provide the status of each generator at each time period of the planning horizon under each given scenario, the load on each generator during each period in which it is operating, an optimal fuel mix for each generating unit, and the prices for purchasing and selling power in the periods of the planning horizon. Claims Having thus described my invention, what I claim as new and desire to secure by Letters Patent is as follows: Description BACKGROUND OF THE INVENTION
TABLE 1
______________________________________
Year 1 Year 2 Year 3
Return Stocks Bonds Stocks
Bonds Stocks
Bonds
______________________________________
Scenario 1
10% 5% 8% 7% 4% 12%
Scenario 2
10% 5% 8% 7% 3% 12%
Scenario 3
10% 5% 7% 12% 6% 5%
Scenario 4
10% 5% 8% 8% 12% 3%
Scenario 5
6% 9% 8% 8% 12% 5%
______________________________________
To maximize the expected return, our investor must allocate the $1,000 between stocks and bonds. To do so, he or she uses an (stochastic) optimization to develop a decision tree for the future. The decision tree indicates where to invest in the beginning of the first year and how to reallocate the funds by the end of each year. The reallocation is a function of the return values observed during a year. For example, if we observe a return of 10% on stocks and 5% on bonds in the first year, then we know that Scenario 5 is out of the picture and that the future decisions are based on scenario 1, 2, 3, and 4. At this point (end of year 1), the decisions made for scenarios 1, 2, 3, and 4 must be the same. The fact that we must adopt similar decisions for these four scenarios is called "non-anticipativity" and the corresponding decisions are said to be "bundled". Let us take this example one step further and assume that we observe return rates of 8% and 7% in the second year. At the end of year 2, we know that the only two possible future scenarios are Scenario 1 and Scenario 2. The decision tree provides an investment decision for these two scenarios that is independent of the outcome of Year 3. Here again, we say that scenarios 1 and 2 are bundled at the end of Year 2. The process described is implemented on a computer system for scheduling electric-power generators of a utility company. Given (1) a set of load forecasts on the electric system, (2) a prediction of trading transactions that may take place within the next 168 hours, (3) a description of the physical properties of the generating units and the expected spot market prices for electric power, and (4) fuel prices associated with load forecasts, our process provides for each scenario (1) generation levels, (2) fuel usage, and (3) prices at which power can be traded. This information is then used by decision makers and plant managers to run the electric system reliably. Our tool provides multiple decisions, e.g., generation, fuel consumption, and power prices, for each hour of the planning horizon. Each of these decisions is optimal under certain circumstances. The system administrator observes the market, then looks up the appropriate decision from a table provided by our tool. What distinguishes the system of this invention from existing ones is the incorporation of fuel prices into the model and allowing these prices to vary. The invention also allows the user to impose constraints on fuel consumption. Incorporating fuel into the model requires iterating between a stochastic unit-commitment solver and a stochastic linear-programming model. The stochastic linear program allocates fuel optimally between the different generators of the system. The cost function of each unit is then constructed and a stochastic unit commitment is solved. The process is repeated until a convergence is reached. The present invention provides a utility with a tool that promotes a better understanding of the relationship between the electric-power and fuel markets allowing a utility to hedge against uncertainty in both markets. This is done by modeling the customers' varying demand, the uncertain electric-power market, the generating units, the availability of different fuel, and the fluctuating fuel price in the open commodity exchange. Here is a more accurate description of the input of this process. 1. The forecasted electric load on the system of the utility: This is the load generated by customers who fall within the utility's territory. Given load patterns observed in previous years and given load values for the past week, utilities use the weather forecast (temperature, humidity, sky conditions, and wind) to predict the load for the next week or 168 hours. All utilities have advanced tools and employ experienced planners to perform the forecasting task. Due to uncertainty in load, the user is allowed to provide a set of forecasts to better approximate the load distribution. The user also assigns a weight to each forecast. It is assumed that the load forecasts and their weights are given in the form of a computer file, e.g., a spreadsheet, on the hard disk of a computer system. 2. The physical and operational properties (specifications) of the generating units: Each utility maintains accurate information regarding the specifications of its generators. The description of each generating unit can be summarized using ten numbers: minimum operating capacity, maximum operating capacity, minimum up-time, minimum down-time, start-up heat requirement, shut-down cost, current status, and the heat-input versus power-output curve which requires three parameters. Again, it is assumed that this information is provided on the hard disk in the form of a table or a spreadsheet. 3. Fuel cost and its availability: To translate the curves of FIGS. 1A and 1B into cost, it is assumed the knowledge of the cost per BTU for each fuel used in generation (see FIGS. 1A and 1B and FIGS. 6A and 6B). This information is needed to compute the start-up cost and the operating cost of a generator. Our system permits the user to specify different cost/BTU for a fuel for different hours over the course of the week and for different load scenarios. This allows the user to change the prices of fuel to reflect his or her view of the spot-market. The user can also provide upper and lower bounds (and any other linear constraints) on the amounts of fuel that can be used at each hour or day. It is assumed that fuel information is stored on a computer disk and is accessible by our system. The linear constraints are also assumed to be stored on the disk in a tabular form or in the standard Mathematical Programming System (MPS) format described in IBM document number 4. The projected power-trading transactions in the market: A view of the market and what type of trading transactions may take place must be supplied by the user. For example, the user may indicate that there might be an offer to "buy 200 MWH at $20/MWH tomorrow on-peak with a probability of 10%" or a market to "sell 100 MWH at $25/MWH in two days off-peak with a probability of 25%." It is assumed that this information will be supplied in a computer file that is stored on the hard disk. Given access to the previous data, our tool produces a table (spreadsheet) that indicates the load (MWH) on each unit at each hour of the week. This table is passed on to the administrators of each generator to be used as an operating schedule for the coming week. It also provides prices at which power is expected to be traded. As a result of the calculations, each plant manager is given precisely what type of fuel to use and how much to burn at each hour of the week. The tool can be used to perform a "what-if" analysis which helps the user in developing a better understanding of the relationship between the power market and his/her electric system; and in better quantifying the risk involved in buying and selling power in the periods to come. The existing tools for scheduling electric-power systems use a single load forecast when searching for optimal decisions. Furthermore, they do not consider power trading in the model. In other words, existing tools assume that future loads are known in advance which results in conservative schedules. What distinguishes our tool is that it allows the user to incorporate risk, through predictions of the load and fuel prices, and uses these predictions to create optimal schedules. Our tool uses hedging strategies to produce robust schedules that minimize cost and manage risk efficiently. The idea of using multiple scenarios to approximate uncertainties in the load forecast was suggested in A. Carpentier, G. Cohen, J. C. Culioli, and A. Renaud, "Stochastic optimization of unit commitment: A new decomposition framework," IEEE Transactions on Power Systems, 11(2):1067-1073, May 1996, and in Takriti, Birge, and Long, "A stochastic model for the unit commitment problem," IEEE Transactions on Power Systems, 11(3):1497-1508, August 1996. However, both models assume that fuel prices are known in advance and are fixed over the planning horizon. FIG. 4 is a flow diagram illustrating the stochastic model of Carpentier et al. Load forecasts and generator properties are input in function block 41. Then, using Lagrangian relaxation, the problem is decomposed into single-generator subproblems in function block 42. Lagrange multipliers are initialized in function block 43 prior to entering a processing loop. In the processing loop, the stochastic dynamic program of each generator is solved in function block 44 and, after each solution, a test is made in decision block 45 to determine if the current solution is optimal. If not, the Lagrange multipliers are updated in function block 46, and the process loops back to function block 44. When an optimal solution is obtained, the generation levels under different scenarios are output at function block 47. Carpentier et al. do not discuss issues related to the practicality of their model and do not report computing requirements and execution-time for their technique. The flow diagram for the stochastic model of Takriti et al. is shown in FIG. 5. The load forecasts and generator properties are input in function block 50. Lagrangian relaxation is used in function block 51 to relax the bundle of constraints. In this case, each scenario has its own problem. Progressive hedging penalties are initialized in function block 52 before entering the processing loop. In the processing loop, Lagrangian relaxation is used in function block 53 to decompose the problem into single-generator subproblems. Then, a subprocessing loop is entered beginning with initialization of the Lagrange multipliers in function block 54. The deterministic dynamic program from each generator is solved in function block and, after each solution, a test is made in decision block 56 to determine if the current solution is optimal. If not, the Lagrange multipliers are updated in function block 57 and the process loops back to function block 55. When the current solution is optimal as determined in function block 56, a further test is made in decision block 58 to determine if bundle constraints are satisfied. If not, the progressive hedging penalties are updated in function block 59, and the process loops back to function block 53. When the bundle constraints are satisfied, the generation levels under different scenarios are output at function block 60. Takriti et al. use a parallel machine with thirty-two nodes to handle the large size of their model. Given that a comprehensive model has a significantly larger size than the examples of Takriti et al. and that a parallel platform is very costly, this technique may be hard to apply. The system according to the present invention builds on Carpentier et al. and Takriti et al. but uses different mathematical techniques to accelerate the process of solving the model and to make it more general. To be more specific, the present invention implements: 1. A storage scheme for the scenario tree and bundle constraints: The result is significant reduction in calculations and storage requirements. 2. A new updating mechanism for the Lagrange multipliers of the stochastic unit commitment problem: the bundle trust-region method is used. 3. A clear and concise treatment of power trading. 4. A flexible operating range: the operating range is allowed to be a function of time which allows incorporating maintenance into the unit commitment. Generators are permitted to have a varying capacity when they are turned on (ramping). The resulting system is a practical tool that runs efficiently on any computer platform and under any operating system, including parallel computers. Parallelism reduces the system's execution time (approximately) proportionally to the number of available processors. Given that the market profile may change quickly, solving the model in parallel permits the system administrator to respond efficiently to the dynamic market. System's Input First, there is discussed the input parameters required for the model of the present invention. The duration of the planning horizon is how far ahead we want to look so that our present decisions are close to optimal. A planning horizon varies from three to seven days depending on the utility. The planning horizon is divided into periods. Usually, each period is one hour. Our model assumes that the number of periods, T, is supplied. Second, planners must provide load forecasts (MWH) for each period of the planning horizon for the region covered by the Utility. Presently, all utilities employ trained individuals to produce reasonable forecasts. There are also special forecasting packages that are widely used by utilities. The forecast is a function of the weather in the region of interest, time of day, day of year, and many other factors. Methods for developing load forecasts are not discussed here. It is assumed that a set of S load forecasts is provided. Each forecast (scenario) provides the total load, d.sub.t.sup.s, on the system at each time period, t=1, . . . , T, of the planning horizon. The superscript s indicates that a variable or a parameter is associated with forecast s. For example, d.sub.2.sup.4 is the total load on the system at time period 2 under scenario 4. A weight, p.sub.s, is associated with each scenario, s, to approximate the likelihood of its occurrence in the future. If p.sub.s >p.sub.s', then we are more likely to observe scenario s than to observe scenario s'. If p.sub.s =0, then scenario s cannot occur, and we can drop it out of our scenario set. Note that ##EQU1## represents the probability that scenario s occurs. Table 2 gives an example of load forecasts.
TABLE 2
______________________________________
Load on our Utility, d.sub.t.sup.s
p.sub.s t = 1 2 3 4 5
______________________________________
s = 1 0.35 10495 11135 11653 11829 11995
s = 2 0.56 10846 10982 11563 11674 12039
s = 3 0.09 11138 11956 12310 12388 12583
______________________________________
To reflect uncertainty in fuel prices, the user is allowed to provide different prices for a fuel, j, over the different points in time, t, and under the different load scenarios, s. The price of fuel j is denoted by ##EQU2## Given that the goal is to minimize the expected cost of running the electric system, the expected value of fuel cost over scenarios that belong to the same bundle can be used. That is, if .OMEGA. is the set of scenarios that satisfy the condition d.sub.t.sub.s =d.sub.t.sub.s' for any s and s' in .OMEGA. and for t=1, . . . , .tau., then the expected value E.sub.s.epsilon..OMEGA. (h.sub.t,j.sup.s) can be used as the cost of fuel j at time t=1, . . . , .tau. under the scenarios of .OMEGA.. Third, the model requires a complete description of the generating units of the utility. By a "complete description", what is meant is providing the total number, N, of generators in our system and the operational properties of each generator. That is, for each generator, i .epsilon. {1, . . . ,N}, the user must provide: (a) Operational Range: This is represented by the minimum power, g.sub.i,t, and the maximum power, G.sub.i,t, that can be produced by this generator during period t. Clearly, g.sub.i,t and G.sub.i,t must satisfy the constraint 0.ltoreq.g.sub.i,t .ltoreq.G.sub.i,t. When it is on (during period t), a generator, i, can produce any amount of power in the range [g.sub.i,t, G.sub.i,t ]. Note that the operational range depends on the time t. Although, the minimum and maximum operating capacity for a generator are not affected by time, t is incorporated to allow considering maintenance in the model. For example, if a unit i is scheduled for maintenance over a certain time range, then its capacity over this range can be reduced or made zero (it is not always necessary to shut down a unit during maintenance). In some cases, a unit cannot operate at its maximum capacity immediately after it is started. For example, when the load reaches g.sub.i,t (or some other level), it must be kept at that level for a few periods (usually two hours). Such limits are applied directly to the states of the dynamic program of each generating unit. Note that we can allow g.sub.i,t and G.sub.i,t to vary under different scenarios in the model. However, there is no need for such flexibility in practice. (b) Heat-input versus Power-output Curve: This is the curve that represents the relationship between the heat in the burner and electric-power output (see FIGS. 1A and 1B). This curve is denoted by f.sub.i.sup.h where i .epsilon. {1, . . . , N}. In other words, to generate x units of power (MWH), the burning fuel must provide f.sub.i.sup.h (x) thermal units (BTU). The function f.sub.i.sup.h is quadratic, convex, and increasing. It can be fully described by providing three parameters: a.sub.i, b.sub.i, and c.sub.i. That is, the heat required to produce x units of power for one period using generator i is a.sub.i x.sup.2 +b.sub.i x+c.sub.i. To guarantee that f.sub.i.sup.h is convex and increasing, the parameters a.sub.i, b.sub.i and c.sub.i must satisfy a.sub.i >0, -0.5 b.sub.i /a.sub.i .ltoreq.g.sub.i,t if a.sub.i >0, b.sub.i .gtoreq.0 if a.sub.i 0, and a.sub.i g.sup.2.sub.i,t +b.sub.i g.sub.i,t +c.sub.i .gtoreq.0. The cost function of generating electricity on generator i is denoted by f.sub.i,t.sup.s. Although f.sub.i.sup.h is a quadratic function, the function f.sub.i,t.sup.s may not be quadratic. The reason is that when the upper capacity, G.sub.i,L, is approached, a generator usually requires a more combustible fuel. Some generators, for example, require the use of natural gas in addition to coal when the load exceeds 80% of G.sub.i,t. As a result, the generating cost curve must combine the cost curves of both fuels. FIGS. 6A and 6B show an example of a cost function f.sub.i,t.sup.s. The generation levels at which we switch fuel is denoted by G.sub.i,t.sup.k, k=1, . . . , K, where K+1 is the total number of different fuels (excluding the start-up fuel) used on i. The values of G.sub.i,t.sup.k are assumed to be known for each generator. The cost function f.sub.i,t.sup.s can then be constructed from the quadratic cost functions of the individual fuels. Given that we switch from a cheap fuel to a more expensive one as we increase the load, the function f.sub.i,t.sup.s is convex which makes the task of minimizing it a simple one. From here on, it is assumed that the cost function, f.sub.i,t.sup.s (x) is convex and increasing and that f.sub.i,t.sup.s (g.sub.i,t)>0. It is our experience that cost functions faced in power generation fall within this class of functions. Hence, our assumption does not pose any limitations on the applicability of this technique. It is also assumed that we have a tool for finding the minimum of f.sub.i,t.sup.s (x.sub.i,t.sup.s)-.lambda..sub.t.sup.s x.sub.i,t.sup.s over the range [g.sub.i,t, G.sub.i,t ] where .lambda..sub.t.sup.s is a non-negative real number. Since f.sub.i,t.sup.s is convex, the previous minimization is trivial. (c) Minimum Up-time and Minimum Down-time: When a generator is switched on, it has to remain on for at least L.sub.i periods and when it is switched off, it has to remain off for at least l.sub.i periods. Note that if either of these two constraints does not exist, one can set the corresponding parameter to zero. For example, if there is not a minimum up-time requirement on a generator, i, then L.sub.i can be set to 0 and the constraint is dropped. The values of L.sub.i and l.sub.i must be non-negative integer for all i .epsilon.{1, . . . ,N}. (d) Start-up and Shut-down Costs: A generator must be warmed up for a number of periods before it starts generating electricity. The cost of fuel (usually, natural gas) used at this stage is called a start-up cost. It is a function of the heat, SU.sub.i.sup.h BTU, required to warm up the unit and the price, ##EQU3## of the heating fuel during the warm-up period. The start-up cost is denoted by SU.sub.i,t.sup.s. A shut-down cost, SD.sub.i,t.sup.s, is incorporated in the model. Most utilities set SD.sub.i,t.sup.s to zero. (e) Status of Each Generator Prior to the Beginning of the Planning Horizon: Given the minimum up-time and minimum down-time constraints, we need to know for how long a generator has been up or down prior to the first period. The reason for that is to make sure that we satisfy minimum up-time and down-time constraints at the beginning of the planning horizon. (f) Classification of Generators: Generating units are usually divided into different classes. Some units are classified as "must-run units". As the name indicates, these units are functional all the time and we do not need to worry about scheduling them. An example of such units are nuclear generating units. Another class is the "cycling units". These units are switched on and off during the planning horizon depending on the load on the system. A third class is "speakers" that are used during emergencies and high-demand periods. Finally, we have the "unavailable" units. These are units scheduled for maintenance or unavailable for other reasons. Knowing the types of units helps accelerating the solution procedure. (g) Loss Factors: To consider losses in transmission lines, one can use a loss factor for each unit to adjust its production. For example, if the average transmission losses for a unit is 9%, then one can apply a reduction factor of 91% to the production of this unit. Note that these factors can be incorporated simply by multiplying the heat curve of a unit by a constant that depends on its penalty. Fourth, to avoid any blackouts, utilities make sure that, at each period, the maximum operating capacity of their system exceeds the demand of this period by a certain amount. This excess capacity is called "spinning reserves". To clarify the concept of spinning reserves, assume that our system has ten generators of which seven are on line at the current time period. Let us also say that the forecasted demand at this period is 12,000 MWH. In an optimal solution, the total generation would be close to 12,000 MWH. However, if the maximum capacity of our operating units; i.e., the total capacity when each unit is operating at G.sub.i,t, is close to 12,000 MWH, our system cannot take any unexpected increase in the demand. In other words, the reliability of our system is low. The reliability can be improved by forcing the total maximum capacity of the operating units to exceed the expected demand by a certain amount of power. This excess capacity is the spinning reserves and is indicated by r.sub.t.sub.s. There are other reserve constraints that can be enforced to improve reliability. The treatment of such constraints is very similar to our treatment of spinning reserves. Fifth, to incorporate trading transactions, the user of our system must provide his or her view of the future power market. Using the weather forecast and information that may influence power usage in other regions of the country, power traders estimate the price of buying or selling power in the market and the quantities that may be offered for trading. The projection of trading transactions is performed for the next two to seven days. The tool according to the invention uses four parameters to describe a transaction. These parameters are: amount of power, v(j) MWH; price per unit, .zeta..sub.j $/MWH; the probability, .pi..sub.j, that such a transaction may take place; and the delivery time of the transaction. The delivery time of a transaction indicates the date and time at which power will be delivered. The delivery time can be on-peak (between 7:00 a.m. and 10:59 p.m.) or off-peak (between 11:00 p.m. and 6:59 a.m.). Weekends are considered off-peak. Currently, a utility uses the information outlined above as the first, third and fourth in addition to a single load-forecast from the second to generate a reasonable schedule for its generating units. In many cases, the effect of fuel on a generator's cost function is approximated and fuel constraints are ignored. The multiple forecasts of the second and the uncertain nature of trading transactions and fuel prices are yet not incorporated into generation in the power industry. Solution Technique The overall structure of the risk management system according to the present invention is shown in the flow diagram of FIG. 7. Load forecast, trading forecast and generator and fuel properties are input in function block 71. The first step in processing the input data is to generate load scenarios. These scenarios are a result of applying power-trading contracts to the original load forecasts. The resulting scenario tree approximates future uncertainties in load and trades. The probability of each scenario is computed by multiplying the probabilities of the trades with those of the load forecasts. Scenarios with relatively small probabilities are eliminated and their probabilities are distributed among other scenarios. The scenarios are generated by calling the procedure TREE in function block 72. Procedure TREE is described in more detail below. In some cases, the user may provide a scenario tree which must be processed to define the bundle constraints. Recall that two scenarios are members of the same bundle at time t if their loads are the same up until t. Thus, if needed, the procedure BUNDLE is called in function block 73. Using the fuel available for consumption by each generator, i, we compute, in function block 74, an approximate value for the cost per BTU or h.sub.i,t.sup.s (recall that a generator may use more than one fuel at any time period). An easy way is to use the fuel with the least cost as an estimation of h.sub.i,t.sup.s, then update this value (as in function block 78). In this way, the cost function, f.sub.i,t.sup.s, of generating a MWH of power on generator i is obtained by multiplying f.sub.i.sup.h by h.sub.i,t.sup.s. A processing loop is now entered which begins by calling the procedure SUCP in function block 75 to obtain the load on each generator under any scenario. Given f.sub.i,t.sup.s, a stochastic unit-commitment model is solved. As a result, the generation of each unit at each time period (under the different scenarios) is obtained, and this can be used to compute the heat-input needed for each unit throughout the planning horizon. Then given the load on each generator, the procedure FUEL is called in function block 76 to determine an optimal fuel allocation. To satisfy the required heat input for each generator, a linear program is solved in which the decision variables are the amount of fuel burnt on each unit at each time period. Of course, our decision variable has a component for each possible fuel in the model. The linear program is solved subject to the constraint that fuel fed to a generator must be sufficient to generate the heat needed. It must also consider non-anticipativity and other fuel constraints imposed by the user. The solution of the linear program provides the fuel quantities that need to be fed to each generator at each hour of the planning horizon so that the (expected value of) cost is minimized. A test is next made in decision block 77 to determine if the current fuel allocation is the same as before. If not, a new cost function for each generator is computed in function block 78 before the process loops back to function block 75. Using the linear program solution in function block 78, a new h.sub.i,t.sup.s for each generator can now be computed by averaging the values of ##EQU4## over all fuels fed to a given generator. The new value of h.sub.i,t.sup.s yields a new cost function, f.sub.i,t.sup.s, that is used in resolving the unit commitment problem. As the process is repeated, the fuel mixtures and the load on the generators approach an optimal solution for the problem. If the test in decision block 77 is yes; i.e., the fuel allocation has not changed as a result of the new iteration, then the process moves to function block 79. In this case, the process has converged to an optimal solution. Function block 79 outputs the results of the final iteration. This includes the status of each generating unit at each time period and under each scenario, the amount of power generated on each generator at each time period and under each scenario, the marginal prices or the Lagrange multipliers, and the fuel usage provided by the linear program solution. The process is then terminated. Procedure TREE The procedure TREE is called in function block 72 in the process shown in FIG. 7. Given a forecast for power-trading transactions in the next two to seven days, TREE generates a scenario tree that represents trade opportunities. Note that we do not concern ourselves with trading transactions on the following day because utilities are required to close all deals twenty-four hours in advance. To create a scenario tree, the user supplies his or her vision of the power market in the next two to seven days. A "vision" is represented by the size of a contract in MWH, the cost of contractual power per MWH, the type of contract; i.e., whether it is buying or selling, the day on which the delivery will take place, and the time of delivery. The time of delivery can be either on-peak or off-peak. The on-peak period is between 7:00 a.m. and 10:59 p.m. while the off-peak period covers the rest of the day. Weekends are considered off-peak. The user must provide a probability for each contract. FIG. 8 is a time line illustrating on-peak and off-peak time periods. Given that we may initiate a trade at two points in time for a given day, the scenario tree branches at most at two points on all days except for the weekend. On Saturdays and Sundays we have one branching point per day. To create the scenario tree, it is assumed that the contractual load for the first day is known (because the contracts are closed for this day). For day two, a number of branches are created equal to the number of off-peak contracts. The branching point is the beginning of day two. The probability of each branch is the same as the probability of the corresponding trade. At 7:00 a.m. of day two, for each branch of the tree a set of branches are created to reflect the on-peak potential contracts. The probability of each new branch is equal to the probability of its contract times the probability of its predecessor. If the probability of a branch is below a certain threshold, .epsilon., the branch is eliminated. The probability of this branch is distributed among other branches that share the same predecessor in proportion to their probabilities. The process is repeated until the last branching point in the system is reached. The previous process may yield a large number of scenarios. In practice however, due to the difficulty in predicting the market on a horizon longer than three days, power-trading forecasts are given for day two and day three only. Another factor that reduces the number of scenarios is the use of .epsilon.. A scenario with a probability of .epsilon. or less is assumed to be insignificant. Our experience indicates that in a reasonable tree, .epsilon. can be set to 2% without affecting the hedging results. In other words, it is sufficient to consider fifty or less scenarios. The user may prefer to provide a set of load forecasts (and a set of corresponding fuel prices h.sup.t,j.sup.s) instead of a single one. In this case, the process of branching, using trade forecasts, needs to be performed on each load scenario. The probabilities need also to be multiplied by the probability of each load forecast. To give an example, consider the scenario tree of FIG. 9A. The user provides two possible forecasts. The first has a probability of 1/3 and the second has a probability of 2/3. Let us say that we expect to sell a certain amount of power with a probability 1/3 on the beginning of period four. Then, each load forecast branches at the beginning of period four creating two branches. The final probabilities are shown in FIG. 9B. A depth-first search is used to generate the scenario tree. The steps required when one load forecast is supplied are described. The method can be generalized easily to the case in which multiple load forecasts are provided. To fix notations, assume that the load forecast is d(t), t=1, . . . , T. Denote the number of branching points by M and the time periods at which a branching takes place by .tau.(i), i=1, . . . , M. .OMEGA.(i) is defined to be the set of all trades that can start at time .tau.(i). The user of our system supplies for each trade, j=1, . . . , J, its end point, .tau..sub.l (j); its volume, v(j) MWH; cost per unit, .zeta.(j) $/MWH; and its probability, .pi.(j). Note that v(j) is negative if j represents a purchase offer and positive if j is a selling offer. The approach is clarified through the example of Table 3.
TABLE 3
______________________________________
j .tau..sub.e
.nu. .zeta.
______________________________________
1 3 0 0 0.50
2 3 20 25 0.25
3 3 10 15 0.25
4 4 0 0 0.67
5 4 -10 10 0.33
______________________________________
Assume that we have four periods. We can sell twenty MWH with probability 1/4 or sell ten MWH with probability 1/4. Each of these two selling contracts starts at the beginning of period two and has a duration of two periods. At the beginning of period four, we may buy ten MWH with a probability of 1/3. Note that .OMEGA.(1)={1,2}, .OMEGA.(2)={3}, .tau.(1)=2, and .tau.(2)=4. It is assumed that d(t)=0, t=1, . . . , 4. Depth-first produces the scenarios as shown in Table 4.
TABLE 4
______________________________________
s/t 1 2 3 4 p .tau.
.sigma.
K .DELTA.z
______________________________________
1 0 0 0 0 0.33 1 1 4 0
2 0 0 0 -10 0.17 4 1 5 100
3 0 20 20 0 0.17 2 1 8 -500
4 0 20 20 -10 0.08 4 4 9 -400
5 0 10 10 0 0.17 2 1 12 -150
6 0 10 10 -10 0.08 4 5 13 -50
______________________________________
To manage the scenarios efficiently, for each scenario, s, the first point in time at which it branches off the tree, .tau.(s), its predecessor, .sigma.(s), and the change in the objective function cost due to buying/selling power, .DELTA.z(s), are stored. The scenarios are stored in a string of real numbers, d. For example, the scenarios of Table 4 are stored in the form (0,0,0,0,-10,20,20,0,-10,10,10,0,-10). The variable .kappa.(s) indicates the location in which the last element of scenario s is stored. For example, Scenario 1 is stored in d(1) . . . d(.kappa.(1)). For Scenario 2, only the fourth period needs to be changed. Hence, its elements are stored in d(.kappa.(1)+1 . . . .kappa.(2)) or d(5). This scheme reduces the memory needed to store the scenario tree. If we guarantee that there is no overlap between the trades of two different branching points, it is possible to further refine the previous approach. The following is a pseudo-code of the depth-first search. Input. integer T, integer M, integer J, float d(1 . . . T), integer .tau.(1. . . M), integer .OMEGA.(1 . . . M,1 . . . .vertline..OMEGA.(i).vertline.), integer .tau..sub.l (1 . . . J), float v(1 . . . J), float .zeta.(1 . . . J), float .pi.(1 . . . J) Output. integer S, integer .tau.(1 . . . S), integer .sigma.(1 . . . S), integer .kappa.(1 . . . S), float .DELTA.z(1 . . . S), float d(1 . . . T.times.S) Local Variables. integer i, integer k, integer l(1 . . . M) Initialization. 1. Set k.rarw.M, S.rarw.1, and l(i).rarw.1, i=1, . . . ,M. 2. Set .tau.(S).rarw.1, .sigma.(S).rarw.1, and .kappa.(S).rarw.T. 3. Add v(.OMEGA.(i,l(i))) to d between .tau.(i) and .tau..sub.l (.OMEGA.(i,l(i))) for all i=1, . . . ,M. Store the resulting vector in d(1 . . . .kappa.(S)). ##EQU5## General Step. 1. Increment l(k) by 1. 2. If l(k)=.vertline..OMEGA.(k).vertline.+1, then set l(k).rarw.1 and k.rarw.k-1. If k=0, then terminate. Go to 1. 3. For each i=k, . . . , M, add v(.OMEGA.(l(i))) to d between .tau.(i) and .tau..sub.l ((.OMEGA.(l(i))). Store the resulting vector in d(.kappa.(S)+1 . . . .kappa.(S)+1+T-.tau.(k)). 4. Set .sigma.(S+1).rarw.S, .tau.(S+1).rarw..tau.(k), and .kappa.(S+1).rarw..kappa.(S)+1+T-.tau.(k). ##EQU6## 6. Set S.rarw.S+1 and k.rarw.M. 7. Go to 1. At termination, one can eliminate all scenarios that have probabilities less than .epsilon. and distribute these probabilities among other scenarios. Procedure BUNDLE The procedure BUNDLE is called in function block 72, if needed, in the process shown in FIG. 7. The flow diagram of BUNDLE is shown in FIG. 10. Procedure BUNDLE begins in function block 101 in which the predecessor of Scenario 1 is set to 1, its split time is set to 1, and the scenario index, s, is set to 2. In function block 102, the load of scenario s is compared to the load of scenario 1 to determine the split time of s. That is, we find the first point in time at which the load of Scenario s is different from that of Scenario 1. At this point, the predecessor of s is set to 1. A new variable, s', is introduced and initialized to 2. The idea is to compare the load of s to all other scenarios s'=1, . . . , s-1, in order to determine the split time and predecessor of s. The comparison between Scenario s and Scenario 1 is performed in function block 102 while the comparison between s and each s' in {2, . . . s-1} is performed in function block 105. In decision block 103, a determination is made as to whether s' is less than s. If s'.notlessthan.s, i.e., s'=s, then the execution is transferred to function block 107 in which s is incremented by 1; otherwise, the execution moves to decision block 104. In decision block 104, the split times of s and s' are compared. If they are not equal, then the execution is transferred to function block 106. The fact that the split times are not equal indicates that s' should not be used as a predecessor to s. If the split times are equal, then s' might be used as a predecessor to s. In this case, the execution is transferred to function block 105. In function block 105, the loads of s and s' are compared to obtain a new split time for s. As one can see, the split time of Scenario s is getting higher as we go through more scenarios s' which results in lesser storage for the scenario tree. The predecessor of Scenario s is set to s'. Then, in function block 106, the value of s' is incremented by 1. This is how all scenarios from 2 to s-1 are scanned to determine the predecessor and split time of s. In function block 107, the index s is incremented by 1, as already mentioned. This is how all the scenarios in the scenario tree are scanned. Finally, in decision block 108, s is checked against the total number of scenarios, S, in our model. If s=S, the execution is terminated; otherwise, the execution is transferred to decision block 102 to continue processing. Thus, given a set of load forecasts, d.sub.t.sup.s, t=1, . . . , T, s=1, . . . , S, the procedure BUNDLE organizes these loads in the form of a tree. For example, if S=2 and T=3 and if d.sup.1 =(1, 2, 2) and d.sup.2 =(1, 2, 3), then d.sup.1 and d.sup.2 form a tree that has one branch at t=1 and t=2 and two branches at t=3. The role of BUNDLE is to study the forecasts, d.sup.1, . . . , d.sup.s, and to define the different branches of the tree. Note that if the scenarios are generated by TREE, then there is no need for using BUNDLE. The procedure BUNDLE is provided to handle the case in which scenarios are provided by the user. To clarify the previous points, the scenario tree of FIG. 11 is used. The process is initialized by setting .tau.(1)=1 and .sigma.(1)=1. Scenario 2 has the same demand as Scenario 1 for the first two periods. Then, .tau.(2)=3 and .sigma.(2)=1. To place Scenario 3 in the tree, Scenario 3 and Scenario 1 are first compared which results in .tau.(3)=3 and .sigma.(3)=1. Now, given that .tau.(3)=.tau.(2)=3, Scenario 3 and Scenario 2 are compared starting at period 3. Scenario 3 branches off Scenario 2 in the fourth period. That is, we set .tau.(3)=4 and .sigma.(3)=2. Finally, comparing Scenario 4 with Scenario 1 yields .tau.(4)=2 and .sigma.(4)=1. Given that .tau.(4).noteq..tau.(2), we do not compare scenarios 2 and 4. In the case of scenarios 3 and 4, we have .tau.(3).noteq.(4) and the process terminates. The following is a pseudo code of the procedure BUNDLE. Parameters. float .epsilon..apprxeq.10.0 Input. integer T, integer S, float d(1 . . . S, 1 . . . T) Output. integer .tau.(1 . . . S), integer .sigma.(1 . . . S), integer .kappa.(1 . . . S), float d(1 . . . T.times.S) Local Variables. integer t, integer s, integer s'. Initialization. Set .tau.(1).rarw.1, .sigma.(1).rarw.1, and .kappa.(1).rarw.T. General Step. For each scenario, s=2, . . . , S, Find the first time-period, t, at which .vertline.d(s, t)-d(1, t).vertline.>.epsilon.. Set .tau.(s).rarw.1 and .sigma.(s).rarw.1. For each scenario s'=2, . . . , s-1, if .tau.(s)=.tau.(s'), then find the first time-period, t>.tau.(s), at which .vertline.d(s, t)-d(s', t).vertline.>.epsilon. and set .tau.(s).rarw.t and .sigma.(s).rarw.s'. Set .kappa.(s).rarw..kappa.(s-1)+T-.tau.(s)+1. Procedure SUCP The procedure SUCP is called in function block 75 of the flow diagram shown in FIG. 7. The flow diagram for the procedure SUCP is shown in FIG. 12. The execution starts at function block 121 in which the Lagrange multipliers are initialized. There are different methods for this initialization in the literature. The following simple procedure is suggested: 1. Using an average fuel cost, ##EQU7## construct cost functions f.sub.i,t.sup.s. 2. For each scenario and period in the planning horizon, Rank the generators in the ascending order of average marginal cost ($/MWH) at the maximum production level, G.sub.i,t. Select enough generators so that the load and spinning-reserve constraints are met. Solve an economic power dispatch. The dual variables, .lambda. and .mu., can be used to start the bundle trust-region method. Refer to S. Takriti, J. R. Birge and E. Long, ibid., for more details. In function block 122, the bundle-trust method for solving the dual problem is used. This method is described in H. Schramm and J. Zowe, "A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results", SIAM Journal on Optimization, 2(1), pp. 121-152, February 1992. A brief description of this algorithm is given below: Let .pi..sub.1 =(.lambda..sub.1,.mu..sub.1), where .lambda..sub.1 and .mu..sub.1 are the dual multipliers obtained from the Initialization step. Denote the Lagragian by .English Pound.(.pi.) and a subgradient for it at .pi..sub.1 by .omega..sub.1. Set k.rarw.1. 1. Solve the program max.sub..pi. {min.sub.1.ltoreq.i.ltoreq.k .omega..sub.i.sup.T .pi.+.omega..sub.i.sup.T (.pi..sub.i -.pi..sub.k) ##EQU8## 2. If .English Pound.(.pi..sub.k +.pi.) is sufficiently larger than .English Pound.(.pi..sub.k), then either (a) enlarge t.sub.k and go back to 1; or (b) set .pi..sub.k+1 =.pi..sub.k +.pi., (c) compute a new subgradient .omega..sub.k by calling DP for all generators and computing the slack of demand and reserve constraints, (d) increase k by 1 and go to 1. 3. If .English Pound.(.pi..sub.k +.pi.) is not sufficiently larger than .English Pound.(.pi..sub.k), then either (a) reduce t.sub.k and go back to 1; or (b) set .pi..sub.k+1 =.pi..sub.k, (c) compute a subgradient, .omega..sub.k+1, at .pi..sub.k +.pi., (d) go to 1. The algorithm terminates when the norm of the subgradient is small enough. At this point, an optimal solution for the dual problem has been found. Note that at termination of function block 122, there may not be a feasible solution for the stochastic unit commitment problem. In function block 123, the solution of function block 122 is used to search for a feasible solution for the primal problem; i.e., the stochastic unit commitment model. The preferred approach is that of F. Zhuang and F. D. Galiana, "Towards a More Rigorous and Practical Unit Commitment by Lagrangian Relaxation", IEEE Transactions on Power Systems, 3(2), pp. 763-773, 1998. The following is a brief description of their approach: 1. If all reserve constraints are satisfied, then proceed to the economic power-dispatch phase. 2. Weight the violations of reserve constraints by their probabilities. Find scenario s and period t for which the weighted reserve constraints are most severely violated. 3. Increase .mu..sub.t.sup.s by .DELTA..mu. and resolve DP. 4. Go to 1. After obtaining a feasible solution, the execution moves to function block 124 in which an economic power dispatch is solved. This is the problem of allocating the electric load optimally between the different generators at each time period and under each scenario. Note that the economic dispatch problem assumes that units' status are given (from solving a unit commitment). Economic dispatch is a simple mathematical program in which each time-period is treated independently of others (unless we want to consider ramping rates). To solve such a problem efficiently, one can relax the demand and spinning-reserve constraints for each period and solve the dual. A good starting point is the Lagrange multipliers obtained from the unit-commitment solver. Given that the generators' cost functions depend on fuel prices, we revise the fuel mix using the economic power-dispatch solution. If the changes in fuel mix are significant, we resolve the economic power dispatch model. Note that one can avoid iterating between economic power dispatch and fuel assignment by merging-these two problems into a large-scale mathematical program. The standard economic power dispatch method is modified to fit the model implemented in the present invention. Here is the resulting procedure: 1. Solve a minimization problem for each period of the planning horizon. Each problem has two constraints: demand and spinning reserves. These two constraints are relaxed using .lambda. and .mu. and the Lagrangian is optimized over the resulting period. 2. If the total generation cost is equal (close enough) to that of the previous iteration, then terminate. 3. Using the load on each generator, call the procedure FUEL. 4. Compute a new cost function. 5. Go to 1. For a more detailed description of the economic power dispatch problem, the reader is referred to the book of A. J. Wood and B. F. Wollenberg, ibid. Summarizing, given a set of generators, {1, . . . , N}, and all related data, such as f.sub.i,t.sup.s, g.sub.i,t, G.sub.i,t, and G.sub.i,t, and given a set of load forecasts on the electric system at each period in the planning horizon, SUCP solves a stochastic unit commitment problem. That is, it produces, for each scenario, a schedule indicating the time periods in which each generating unit is running and its load during these periods. The resulting schedule guarantees that the total generation cost is close to minimal and that the system provides enough supply to meet demand. An important output of SUCP is the marginal cost, .lambda..sub.t.sup.s ($/MWH), of power at each period. Under a given scenario, the marginal cost at time t is the cost, over all operating generators, of producing one unit of power during this period. Marginal costs are of great value to the decision maker because they provide pricing information that can be used in decisions related to buying and selling power. SUCP assumes that the cost curves, f.sub.i,t.sup.s, are given and independent of fuel prices (which are dealt with in FUEL). Mathematically, SUCP minimizes the cost function ##EQU9## where (u.sub.i,t.sup.s -u.sub.i,t-1.sup.s).sup.+ and (u.sub.i,t.sup.s -u.sub.i,t-1.sup.s).sup.- are the positive and negative parts of u.sub.i,t.sup.s -u.sub.i,t-1.sup.s. The minimization of (1) is subject to the demand constraints ##EQU10## and spinning-reserve constraints ##EQU11## in addition to minimum up-time, minimum down-time, and operating capacity of each generator. Note that it is desirable in some cases to impose additional constraints to improve the reliability of the solution. The treatment of any set of linear constraints that links the generators is similar to that suggested for the above constraints. The procedure described is based on Lagrangian relaxation. To solve (1), the demand and spinning-reserve constraints are relaxed by associating non-negative multipliers, .lambda. and .mu., with them. The value of .lambda..sub.t.sup.s represents the marginal cost of producing power during t. Similarly, .mu..sub.t.sup.s represents the cost of having spinning reserves on-line at time period t. The problem becomes that of maximizing the resulting concave dual. This is the main attraction behind this approach: substituting a difficult primal by a convex program. On the other hand, the resulting Lagrangian is not smooth. The bundle trust-region method of Schramm and Zowe, ibid., is used to solve the dual. Relaxing the demand and spinning-reserve constraints decouples the generating units. Each generator's problem is solved using dynamic programming. The solutions to the dynamic programs provide the load on each generator. Using the solutions of the single-generator dynamic programs, one can compute the total generation at each time period and under each scenario. We check for optimality and, if needed, we repeat the previous process using an updated .lambda. and .mu.. The violations of the demand and reserve constraints form a subgradient to the dual which can be used in the bundle method iterations. If a parallel computer is available, the dynamic programs of the generating units can be distributed among the processors. Given that solving the dynamic program of a cycler requires more calculations than solving the dynamic program of a must-run unit, we distribute the single-generator problems so that the number of cyclers and the number of must-run units are almost the same over all processors. Procedure FUEL The procedure FUEL is called by the procedure SUCP. Procedure FUEL solves a linear program to determine an optimal allocation for fuel under certain generation load, x.sub.i,t.sup.s. The constraint matrix of the linear program is built iteratively, as shown in FIG. 15. The process starts in function block 1501 in which we set k.rarw.1, s.rarw.2, t.rarw.1, i.rarw.1, and j.rarw.1. These variables are the counters used in the construction of the constraint matrix of the linear program solved to obtain an optimal fuel allocation. In function block 1502, B(k,I(y.sub.i,t,j.sup.s)) to 1 and B(k,I(y.sub.i,t,j.sup..sigma.(s))) to -1. Note that I(y.sub.i,t,j.sup.s) is the index of the column in the constraint matrix corresponding to the variable y.sub.i,t,j.sup.s. Similarly, I(y.sub.i,t,j.sup..sigma.(s)) is the index of the column in the constraint matrix corresponding to y.sub.i,t,j.sup..sigma.(s). In function block 1503, the value of j is incremented by 1. Then, in decision block 1504, if j.ltoreq.F, the execution is directed to function block 1502; otherwise, the execution is directed to function block 1505. In function block 1505, i is incremented by 1. Then, in decision block 1506, if i.ltoreq.N, the execution is directed to function block 1502; otherwise, the execution block proceeds to function block 1507. In function block 1507, the value of t is incremented by 1. Then, in decision block 1508, if t.ltoreq..tau.(s-1), the execution is directed to function block 1502; otherwise, the execution proceeds to function block 1509. In function block 1509, the value of the scenario index, s, is increased by 1. Then, in decision block 1510, if s.ltoreq.S, the execution is directed to function block 1502; otherwise, the execution terminates. The cost of generating one MWH of electricity is a function of the cost of fuel used and its heat content. It is assumed that we have F different fuels and that the cost of providing a BTU using fuel j at time t is h.sub.t,j.sup.s $/BTU. Note that s here is a scenario index that reflects load forecasts provided by the user. When TREE builds on these forecasts to generate new scenarios, each branch in the resulting tree has values of h equal to those of the original scenario that is used to create this branch. Note that h.sub.t,j.sup.s is a function of t which allows incorporating the fluctuation in fuel cost, over the planning horizon, into calculations. Given the generation load, x.sub.t,j.sup.s, under scenario s on each unit i at time period t, we must provide enough fuel to generate the required electric power. That is, the amount of fuel used must satisfy the constraint ##EQU12## where y.sub.i,t,j.sup.s .gtoreq.0 is the heat generated (BTU) by fuel j on generator i at time t under s. For the start-up energy requirement, we enforce a similar constraint, ##EQU13## where .GAMMA.i is the set of fuels that may be used to start-up generator i. There might be other constraints that need to be imposed on fuel allocation. For example, we may want to impose a constraint on the maximum amount of fuel j that can be used by a certain generating unit, i, during the planning horizon. That is, ##EQU14## must be less than the total heat available from fuel j regardless of s. Another constraint might be an upper bound on the amount of fuel j used over the planning horizon. In other words, the value of ##EQU15## must be bounded above by a given constant. An important constraint is "fuel j cannot be used on unit i" which can be modeled by setting y.sub.i,t,j.sup.s =0 for all t and s. To simplify notations, we write fuel constraints (which are assumed to be linear) in the form Ay.ltoreq.b.sup.h where A is a constraint matrix of appropriate dimension and b.sup.h is the corresponding right-hand side. Note that the fuel usage of a generator must fulfill the bundle (i.e., non-anticipativity) constraints imposed by the scenario tree. For example, if Scenario 1 and Scenario 2 have the same load between the first period and .tau., then y.sub.i,t,j.sup.1 -y.sub.i,t,j.sup.2 =0 for all i=1, . . . , n, t=1, . . . .tau., j=1, . . . , F. The constraint matrix corresponding to bundle constraints is denoted by B. The matrix B is constructed using the variables .sigma. and .tau. returned by TREE and BUNDLE. To do so, I(y.sub.i,t,j.sup.s) is defined to be the column of B (or A) that corresponds to the variable y.sub.i,t,j.sup.s. An integer k is used to count the number of rows in B. The pseudocode for the iterative process of building the linear program solved by FUEL is as follows (see FIG. 15): ##EQU16## At termination, k is the total number of bundle constraints. To reduce storage requirement, only the non-zero elements of B are stored. To utilize fuel optimally, the expected cost of the fuel used is minimized by solving the stochastic linear program ##EQU17## where y and y are the vectors of excess and shortage of fuel, .alpha. and .beta. are penalties on violating the constraint ##EQU18## and l is a vector of ones. The previous stochastic linear program is solved using an interior point approach (e.g., I. J. Lustig, J. M. Mulvey and T. J. Carpenter, "Formulating stochastic programs for interior point methods", Operations Research, 39:757-770, 1991). Many commercial packages already include convenient routines for such techniques (see, for example, the Optimization Subroutine Library of IBM). If a parallel computer is available, the process can be accelerated as described in I. J. Lustig and E. Rothberg, "Gigaflops in linear programming", Operations Research Letters, 18:157-165, 1996. Procedure DP The procedure DP is called from the bundle trust region method of function block 122 in FIG. 12 which shows the procedure SUCP. The flow diagram of the procedure DP is shown in FIG. 14. Given the Lagrange multipliers, DP determines the status and the load on a generating unit by solving a dynamic program. In function block 1401, the values of .beta.(s), s=1, . . . , S, are initialized to T. The recursion starts at time period T and moves backward until time period 1 is reached. The time period under investigation for scenario s is .beta.(s). The scenario index s is set to S. The dynamic program of scenario s is solved by moving backward in time from period .beta.(s) to .tau.(s). What is being done here is similar to the dynamic programming approach used in solving stochastic decision processes. See, for example, D. P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, 1987. In function block 1403, the dynamic program of .sigma.(s) is solved by moving backward from time period .beta.(s) to time period .tau.(s). At this stage both of the dynamic programs of s and its predecessor .sigma.(s) have been solved. The probability p(.sigma.(s)) of .sigma.(s) is incremented by p(s). Then, in function block 1404, the value of .beta.(.sigma.(s)) is set to .tau.(s)-1. The scenario index, s, is decreased by 1 in function block 1405. That is, the dynamic program of s is done, and we are ready to move on to another scenario s-1. In decision block 1406, a check is made to determine if s=0; e.g., have all scenarios been studied? If so, the procedure moves to function block 1407; otherwise, the procedure moves to function block 1402 to study a new scenario. In function block 1407, the solution of the dynamic program has been finished, and we move forward to trace the optimal decisions of the dynamic program. The policy obtained at the end of this stage is the optimal policy that is returned to the calling routine. Given the data related to a generator, procedure DP solves the corresponding single-generator dynamic program and returns an optimal schedule, u, for this generator and the load on it, x, under all scenarios at each period in the planning horizon. The stages in our dynamic programming formulation are the time periods. Each stage has L.sub.i +l.sub.i states. The first L.sub.i states are those corresponding to the generator being on and the second l.sub.i states correspond to the generator being off. The number of states can be reduced to two in some cases as suggested by S. Takriti, J. R. Birge and E. Long, ibid. Given a scenario tree that is described using .tau.(s) and .sigma.(s), s=1, . . . , S, DP solves a single-generator dynamic program by moving backward. A method for organizing the calculations and computer storage are described that a high performance is achieved (see FIGS. 13A and 13B). For the following pseudocode of the procedure DP, it is assumed that scenarios, s=1, . . . , S, are sorted in the ascending order of .tau.(s). Input. integer T, integer N, integer l, integer L, integer v, integer w, float d(1 . . . S,1. . . T), float p(1 . . . S) Output. integer u(1 . . . S,1 . . . T), float x(1 . . . S, 1 . . . T) Local Variables. integer j, integer s, integer t, integer, .beta.(1 . . . S), integer .gamma.(1 . . . S) Initialization. Allocate enough memory for ##EQU19## stages. Each stage contains L+l states and each state constitutes of a real number (cost-to-go) and an integer number (the predecessor index). Set ##EQU20## Set .beta.(s).rarw.T, s=1, . . . , S. For each scenario s=1, . . . , S, set .gamma.(s)=j and j.rarw.j-(T-.tau.(s)+1). General Step. For each scenario s=S, . . . , 1, Starting at t=.beta.(s), move backward using dynamic programming until t=.tau.(s). These calculations must be performed in the allocated space .gamma.(s) to .gamma.(s)-(T .tau.(s)+1). Each state must maintain the index of the predecessor state that provided an optimal solution for it. Starting at t=.beta.(.sigma.(s)), move backward using dynamic programming until t=.tau.(s). These calculations are performed in the allocated space .gamma.(.sigma.(s)) to .gamma.(.sigma.(s))-(T-.tau.(s)+1). Set .kappa.(.sigma.(s))=.tau.(s)-1. Increment the states of stage .gamma.(.sigma.(s)) by the values of the states in .gamma.(s)-(T-.tau.(s)+1) weighted by p.sub.s. Increment p.sub..sigma.(s) by p.sub.s. Using the initial state of the generator, trace the optimal paths to obtain an optimal decision tree. Note that to find that moving backward requires solving an optimization problem at each stage. This problem is that of minimizing f.sub.i,t.sup.s (x.sub.i,t.sup.s)-.lambda..sub.t.sup.s x.sub.i,t.sup.s subject to g.sub.i,t .ltoreq.x.sub.i,t.sup.s .ltoreq.G.sub.i,t. There might be some other bounds on x.sub.i,t.sup.s that can be incorporated. For example, if "the load on a generator cannot exceed (g.sub.i,t +G.sub.i,t)/2 in the first hour after turning it on", then we can force this constraint on the dynamic program in the row corresponding to "On 1" (see FIG. 13B). To accelerate the calculations, DP is applied to cycling units only. For must-run units, one can find the optimal loads by minimizing the function f(x)-.lambda.x at each time period. In general, the peakers can be ignored, u.sub.i,t.sup.s =0, because they are operated in cases of emergency. System's Output Now, the output of the tool according to the invention is described. First, the status, u.sub.i,t.sup.s, of a generator, i, is a binary variable that indicates whether this generator is on, u.sub.i,t.sup.s =1 , or off, u.sub.i,t.sup.s =0, at time period t under scenario s. The procedure guarantees that the resulting values of u.sub.i,t.sup.s are feasible; i.e., (a) they satisfy the minimum up-time and minimum down-time requirements. For example, if the minimum up-time, L.sub.i, of a generator, i, is equal to three, then sequences such as 0110, 0100, and 0101, are infeasible. The reason for that is that when the generator is switched on; i.e., 0.fwdarw.1, it has to remain on for three periods or more. Note that the sequence 0111 is feasible in this example. (b) they are consistent between the different scenarios. This condition is known as non-anticipativity in stochastic programming (see, for example, Rockafellar and Wets, "Scenarios and policy aggregation in optimization under uncertainty", Mathematics of Operations Research, 16(1):119-147, 1991). To clarify this concept, let us pay attention to the beginning of the first period, t=1, in our planning horizon. Although there are different scenarios that may occur in the future, we must make one decision for each generating unit regardless of which scenario may occur in the periods to come. This implies that the decision we make must be feasible for all scenarios, s=1, . . . , S. To further clarify the concept of non-anticipativity, let us discuss the set of scenarios presented in FIG. 11. The scenarios are organized in a scenario tree. Each branching node in the scenario tree (which must be at the beginning of a period) represents a point in the planning horizon at which we can make decisions regarding the status of our generators: switch on or switch off a unit. The first decision point is the beginning of the first period, t=1. Note that all scenarios go through this node. Hence, the decisions made at this node must be feasible to all scenarios (because we do not know which scenario we may face in the future). Mathematically speaking, we must enforce the constraint u.sub.i,1.sup.s =u.sub.i,1.sup.s', .A-inverted.s and s'=.epsilon.{1, 2, 3, 4} for each generator i.epsilon.{1, . . . , N}. During the first period, we expect our demand pattern to follow one of two paths: either that of Scenario 4 or the path of scenarios 1, 2, and 3. Let us assume that our demand is moving up during the first period; i.e., we are expecting scenario 1, 2, or 3 in the future. When we reach the beginning of period 2 which is our second decision point, we must make decisions that are feasible for scenarios 1, 2, and 3 (because we do not know yet which one is going to occur). The mathematical constraint is then u.sub.i,2.sup.s =u.sub.i,2.sup.s', .A-inverted.s and s'.epsilon.{1,2,3} for each generator i.epsilon.{1, . . . ,N}. Let us say that during period 2, we observe a demand pattern similar to that of scenario 2 (or scenario 3 since they are the same so far). At the beginning of period 3, we make a decision for each generator such that our decision set is feasible for the demand of scenario 2 and that of scenario 3. The process continues as long as we have two or more scenarios sharing the same demand pattern up until this point in time. To summarize, the procedure produces an implementable set of decisions. That is, decisions that satisfy the mathematical conditions imposed by the structure of the scenario tree. The fact that we have a set of scenarios improves the robustness of the solution obtained without sacrificing the implementability of the decisions among the scenarios. Second, if the status of a generator, i, at a certain time period, t, and under scenario s is 1, then the procedure provides the load (MWH) on this generator during t. The load, indicated by x.sub.i,t.sup.s, satisfies the constraints imposed by the operational range of the generator. That is, .English Pound..sub.i,t .ltoreq.x.sub.i,t.sup.s .ltoreq.G.sub.i,t, .A-inverted.i .epsilon.{1, . . . ,N}, .A-inverted.t .epsilon.{1, . . . , T}, .A-inverted.s .epsilon.{1, . . . S}. If u.sub.i,t.sup.s =0, then the load is 0. Third, the variables y.sub.i,t,j.sup.s of FUEL provides an optimal fuel allocation. Given the heat content, .alpha..sub.j BTU/Ton, of fuel j, the expected amount of fuel used by generator i at time t is ##EQU21## Of course, when scenario s is observed, we adopt the fuel strategy imposed by the variables y.sub.i,t,j.sup.s. Fourth, the procedure also provides the average cost per unit of power, .lambda..sub.t.sup.s, at each time period under every scenario. These values can be used in pricing the power at each time period of the planning horizon. Note that as time progresses, we obtain a new forecast. The excess capacity in the electric system (over the refined forecast) represents the amount of power that we should offer to sell in the market. In case of having less generation than the new forecasted load, we buy the needed power from the open market. Fifth, the values of the dual variables of the linear program of procedure FUEL and of the stochastic program of procedure SUCP provide important sensitivity analysis information. For example, the value of .lambda..sub.t.sup.s indicates the change in the generation cost if d.sub.t.sup.s increases by one unit. The dual variables of FUEL denote the economical importance of each constraint and how it may affect the value of an optimal solution. Note that the dual variables corresponding to the bundle constraints in FUEL indicate the importance of non-anticipativity for a given scenario and time period. Finally, one can use the linear program to study the range in which fuel prices can change without changing the optimal fuel allocation. Note that in reality, the observed scenario is (most likely) not a member of the set of the original scenarios used in the model. One can adopt the solution of the closest scenario and apply it to the real system. Commercial packages available in the market deal with one forecast and provide a feasible schedule. They do not consider the uncertainty in future demands and do not model the buying and selling transactions. Also, these packages do not incorporate fuel constraints and changes in fuel cost in their models. On the other hand, our model considers uncertainty by using a set of scenarios and produces prices at which power may be traded without violating fuel constraints. While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||