Abstract

Lagrangian relaxation has been widely used for the hydrothermal scheduling of power systems. The idea is to use Lagrangian multipliers to relax system-wide demand and reserve requirements, and decompose the problem into unit-wise subproblems that are much easier to solve. The multipliers are then updated at the high level, most commonly by using a subgradient method (SGM). Since the high level dual function is non-differentiable with many "ridges," SGM may zigzag across ridges resulting in slow convergence. This paper presents an algorithm that utilizes a recently developed ìreduced complexity bundle methodî (RCBM) to update the multipliers at the high level. The RCBM is a kind of ìbundle methodî that enjoy faster convergence compared to SGM, but has much reduced complexity as compared to a conventional bundle method. Testing results show that RCBM can find better directions, avoid zigzagging behavior, and obtain better dual and feasible solutions as compared to the SGM.

1. Introduction

Lagrangian Relaxation for Hydrothermal Scheduling

Hydrothermal scheduling is concerned with the commitment and dispatch of generating units. The objective is to minimize the total generation cost over a period of up to one week, subject to system-wide demand and reserve requirements and individual unit constraints. This mixed integer programming problem is believed to be NP-hard where the computational requirements for obtaining an optimal solution grow exponentially as the problem size increases. Lagrangian relaxation has been successful for obtaining near-optimal solutions with quantifiable quality. The basic idea is to use Lagrangian multipliers to relax system-wide demand and reserve requirements, and decompose the problem into unit-wise subproblems. The multipliers are then updated at the
 
 
 
 
 
 
 
 
 
 

high level, mostly by using a subgradient method (SGM) [1, 2, 3]. Since dual solutions are usually infeasible, heuristics are then used to obtain a feasible schedule.

Shortcomings of Subgradient-Type Methods

Given the current set of multipliers, the SGM sets the search direction to be one of the subgradients. This is computationally simple. However, since the dual function is non-differentiable with many "ridges," the SGM may cause the multipliers to zigzag across ridges resulting slow convergence [4, 5]. The zigzagging behavior is demonstrated by the SGM trajectory in Fig. 1 for the example to be presented in subsection 4.1. Although techniques have been developed to address the slow convergence issue, including the modified subgradient method [6] and adaptive step-sizing techniques [7], the basic difficulties of subgradient-type methods have not been altered.

Necessity for an Efficient High Level Algorithm and the Reduced Complexity Bundle Method

The slow convergence of SGM is becoming a serious problem in view of the needs to solve larger and more complicated problems, e.g., mid-term scheduling, unit commitment with environmental and transmission capacity constraints [8, 9], power transaction problems [10], etc. For example, a large transaction with a constant MW price creates sharp ridges in the dual function, and makes the dual problem difficult to solve. An efficient high level algorithm that can generate high quality solutions in short CPU times is becoming critical to capture frequently emerging opportunities and to avoid crises in the increasingly deregulated power market.

The bundle method overcomes the slow convergence of subgradient-type methods for solving non-differentiable optimization problems [11]. However, finding a search direction becomes computationally intensive as the problem size increases. The recently developed Reduced Complexity Bundle Method (RCBM) maintains the convergence property while reducing the complexity of bundle method [12]. The method can thus be applied to problems of practical sizes such as the dual problem of hydrothermal scheduling.

Compared to SGM, RCBM adopts the subgradient direction only when it is good. Otherwise, it accumulates subgradiets in a "bundle," and finds a trial direction based on bundle elements. If the trial direction is "good," the method moves along the direction; otherwise, the bundle is updated, and the next trial direction is found. The trajectories generated by RCBM for the same example of subsection 4.1 is presented in Fig. 2. The zigzagging behavior of SGM has been eliminated.

In the following, problem formulation and solution methodology of a hydrothermal scheduling problem are presented in Section 2. The RCBM and its implementation for solving the dual problem are presented in Section 3. Results from extensive testing are presented in Section 4.

(1)

(2)

"o": initial point; "*": optimal point;

(i) the multiplier with respect to system demand at hour i ($/MW)

(1)

(2)

"o": initial point; "*": optimal point;

(i): the multiplier with respect to system demand at hour i ($/MW)

2. Problem Formulation and Solution Methodology

2.1 Problem Formulation

Consider a power system with I thermal units, J hydro units, and K pumped-storage units. The objective is to minimize the total generation cost. This minimization is subject to system-wide demand and reserve requirements, and individual unit constraints.

The objective function to be minimized is the sum of thermal generation costs  and start up costs , i.e.,

(2.1)

(2.1)

In the above,  is the generation of thermal unit i at time t,  the water released of hydro unit j,  the water released of pumped-storage unit k (negative for pumping), and T is the time horizon (e.g., T = 168 hours).

The system demand constraints require that the sum of all thermal generation , hydro generation , and pumped-storage generation  (negative for pumping) should equal the system demand  at each hour, i.e.,

t=1, ..., T, (2.2)

where  and  are water-power conversion functions for hydro unit j and pumped-storage unit k, respectively.

Reserve requirements states that the sum of reserve contributions of thermal units , hydro units , and pumped-storage units  should be greater than or equal to the reserve required  at each hour, i.e.,

,

t=1, ..., T. (2.3)

Individual thermal unit constraints include capacity and minimum generation, minimum up/down times, ramp rate, minimum generation for the first and last hour, and must-run and must-not-run. Individual hydro unit constraints include capacity and minimum generation, and available hydro energy. Individual pumped-storage unit constraints include pond level dynamics and limit constraints, and generation and pumping level constraints. The detailed descriptions have been presented in [2], [13], and [14], respectively.

2.2 Solution Methodology

2.2.1 The Relaxed Problem

Relaxing system-wide demand (2.2) and reserve requirements (2.3) by using Lagrange multipliers l and m, respectively, the following relaxed problem is formed:

(2.4)

2.2.2 Solving Subproblems

After re-grouping relevant terms, individual thermal, hydro, and pumped-storage sub-problems are formed, one for each unit. The resolution of these subproblems can be found in [2], [13] and [14], respectively.

2.2.3 The High Level Dual Problem

The dual problem is to update multipliers to maximize the dual cost (, ), i.e.,

with

(2.5)

where L is defined in (2.4). The dual problem will be solved by the RCBM to be presented in subsection 3.3.

2.2.4 Obtaining A Feasible Solution

The solutions of subproblems are usually associated with an infeasible schedule, i.e., system demand and reserve requirements may not be satisfied. Heuristic methods as presented in [2, 13 and 14] are used to adjust subproblem solutions to obtain a feasible schedule. Heuristics are performed at the end of each high level iteration after all subproblems are solved, except for the first few high level iterations. The feasible solution with the lowest cost is recorded as the scheduling decisions.

3. The Reduced Complexity Bundle Method

3.1 The Bundle Method (BM)

The bundle method emerged recently as a promising approach for maximizing non-smooth concave functions (e.g., [11]). It employs a concept called the "-subdifferential," defined as

,

(3.1)

which is an extension of the "subdifferential" concept. Elements in  are called -subgradients. Correspondingly, the -directional derivative along direction d at x is defined as

. (3.2)

It is shown that  [15, p. 102]. From (3.2), if a direction can be found such that , then the dual cost can be increased by at least . The bundle method thus sets the direction to be the one that maximizes the directional derivative, i.e.,

(3.3)

This d* is therefore the -subgradient with the smallest norm. The availability of only one subgradient at each point within the Lagrangian relaxation framework, however, implies the unavailability of the complete . Bundle method accumulates -subgradients of the current iterate in a bundle Bb, and approximate  by the convex hull  of bundle elements:

, (3.4)

where is the i-th element of the bundle with a total of b elements. A trial direction is then obtained as the element in  that has the smallest norm. This direction can be obtained by quadratic programming, however, the process can be computationally intensive as the size of the bundle increases.

1. Reduced Complexity Bundle Method (RCBM)

The minimum-norm direction obtained by BM can be viewed as the projection of the origin onto the convex hull . The RCBM sets the direction to be the orthogonal projection of the origin onto the affine manifold A(P

) containing , i.e.,

(3.5)

The orthogonal projection of the origin onto A(Pb) is equivalent to the projection of any bundle element onto the subspace normal to A(Pb), and can be efficiently performed by using Cholesky decomposition [12]. This direction maintains global convergence of the traditional bundle method, but is obtained with much reduced computational requirements than that required by quadratic programming. The method can thus be applied to problems of practical sizes such as maximizing the dual function of the power system scheduling problem.

3. 3 Implementing RCBM for the Dual Problem

Since dual function (, ) is concave according to [16, p. 423], RCBM can be used to maximize it. The subgradient g of (, ) is a 2T by 1 vector consisting of  and , where  and  are the subgradient of with respect to and , respectively. The t-th element of  is

, (3.6)

and the t-th element of  is

. (3.7)

At each high level iteration, RCBM first uses the subgradient as a trial direction. Line search is then performed, with only the following two possible outcomes [11, p. 213]:

1. The dual function can be increased by a pre-specified value , i.e.,

; (3.8)

where t is the step size. In this case, the next point will be set to ( + td, + td).

2. If the dual function cannot be increased by , the line search will find a subgradient belonging to the -subdifferential of (, ). This -subgradient is then added to the bundle, and a new trial direction is formed with the augmented bundle. The process then repeats till condition (3.8) is satisfied. The RCBM can now be summarized as follows.

Step 1: [Initialize Multipliers.] Initialize according to a priority-list commitment and dispatch. Initialize to zero. Solve individual subproblems as presented in subsection 2.2.2 and calculate the dual function (, ) and subgradient . Set iteration number iter = 1.

Step 2: [Initialize the Bundle.] Initialize the Bundle to  = { }. Set the number of bundle elements b = 1.

Step 3: [Set Direction.] If b = 1, set search direction d to be the subgradient direction; else, select d by projecting an arbitrary bundle element onto the subspace normal to A(Pb).

Step 4: [Test Convergence.] If  ( is a pre-specified stopping criterion), stop.

Step 5: [Perform Line Search and Run Heuristics.] Perform line search to find a step size t. Calculate the dual function (+td, +td) and the subgradients . If iter is greater than a pre-specified number, run heuristics and store the best feasible solution. If condition (3.8) is satisfied, go to Step 6; else go to Step 7.

Step 6: [Move to the Next Iterate.] Set = + td, = + td, , iter = iter + 1, then go to Step 2.

Step 7: [Augment the Bundle.] Add  to the bundle B, and set b = b + 1, then goes to Step 3.

4. Numerical Testing Results

The RCBM was implemented in C++ and the resolution of individual subproblems and heuristics were implemented in FORTRAN on a SUN Ultra Station 1.

4.1 Testing of a Small Example

A system with two thermal units is to be scheduled over two hours following [5]. Only system demand, unit minimum generation and capacity are considered. The minimum generation of unit is denoted as  and the capacity . The thermal cost  of the first unit is piece-wise linear with four equal size blocks, and  denotes the incremental cost of block m. The second unit has a single block. The parameters are listed below.

Parameters of the Two Units System

Thermal unit 1 parameters:

Thermal unit 2 parameters:

System demand at each hour:

.

The polyhedron dual function ((1), (2)) and its contour are plotted in Fig. 3. There are two ridges, one at (1) = 34, and the other at (2) = 34. The initial multipliers are set to = (13, 13), and the optimal dual solution is * = (34, 34) with f* = $8586.

The trajectory generated by SGM has been presented in Fig. 1. It can be seen that the trajectory zigzags across an ridge resulting in slow convergence. The trajectory generated by RCBM has been presented in Fig. 2. Initially, RCBM takes the subgradient direction to move to the point = (33.98, 19.56) by line search, which is near the ridge. At this point, the subgradient is not a good direction. Two subgradients, one at each side of the ridge, then forms the bundle, resulting a direction parallel to the ridge as shown in Fig. 4. Along this direction, RCBM moves to the point = (33.98, 34.05), and the algorithm stops in two high level iterations. Testing results are summarized in Table 1.

(1)

(2)

and  are two -subgradients.

4.2 Testing Results for Northeast Utilities Data Sets

In this testing, data sets from Northeast Utilities Service Company are used to compare the performance of RCBM vs. SGM in updating the multipliers. The methods for solving subproblems and the heuristics are kept identical. There are 65 thermal units, 7 hydro units, 1 large pumped-storage unit, and 2-10 schedulable contracts. The scheduling horizon is either 7 days (168 hours) or 8 days (192 hours). Detailed system characteristics can be found in [14]. Many practical considerations are included, and all the billing rules of New England Power Pool are satisfied. Results for the six 1994 data sets are summarized in Tables 2 and 3.

Although RCBM needs more function evaluations in coming up with a direction, the directions are generally good --resulting in significant reductions of the numbers of high level iterations. With very similar CPU times, RCBM can obtain higher dual costs. Higher dual costs generally correspond to lower feasible costs, resulting in better overall performance (although exceptions do exist as indicated by October Week 1 data). The average dual cost is increased by $4,450 per case, and the average feasible cost is decreased by $10,600 per case.

Fig.5 Dual Function Shape for Case 09, w2

To investigate the rationale behind the above RCBM performance improvement, the dual function for September Week 2 data set is plotted with respect to demand multipliers of hours 20 and 21 in Figure 5. It can be seen that the dual function is non-differentiable with many ridges, consistent with what was presented in Figure 3.

In another testing, one data set in 1996 is used as a base case. The load is first increased by 25MW for all the hours, and then by 100MW to generate two modified cases. These data sets have many transactions each with a single constant MW price block, making the dual problem difficult to solve. The feasible cost and duality gap obtained by SGM and RCBM are listed in Table 4. The CPU time are quite similar and are thus omitted. It can be seen that RCBM can constantly generate better results than what obtained by SGM.

5. Conclusion

This paper presents the application of RCBM for solving hydrothermal scheduling problems within the Lagrangian relaxation framework. Rationales for the performance improvement are intuitively explained and illustrated by examples. Testing results support the intuitive argument, and show that RCBM can avoid the zigzagging behavior of subgradient methods, obtain higher dual cost, and result in better overall performance.

Acknowledgment

This work was supported in part by the National Science Foundation under Grants ECS-9420972 and DMI-9500037, and by a grant from Northeast Utilities Service Company. The authors would like to thank Professor Xiaohong Guan of Xian Jiaotong University, P. R. China, for pointing out the concavity of the dual function. Valuable suggestions from Mr. Sen Lin and Mr. Guangyu Liu of UConn, Mr. Martin B. Gabris, Mr. Jim A. Palmberg and Mr. Carl Larson of Northeast Utilities, and three anonymous reviewers are greatly appreciated.

References

[1] Polyak, B.T., ìMinimization of Unsmooth Functionals,î USSR Computational Math. and Math. Physics, Vol. 9, 1969, pp. 14.

[2] Guan, G., P. B. Luh, H. Yan, and J. A. Amalfi, ìAn Optimization-Based Method for Unit Commitment,î Electric Power & Energy Syst. Vol. 14, 1992, pp. 9-17.

[3] Wang, S. G., S. M. Shahidehppour, D. S. Kirschen, S. Mokhtari, etc., ìShort-Term Generation Scheduling with Transmission and Environmental Constraints Using an Augmented Lagrangian Relaxation,î IEEE Transactions on Power Systems, Vol. 10, No. 3, Aug. 1995, pp. 1294-1301.

[4] Czerwinski, C. S., and P. B. Luh, ìScheduling Products with Bills of Materials Using an Improved Lagrangian Relaxation Technique,î IEEE Trans. on Robotics and Automation, Vol. 10, No. 2, April 1994, pp. 99-111.

[5] Guan, G., P. B. Luh and L. Zhang, ìNonlinear Approximation Method in Lagrangian Relaxation-Based Algorithms for Hydrothermal Scheduling,î IEEE Transactions on Power Systems, Vol. 10, No. 2, May 1995, pp. 772-778.

[6] Camerini, P., L. Fratta, F. Maffioli, ìOn Improving Relaxation Methods by Modified Gradient Techniques,î Mathematical Programming Study, 3, Amsterdam, 1975, pp. 26-34.

[7] Sandell, N. R. Jr., D. P. Bertsekas, J. J. Shaw, etc., "Optimal Scheduling of Large-Scale Hydrothermal Power Systems," Proceedings of the 1982 IEEE International Large-Scale Systems Symposium, Virginia Beach, Virginia, Oct. 1982.

[8] Shaw, J., ìA Direct Method for Security-Constrained Unit Commitment,î IEEE Transactions on Power Systems, Vol. 10, No. 3, August 1995, pp. 1329-1339.

[9] El-Kaib, A., H. Ma and J. Hart, ìEnvironmentally Constrained Economic Dispatch Using Lagrangian Relaxation Method,î IEEE Transactions on Power Systems, Vol. 9, No. 4, Nov. 1994.

[10] H. Yan, and P. B. Luh, A Fuzzy Optimization-Based Method for Integrated Power System Scheduling and Inter-Utility Power Transaction with Uncertainties, paper presented at 1996 IEEE Power Engineering Society Summer Meeting, Denver, Colorado, July 1996, also to appear in IEEE Transactions on Power Systems.

[11] Hiriart-Urruty, J.-B., and C. Lemarechal, Convex Analysis and Minimization Algorithm, Vol. 2, Springer-Verlag, 1993.

[12] Tomastik, R. N., and P. B. Luh, ìA Reduced-Complexity Bundle Method for Maximizing Concave Nonsmooth Functions,î to appear in Proceedings of the 35th IEEE Conference on Decision and Control, Kobe, Japan, Dec. 96.

[13] H. Yan, P. B. Luh, X. Guan, and P. M. Rogan, ìScheduling of Hydrothermal Power Systems,î IEEE Trans. on Power Systems, Vol. 8, No. 3, August 1993, pp. 1358-1365.

[14] X. Guan, P. B. Luh, H. Yan, and P. M. Rogan, ìOptimization-based Scheduling of Hydrothermal Power Systems with Pumped-Storage Units,î IEEE Trans. on Power Syst, Vol. 9, No. 2, May 1994, pp. 1023-1031.

[15] Hiriart-Urruty, J.-B., and C. Lemarechal, Convex Analysis and Minimization Algorithm, Vol. 1, Springer-Verlag, 1993.

[17] Bertsekas, D. P., Nonlinear Programming, Athena Scientific, 1995.

Peter B. Luh (S'77-M'80-SM'91-F'95) received his B.S. degree in Electrical Engineering from National Taiwan University, Taipei, Taiwan, Republic of China, in 1973, the M.S. degree in Aeronautics and Astronautics Engineering from MIT, Cambridge, Massachusetts, in 1977, and the Ph.D. degree in Applied Mathematics from Harvard University, Cambridge, Massachusetts, in 1980. Since 1980, he has been with the University of Connecticut, and currently is a Professor in the Department of Electrical and Systems Engineering, and Director of Production Systems and Information Technology Program within the Advanced Technology Center for Precision Manufacturing. His major research interests include schedule generation and reconfiguration for manufacturing systems and power systems. Dr. Luh is an Editor of the IEEE Transactions on Robotics and Automation, was an Associate Editor of the IEEE Transactions on Automatic Control, and has served on program committees and operating committees of many major national, international, and inter-society conferences.

Daoyuan Zhang was born in Hubei Province, P. R. China in Nov. 25, 1965. He received his B.E. degree in Control Engineering from Tsinghua University, P. R. China in 1989. From 1990 to 1995, he had been working on power system scheduling. He is a Ph.D. candidate at the University of Connecticut now.

Robert N. Tomastik received the B.S. degree from the University of Connecticut in 1989, the M.Eng. degree from Rensselaer PolytechnicInstitute in 1992, and the Ph.D. Degree from the University of Connecticut in 1995, all in electrical engineering. He is currently with United Technologies Research Center, in Connecticut. His research interests are in production scheduling, active control for machining, and optimization theory.