9512.net
甜梦文库
当前位置:首页 >> >>

Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system unde


Stochastic Lagrangian Relaxation applied to Power Scheduling in a Hydro-Thermal System under Uncertainty
M.P. Nowak and W. Romisch Institut fur Mathematik Humboldt-Universitat Berlin 10099 Berlin, Germany
A dynamic (multi-stage) stochastic programming model for the weekly cost-optimal generation of electric power in a hydro-thermal generation system under uncertain load is developed. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints coupling power units. It is assumed that the stochastic load process is given (or approximated) by a nite number of realizations (scenarios) in scenario tree form. Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single (thermal or hydro) unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a speci c descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the rst stage (primal) decisions starting from the optimal (stochastic) multipliers is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon from 7 to 9 days. The sizes of the corresponding optimization problems go up to 200.000 binary and 350.000 continuous variables, and more than 500.000 constraints.

Abstract

1 Introduction
Mathematical models for the e cient operation of electric power generation systems often lead to rather complex optimization problems. In particular, they are 1

characterized by combinations of challenges like mixed-integer decisions, nonlinear costs, large dimensions and data uncertainty. The latter aspect mostly concerns uncertainties of electrical load forecasts, of generator failures, of ows to hydro reservoirs or plants, and of fuel or electricity prices (cf. 12, 13, 15, 18, 29] for earlier relevant work). The present paper aims at treating power optimization in a hydro-thermal system under uncertain electrical load. More precisely, a generation system comprising thermal units and pumped hydro storage plants as encountered at the German utility VEAG Vereinigte Energiewerke AG Berlin is considered. The relevant mathematical optimization model contains a large number of binary and continuous variables, constraints and uncertainty appearing in the load constraints. The time horizon is 7 to 9 days as it is needed for the e cient weekly operation of hydro-thermal systems involving weekly load and pumping cycles. The machinery of stochastic programming o ers modelling and solution techniques for such optimization problems under uncertainty. In the present paper, a multistage stochastic programming model in which the expected production costs are minimized and stages refer to the availability of further observations of the load is developed. In particular, the rst stage refers to the time period for which a reliable load forecast is available. The attention is focused on the (deterministic) rst-stage scheduling decisions (on/o and outputs), which are obtained by minimizing the total expected generation costs and, hence, hedge against uncertainty. Since the stochastic programming model contains mixed-integer decisions in all stages and is large-scale, new questions on the design of solution algorithms are raised. Nowadays, solution methods are well developed for linear multi-stage stochastic programs without integrality constraints (cf. the monographs 3, 17, 16, 38] and the state-of-the-art surveys 2, 34]). Recently, progress has been made for mixedinteger stochastic programming models and applications to power optimization. The following algorithmic approaches for mixed-integer multi-stage models seem to be known in the literature: (a) Stochastic branch and bound methods ( 26]), (b) scenario decomposition by splitting methods combined with suitable heuristics ( 32], 25], 36, 37]), (c) scenario decomposition combined with branch and bound ( 6, 7]), (d) stochastic (augmented) Lagrangian relaxation of coupling constraints ( 8, 30], 10, 33]). The approaches in (b) and (c) are based on a successive decomposition of the stochastic program into nitely many deterministic (or scenario) programs, which may be solved by available conventional techniques. The idea of (d) is a successive decomposition into nitely many smaller stochastic subproblems for which (e cient) solution techniques have to be developed eventually. Due to the nonconvexity of the underlying stochastic program, the successive decompositions in (b)-(d) have to be combined with certain global optimization techniques (branchand-bound, heuristics etc.). The approach followed in the present paper consists in a stochastic version of the classical Lagrange relaxation idea ( 23]), which is very popular in power optimization ( 1, 11, 14, 24, 35, 39, 40]). Since the corresponding coupling constraints contain 2

random variables, stochastic multipliers are needed for the dualization, and the dual problem represents a nondi erentiable stochastic program. Subsequently, the approach is based on the same, but stochastic, ingredients as in the classical case: a solver for the nondi erentiable dual, subproblem solvers, and a Lagrange heuristics. It turns out that, with a state-of-the-art bundle method for solving the dual, e cient stochastic subproblem solvers based on a speci c descent algorithm and stochastic dynamic programming, respectively, and a speci c Lagrange heuristics for determining a nearly optimal rst-stage solution, this stochastic Lagrangian relaxation algorithm becomes e cient. The paper is organized as follows. In Section 2 a detailed description of the hydrothermal generation system is given and the stochastic programming model is developed. Section 3 describes the stochastic Lagrangian relaxation approach together with its components: algorithms for solving the stochastic dual, single-unit subproblems and economic dispatch problems, and the Lagrange heuristics. For all (sub)algorithms, numerical experience is provided. Finally, numerical results for the stochastic Lagrangian relaxation based algorithm are reported in Section 4 for realistic data and the VEAG-owned hydro-thermal generation system.

2 Model
We consider a power generation system comprising (coal- red and gas-burning) thermal units, pumped hydro storage plants and delivery contracts, and describe a model for its weekly cost-optimal generation under uncertainty on the electrical load (cf. 10], 28]). Let T denote the number of time intervals obtained by discretizing the operation horizon. This discretization may be chosen uniformly (e. g. hourly) or non-uniformly. Let I and J denote the number of thermal and pumped hydro storage units in the system. Delivery contracts are regarded as particular thermal units. The decision variables in the model correspond to the outputs of units, i. e., the electric power generated or consumed by each unit of the system. These decision variables are denoted by
ui pi

t; t;

i = 1; : : : ; I; and stj ; wjt ; j = 1; : : : ; J; t = 1; : : : ; T;

where uti 2 f0; 1g and pti are the on/o decisions and the production levels of the thermal unit i during the time period t. Thus, uti = 0 and uti = 1 mean that the unit i is o -line and on-line during period t, respectively. stj ; wjt are the generation and pumping levels of the pumped hydro storage plant j during the period t, respectively. Further, by ltj we denote the storage volume in the upper reservoir of plant j at the end of the interval t. All variables mentioned above have nite upper and lower

3

bounds representing unit limits and reservoir capacities of the generation system:

pmin uti pti pmax uti ; uti 2 f0; 1g; i = 1; : : : ; I; t = 1; : : : ; T; i i 0 stj smax; 0 wjt wjmax; j 0 ltj ljmax ; j = 1; : : : ; J; t = 1; : : : ; T:

(1)

The constants pmin ; pmax; smax; wjmax, and ljmax denote the minimal/maximal outputs i i j of the units and the maximal storage volumes in the upper reservoirs, respectively. The dynamics of the storage volume, which is measured in electrical energy, is modelled by the equations:
lt j lj
0

= ltj? ? stj + j wjt ; t = 1; : : : ; T; = ljin; lT = ljend ; j = 1; : : : ; J: j
1

(2)

Here, ljin and ljend denote the initial and nal volumes in the upper reservoir, respectively, and j is the cycle (or pumping) e ciency of plant j . The cycle e ciency is de ned as the quotient of the generation and of the pumping load that correspond to the same volume of water. The equalities (2) show, in particular, that there occur no in- or out ows in the upper reservoirs and, hence, that the storage plants of the system operate with a constant amount of water. Together with the upper and lower bounds for ltj the equations (2) mean that certain reservoir constraints have to be maintained for all storage plants during the whole time horizon. Further single-unit constraints are minimum up- and down-times and possible must-on/o constraints for each thermal unit. Minimum up- and down-time constraints are imposed to prevent thermal stress and high maintenance costs due to excessive unit cycling. Denoting by i the minimum down-time of unit i, the corresponding constraints are described by the inequalities:
ui

t?1 ? ut i

1 ? ui ;

= t + 1; : : : ; minft + i ? 1; T g; t = 1; : : : ; T:

(3)

Analogous constraints can be formulated describing minimum up-times. The next constraints are coupling across power units: the load and reserve constraints. The rst constraints are essential for the operation of the power system and express that the sum of the output powers is greater than or equal to the load demand in each time period. Denoting by dt the load demand during period t, the load constraints are described by the inequalities:
J I X t X t (sj pi + j =1 i=1

? wjt )

d

t;

t = 1; : : : ; T:

(4)

In order to compensate unexpected events (e.g. sudden load increases or decreases, outages of units) within a speci ed short time period, a spinning reserve describing the total amount of generation available from all units synchronized on the system 4

minus the present load is prescribed. The corresponding constraints are given by the following inequalities:
I X max t (pi ui i=1

? pti )

r

t;

t = 1; : : : ; T;

(5)

where rt > 0 is the spinning reserve in period t, which is assumed to be proportional to dt. The objective function is given by the total costs for operating the thermal units. These costs consist of the sum of the costs of each individual unit over the whole time horizon, i. e.,
I T XX i=1 t=1

FCi(pti ; uti) + SCit (ui)];

(6)

where FCi are the fuel costs for the operation of the thermal unit i during period t and SCit are the start-up costs for getting the unit on-line in this period. We assume that each FCi is piecewise linear convex, strictly monotonically increasing and of the form FCi(p; u) = l max fail p + bil ug ; (7) ;:::;L
=1

where ail and bil are xed cost coe cients. The start-up costs SCit(ui ) may vary from a maximum cold-start value to a much smaller value when the unit i is still relatively close to its operation temperature. The following description of start-up costs re ects this dependence on the down-time:

SCit(ui ) = max ci (uti ? ;:::;
=0

c i

X t? ui
=1

);

where ci = 0 and ci , = 0; : : : ; ic are cxed increasing cost coe cients, ic is the time the unit i needs to cool down, and ci i its maximum cold-start costs. Altogether, minimizing the objective function (6) subject to the constraints (1)-(5) leads to a cost-optimal schedule for all units of the power system during the speci ed time horizon. It is worth mentioning that a cost-optimal schedule has the following two interesting properties, which are both a consequence of the strict monotonicity of the fuel costs. If a schedule (u; p; s; w) is optimal, then the load constraints (4) are typically satis ed with equality and we have stj wjt = 0 for all j = 1; : : : ; J; t = 1; : : : ; T; i. e., generation and pumping do not occur simultaneously (cf. 15]). The minimization problem (1)-(6) represents a mixed-integer program with linear constraints, and IT binary and (I +2J )T continuous decision variables, respectively. For a typical con guration of the VEAG-owned generation system with I = 25 (thermal), J = 7 (hydro) and T = 168 (i. e., 7 days with hourly discretization), the dimension of the model is shown in the rst row of Figure 3. Figure 1 shows a typical load curve of a peak load week and a corresponding cost-optimal hydro-thermal
0

5

load thermal generation hydro generation hydro pumping

Figure 1: Load curve and hydro-thermal schedule Figure 2: Example for a Scenario Tree
Monday Tuesday W-day Thursday Friday Saturday Sunday

schedule. The load curve in Figure 1 exhibits two overlapping cycles: a daily and weekly cycle. Pumped hydro storage plants are designed to exploit these two cycles by saving fuel costs when serving the peak load with hydro-energy and pumping to re ll the reservoir during o -peak periods, i. e., during the nights and weekends. The hydro schedule in Figure 1 re ects this typical operation of pumped hydro storage plants. The remaining load, i. e., the di erence between the original system load and the hydro schedule, shows a more uniform structure than the original load. This portion of the load is covered by the total output of thermal units. So far we have tacitly assumed that the electrical load is given and deterministic over the whole time horizon. In electric utilities, schedulers forecast the electrical load for each time period of the day or week in advance. But, clearly, the actual electrical load may deviate from the predicted load at any time period due to various unforeseeable (random) in uences (temperature, daylight, switch o of local consumers etc.). This gives rise to a stochastic model of the electrical load fdt : t = 1; : : : ; T g as a (discretetime) stochastic process on some probability space ( ; A; IP ) re ecting that the information on the load is complete for t = 1, and that the uncertainty increases with growing t. Let fAt : t = 1; : : : ; T g be the ltration generated by the load process, where At is the - eld de ned by the random vector (d ; : : : ; dt ). Hence, we have f;; g = A A : : : At : : : AT A. The sequence of t ; pt ; st ; wt ) : t = 1; : : : ; T g also forms a stochastic process scheduling decisions f(u on ( ; A; IP ), which is assumed to be adapted to the ltration of - elds, i.e., nonanticipative. The latter condition means that the decision (ut ; pt ; st ; wt) depends only on the data history (d ; : : : ; dt ) or, equivalently, that (ut ; pt ; st ; wt) is Atmeasurable. Since all decision variables are uniformly bounded, we may restrict our attention to decisions (u; p; s; w) belonging to L1( ; A; IP ; IRm), where m := 2(I + J )T . Then the non-anticipativity condition can be formulated equivalently as
1 1 2 1

(u; p; s; w) 2 t L1
=1

T

; At; IP ; IR

2( + )

I J

;

(8)

6

and the (stochastic) optimization problem consists in minimizing the expected cost (cf. (6)) I T X X FCi(pti ; uti ) + SCit(ui )]g (9) I f E over all decisions (u; p; s; w) satisfying the non-anticipativity constraint (8), and IP -almost surely, the constraints (1)-(5). Among the constraints (1)-(5), (2) and (3) re ect the dynamics of the model and (4), (5) couple power units. Altogether, the stochastic program involves 2(I + J )T stochastic decision variables. It is a discrete-time dynamic or multi-stage stochastic recourse problem, where the stages correspond to steps in the decision process at which new observations of the stochastic load are taken into account. For the numerical solution of the dynamic recourse model we now assume that an (approximate) discrete multivariate probability distribution of the stochastic load vector d = (d ; : : : ; dT ) is given, such that its support consists of nitely many atoms or scenarios and that the non-anticipativity constraint (8) is satis ed. This approximation of the load can be represented in the form of a scenario tree. Each path of the tree from the root to a leaf corresponds to one scenario; each node of the tree corresponds to a component of the decision (u; p; s; w). Figure 2 shows an example of a load scenario tree over a weekly time horizon, where new observations of the electrical load lead to a number of additional daily scenarios. Since the decision variable (u; p; s; w) exhibits the same tree structure as the load, the model may easily become extremely large if the number of nodes in the scenario tree increases. Figure 3 shows how the dimension of the model (1)-(5), (8), (9) increases with the number of scenarios for a scenario tree with equidistant binary branches (without taking into account the constraints of type (3) and the objective function).
1

i=1 t=1

Variables Constraints Nonzeros binary continuous 1 168 4200 6652 13441 19657 5 462 11550 18018 36965 54059 10 756 18900 29484 60490 88462 20 1176 29400 45864 94100 137612 30 1663 41575 64857 133070 194601 50 2478 61950 96642 198290 289976 80 3696 92400 144144 295760 432512 100 4200 105000 163800 336100 491500 Figure 3: Dimension of the mixed-integer LP depending on the number of scenarios with T=168, I=25 and J=7

Scenarios Nodes

7

3 Stochastic Lagrangian Relaxation
The huge size of the model, described in the previous section, prevents the application of state-of-the-art mixed-integer LP solvers. However, decomposition techniques may provide a practicable alternative. Here, we make use of the fact that the model is loosely coupled with respect to the operation of di erent units. Associating stochastic Lagrange multipliers with the coupling constraints (4) and (5) leads to the Lagrangian L and the dual function D:

L(u; p; s; w; ; ) = IE f
+ t(dt ?
I X t pi i=1 J X j =1

T I X X t=1 i=1

FCi(pti ; uti) + SCit (ui)]
I X i=1

(10) (11) (12)

? (stj ? wjt )) + t (rt ? (utipmax ? pti )g i
( )

where the minimization in (12) is subject to the remaining single unit constraints (1), (2), (3) and (8). Justi ed by general duality results for convex multi-stage stochastic programs (see 31] and the review in Section 4 of 10]) we consider the dual problem In particular, this means that the stochastic multiplier processes and are nonnegative IP -almost surely and adapted to the ltration fAt : t = 1; : : : ; T g generated by the load process. Hence, they exhibit the same tree structure as d. Furthermore, the dimension of the dual problem (13) is twice the number N of nodes in the scenario tree. The optimal value of the dual problem (13) provides a lower bound for the optimal costs of the nonconvex (primal) model. For a discussion of the (relative) duality gap in our context of power optimization, the reader is referred to 1], 24] and Section 4 in 10]. Due to the relaxation of the coupling constraints (4) and (5), the minimization in (12) decomposes into stochastic single unit subproblems and the dual function takes the form maxfD( ; ) : ( ; ) 2 t L ( ; At; IP ; IR )g :
1 =1 2 +

D( ; ) = uminw L(u; p; s; w; ; ) ; ;p;s;

T

(13)

D( ; ) =

I X i=1

Di( ; ) +

J X

j =1

X ^ Dj ( ) + IE

T

t=1

t dt + t rt ]

;

(14)

^ where Di( ; ) and Dj ( ) refer to the optimal values of the thermal subproblem (21) and the hydro storage subproblem (15), respectively. The dual function D is concave and nondi erentiable on IR N , and, in fact, polyhedral due to (7). Similar to the deterministic case, the stochastic Lagrangian relaxation algorithm for solving the model in Section 2 consists of the following ingredients:
2

8

(a) Maximization of the dual function D by a proximal bundle method using function and subgradient information (Sect. 3.3); (b) E cient solvers for the stochastic single unit subproblems: stochastic dynamic programming (Sect. 3.2) and a speci c descent algorithm (Sect. 3.1); (c) Lagrange heuristics for determining a feasible rst-stage decision (Sect. 3.4); (d) Economic dispatch for determining an approximate solution for the optimal rst-stage decision (Sect. 3.5). In the remaining part of this section we provide a detailed description of all these ingredients. The subproblem (15) - (17), which corresponds to the hydro storage plant j , is a linear multi-stage stochastic program: ^ Dj ( ) = smin ;w
( j

3.1 Descent Algorithm for Stochastic Storage Problems
(
I E

j)

T X t t (wj t=1
sj
1

? stj )] : (sj ; wj ) 2 t T L1( ; At ; IP ; IR ) ;
2 =1

(15) (16) (17)

0 0
lj

t

smax ; 0 j

wj

t

wjmax; t = 1; : : : ; T;
lj
0

t

ljmax ; ltj = ltj? ? stj +

t j wj ;

t = 1; : : : ; T;
0

= ljin;

lj

T

= ljend :

)

In this problem the storage volume variable ltj plays the role of a resource state variable, which means that the variables for t > t and t < t do not in uence each other when ltj for t = t is xed. The equation (17) describing the dynamics of the system is one-dimensional. Hence, the storage volume can be increased and decreased using w and s, respectively. The costs of changing the storage volume, i.e., t0 ( wt0 ? st0 ), have to be compared with the changes of costs in all subsequent j j time periods, i.e., T X t ( wt ? st )]; (18) I E j j
0 0

to nd out whether an alteration of the storage volume leads to a decrease of the objective function or not. If such a change of the storage volume ltj in any node does not lead to a decrease of the objective function, then the current point is optimal. The subsequent costs are caused by changes of variables in the subtree in order to satisfy the balance (17). Since the problem has a special structure, elements ( stj ; wjt ) yielding a minimal value of (18) have many zero components. In 27] it is shown that the search for descent directions may be restricted to such elements. Moreover, the non-zero components describe a subtree of the scenario tree. Then, the conditions on step lengths and on steps to be descent directions take simpler forms. The construction of these subtrees is done in a systematic way starting at 9

t=t0 +1

Capacity bound reached

Descent direction 45
20 10 15 35 30 60 40

80

60

40

50

70

25
14 17

35

15

Figure 4: Example of a simple descent direction the leaves and determining which nodes should be leaves in such subtrees. This is explained next. Figure 4 shows an example with 4 scenarios having identical probabilities (i.e. ) and 7 stages. The small numbers at the nodes represent the values t . The subtree mentioned above is marked with thick arrows (starting at the node with value 10, ending at nodes with 60, 70, 35, and 15). For the moment and without loss of generality we assume that j = 1, thus there is just one variable x for changing the storage volume. To simplify the presentation, we take up the position of the storage operator. Then, the -values represent prices for buying and selling a certain commodity, and the aim is to maximize the pro t. In addition, increasing and decreasing the storage volume by a certain amount could be understood as buying and selling a certain amount, respectively. Assume that a certain amount is bought at the second stage to a price of 10. The price paid at this node has to be compared with the gain from selling the amount at some nodes in the subtree in order to keep the balance (17). Each node in the subtree is examined in order to determine whether the amount should be sold at this node or should be kept for the subsequent nodes. If the amount is kept up to the last stage, it has to be sold in any case. In our example, the gain is 15 in the lowest scenario. If this happens, the amount is also sold at the last stage of the second lowest scenario due to the stochastic nature of the problem. Hence, the gain is 35. The average gain of these two scenarios is 25, shown at the lowest inner solid surrounding. The comparison of this average gain with the price at the node before, i.e. 17, leads to the decision to keep the amount up to the last stage. Hence, it follows that the gain of selling the amount at this node or later is 25. This is denoted by a surrounding with a dotted line, indicating that it has the same value as the inner one. The decision at the node before, i.e., the result of the comparing the value of the surrounded
1 4

10

subtree (25) with the value at the node (14), leads to the same decision (to keep the amount) except for the fact that, at this point, it is out of interest at which node the amount is actually sold. In the last but one stage of the second scenario the comparison of the value for the last stage (60) with the one of the stage before (70) yields the decision to sell the amount at that node, i.e. at the last but one stage. The uppermost scenario indicates the case where keeping up to the last stage is not feasible due to capacity bounds. Hence, the comparison leads to selling at the node with value 60. Applying the same analysis to all nodes yields where the amount should be kept and where it should be sold in order to get maximal gain from buying at the second stage. A ow from the second stage to subsequent stages is associated with this maximal gain, which corresponds to a subtree denoted by thick arrows in Figure 4. Note that the leaves of this subtree correspond to nodes where the decision is selling. Further, these decisions are independent of the node at which this subtree starts. In case the storage is not empty at the rst stage, it is also feasible to sell rst and to buy back the amount later. However, this can be treated in a similar way and leads to a second set of binary decisions. After this analysis has been applied to all nodes of the scenario tree, a descent direction examining all nodes just once can be found. For technical details of this method and for the case of j 6= 1 the reader is referred to 27]. Here, we only sketch the conditions on the existence of a descent direction. The variables and decisions for the case of an increased storage are denoted by the superscript up, while down refers to the case of a decreased storage. The decision to reduce the storage is denoted by bup = 1, whereas bup = 0 refers to the decision to keep it. Similarly, the notations k k bdown = 1 and bdown = 0 are used. Let k be the probability and Succ(k) the set of k k all successors of the node k, and introduce the following auxiliary variables: dup and ddown denote upper bounds for the step length: k k

dup = k ddown k

(

if bdown = 1 : k = minfl?; xk ; k min 2Succ k ddown g; if bdown = 0 k
( )

( max x

xk ? xmin ; if bup = 1 k minflmax ? lk ; min 2Succ k dupg; if bup = 0 k
( )

up down rk and rk denote the best average values for the subtrees: up rk = down rk
(

=

(

k ; P k up 2Succ(k) r ;

if bup = 1 k if bup = 0 k if bdown = 1 : k if bdown = 0 k

k ; P k down; 2Succ(k) r

11

Now, the conditions on the existence of a descent direction, to which a subtree starting at node k is associated, read: up Case of increasing the level: minfxmax ? xk ; dupgf k k + rk g 0 ; (19) k down Case of decreasing the level: minfxk ? xmin ; ddowngf k k + rk g 0 : (20) k Having these conditions in mind, the algorithm can be outlined as follows: Step 1: Input and initialization; Step 2: Determine a feasible point; up up down at all nodes; Step 3: Compute dk , ddown , rk , and rk k Step 4: Search for the node (root of the subtree) with the steepest descent; unless it can be found, then the current iterate is optimal ! STOP; Step 5: Update xk and lk at all nodes; Step 6: Goto Step 3.
50 45 40 35

computing time[s]

30 25 20 15 10 5 0 0 50000 100000 scenarios 150000 200000 250000

Figure 5: Computation times s] of EXCHA This descent algorithm EXCHA was implemented and tested for the case of j < 1. Each step of the algorithm requires only a few elementary computations, and in each step some variable attains an upper or lower bound. Hence, the algorithm is very e cient, as can also be seen in Figure 5, where the computing times in seconds of EXCHA on an HP-workstation are shown for a stochastic hydro storage problem with T 18 and binary trees branching at all time periods with numbers of scenarios ranging up to 200.000. Notice that, in case a sequence of such problems with slightly di erent dual variables has to be solved, the last iterate of the previous problem can be used as the next initial point. 12

3.2 Stochastic Dynamic Programming

The subproblem (21) - (22), that corresponds to the thermal unit i, is a mixedinteger multi-stage stochastic program. But, since the inner minimization with respect to the one-dimensional continuous variable pti can be carried out explicitly by examining the kinks of the fuel costs FCi, it reduces to a combinatorial multistage stochastic program:

Di( ; ) = minf (min FCi(pti ; uti ) ? ( t ? t ) pti] ? u p
i

T X t=1

t i

t ut pmax + SC t (u )) : i i i i

(21)

dynamic programming algorithm to stochastic programs, the state space is extended by including the recent history such that minimum up/down-times and start-up costs depend just on the current and the previous state. Figure 6 shows a part of the state transition graph of a thermal unit having a minimum up-time of 6 hours, a minimum down-time of 5 hours, and a cooling down time of 8 hours. It shows possible and feasible transitions on some xed arc of the scenario tree, where the arrows refer to feasible transitions. From now on, the index i of the ( xed) thermal unit is omitted.
6 5 4 3 2 1 1 2 3 4 5 6 7 8

t pmax ; t = 1; : : : ; T; (u ; p ) 2 T L1 ( ; A ; IP ; IR2 )g : (22) i i t i t=1 The start-up costs SCit(ui ) depend on the components ui of ui , = t; t ? 1; : : : ; t ? c c i , where i is the time the unit i needs to cool down. In order to apply the
ui

t pmin i

pi

t

ui

t

t+1

min-up-time

Online

min-down-time

Offline
cool-time

Figure 6: Transition graph for 2 time periods
d ~ Let t(s) denote the node weight at time t and state s and SC (s; s) the arc weight for the arc from state s to state s in the state transition graph. The node weights ~

13

are equal to 0 for o -line states s and correspond to the linearly perturbed fuel costs for on-line states s, i.e., min p pmax g : (23) t (s) = minfFC (p; 1) ? ( t ? t )p : p p
d ~ The arc weights SC (s; s) describe start-up costs for the thermal unit. They are independent of and , and are non-zero only for arcs leading from o -line states to on-line states. The cost-to-go functions are given as

t (s)

t (s) = t (s) + IE

Having the formula for the costs-to-go, the dynamic programming algorithm can be applied. As each node of the scenario tree is considered only twice, the algorithm is reasonably fast. For one thermal unit, one load scenario, and one week with an hourly discretization the algorithm needs just 40 milliseconds on an HP-workstation. We consider the minimization of a convex function f on a nonempty closed convex set X in IRn and assume that the optimal set X is nonempty and we can compute f (x) and a subgradient g(x) 2 @f (x) for each x 2 X . The proximal bundle method 19, 21] generates a sequence (xk ) in X converging to some element of X , and trial points yk 2 X starting with y = x for evaluating subgradients g(yk) of f and its polyhedral lower approximation n o (25) f~k (x) = max f (yj )+ < g(yj ); x ? yj > ; j 2J k
1 1 +1 +1 2

d ~ minfSC (s; s) + s
~

s t+1 (~)gjAt

:

(24)

3.3 Proximal Bundle Method

where J k is a subset of f1; :::; kg. In the iteration k the next trial point yk is selected by 1 yk 2 arg minff~k (x) + 2 uk kx ? xk k : x 2 X g (26) where uk is a proximity weight. A descent step to xk = yk occurs if f (yk ) f (xk ) + vk , where 2 (0; 1) is xed and vk = f~k (yk ) ? f (xk ) 0. If vk = 0, then xk is optimal. Otherwise, a null step xk = xk improves the next polyhedral function f~k . Strategies for updating uk and choosing J k are discussed in 19, 21]. The method is implemented such that the cardinality of J k is bounded (by some natural number NGRAD) and that it terminates if ?vk is less than a given (relative) optimality tolerance. This technique is applied to solve the dual stochastic problem (13) by putting f = ?D and X = IR N , where N is the number of nodes of the load scenario tree. Our computational experience with the proximal bundle code NOA 3.0 ( 20]) for solving (13) is very encouraging (cf. Section 4). In our test runs, for instance, NOA 3.0 applied to solving (13) performed in 300 iterations as good as a standard subgradient method (with step lengths k ) in 10.000 iterations.
+1 +1 +1 +1 +1 +1 2 + 1

14

After having solved the dual stochastic program (13) we obtain a lower bound to the optimal costs of the power scheduling model in Section 2, and together with the optimal ( ; ) we have scheduling decisions (u; p; s; w). In general, however, the scheduling decisions violate the load and reserve constraints (4) and (5). In the following, we describe a technique for determining a feasible approximate solution for the optimal rst-stage decision of the multi-stage stochastic power scheduling problem. Since this technique starts from the available dual information ( ; ), it is called Lagrange heuristics as in the deterministic setting. In a rst step, the mean value functions of the (discrete-time) stochastic processes d (load), r (reserve), l (storage volumes), and are computed. Clearly, they coincide with their realizations (scenarios) during all time periods belonging to the rst stage. Next, generation and pumping decisions, sj and wj , are determined from the constraints (2), where lj is replaced by its expectation IE lj ]. Furthermore, on/o decisions ui are computed by dynamic programming as solutions of the thermal subproblems (21), where the stochastic multipliers and are replaced by their expectations = IE ] and = IE ], respectively. For one of the test runs explained in Section 4, Figure 7 shows the results after the rst step of the heuristics: the mean load and reserve curves IE dt ] and IE rt], the hydro generaload thermal generation storage plants reserve reserve diff

3.4 Lagrange Heuristics

high

medium

low

Load
gen. mode

0 pump mode

0

20

40

60

80 100 Time periods

120

140

160

Figure 7: Schedules after averaging 15

tion andP pumping curves PJ stj and PJ wjt , and the reduced mean load curve j j J t I dt ] ? j (st ? wj ) for t = 1; :::; T . Furthermore, it shows that the reserve conE j straint (28) is violated e.g. during 1 t 12 and 110 t 168. In order to nd scheduling decisions (u; p; s; w) that are feasible for the reserve constraint (28), the schedules of the pumped hydro storage and the thermal plants are modi ed during the next two steps. The second step consists in applying a water rescheduling procedure, which is taken from 9]. Its idea is to reduce the value
=1 =1 =1

I d E

J t ] + IE rt ] + X(wt ? st ) j j j =1 J t ] + IE rt ] + X(wt ? st ) j j j =1

(27)

by modifying the schedule of the hydro plants if the (modi ed) reserve constraint
I X t max ui pi i=1
I d E

(28)

is violated at time t and the value (27) is the largest in a certain set of neighbouring time intervals. In the third step, the hydro schedules are kept xed and binary variables uti satisfying the reserve constraint (28) are determined by the algorithm described in 40]. Its main idea consists in determining the time t, where the constraint (28) is violated the most, and in computing the necessary increase of t to switch on (by dynamic programming) just as many thermal units as needed to satisfy (28). This procedure is repeated until the reserve constraint (28) is satis ed in all time intervals. Since this technique does not distinguish between identical units which appear in real-life power generation systems quite often, the start-up costs of such units are slightly modi ed. In our computational experiments this modi cation led to improved computational results (cf. Section 4). Altogether, the Lagrange heuristics takes the following form: Step 1 Determine the mean values of d, l, and , Step 2 Use the hydro plants as in 9] to reduce - the violation of the reserve constraints, - the di erence between maximal and minimal thermal load, Step 3 Search for a reserve feasible schedule by the procedure in 40] after having modi ed start-up costs for identical units.

3.5 Economic Dispatch Algorithm

The Lagrange heuristics ends with a binary schedule uti for the thermal units such that a feasible schedule (u; p; s; w) exists for the original power optimization problem in Section 2 when replacing the stochastic load d and reserve r by their expected values. In a nal step, a cost-optimal schedule (p; s; w) is determined for xed u by 16

solving the corresponding primal problem, in which the start-up costs are xed and, hence, negligible. The aim of this section is to develop an algorithmic approach for solving this economic dispatch problem. The approach also applies to multi-stage stochastic power scheduling models with xed stochastic binary decisions u. Since this may be of independent interest, we consider the model:
(

min p;s;w

(

The stochastic program (29)-(34) has the same structure as (15)-(17) except for the appearance of thermal units. This motivates the idea to apply the same technique as in Section 3.1. Thermal units and storage plants are coupled by the constraints (33). Moving the sum PJ (stj ? wjt ) to the right-hand side in (33) and taking the rightj hand side as a parameter, the optimization problem (29), (30), (33) decomposes into parametric programs for each time period t and scenario !. Denoting the parameter by v the parametric programs are of the form:
=1

i=1 t=1 pmin pti pmax; t = 1; : : : ; T; i = 1; : : : ; I; if uti = 1 i i t smax ; 0 wt wmax ; 0 lt lmax ; 0 sj j j j j j t = lt?1 ? st + wt ; t = 1; : : : ; T; l0 = lin ; lT = lend ; j = 1; : : : ; J; lj j j j j j j j j J I X t X t (sj ? wjt ) dt ; t = 1; : : : ; T; pi + j =1 i=1 ) I X t max t ) rt ; t = 1; : : : ; T (ui pi ? pi : i=1
) =1

I E

I T XX

FCi(pti ; uti) : (p; s; w) 2 t L1( ; At; IP ; IRI

T

+2

J) ;

(29) (30) (31) (32) (33) (34)

Pt;! (v) : minf FCi(pti; uti (!)) : p
t

I X i=1

I X t pi i=1

v ; uti (!)pmin pti i

ui

t (! )pmax g : i

(35)

Such programs were studied in 4, 5] for piecewise linear and quadratic fuel costs and, viewed as parametric programs, in 22] for the case of (piecewise) quadratic costs. The solution method for Pt;! (v) starts with all units at their minimum output level. Then, a priority list is used to determine in which order the units have to increase their output level until the parameter v 2 PI uti (!)pmin ; PI uti (!)pmax ? rt(!)] i i i i is met. The priority list can be built beforehand, and then used for all time periods. Denoting the optimal value function of Pt;! (v) by t;! (v), the objective function (29) reads J T X t X t t (36) min IE t; : (d ? (sj ? wj )): s;w
=1 =1 ( )

The objective function (36) now has to be minimized with respect to the constraints (31) - (32). This reformulation of the model allows to study how the objective function varies when altering the operation of the hydro plants. Since the linearization 17

t=1

j =1

of the model (36), (31)-(32) coincides with the problem (15)-(17), the search for descent directions of the objective function can be done in the same way as in Section 3.1. The place of the dual parameter is now taken by the derivative of t;! ( : ) if it exists. This leads to T J X t t X (wj ? stj ) ; (37) min IE s ;w where
t

is de ned by

j =1 (

j

j)

t=1

t

t; = ddv : (dt ?

J X t (sj j =1

? wjt )) :

(38)

The calculation of step-lengths has to take care of the structure of t;! ( : ), i.e., steps should not go further than the next kink of t;! ( : ). In non-di erentiability points of t;! ( : ) directional derivatives have to be used instead. Then, the determination of descent steps has to deal with several cases. Another possibility consists in smoothing the function t;! (v) and in reducing the smoothing intervals as the number of iterations increases. This descent method was coded, tested and compared with Pricing strategy primal/dual -1 0 1 2 3 4 Simplex/primal 1232.4 1188.4 1918.1 2664.1 2440.7 1696.9 Simplex/dual 1086.1 946.2 1103.4 1466.5 1083.8 baropt 94.78 hybbaropt/primal 114.7 114.3 114.3 486.5 114.4 114.3 hybbaropt/dual 115.0 114.6 693.0 1424.8 114.8 hybnetopt/primal 957.6 910.3 1298.0 2252.8 1960.9 1162.6 hybnetopt/dual 1393.8 1253.7 1412.0 1833.9 1392.3 Table 1: Computing times s] for di erent CPLEX-functions and options CPLEX-function

CPLEX 4.0. Test runs of our code ECDISP were performed for the VEAG system

with 25 thermal units and 7 pumped hydro storage plants. Table 1 contains results for a test example with one load scenario and 192 time periods, which is equivalent to an LP with 14200 columns, 17856 rows, and 46256 non-zeros. The table shows computing times of CPLEX 4.0 on a SPARCstation IPX (4/50) with 64 MB main memory and 40 MHz, which have to be compared with the ECDISP computing time of 50.95 seconds. Since the barrier method performs signi cantly better than the simplex method, and even better than the network simplex method, further comparisons were made with the barrier method only. Table 2 contains results for test problems with T = 192 and up to 22 scenarios. CPLEX 4.0 ran out of memory for problems with a higher number of scenarios. The advantage of using ECDISP ranges from 1.8 up to 18.7, and in average ECDISP is 5-6 times faster. The Figures 18

scen's 3 5 7 9 11 13 15 17 19 21 22

nodes columns rows non-zeros ECDISP s] CPLEX s] 336 24840 31248 80944 18.69 97.61 462 34148 42966 111294 29.48 162.47 588 43456 54684 141644 47.93 206.00 687 50766 63891 165487 43.09 305.43 792 58520 73656 190776 67.17 500.30 930 68716 86490 224018 86.73 461.54 1035 76470 96255 249307 98.04 569.18 1036 76528 96348 249532 117.42 620.65 1120 82728 104160 269760 91.63 1720.33 1232 91000 114576 296736 131.94 243.27 1260 93064 117180 303476 128.18 794.93 Table 2: Comparison of ECDISP with CPLEX

adv' 5.22 5.51 4.30 7.09 7.45 5.32 5.81 5.29 18.7 1.84 6.20

8 and 9 show that the number of steps and the computing times of ECDISP grow almost linearly with respect to the number of scenarios.
200000 steps 180000 160000 140000 120000 100000 80000 60000 40000 20000 0 0 0 50 100 150 200 250 300 350 400 450 500 500 1000 1500 2000 2500 time

Figure: 8: Number of steps versus number of scenarios

Figure: 9: Computing times s] versus number of scenarios

0

50

100

150

200

250

300

350

400

450

500

4 Numerical Results
The stochastic Lagrangian relaxation algorithm described in the previous section has the following structure: Step 1: Input and initialization Step 2: Solve the dual problem by the proximal bundle method (Sect. 3.3) Step 2.1: Solve the thermal unit subproblems by stochastic dynamic programming (Sect. 3.2) Step 2.2: Solve the storage subproblems by a descent algorithm (Sect. 3.1) Step 3: Apply the Lagrange heuristics (Sect. 3.4) 19

Step 4:

Solve a nal economic dispatch problem (Sect. 3.5) The algorithm was implemented and coded in C++ except for the proximal bundle method where the FORTRAN-package NOA 3.0 ( 20]) was used as a callable library. For testing the implementation, a test bunch of load scenario trees was generated as follows. The tree structure was built by generating scenarios successively from randomly chosen base scenarios and branching points. Each load scenario was generated by adding a (discretized) Brownian motion to a reference load process obtained from real-life data of the utility VEAG. In a nal step, randomly chosen probabilities were assigned to each scenario. Test runs were performed for the hydro-thermal power generation system of VEAG comprising 25 thermal units and 7 pumped storage plants on an HP 9000 (780/J280) Compute-Server with 180 MHz frequency and 768 MByte main memory under HP-UX 10.20. Nr.
opt.tol: 10?3 opt.tol: 10?4 gap/% time/s gap/% time/s gap/% time/s gap/% time/s opt.tol: 10?3

modi ed cost functions

opt.tol: 10?4

original cost functions

1 0.18 34.08 0.10 89.84 0.67 31.32 0.56 86.24 2 0.25 47.82 0.12 109.92 0.60 42.67 0.61 100.07 3 0.43 44.81 0.26 111.75 0.44 35.10 0.25 102.61 4 0.34 53.86 0.14 119.84 0.94 47.40 0.96 115.55 5 0.20 78.42 0.11 157.31 0.98 73.76 0.93 151.64 6 0.27 41.24 0.19 85.12 1.23 34.09 1.13 80.42 7 0.39 39.52 0.11 88.35 0.66 37.42 0.54 79.88 Table 3: In uence of modi ed costs and of bundle method optimality tolerances on the gap and computing times. For test runs with 10 scenarios Table 3 shows the in uence of modifying the start-up costs and of changing the optimality tolerance of the bundle method on the gap and computing times. It shows that a (slight) modi cation of start-up costs of former identical units leads to smaller gaps. Here, the gap refers to the (relative) di erence of the costs for the primal feasible (approximate) solution and the optimal value of the dual stochastic problem. Moreover, improving optimality tolerances leads to smaller gaps paid by increased computing times. Figure 10 provides the nal output of the algorithm and contains, in particular, the approximately optimal rst-stage solution for the total thermal and hydro generation (for the time periods t = 1; : : : ; 24). Table 4 shows how the computing time grows with increasing numbers of scenarios. Since the complexity of the model is higher compared to the stochastic programs in Sections 3.1 and 3.4, the variance of the computing time is larger than the variances expressed in the Figures 5 and 9. The reason is that the iteration numbers in the bundle method, in the method for 20

Scenarios Nodes time s]/gap %] 10 781 31.2 / 0.274 10 1232 50.36 / 0.201 20 1982 89.13 / 0.149 20 1651 67.94 / 0.367 30 2643 139.71 / 0.528 30 2548 147.51 / 0.849 50 4530 475.29 / 0.175 50 4041 312.86 / 0.099 80 7190 804.04 / -0.018 80 6548 537.28 / 0.137 100 9230 1183.25 / 0.108 100 7727 929.68 / 0.087

Nodes 1043 975 1627 1805 2643 2515 4060 4457 7120 6501 9224 8867

time s]/gap %] 52.93 / 0.138 54.21 / 0.723 93.62 / 0.101 84.73 / 0.066 138.61 / 0.528 162.14 / 0.175 274.43 / 0.096 288.03 / 0.430 698.19 / 0.379 597.04 / 0.114 1072.18 / 0.131 1234.12 / 0.304
3

Table 4: Computing times and gaps (NOA 3.0: Opt:tol = 10? ; NGRAD = 50)

high

load thermal generation storage plants reserve reserve diff

medium

low

Load
gen. mode

0 pump mode

0

20

40

60

80 100 Time periods

120

140

160

Figure 10: Approximate solution 21

searching a reserve feasible solution and in the economic dispatch solver depend on the input data in a very involved way. Another observation is that the gap seems to be independent of the number of scenarios.

5 Conclusions
We have elaborated a mixed-integer multi-stage stochastic programming model for power scheduling in a hydro-thermal generation system under uncertainty on the electrical load. Due to the huge size of the model, an application of state-of-the-art mixed-integer LP solvers is prevented. Therefore, we have developed a novel approach based on stochastic Lagrangian relaxation of coupling constraints. It consists of proximal bundle iterations for solving a stochastic dual followed by a Lagrange heuristics to determine a nearly optimal primal rst-stage solution. The stochastic dual decomposes into stochastic thermal and hydro subproblems, which are solved by speci c fast algorithms. Our computational experience indicates that the stochastic Lagrangian relaxation algorithm is able to produce good approximate rst-stage solutions for medium-size realistic power systems and 20 (100) load scenarios within less than 2 (20) minutes on a modern HP-workstation. It also indicates that the algorithm bears potential for solving more complex real-life power scheduling models under uncertainty in reasonable time.

Acknowledgement
The authors are grateful to K.C. Kiwiel (Polish Academy of Sciences, Warsaw) for the permission to use the NOA 3.0 package, to Darinka Dentcheva (Humboldt-University Berlin) for useful discussions on the Lagrange heuristics described in Section 3.4 and to G. Schwarzbach and J. Thomas (VEAG Vereinigte Energiewerke AG, Berlin) for providing us with the data used in our test runs. This research was supported by the Schwerpunktprogramm Echtzeit-Optimierung gro er Systeme of the Deutsche Forschungsgemeinschaft and the Graduiertenkolleg Geometrie und Nichtlineare Analysis at the Humboldt-University Berlin.

References
1] D.P. Bertsekas, G.S. Lauer, N.R. Sandell Jr. and T.A. Posbergh: Optimal short-term scheduling of large-scale power systems, IEEE Transactions on Automatic Control AC-28(1983),1-11. 2] J.R. Birge: Stochastic programming computations and applications, INFORMS Journal on Computing 9 (1997), 111-133.

22

3] J.R. Birge and F. Louveaux: Introduction to Stochastic Programming, Springer, New York 1997. 4] P.P.J. van den Bosch: Optimal static dispatch with linear, quadratic and nonlinear functions of the fuel costs, IEEE Transactions on Power Apparatus and Systems PAS-104 (1985), 3402-3408. 5] P.P.J. van den Bosch and F.A. Lootsma: Scheduling of power generation via largescale nonlinear optimization, Journal of Optimization and Applications 55(1987), 1684-1690. 6] C.C. Car e and R. Schultz: Dual decomposition in stochastic integer programming, Preprint SC 96-46, Konrad-Zuse-Zentrum fur Informationstechnik Berlin, 1996 and to appear in Operations Research Letters. 7] C.C. Car e and R. Schultz: A two-stage stochastic program for unit commitment under uncertainty in a hydro-thermal power system, DFG-Schwerpunktprogramm Echtzeit-Optimierung gro er Systeme, Preprint 98-13, 1998. 8] P. Carpentier, G. Cohen, J.-C. Culioli and A. Renaud: Stochastic optimization of unit commitment: a new decomposition framework, IEEE Transactions on Power Systems 11(1996), 1067-1073. 9] D. Dentcheva, R. Gollmer, A. Moller, W. Romisch and R. Schultz: Solving the unit commitment problem in power generation by primal and dual methods, in: Progress in Industrial Mathematics at ECMI 96 (M. Br ns, M.P. Bends e and M.P. S rensen Eds.), Teubner, Stuttgart 1997, 332-339. 10] D. Dentcheva and W. Romisch: Optimal power generation under uncertainty via stochastic programming, in: Stochastic Programming Methods and Technical Applications (K. Marti and P. Kall Eds.), Lecture Notes in Economics and Mathematical Systems Vol. 458, Springer-Verlag, Berlin 1998, 22-56. 11] S. Feltenmark and K.C. Kiwiel: Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems, Report TRITA/MAT-98-OS1, Department of Mathematics, Royal Institute of Technology, Stockholm, January 1998, revised November 1998 and submitted to SIAM Journal on Optimization. 12] S.-E. Fleten, S.W. Wallace and W.T. Ziemba: Portfolio management in a deregulated hydropower based electricity market, in: Hydropower' 97 (E. Broch, D.K. Lysne, N. Flatab and E. Helland-Hansen Eds.), Balkema, Rotterdam 1997. 13] A. Gjelsvik, T.A. R tting and J. R ynstrand: Long-term scheduling of hydro-thermal power systems, in: Hydropower '92 (E. Broch and D.K. Lysne Eds.), A.A. Balkema, Rotterdam 1992, 539-546. 14] R. Gollmer, A. Moller, W. Romisch, R. Schultz, G. Schwarzbach and J. Thomas: Optimale Blockauswahl bei der Kraftwerkseinsatzplanung der VEAG, in: Optimierung in der Energieversorgung II, VDI-Berichte 1352, Dusseldorf 1997, 71-85.

23

15] N. Growe, W. Romisch, R. Schultz: A simple recourse model for power dispatch under uncertain demand, Annals of Operations Research 59(1995), 135-164. 16] J.L. Higle and S. Sen: Stochastic Decomposition - A Statistical Method for Large Scale Stochastic Linear Programming, Kluwer, Dordrecht 1996. 17] G. Infanger: Planning Under Uncertainty - Solving Large-Scale Stochastic Linear Programs, Boyd and Fraser, 1994. 18] J. Jacobs, G. Freeman, J. Grygier, D. Morton, G. Schultz, K. Staschus and J. Stedinger: SOCRATES: A system for scheduling hydroelectric generation under uncertainty, Annals of Operations Research 59(1995), 99-133. 19] K.C. Kiwiel: Proximity control in bundle methods for convex nondi erentiable optimization, Mathematical Programming 46(1990), 105-122. 20] K.C. Kiwiel: User's Guide for NOA 2.0/3.0: A Fortran package for convex nondifferentiable optimization, Polish Academy of Sciences, Systems Research Institute, Warsaw (Poland), 1993/94. 21] K.C. Kiwiel: Approximations in proximal bundle methods and decomposition of convex programs, Journal of Optimization Theory and Applications 84(1995), 529548. 22] P. Kleinmann and R. Schultz: A simple procedure for optimal load dispatch using parametric programming, ZOR - Methods and Models of Operations Research 34(1990), 219-229. 23] C. Lemarechal: Lagrangian decomposition and nonsmooth optimization, in: Nonsmooth Optimization Methods and Applications (F. Gianessi Ed.), Gordon and Breach 1992, 201-216. 24] C. Lemarechal and A. Renaud: Dual equivalent convex and nonconvex problems, Research Report, INRIA, Rocquencourt 1996 and submitted to Mathematical Programming. 25] A. L kketangen and D.L. Woodru : Progressive hedging and tabu search applied to mixed integer (0,1) multi-stage stochastic programming, Journal of Heuristics 2(1996), 111-128. 26] V.I. Norkin, G. P ug and A. Ruszczynski: A branch and bound method for stochastic global optimization, Mathematical Programming 83(1998), 425-450. 27] M.P. Nowak: A fast descent method for the hydro storage subproblem in power generation, International Institute for Applied Systems Analysis (Laxenburg, Austria), Working Paper WP-96-109, 1996.

24

28] M.P. Nowak and W. Romisch: Optimal power dispatch via multistage stochastic programming, in: Progress in Industrial Mathematics at ECMI 96 (M. Br ns, M.P. Bends e and M.P. S rensen Eds.), Teubner, Stuttgart 1997, 324-331. 29] M.V.F. Pereira and L.M.V.G. Pinto: Multi-stage stochastic optimization applied to energy planning, Mathematical Programming 52(1991), 359-375. 30] A. Renaud: Optimizing short-term operation of power generation: a new stochastic model, Lecture presented at the VIII International Conference on Stochastic Programming, Vancouver (Canada), August 1998. 31] R.T. Rockafellar and R.J.-B. Wets: The optimal recourse problem in discrete time: L1 -multipliers for inequality constraints, SIAM Journal on Control and Optimization 16(1978), 16-36. 32] R.T. Rockafellar and R.J.-B. Wets: Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research 16(1991), 119-147. 33] W. Romisch and R. Schultz: Decomposition of a multi-stage stochastic program for power dispatch, ZAMM - Zeitschrift fur Angewandte Mathematik und Mechanik 76(1996) Suppl.3, 29-32. 34] A. Ruszczynski: Decomposition methods in stochastic programming, Mathematical Programming, Series B, 79(1997), 333-353. 35] G.B. Sheble and G.N. Fahd: Unit commitment literature synopsis, IEEE Transactions on Power Systems 9(1994), 128-135. 36] S. Takriti, J.R. Birge and E. Long: A stochastic model for the unit commitment problem, IEEE Transactions on Power Systems 11(1996), 1497-1508. 37] S. Takriti, B. Krasenbrink and L.S.-Y. Wu: Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem, IBM Research Report RC 21066, Yorktown Heights, New York 1997. 38] R. J.-B. Wets: Stochastic Programming, in: it Handbooks in Operations Research and Management Science, Vol. 1, Optimization (G.L. Nemhauser, A.H.G. Rinnooy Kan, M.J. Todd Eds.), North-Holland, Amsterdam 1989, 573-629. 39] A.J. Wood and B.F. Wollenberg: Power Generation, Operation, and Control (Second Edition), Wiley, New York 1996. 40] F. Zhuang and F.D. Galiana: Towards a more rigorous and practical unit commitment by Lagrangian relaxation, IEEE Transactions on Power Systems 3(1988), 763-773.

25


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图