Unit commitment using dynamic programming–an exhaustive working of both classical and stochastic approach

Abstract

In the present electricity market, where renewable energy power plants have been included in the power systems, there is a lot of unpredictability in the demand and generation. There are many conventional and evolutionary programming techniques used for solving the unit commitment (UC) problem. Dynamic programming (DP) is a conventional algorithm used to solve the deterministic problem. In this paper DP is used to solve the stochastic model of UC problem. The stochastic modeling for load and generation side has been formulated using an approximate state decision approach. The programs were developed in a MATLAB environment and were extensively tested for a four-unit eight-hour system. The results obtained from these techniques were validated with the available literature and outcome was good. The commitment is in such a way that the total cost is minimal. The novelty of this paper lies in the fact that DP is used for solving the stochastic UC problem.

Keywords

unit commitment (UC) / deterministic / stochastic / dynamic programming (DP) / optimization / state diagram

Introduction

The unit commitment (UC) problem deals with the optimum amount of time in which a generating unit must be operated on a per hour basis in order to meet the load requirements effectively. Besides achieving the minimum total production cost, a generation schedule needs to satisfy a number of operating constraints. These constraints reduce freedom in the choice of starting up and shutting down generating units [1]. The constraints to be satisfied are usually the status restriction of individual generating units, minimum up time, minimum down time, capacity limits, generation limit for the first and last hour, limited ramp rate, group constraint, power balance constraint, spinning reserve constraint, and etc. The high dimensionality and combinatorial nature of the UC problem curtails the attempts to develop any rigorous mathematical optimization method capable of solving the whole problem for any real-size system. The UC problem is applied for both deterministic and stochastic loads. The deterministic approach provides definite and unique conclusions, but the results obtained for stochastic loads may not be exact. However, in stochastic models, the constraints are changed into determinate ones, and the formulation can be solved by any of the usual algorithms. Deterministic approaches include priority list (PL), integer/mixed-integer programming method, dynamic programming (DP), branch-and-bound method, and Lagrangian relaxation (LR). PL [2] is the simplest and fastest but achieves a poor final solution. DP [3] techniques, essentially based on PLs, are flexible, but the computation time suffers from the curse of dimensionality, which leads to more mathematical complexity and an increase in computation time. The LR method [4] provides a faster solution but it suffers from numerical convergence [5] and existence of duality gap. The integer [6] and mixed-integer [7] method adopt linear programming to solve and check for an integer solution. These methods fail when the number of units increases because they require a large memory and suffer from great computational delay. The branch-and bound method [8] employs a linear function to represent fuel cost and start-up cost and obtains a lower and upper bounds. The deficiency of this method is the exponential growth in the execution time for systems of a practical size [9]. The UC problem has been earlier solved by enumerating all possible combinations of the generating units and then the combinations that yield the least cost of operation are chosen as the optimal solution. Even though the method was not suitable for a large size electric utility, it was capable of providing an accurate solution. This paper provides a detailed analysis of the solution for the UC problem using DP. It is known that user demand cannot be precisely predicted because it varies with the seasons in a year, calendar days, overall climate, user consumption patterns, and many other factors. In addition, the generations from the renewable sources are very volatile. Two types of uncertainties, user demands and generation outputs, can exist due to the renewable sources like wind power plant etc. Three cases are considered for the 4 unit system first, and the same approach is then applied for a 5 unit system. The DP method is apt for small and medium size number of units because it is very easy to calculate the solution using this method. For a system of more units, a hybrid approach can be adopted, i.e. by carrying out the search process for DP using some other programming techniques. The future scope of this paper is to develop a hybrid dynamic programming (HDP) technique. In the first case, the DP approach is used to find feasible solutions for the deterministic problem. In case 2, the uncertainty in the load side is considered and further this problem is solved using the DP approach. In case 3, the uncertainty factor in the generation side is considered. In case 4, the uncertainty in both the generation and the load side are considered. In the end, the total costs calculated for the above 4 cases are compared.

UC problem formulation

Deterministic UC

The UC problem is defined as the scheduling of a set of generating units to be on, off, or in standby (banking mode) for a given period of time to meet uncertain objective. For the ease of calculation in this report we have considered only the up and down time constraints. The objective Eq. (1) consists of operation and start-up/shut-down (SUSD) costs of thermal generators, Eq. (2) corresponds to system power balance constraints; Eq. (3) denotes the constraints only associated with integer variables, like minimum online/offline time limits; and Eq. (4) denotes the constraints for the SUSD cost. In this paper the problem is solved using time constraints only, to reduce the complexity of the problem.

(1)\min {\displaystyle \sum _{i=\mathrm{1}}^N{\displaystyle \sum _{t=\mathrm{1}}^T(C_i{P}_{i,t}+C_{i,t,U}+C_{i,t,D})},}

s.t.

(2){\displaystyle \sum _{i=\mathrm{1}}^N{P}_{i,t}=D_t},

(3)({\mathit{T}}_{\mathrm{o}\mathrm{n}}(i,t-\mathrm{1})-{\mathit{T}}_{\mathrm{u}\mathrm{p}}(i))(I(i,t-\mathrm{1})-I(i,t))\ge \mathrm{0},

(4)(T_{\mathrm{o}\mathrm{f}\mathrm{f}}(i,t-\mathrm{1})-T\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}(i))(I(i,t-\mathrm{1})-I(i,t))\ge \mathrm{0},

where I (i,t) is the unit on/off status; P_{i,t}, the generation of unit i at time t; T_off (i, t), the continuous off-time of unit i at time t; T_down (i), the minimum down-time of unit i; T_on (i,t), the continuous on-time of unit i at time t; T_up(i), the minimum up-time of unit I; C_iP_i,t, the production cost; C_i,t,U, the start-up cost; and C_i,t,D, the shut-down cost.

Stochastic UC

The generation of a wind turbine varies with several variables such as the rated maximum power, cut-in and cut-out speed, generator efficiency, air density and wind velocities. When uncertainties are included in the UC problem, the conventional methods like Lagrange relaxation, mixed integer programming and DP etc. cannot be directly used to solve the stochastic problem. Therefore one approach is to develop efficient solution algorithms to find optimal or suboptimal schedules.

In a deterministic framework, the stochastic UC problem may be formulated as

(5)\min {\displaystyle \sum _{i=\mathrm{1}}^N{\displaystyle \sum _{t=\mathrm{1}}^T(C_i{P}_{i,t}+C_{i,t,U}+C_{i,t,D})+M{\displaystyle \sum _{k=\mathrm{1}}^N{\displaystyle \sum _{t=\mathrm{1}}^T\left({\widehat{w}}_{k,t}-w_{k,t}\right)}}}},

s.t.

(6)\begin{array}{ll}{\displaystyle \sum _{i=\mathrm{1}}^N{P}_{i,t}+{\displaystyle \sum _{k=\mathrm{1}}^{N_w}{W}_{k,t}=D_t}}\hfill & (t=1,\cdots ,T)\hfill \end{array},

(7)g_I(I_{i,t})\le \mathrm{0},

(8)g_c(C_{i,t,U},C_{i,t,D},I_{i,t})\le \mathrm{0},

(9)\mathrm{0}\le w_{k,t}\le {\widehat{w}}_{k,t},

(10)I_{i,t}{P}_{i,\min }\le P_{i,t}\le I_{i,t}{P}_{i,\max },

wherew_{k,t}is the power dispatch at wind farm k at time t; {\widehat{w}}_{k,t}, the actual power output of the generator; P_{i,t}, the generation of unit i at time t; g_I, the constraint associated with integer variable;

g_c

, the constraint for SUSD cost; P_{i,\min }, the minimum generation limit for the ith generator; and p_{i,\max }, the maximum generation limit for the ith generator.

Objective Eq. (5) consists of the operation and SUSD costs of thermal generators, as well as the expected wind power spillage; Eq. (6) corresponds to system power balance constraints; Eq. (7) denotes the constraints only associated with integer variables, like minimum online/offline time limits; the g_c in Eq. (8) denotes the constraints for the SUSD cost; Eqs. (9) and (10) denote the upper and lower limits of the real power output of wind and thermal generators.

DP approach

DP is based on the repeated application of the principle of optimality. It is a method which systematically calculates a large number of possible decisions for a multi-stage problem [10]. It decomposes the problem into sub-problems, solves the smaller problems and develops an optimal solution to the original problem step by step. It also offers adaptability and flexibility which can examine any state in any interval. The method consists in implicitly enumerating feasible schedule alternatives and comparing them in terms of operating costs. Because of this implicit order defined upon the elements, the order cannot be scrambled without completely changing the problem [11]. The biggest limitation of DP is the number of partial solutions to keep track of. The partial solutions can be defined by specifying the stopping places in the input. If the already existing conventional DP method is implemented, correct results may be obtained but the time requirements will be very high. For example, in a case of 4 generating units which meets the 24 hour demand, the maximum number of combinations to be tested before an optimal outcome is attained is given by

Maximum combinations=2⁴-1= 15,

Total paths=(2⁴-1)²⁴ .

If a strict priority order is imposed this disadvantage can be eliminated and the dimensionality of the problem can be reduced. Besides, the calculation of production cost lies near the optimal solution. For example, for the given 4 unit systems, the PL can be created as

Priority 1 Unit,

Priority 1 Unit+ Priority 2 Unit,

Priority 1 Unit+ Priority 2 Unit+ Priority 3 Unit,

Priority 1 Unit+ Priority 2 Unit+ Priority 3 Unit+ Priority 4 Unit.

DP can be solved using either the backward recursion, where the computation proceeds from an end state to the initial state or the forward recursion [1] where the computation proceeds from the initial state to a feasible end state. The forward approach is commonly used due to the unique advantages it offers to solve the UC problem. At each stage, the initial condition can be easily taken into consideration and the computations can be performed in forward direction for a given time period. The calculations are done using

(11)F_{\cos \mathrm{t}}(R,I)=\min (F_{\cos \mathrm{t}}(R,I)+S_{\cos \mathrm{t}}(R-\mathrm{1},L:R,I)+F_{\cos \mathrm{t}}(R-\mathrm{1},L)),

where R is the number of hours; L, the number of feasible states; F_cost(R, I), the total cost; P_cost(R, I) the production cost; S_cost(R–1, L: R, I), the transition cost; and F_cost(R–1, L), the fixed cost (startup/shutdown cost).

The proposed methodology is introduced as follows:

1) DP algorithm

Step 1: Calculate the production cost, P_cost for all feasible states I, for each hour.

Step 2: Calculate the total cost for R = 1, the transition cost is zero for the first hour. Save the minimum total cost value.

Step 3: Calculate the total minimum cost for the next hour. Now the transition cost is the minimum cost of the previous hour.

Step 4: Repeat Step 3 until the last hour to obtain the optimal schedule.

PL is decided on the basis of full load average cost, before starting the algorithm. Calculate the incremental cost for each unit separately. The production cost is calculated using

F(P) = No load cost+ Inc. Cost×P

Further, the total cost is calculated for all 8 hours and the unit combination schedule is obtained.

2) Flowchart

The flowchart for forward DP is shown in Fig. 1.

3) Block diagram

The block diagram for the DP algorithm is represented in Fig. 2.

Simulation results

The results for DP are tested on a 4-unit 8-hour system. The program code was written using MATLAB. The input data and the load data for the 4-unit system are demonstrated in Tables 1 and 2 respectively [1]. The UC schedule is determined using DP considering the usual case and also considering stochasticity in the load and generation side.

Table 3 gives the hourly and total cost distribution data of the 4-generator unit in an 8 hours time period, where 0 represents the OFF state and the ON state. For each hour, the expected output of each generator unit is evaluated, so that the load requirements are fulfilled. Table 4 presents the unit combination schedule for the normal case, while Table 5, the hourly and total cost distribution data when stochasticity is considered on the load side. The variation considered for the load data is 20%. Table 6 tabulates the unit combination schedule for this case, whereas Table 7, the hourly and total cost distribution data when stochasticity is considered on the generation side. The maximum power output of Unit 3 is varied from 300 MW to 230 MW as a result of which the PL of the units changes. The reduction of maximum power output can be accounted by the ageing of the thermal unit (i.e., Unit 3). Table 8 lists the unit combination schedule for this case, while Table 9, the hourly and total cost distribution data when stochasticity is considered both on the load and the generation side. The load data is considered the same as the second case where stochasticity is considered only on the load side. The maximum power output is 230 MW for Unit 3 which is the same as the third case when stochasticity is considered only on the generation side. The total cost obtained by considering stochasticity on the load side, generation side and both the load and generation side is $72500, $76402 and $75133, respectively. Table 10 gives the unit combination schedule.

State space diagram

State space diagram for DP solution, without considering up and downtime constraints

The 8 stage search process is represented in the form of a dynamic process. At the first stage, the initial feasible state is ‘state 12’. The total cost is calculated for all 4 states in stage 1 (i.e., load= 450 MW). The state which has the least value of the total cost is the most feasible state and this value is used for the calculation of total cost for the next stage. The search process is stopped when the last stage is reached. The path illustrated in Fig. 3 represents the optimal solution obtained by the DP algorithm.

State space diagram for DP solution when uncertainty is on the load side

For stochasticity on the load side, the load is varied in a range of 20%, and the changes are observed. The search process is stopped when the last stage is reached. The path displayed in Fig. 4 represents the optimal solution obtained by the DP algorithm.

State space diagram for DP solution when uncertainty is on the generation side, without considering the up and downtime constraints

For stochasticity in the generation side, the maximum power output for the Unit 3 is varied from 300 MW to 230 MW. As a result, the priority grouping of the Units (1 to 4) differs from [3,2,1,4] to [2,3,1,4]. The process continues in the forward direction until all stages are searched and optimal decisions are obtained. The search process is stopped when the last stage is reached. The path exhibited in Fig. 5 represents the optimal solution obtained by the DP algorithm.

Validation of result

The validation of result is shown in Table 11. In the first case, the classical approach is considered and the total cost calculated is $73274. The results obtained are similar to the results given in Allen Wollenberg [1]. In the second case, stochasticity is considered on the load side and the resultant cost is $72500. In the third case, when stochasticity is considered on the generation side, the total cost increases to $76402. In the fourth case, when stochasticity is considered on both the load and generation side, the total cost becomes $75133.

Conclusions

The variation in cost is observed because of the continuous switching on and off, of the generator units. This change may be observed due to the ageing of one of the thermal units. Besides, considering environmental factors, the power output of the base unit i.e. the unit with the maximum power output, may be varied. The total cost obtained by the DP method is lesser compared to the other conventional methods. The future work includes the consideration of other constraints in addition to the operating constraints for the case where stochastic approach is applied on the generation side only and for the case where stochasticity is considered on both the load and generation side, plus, the evaluation of UC schedule for large system by considering the renewable sources using hybrid DP.

References

[1] Wood A J, Wollenberg B F. Power Generation Operation and Control. New York: Wiley & Sons, 2003

[2] Catalao J P S, Mariano S J P S, Mendes V M F, Ferreira L A F M. Profit based unit commitment with emission limitation: a multiobjective approach. In: Proceedings of IEEE Lausanne conference on Power Technology. Lausanne Switzerland, 2007, 1417–1422

[3] Burns R M, Gibson C A. Optimization of priority lists for a unit commitment program. In: Proceedings of IEEE/PES Summer Meeting. San Francisco, USA, 1975, 453–456

[4] Ouyang Z, Shahidehpour S M. An intelligent dynamic programming for unit commitment application. IEEE Transactions on Power Systems, 1991, 6(3): 1203–1209

[5] Virmani S, Adrian E C, Imhof K, Mukherjee S. Implementation of a Lagrangian relaxation based unit commitment problem. IEEE Transactions on Power Systems, 1989, 4(4): 1373–1380

[6] Ongsakul W, Petcharaks N. Unit commitment by enhanced adaptive Lagrangian relaxation. IEEE Transactions on Power Systems, 2004, 19(1): 620–628

[7] Dillon T S, Edwin K W, Kochs H D, Taud R J. Integer programming approach to the problem of optimal unit commitment with probabilistic reserve determination. IEEE Transactions on Power Apparatus and Systems, 1978, PAS-97(6): 2154–2166

[8] Daneshi H, Choobbari A L, Shahidehpour S M, Li Z Y. Mixed integer programming method to solve security constrained unit commitment with restricted operating zone limits. In: Proceedings of IEEE International Conference on Electro/Information Technology. Ames, USA, 2008, 187-192

[9] Cohen A I, Yoshimura M. A branch-and-bound algorithm for unit commitment. IEEE Transactions on Power Apparatus and Systems, 1983, PAS-102(2): 444–451

[10] Logenthiran T. Formulation of unit commitment (UC) problems and analysis of available methodologies used for solving the problems. In: Proceedings of IEEE International Conference on Sustainable Energy Technologies. Kandy, Sri Lanka, 2010, 1–6

[11] Snyder W L, Powell H D, Rayburn J C. Dynamic programming approach to power system unit commitment. IEEE Transactions on Power Systems, 1987, 2(2): 339–348

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg