620IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004Unit Commitment by Enhanced Adaptive Lagrangian RelaxationWeerakorn Ongsakul, Member, IEEE, and Nit PetcharaksAbstract—This paper proposes an enhanced adaptive Lagrangian relaxation (ELR) for a unit commitment (UC) problem. ELR consists of adaptive LR (ALR) and heuristic search. The ALR algorithm is enhanced by new on/off decision criterion, new initialization of Lagrangian multipliers, unit classification, identical marginal unit decommitment, and adaptive adjustment of Lagrangian multipliers. After the ALR best feasible solution reached is obtained, the heuristic search consisting of unit substitution and unit decommitment is used to fine tune the solution. The proposed ELR is tested and compared to conventional Lagrangian relaxation (LR), genetic algorithm (GA), evolutionary programming (EP), Lagrangian relaxation and genetic algorithm (LRGA), and genetic algorithm based on unit characteristic classification (GAUC) on the systems with the number of generating units in the range of 10 to 100. ELR total system production costs are less expensive than the others especially for the large number of generating units. Furthermore, the computational times of ELR are much less than the others and increase linearly with the system size, which is favorable for large-scale implementation. Index Terms—Heuristic search, Lagrangian relaxation, unit commitment.NOMENCLATURE Cold startup cost of unit (in dollars). Current unit at hour . Value of the on/off decision criteria of unit at hour . Ramp down rate limit of unit (in megawatts per minute). Generator fuel cost function in a quadratic form. Average production cost of unit at hour , (in dollars per megawatt-hour). Full load average production cost of unit at hour , (in dollars per megawatt-hour).Manuscript received March 3, 2003. This work is supported in part by the Energy Conservation Promotion Fund under Contract 029/2545, Energy Policy and Planning Office of Thailand. W. Ongsakul is with Energy Field of Study, School of Environment, Resources and Development, Asian Institute of Technology, Pathumthani 12120, Thailand (e-mail: ongsakul@ait.ac.th). N. Petcharaks is with Energy Field of Study, School of Environment, Resources and Development, Asian Institute of Technology, Pathumthani 12120, Thailand, on leave from the Electrical Engineering Department, Dhurakijpundit University, Bangkok 10210, Thailand (e-mail: nitp@dpu.ac.th). Digital Object Identifier 10.1109/TPWRS.2003.820707 0885-8950/04$20.00 © 2004 IEEERelative duality gap at iteration . th local peak load hour. Hot startup cost of unit (in dollars). Best total economic dispatch production cost reached (in dollars). Total economic dispatch production cost at iteration (in dollars). ALR iteration counter. Maximum allowable number of iterations. Total number of generator units. Number of major load peaks over the scheduled time horizon. Highest possible power output of unit at hour (in megawatts). Lowest possible power output of unit at hour (in megawatts). Minimum real power generation of unit (in megawatts). Maximum real power generation of unit (in megawatts). Generation output power of unit at hour (in megawatts). Economic dispatch generation output of unit at hour (in megawatts). Load demand at hour (in megawatts). Unit reserve contribution at hour , (in megawatts). Spinning reserve at hour (in megawatts). Set of identical marginal units at hour . Startup ramp rate limit of unit (in megawatts). Set of committed units at hour sorted in the descending order of negative value of . Set of committed units at hour sorted . in the descending order of Set of uncommitted units at hour sorted in the ascending order of . Startup cost of unit at hour (in dollars). Total number of hours. Continuously on time of (in hours). Cold start hour unit (in hours). Minimum down time of unit (in hours).

ONGSAKUL AND PETCHARAKS: UNIT COMMITMENT BY ENHANCED ADAPTIVE LAGRANGIAN RELAXATION621,,Continuously off time of unit (in hours). Continuously on time of unit (in hours). Minimum uptime of unit (in hours). Status of unit at hour ( , ). Best feasible solution reached. Solution at iteration . Ramp up rate limit of unit (in megawatts per minute). Duality gap tolerance. Reserve response time frame (i.e., 10–15 min). Initial Lagrangian multipliers at hour (in dollars per megawatt hour, dollars per megawatt). Lagrangian multipliers at hour at iteration (in dollars per megawatt hour, dollars per megawatt). Initial Lagrangian multiplier of unit at hour (in dollars per megawatt). I. INTRODUCTIONUNIT COMMITMENT (UC) is used to schedule the generators such that the total system production cost over the scheduled time horizon is minimized under the spinning reserve and operational constraints of generator units. UC problem is a nonlinear, mixed integer combinatorial optimization problem. The global optimal solution can be obtained by complete enumeration, which is not applicable to large power systems due to its excessive computational time requirements [1]. Lagrangian relaxation (LR) for UC problem [2]–[5] was superior to dynamic programming [6] due to its higher solution quality and faster computational time. However, numerical convergence and solution quality of LR are not satisfactory in the presence of identical heat rate units since they will be committed as a group on a pro-rata basis, apportioning dispatched power to their megawatt quantity [7]. Therefore, there was an attempt to differentiate identical units by slightly adjusting the heat rate of the identical units [3]. However, adjusting the heat rate may not be justified due to contractual agreement of energy payment between generator companies and a utility in a single buyer model. In [4], they combined LR, sequential unit commitment (SUC) based on the least reserve cost index and unit decommitment (UD) based on the highest average spinning reserve cost index. However, this method could not decommit some units that violate the minimum up time constraints even though the excessive reserve exists, leading to a higher production cost. In [8] and [9], augmented Lagrangian relaxation algorithms were originally developed to overcome the oscillation of LR solution caused by linearized cost functions. An augmented Lagrangian was formed by adding a penalty term to the Lagrangian function including the product of penalty coefficients and the total power demand mismatch squared. Nevertheless, the convergence rate was related to penalty coefficients, and it was still difficult to select the effective penalty coefficients that were suitable for different types of subproblems at the same time.Meanwhile, mixed integer linear programming (MILP) has been proposed to solve generation scheduling [10]–[12]. For solving UC problem, MILP was used to generate UC schedules where unit statuses were handled by partial enumeration such as branch-and-bound method [11]. MILP requires linearization of cost function and constraints. As the problem size is larger, computation requirement may become too large for practical applications due to a large number of variables and constraints [11], [12]. In the advent of heuristic approaches, genetic algorithm (GA) [13], evolutionary programming (EP) [14], simulated annealing (SA) [15], and tabu search (TS) [16] have been proposed to solve the UC problems. GA and EP have common processes in natural evolution but differences in the solution coding and the mechanism of selection candidates for reproduction. Nevertheless, the obtained results by GA, EP, and SA required a considerable amount of computational time especially for a large system size. There was an attempt to combine the LR and GA method (LRGA) to obtain a higher quality of UC solution in a shorter time by using normalized Lagrange multipliers as the encoded parameter [17]. But it could not resolve the problem with identical heat rate units. On the other hand, a genetic algorithm based on unit characteristic classification (GAUC) [18] was also proposed to obtain the nearer optimal solutions with shorter CPU times. In general, Lagrangian relaxation consumes a large computational time when using single-unit dynamic programming to determine the optimal path indicating the status of each unit for 24 h. Moreover, Lagrangian relaxation is not effective when the identical units exist [7]. In addition, the solution quality heavily depends on the initial Lagrangian multipliers [7] and updating Lagrangian multipliers method [7], [17]. Several multiplier updating methods were developed including modified subgradient method [2], reduced complexity bundle method (RCBM) [19], bundle trust region method (BTRM) [20], and dynamic constrained cutting plane (DC-CP) [5]. The modified subgradient method was computationally simple but might cause a slow convergence if an inappropriate initial multipliers solution was used. RCBM and BTRM were based on a bundle method consisting of two procedures: direction search and line search to determine how far to move along a direction. However, obtaining an accurate step size was generally a difficult task in RCBM, whereas the threshold parameters used in BTRM were important to the convergence of the method and were application specific. On the other hand, the computational time for DC-CP was still expensive for a large case study. This paper proposes an enhanced adaptive Lagrangian relaxation (ELR) consisting of adaptive LR (ALR) and heuristic search algorithms. ALR is enhanced by hourly new on-off decision criterion to determine the hourly unit status instead of single-unit dynamic programming, new initialization to obtain a high-quality initial feasible solution, unit classification to avoid decommitting base load units, identical marginal unit decommitment algorithm to address overcommitment problem, and adaptive Lagrangian multipliers to speedup the convergence. The ALR best feasible solution reached will be used as the initial solution for the heuristic search procedure, searching for the better solution by unit substitution and unit decommitment. To

622IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004illustrate the effectiveness of the proposed ELR, it is tested and compared to the conventional LR [13], GA [13], EP [14], LRGA [17], and GAUC [18] on the systems with the number of units in the range of 10 to 100. The organization of this paper is as follows. Section II addresses the UC problem formulation. The ELR algorithm including ALR and heuristic search for UC are described in Section III. Numerical results are presented in Section IV. Lastly, the conclusion is given. II. UNIT COMMITMENT PROBLEM FORMULATION The objective of UC problem is to minimize the production cost over the scheduled time horizon (e.g., 24 h) under the generator operational and spinning reserve constraints. The objective function to be minimized isoptimization procedure attempting to reach the constrained optimum by maximizing the Lagrangian(7) with respect to nonnegative and whereas minimizing it with respect to the other control variables in the problem, that is Max where Min (9) (8)(1) subject to (a) power balance constraint (2) (b) spinning reserve constraint (3) (c) generation limit constraints (4) (d) minimum up and down time constraintsEquations (2) and (3) are the coupling constraints across the units. In particular, what is done to one unit affects the other units. The Lagrangian function is rewritten as(10)The term can be minimized separately for each generating unit, when the coupling constraints are temporarily ignored. Then, the minimum of the Lagrangian function is solved for each generating unit over the time horizon, that is Min min (11) for , and subject to the constraints in (5). 1) New On/Off Decision Criterion: In the conventional Lagrangian relaxation method, the dual solution is obtained by using dynamic programming for each unit separately. This can be visualized in Fig. 1 showing the only two possible states for or 1): unit (i.e., At the state, the value of the function to be mini, mized is trivial (i.e., it equals zero), at the state where the function to be minimized is (the startup cost and the term are dropped here since the minimization is with re. spect to ) min will be To find the dual power, the term minimized by the optimality condition (12)(5) otherwise (e) startup cost if if , . (6) III. ENHANCED ADAPTIVE LAGRANGIAN RELAXATION FOR UC An enhanced adaptive Lagrangian relaxation consists of ALR and heuristic search algorithm. A. Adaptive Lagranian Relaxation The LR procedure solves the UC problem by relaxing or temporarily ignoring the coupling constraints and solving the problem as if they did not exist. This is done through the dual

ONGSAKUL AND PETCHARAKS: UNIT COMMITMENT BY ENHANCED ADAPTIVE LAGRANGIAN RELAXATION623Ui = 1 STi Ui = 0 t=0 t=1 t=2 t =3 t = T-1 t=T STi STi STiFig. 1. Search paths of each unit in dynamic programming.The solution to this equation is (13) The dual power is obtained (14) There are three cases to check against its limits 1) If , then . , then . 2) If 3) If , then . Dynamic programming is used to determine the optimal schedule of each unit over the scheduled time period. More specifically, for each state in each hour, the on/off decision making is needed to select the lower cost by comparing the combination of the startup cost and the accumulated costs from two historical routes. Dynamic programming CPU time and (upper bounded by increases at least linearly with additions and comparisons). Therefore, this paper proposes a new on/off decision criterion using the reduced startup cost to decide the schedule of each unit. The reduced startup cost is calculated by dividing the startup cost by the minimum uptime. The dual power, calculated by (14) and within the limit, will be substituted in the new on/off decision criterion (15) If the full startup cost is used in (15), the units with high startup cost and low operation cost will be committed only when and are large enough. This would therefore result in a higher production cost due to the overcommitment. With the and , it is more difficult for ALR to converge to the high optimal solution. and at hour have The Lagrangian multipliers is the marginal price of an economic interpretation: is the marginal the next megawatt-hour of energy and price of the next megawatt of spinning reserve at hour . , is the total fictitious payment of unit , , is the unit whereas generator fuel cost with the reduced startup cost. To minimize the above term in (15) at each hour, if , or this unit will be committed if it does not violate the minimum downtime con. Otherwise, this unit will not be committed if straint . it does not violate the minimum uptime constraint 2) Initialization: The initial values of Lagrangian multipliers are very critical to the LR solution since they may prevent LR from reaching the optimal solution or require a longercomputational time to reach one [7]. Different initial values may also lead LR to different solutions. In [21], the initial multiplier was set to the hourly system marginal cost of the schedule to satisfy the power balance constraint and the initial was set to zero, leading to an infeasible initial multiplier was set to solution. On the other hand, the initial multiplier the hourly system marginal cost of the schedule to satisfy both the power balance and spinning reserve constraint, whereas the was set to zero which was generally lower initial multiplier [22]. than the optimal value Our initialization procedure intends to create a high quality feasible schedule in the first iteration. The generating units are sorted in the ascending order of full load average production . For each of the 24 h, the group of identical cost, will be committed one group units with the least by one group until the power balance constraint is satisfied. Subsequently, economic dispatch in each hour is carried out to obtain the hourly equal lambda which is initially set to Lagrangian , in each hour. For the hours with insufficient multipliers spinning reserves, more unit(s) are needed to be committed to give the initial feasible solution. This is obtained by commitone ting a group of identical units with the least group by one group until the spinning reserve is satisfied. is determined by For each of the 24 h, each non-negative the upper bound of zero on/off decision criteria of the committed unit as follows: max is determined by the highest The initial committed units as max (16) among the (17)where is the marginal unit with the highest giving the sufficient spinning reserve at hour . 3) Unit Classification: In general, generation units can be classified into three types: base load units with low operation cost, high startup cost, and long minimum up/down times, intermediate load units with medium operating cost, medium startup cost and medium minimum up/down time, and peak load units with high operation cost, low startup cost and short minimum up/down time. Base load units should not be shut down. Intermediate load units could be committed during onpeak and decommitted during offpeak periods. Finally, peak load units could be frequently turned on/off. Based on the full load average production costs (FLAC) and generator operational constraints of ten units shown in Table I, units 1 and 2 are classified as base load units, units 3, 4, 5, 6, and 7 are intermediate units and units 8, 9, and 10 are peak load units. Note the identical marginal unit decommitment in ALR (Section III-A-4) and unit decommitment in heuristic search algorithm (Section III-B-2) will exclude the base load units. For unit substitution in heuristic search algorithm (Section III-B-1), the intermediate unit(s) may be decommitted and replaced with peak load unit(s). 4) Identical Marginal Unit Decommitment: LR could find only suboptimal solutionswhen identicalor similar units exist [7]. Theseunitshavetheidenticalcostparameters , , ,andstartup

624IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004where (19) norm (20)Fig. 2. Excessive spinning reserve due to the identical units.max cost which will be simultaneously turned on/off as a result of the same on/off decision criterion. This will not lead to the optimal solution because committing one unit at a time will be less expensive than committing a whole group of units, which may lead to overcommitment. As an example, the shadow blocks illustrate the excessive reserve due to the identical units no. 25, 26, 27, and 28 as shown in Fig. 2. Thus, after committing a whole group of identical marginal units, we shall decommit one identical marginal unit at a time if it does not violate the minimum uptime constraint until either the spinning reserve requirement is not satisfied or there is onlyonemarginalunitleft.Theidenticalmarginalunit decommitment procedure is as follows. . Step 1) Set Step 2) Sort the committed unit(s) excluding the base load units in the descending order of negative value of . on/off decision criteria to obtain Let the first group of marginal identical units from be . has more than one unit, let the first unit in Step 3) If be . Otherwise, go to step 8. Step 4) Calculate the excess spinning reserve of hour . Step 5) If the excess spinning reserve is less than maximum , go to step 8. generation of violates its minimum up time Step 6) If decommitting constraint, go to step 8. and delete it from the set . Step 7) Decommit and return to step 3. Update , and return to step 2. Otherwise, Step 8) If carry out the economic dispatch in Section III-A-6. The proposed identical marginal unit decommitment is also applicable to a centralized power pool auction. A fair and practical rule is to decommit the identical bid units one at a time in the order of the latest time stamps of the final bid submission before the trading deadline. 5) Adaptive Updating of the Lagrangian Multiplier: In general, adjusting Lagrangian multiplier by subgradient method is not efficient in the presence of the spinning reserve constraint [2]. The LR performance is heavily dependent on the method used to update the multipliers. In this paper, the Lagrangian multiplier update rule is designed such that the step size is large at the beginning of iterations and smaller as the iteration grows as proposed in [7]. The values of and are determined heuristically [23]. Each nonnegative and are adaptively updated by, max wherenorm(21)(22) norm (23) are divided into three cases depending on the signs of and as follows: Case 1) and : updating both and by using and ; and : updating both and Case 2) by using , ; and : updating only by using Case 3) , . and in hour In fact, updating these two multipliers must move them in the same direction. In hour , if and have the same signs, either positive or negative, and will be updated (increase or decrease) by (18) and (21), respectively. When the total dual generation output is larger than but the spinning reserve is the load in that hour , more committed unit(s) are required insufficient to satisfy the spinning reserve constraints. However, updating by (18), will decrease its value, resulting in committing less units. Therefore, when and , only will be updated. Note the subgradient method generally needs a large number of iterations to converge to near the dual optimum, but per iteration multiplier update is very fast. Our adaptive subgradient method using high-quality initial feasible multipliers requires much less number of iterations to converge, leading to fast computational time. 6) Economic Dispatch: If the 24-h schedule is feasible, the equal lambda economic dispatch is carried out to determine the for each of the 24 h, and optimal generation power outputs . the total production cost 7) Stopping Criteria: The relative duality gap is and(24) wherenorm (18) (10).andis calculated from

ONGSAKUL AND PETCHARAKS: UNIT COMMITMENT BY ENHANCED ADAPTIVE LAGRANGIAN RELAXATION625The relative duality gap is used to measure the solution quality, by checking against the stopping criteria. The iteration process stops when either the relative duality gap is less than the specified tolerance or the iteration counter exceeds the maximum allowable number of iterations. Note, to calculate , the full startup cost is used instead of the reduced startup cost. B. Heuristic Search The heuristic search uses ALR solution as its initial base solution to determine a better solution by the heuristic search including unit substitution and unit decommitment. 1) Unit Substitution: In peak load periods, some units are committed due to the minimum uptime constraints. This may result in excessive spinning reserve as the load decreases in the next few hours. As an example, the shadow blocks show the excessive spinning reserve due to the minimum uptime constraints of units number 6 and 7 as shown in Fig. 3. Therefore, those intermediate load units could be decommitted for all of their minimum uptime hours and replaced with one uncommitted peak load unit based on the least full load average production cost index at a time until the spinning reserve requirement is satisfied. For each peak period, starting from 2 h after peak hour, if the excessive spinning reserve exists, the unit substitution will be carried out. This procedure will continue decommitting the next highest average production cost intermediate load unit until one of the following three conditions are not satisfied: i) decommitting the units violates the minimum up time constraints (unit substitution is needed); ii) the total production cost of the new schedule is lower; iii) there are sufficient uncommitted units to replace the decommitted unit. Subsequently, the unit substitution procedure will be repeated at the next peak period until the last peak period. The solution of this procedure will be the best solution reached and used as an initial solution for the unit decommitment. The unit substitution procedure is as follows. Step 1) Step 2) Step 3) Step 4) from ALR. Obtain Determine the number of major load peaks over the . Let . scheduled time horizon be an initial solution. Let Let . for each committed inCalculate termediate load unit in hour and sort them to obin the descending order of tain . Let the first unit in be . If the excess spinning reserve at hour is less than the maximum go to step 14. generation of violates its minimum upIf decommitting time constraint, decommit for all the previous hours. Otherwise, go to step 14. hour, referred Starting from the first hour of . as Check the spinning reserve at hour . Calculate the full load average production cost of the uncommitted peak load units with one hour minimum up time. Sort themFig. 3.Excessive spinning reserve due to minimum uptime constraints.Step 5)Step 6) Step 7)in the ascending order of to obtain . is sufficient, go Step 8) If the spinning reserve at hour to step 11. Step 9) If the total capacity of the uncommitted peak load is insufficient to replace the deunits at hour , go to step 14. committed Step 10) Commit an uncommitted unit in , one unit at a time until the spinning reserve constraint is satisfied. is not the last hour of hour, Step 11) If , and return to step 7. Step 12) Calculate the total production cost of the modified schedule. If the total production cost is smaller , update and , delete from than . Otherwise, go to step 14. Step 13) Let the first unit in be and return to step 5. , and return to step 3. OtherStep 14) If wise, the unit substitution procedure is terminated, is the solution of unit substitution. 2) Unit Decommitment: Excessive spinning reserve is not desirable due to the high operation cost. Starting from the last hour, this procedure determines whether decommitting the highest average production cost, , committed unit, one unit at a time will leave sufficient spinning reserve and satisfy the minimum up and downtime constraints. If there are no other units to be decommitted, it will proceed to the previous hour. When it reaches the first hour, unit decommitment procedure will be terminated. The final solution will be the ELR solution. The unit decommitment procedure is as follows. Step 1) Let the solution obtained from the unit substitution be an initial solution. procedure . Step 2) Set of Step 3) Calculate the average production cost each committed unit excluding the base load units in hour and sort the units in the descending order of to obtain . Let the first unit in be . Step 4) Calculate the excess spinning reserve at hour . Step 5) If the excess spinning reserve is less than the maximum generation of , go to step 9.

626IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004Step 6) If decommitting does not violate its minimum and update . uptime constraint, decommit from . Step 7) Delete is not empty, let be the first Step 8) If unit in and return to step 4. , and return to step 3. Otherwise, Step 9) If stop and is the ELR solution. C. ELR Solution Procedure ALR Procedure Step 1. Initialize and described in Section III-A-2. , Step 2. Initialize the ALR iteration counter, and . Step 3. Solve the unit subproblems by using the new on/off decision criteria described in Section III-A-1. Step 4. If the dual solution is not feasible, go to step 9. Step 5. Carry out the identical marginal unit decommitment procedure described in Section III-A-4. Step 6. Carry out the economic dispatch, cal, the dual cost culate the primal cost and the relative dual gap as described in Sections III-A-6 and III-A-7. , and Step 7. If . , go to step 10. Step 8. If the relative dual gap , , update Lagrangian Step 9. If multiplier adaptively as described in Section III-A-5 and return to step 3. Otherwise, go to step 10. Heuristic Search Procedure Step 10. Perform the unit substitution procedure described in Section III-B-1. Step 11. Perform the unit decommitment procedure described in Section III-B-2. IV. NUMERICAL RESULTS As shown in Tables I and II, a ten-unit system data and load demands are given [13]. The 20, 40, 60, 80, and 100 units data are obtained by duplicating the base case (ten units), whereas the load demands are adjusted in proportion to the system size. In the simulation, the reserve is required to be 10% of the load demand. The dynamic programming-based LR (DPLR) is implemented for comparison. DPLR uses single-unit dynamic programming to determine the optimal path instead of new on/off decision criteria. The identical marginal unit decommitment and unit classification are not applicable to DPLR. In addition, the heuristic search is not used to fine tune the DPLR solution. The duality gap tolerance for ALR and DPLR are set to 0.001. Note is two. the number of major load peaks The ELR solution on the ten-unit system is shown in Table II. As shown in Table III, the total production costs of ELR are shown to be less expensive than those of LR [13], GA [13], EP [14], GAUC [18], DPLR, and ALR on all generating unit systems. For the 60-, 80-, and 100-unit generating systems, ELR total product costs are less expensive than LRGA [17]. Obviously, ALR alone vastly improves DPLR in terms of both solution quality and CPU times especially on the large gener-TABLE I UNIT DATA FOR THE TEN-UNIT SYSTEMator unit systems. ALR converges to the solution at a faster rate than DPLR. If the full startup cost is used in (15) instead, of ALR with full startup cost (ALR-FST) solution in each the ten-unit system is higher than DPLR and ALR as shown in Fig. 4, thereby leading to a higher production cost of $ 581 694. This clearly demonstrates the advantage of using the reduced startup cost over the full startup cost in the new on-off decision criteria. The CPU times shown in Table IV may not be directly comparable due to different computers used. CPU times of GA [13] and EP [14] are obtained from HP Apollo 720 workstation and HP C160 workstation, respectively, whereas CPU times of DPLR, ALR, and ELR are obtained from a Pentium IV, 1.6-GHz personal computer. LRGA [17] and GAUC [18] did not report the computers used. However, the CPU times of ELR are much smaller than those of the other methods. Moreover, the ELR CPU time increase linearly with the system size which is favorable for large-scale implementation. It should be observed that ramp rate limit constraints are not taken into account in this paper since we would like to compare the solutions with the previous work [13], [14], [17], and [18]. However, the framework used allows to consider those constraints for both unit basis and system basis. On the unit basis, the generation limit constraint in (4), including the generator operating and startup ramp rate limits, is modified as (25)

ONGSAKUL AND PETCHARAKS: UNIT COMMITMENT BY ENHANCED ADAPTIVE LAGRANGIAN RELAXATION627TABLE II LOAD DEMANDS AND ELR SOLUTION OF THE TEN-UNIT SYSTEMHr 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24Load (MW) 700 750 850 950 1000 1100 1150 1200 1300 1400 1450 1500 1400 1300 1200 1050 1000 1100 1200 1400 1300 1100 900 800Unit 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 4 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 5 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 6 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 7 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 8 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0TABLE III COMPARISON OF TOTAL PRODUCTION COSTSwheremin min maxif if if if, , , .On the system basis, the spinning reserve constraint in (3) including the ramp rate limits is modified as (26) To solve ramp rate constrained UC, ALR and heuristic search algorithms have to check against the modified generation limit and spinning reserve constraints.Fig. 4. Lagrangian multipliers of the ALR, ALR-FST, and DPLR solutions of the ten-unit system.

628IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 19, NO. 1, FEBRUARY 2004TABLE IV COMPARISON OF CPU TIMESV. CONCLUSION In this paper, the proposed ELR is efficiently and effectively implemented to solve the UC problem. ELR total production costs over the scheduled time horizon are less expensive than conventional LR, GA, EP, LRGA, and GAUC especially on the large number of generating units. Moreover, the ELR CPU times are much smaller than the others and increase linearly with the system size, which is favorable for large-scale implementation. Accordingly, ELR is very suitable for UC due to the substantial production cost savings and fast computing time. In addition, the proposed ELR could be extended to solve ramp rate constrained UC, network constrained UC, or centralized dispatch day-ahead power pool auctions in our future research work. REFERENCES[1] A. J. Wood and B. F. Wollenberg, Power Generation, Operation & Control, 2nd ed. New York: Wiley, 1996, p. 139. [2] A. Merlin and P. Sandrin, “A new method for unit commitment at Electricite De France,” IEEE Trans. Power App. Syst., vol. PAS-102, pp. 1218–1225, May 1983. [3] S. Virmani, K. Imhof, and S. M. Jee, “Implementation of a Lagrangian relaxation based unit commitment problem,” IEEE Trans. Power Syst., vol. 4, pp. 1373–1379, Oct. 1989. [4] C. Li, R. B. Johnson, A. J. Svoboda, C. Tseng, and E. Hsu, “A robust unit commitment algorithm for hydro-thermal optimization,” IEEE Trans. Power Syst., vol. 13, pp. 1051–1056, Aug. 1998. [5] N. J. Redondo and A. J. Conejo, “Short-term hydro-thermal coordination by Lagrangian relaxation: solution of the dual problem,” IEEE Trans. Power Syst., vol. 14, pp. 89–95, Feb. 1999. [6] G. B. Sheble and G. N. Fahd, “Unit commitment literature synopsis,” IEEE Trans. Power Syst., vol. 9, pp. 128–135, Feb. 1994. [7] S. Dekrajangpetch, G. B. Sheble, and A. J. Conejo, “Auction implementation problems using Lagrangian relaxation,” IEEE Trans. Power Syst., vol. 14, pp. 82–88, Feb. 1999. [8] H. Yan, P. B. Luh, and L. Zhang, “Scheduling of hydrothermal power systems using the augmented Lagrangian decomposition and coordination technique,” in Proc. Amer. Control Conf., vol. 2, 1994, pp. 1558–1562. [9] S. J. Wang, S. M. Shahidehpour, D. S. Kirschen, S. Mokhtari, and G. D. Irisarri, “Short-term generation scheduling with transmission and environmental constraints using an augmented Lagrangian relaxation,” IEEE Trans. Power Syst., vol. 10, pp. 1294–1301, Aug. 1995.[10] J. M. Arroyo and A. J. Conejo, “Optimal response of a thermal unit to an electricity spot market,” IEEE Trans. Power Syst., vol. 15, pp. 1098–1104, Aug. 2000. [11] M. Christoforidis, B. Awobamise, R. J. Frowd, and F. A. Rahimi, “Short term hydro generation and interchange contract scheduling for Swiss rail,” IEEE Trans. Power Syst., vol. 11, pp. 274–280, Feb. 1996. [12] G. W. Chang, M. Aganagic, J. G. Waight, J. Medina, T. Burton, S. Reeves, and M. Christoforidis, “Experiences with mixed integer linear programming based approaches on short-term hydro scheduling,” IEEE Trans. Power Syst., vol. 16, pp. 743–749, Nov. 2001. [13] S. A. Kazarlis, A. G. Bakirtzis, and V. Petridis, “A genetic algorithm solution to the unit commitment problem,” IEEE Trans. Power Syst., vol. 11, pp. 83–92, Feb. 1996. [14] K. A. Juste, H. Kita, E. Tanaka, and J. Hasegawa, “An evolutionary programming solution to the unit commitment problem,” IEEE Trans. Power Syst., vol. 14, pp. 1452–1459, Nov. 1999. [15] A. H. Mantawy, Y. L. Abdel-Magid, and S. Z. Selim, “A simulated annealing algorithm for unit commitment,” IEEE Trans. Power Syst., vol. 13, pp. 197–204, Feb. 1998. [16] , “Unit commitment by tabu search,” Proc. Inst. Elect. Eng., Gen. Transm. Dist., vol. 145, pp. 56–64, Jan. 1998. [17] C. P. Cheng, C. W. Liu, and C. C. Liu, “Unit commitment by Lagrangian relaxation and genetic algorithms,” IEEE Trans. Power Syst., vol. 15, pp. 707–714, May 2000. [18] T. Senjyu, H. Yamashiro, K. Uezato, and T. Funabashi, “A unit commitment problem by using genetic algorithm based on characteristic classification,” in Proc. IEEE/Power Eng. Soc. Winter Meet., vol. 1, 2002, pp. 58–63. [19] P. B. Luh, D. Zhang, and R. N. Tomastik, “An algorithm for solving the dual problem of hydrothermal scheduling,” IEEE Trans. Power Syst., vol. 13, pp. 593–600, May 1998. [20] D. Zhang, P. B. Luh, and Y. Zhang, “A bundle method for hydrothermal scheduling,” IEEE Trans. Power Syst., vol. 14, pp. 1355–1361, Nov. 1999. [21] K. H. Abdul-Rahman, S. M. Shahidehpour, M. Aganagic, and S. Mokhtari, “A practical resource scheduling with OPF constraints,” in Proc. Power Ind. Comput. Applicat. Conf., 1995, pp. 92–97. [22] H. Yan, P. B. Luh, X. Guan, and P. M. Rogan, “Scheduling of hydrothermal power systems,” IEEE Trans. Power Syst., vol. 8, pp. 1358–1365, Aug. 1993. [23] M. L. Fisher, “The Lagrangian relaxation method for solving integer programming problems,” Manage. Sci., vol. 27, pp. 1–18, Jan. 1981.Weerakorn Ongsakul (S’89-M’95) received the B.Eng. degree in electrical engineering from Chulalongkorn University, Bangkok, Thailand, in 1988, and the M.S. and Ph.D. degrees in electrical engineering from Texas A&M University, College Station, in 1991 and 1994, respectively. Currently, he is an Associate Professor and Coordinator of Energy Field of Study at the Asian Institute of Technology (AIT), Pathumthani, Thailand. His interests are in computer applications to power systems, parallel processing applications, AI applications to power systems, and power system deregulation.Nit Petcharaks received the B.Eng. and M.Eng. degrees in electrical engineering from Chulalongkorn University, Bangkok, Thailand, in 1983 and 1993, respectively. She is currently pursuing the Ph.D. degree in energy at the Asian Institute of Technology (AIT), Pathumthani, Thailand. Currently, she is an Assistant Professor of Engineering with Dhurakijpundit University, Bangkok, Thailand.