ABSTRACT

Generally, the procedure for Solving Security constrained unit commitment (SCUC) problems within Lagrangian Relaxation framework is partitioned into two stages: one is to obtain feasible SCUC states; the other is to solve the economic dispatch of generation power among all the generating units. The core of the two stages is how to determine the feasibility of SCUC states. The existence of ramp rate constraints and security constraints increases the difficulty of obtaining an analytical necessary and sufficient condition for determining the quasi-feasibility of SCUC states at each scheduling time. However, a necessary and sufficient numerical condition is proposed and proven rigorously based on Benders Decomposition Theorem. Testing numerical example shows the effectiveness and efficiency of the condition.

1. Introduction

Security-constrained Unit commitment (SCUC) is one of the most important daily functions for independent system operators (ISOs) to clear the electric power market and for generation companies (GENCOs) to analyze generation costs and determine bidding strategies [1-3]. The objective of SCUC is to minimize the total bid cost in current electric power market or generating cost in traditional power systems while satisfying the system constraints including system demand balance, system spinning reserve and related transmission security constraints, and individual unit operating limits such as minimum/maximum generation level, minimum up/down times, ramping rate constraints.

Since the SCUC is an NP-hard mixed integer-programming problem, it is extremely difficult to obtain the exact optimal solution within acceptable time [4]. Lagrangian Relaxation (LR) is one of the most successful methods for obtaining suboptimal solutions [5], where Lagrange multipliers relax the system-wide constraints such as system demand balance, system spinning reserve and DC transmission constraints. Some methods, usually heuristics are needed to modify the dual solution into a feasible one. In fact, the Lagrangian based SCUC methods are all similar but the ways to obtain feasible solutions may vary significantly.

It is clear that the core to develop an effective method for solving SCUC problems within the Lagrangian relaxation framework is how to obtain feasible solutions. First of all, a necessary or sufficient condition used for checking promptly on the feasibility of SCUC states is crucial. Our previous work [6] proposed such conditions. However, a necessary and sufficient condition for determining the feasibility of SCUC states at each scheduling time is not given. Furthermore, ramp rate constraints are not taken into consideration in those results.

A necessary and sufficient condition for determining the feasibility of SCUC states at each scheduling time is proposed and proven rigorously in this paper based on the Benders Decomposition Feasibility Theorem [7,8]. The condition is very crucial for constructing a feasible solution of a SCUC problem. Numerical test example shows that the presented condition is very efficient.

2. Problem Formulation of SCUC Problems

For the convenience of presentation, some notations are defined as follows.

: commitment horizon in hours;

: number of units with the index denoting the unit;

: power generation by unit i at time t;

: binary variable: 1 if the unit is turned on or kept on during the time period, else 0;

: the number of time periods that Unit has been up ()or down ();

: the minimum number of time periods for which the unit must be up;

: the minimum number of time periods for which the unit must be down;

: fuel cost of producing power for thermal unit;

: startup/shutdown cost for unit;

: total demand of the whole power system during time period;

: the spinning reserve requirement during time period;

: is the spinning reserve requirement during time period, is the maximum spinning reserve requirement;

: the maximum generation of unit at scheduling time, if unit has no raping limit,;

: the minimum generation of unit at scheduling time, if unit has no raping limit,;

: the maximum ramp rate;

The objective of the unit commitment problem is to minimize the total operating cost as the following mixed integer-programming problem:

, (1)

subject to

2.1. System Level Constraints

1) System demand constraint

, (2)

where is the demand at bus;

2) Spinning reserve constraint:

, (3)

where is the maximum spinning reserve requirement.

3) Transmission security constraints:

(4)

2.2. Individual Unit Constraints

4) The minimum up/down time constraint:

, (5)

, (6)

5) The relation between the unit state and unit up/ down decision

(7)

6) Generation constraint

(8)

7) Ramp rate constraints: if

then

, (9)

8) Minimal power generation constraint at the first/last up hour:

(10)

3. The New Necessary and Sufficient Condition for Checking the Feasibility of SCUC States

A mixed-integer programming problem can be represented as

, (11)

where is assumed to be a nonempty convex set and is concave on Y for each fixed, and are continuous and discrete variables, respectively.

Definition: A vector is called to be quasifeasible if there exists a vector such that.

Benders Decomposition Feasibility Theorem [7,8]: For problem (11), and are nonempty and is convex, the vector function is concave vector function for each. Furthermore, the set

(12)

is closed for each. Then is quasifeasible if and only if the following inequalities are satisfied for

, (13)

where

, (14)

, (15)

Note 1: The result still holds for all.

Note 2: A SCUC problem can be written as the form of Equation (11), where

, (16)

, (17)

and is the number of generating units at scheduling time, are the indices of generating units, and are the minimal and maximal power generation of unit level, respectively. is a vector function, of which the first and second dimensions corresponds to the system demand constraint (since such constraint can be represented as two inequalities), the third relates to the spinning reserve constraint, and the rest dimensions correspond to transmission security constraints. is the total cost including the fuel cost of all generating units at time and their startup cost.

Since for SCUC state vector at each scheduling time the power generation of units not being started up need not be optimized, the set is determined by and is a convex cube of. For the given SCUC state vector, is the continuous concave vector function over the closed convex set, and hence is closed. Therefore, at each scheduling time, the SCUC problem is a mixed-integer programming of the form (11), which satisfies the conditions of the above Benders Decomposition Feasibility Theorem.

To obtain the desired result, the units are classified into three categories at time t: is the set of units which is on the normal generating state; is the set of units at the first/last generating hour; is the set of units with ramp rate constraints. The set is further classified into four types, named as, , and respectively, as follows:

Using the Benders Decomposition Feasibility Theorem, we obtain the desired necessary and sufficient condition for SCUC states to be feasible.

Theorem: SCUC states at scheduling time is quasifeasible if and only if the optimal value of the following nonlinear program is nonnegative:

, (18)

where

and

Proof: The left hand side of the Benders Decomposition Feasibility Theorem is

(19)

where

The solution of problem (19) depends on the following subproblems since the problem (19) is decomposable with respect to units:

i) Subproblem 1:, we have

ii) Subproblem 2:, we have

iii) Subproblem 3:, we have

iv) Subproblem 4:, we have

v) Subproblem 5:, we have

By Benders Decomposition Feasibility Theorem, we have the desired result. Q.E.D.

Note 3: The all subproblems above are linear programming problems with simple constraints. Thus, by comparing the values of all extreme points, the optimal solutions and corresponding optimal values can be obtained easily.

Note 4: It should be noted that the theorem still hold for.

4. The Numerical Solution of the Problem

Consider the SCUC problem at scheduling time with 0 being the objective

(20)

where, and are defined in Equations (16)-(17). The dual problem of the problem (20) is

, (21)

By the theorem and the note 4, is quasi-feasible if and only if and only if the optimal value of is nonnegative over the positive orthant. While the problem (21) can be solved by using subgradient method [9], and the value can be obtained by Equation (19) for the given Lagrange multiplier vector, the Lagrange multiplier can then be updated by subgradient method. Since the best multiplier vector in the dual iteration of the SCUC problem is taken as the initial multiplier, the rate of convergence of is quite promptly.

5. Numerical Testing Result

The standard IEEE example [5] tests the effectiveness and efficiency of the proposed method (Figure 1), which has 16 units, 43 transmission lines, 31 buses (of which 11 is load bus). The fuel cost function of unit is

The data of units, the system reserve requirement, the system demand at each scheduling time, the maximal value of DC power flow on each transmission line and the amount of electric power on each load bus are given in Tables 1-5, respectively. Units 1 and 4 have minimal power generation constraint at the first/last up hour.

The CPU-time is within 2.3 second for checking SCUC states for 24 scheduling period on a DELL Computer with 2G RAM using MATLAB 7.01. Table 6 gives a feasible SCUC obtained within Lagrangian framework. Figure 2 presented the tendency of with at. Testing example shows that the numerical method for determining the feasibility of a SCUC is effective and efficient.

6. Conclusions

The key of solving SCUC problems is to determine whether a SCUC is quasi-feasible or not. The existence of ramp rate constraints and transmission security constraints increases the difficulty of obtaining an analytical condition. However, a numerical necessary and sufficient condition for checking on the feasibility of SCUC states at each scheduling time is proposed and proved rigorously based on Benders Decomposition Feasibility

Theorem. The condition is very crucial for constructing a feasible solution of a SCUC problem. Numerical testing example shows that the proposed condition is very effective and efficient.

REFERENCES

NOTES

^*The research presented in this paper is supported by the Natural Science Foundation of the Education Department of Shaanxi Province (11JK0498).