# Security-Constrained Unit Commitment Based on a Realizable Energy Delivery Formulation

Authors: Hongyu Wu; Qiaozhu Zhai; Xiaohong Guan; Feng Gao; Hongxing Ye
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Security-constrained unit commitment (SCUC) is an important tool for independent system operators in the day-ahead electric power market. A serious issue arises that the energy realizability of the staircase generation schedules obtained in traditional SCUC cannot be guaranteed. This paper focuses on addressing this issue, and the basic idea is to formulate the power output of thermal units as piecewise-linear function. All individual unit constraints and systemwide constraints are then reformulated. The new SCUC formulation is solved within the Lagrangian relaxation (LR) framework, in which a double dynamic programming method is developed to solve individual unit subproblems. Numerical testing is performed for a 6-bus system and an IEEE 118-bus system on Microsoft Visual C# .NET platform. It is shown that the energy realizability of generation schedules obtained from the new formulation is guaranteed. Comparative case study is conducted between LR and mixed integer linear programming (MILP) in solving the new formulation. Numerical results show that the near-optimal solution can be obtained efficiently by the proposed LR-based method.


---

## Body

## 1. Introduction

Unit commitment (UC) is an important tool for independent system operators (ISOs) to obtain economical generation schedules in the day-ahead or week-ahead electric power market. The objective of UC is to determine the commitment states and generation levels of all generators over the scheduling horizon to minimize the total generation cost while meeting all systemwide constraints, such as system load balance and spinning reserve requirements, and individual unit operating constraints [1–3]. UC is often formulated as a nonlinear, large-scale, mixed integer programming (MIP) problem, and many approaches, such as dynamic programming (DP) [4], genetic algorithms (GAs) [5, 6], Lagrangian relaxation (LR) [1, 2, 7], Benders decomposition (BD) [8, 9], mixed integer linear programming (MILP) [10–12], and particle swarm optimization (PSO) [13–15], have been applied to solve the UC problems. LR is one of the most successful methods among them. The main advantage of applying LR is that its computational complexity of solving the dual problem is almost lineally related to the system size and therefore applicable for large-scale problem. In addition, Lagrange multipliers can be interpreted as the system shadow prices, which are important economic indicators of prices.Since the power grid is being driven to operate more and more close to its security margin, considering security-related transmission constraints in UC problem; that is, security-constrained UC (SCUC) becomes indispensable in the newly deregulated power market [16, 17]. In the current operation practice, a generation schedule is obtained from SCUC in day-ahead market and taken as an energy delivery schedule on an hourly basis in real time. Generators that are committed in the day-ahead scheduling have the obligation to deliver the awarded energy in real time. Generation companies (GENCOs) would be subject to real-time locational marginal prices (LMPs) and possibly incur penalties for deviating from the day-ahead schedule in the energy market [18, 19].In the literature on SCUC, the power output of a unit in each time period is represented by its average generation level such that the power output is formulated as a staircase function (see Figure1(a)). The ramp-rate constraints are also simplified as limits on the difference of average generation levels in consecutive time periods [16, 17, 20]. The most obvious advantage of the staircase power output is its computational simplicity since the energy output at each time period is numerically equal to its average generation level.The comparison of power output models.
(a)
Staircase model(b)
Piecewise-linear modelHowever, a serious issue arises that the energy realizability of the staircase generation schedules obtained in traditional SCUC cannot be guaranteed as stated in our previous work [18]. The staircase generation schedules are actually impossible to be implemented for GENCOs. In fact, we found that even though the ramp-rate constraints were satisfied, generation schedules with staircase generation levels might be still unrealizable in terms of energy delivery. A sufficient and necessary condition was thus established to check whether a generation schedule is deliverable in terms of energy [18]. To our best knowledge, there is little effort in literature to further address this issue. Therefore, it is still open and pressing to obtain energy-realizable schedules for SCUC.The cause of this issue lies in the fact that the energy output is distinguished from the power output especially when the ramping characteristics of generators are considered. If the energy output is to be accurately represented, it must be formulated as an integration of power output over a time period. However, such formulation with integral constraints as proposed in [21] is difficult to be incorporated into SCUC for practical implementation due to the computational complexity of SCUC problem. A trade-off solution is to assume the linear variation of power output such that the energy output at each time period can be easily represented by the power output [3]. This solution has been proven effective to treat the relationship between energy output and power output and thus it is also generalized to SCUC problem in this paper.In this paper we focus on addressing the energy unrealizable issue of traditional SCUC. First of all, this issue is demonstrated and analyzed through an example of SCUC problem. The piecewise-linear power output (see Figure1(b)) is then formulated by introducing additional continuous variables. All individual unit constraints and systemwide constraints such as system energy balance, spinning reserve requirements and, DC transmission constraints are reformulated based on the piecewise-linear model.The SCUC formulation established in this paper is then solved within the LR framework with all coupling constraints on different units relaxed by the Lagrange multipliers. A double dynamic programming method is used to obtain the exact optimal solution to each individual unit subproblem, and a modified subgradient algorithm is employed to update the multipliers. After the convergence of the Lagrange multipliers, a systematic method is developed for obtaining feasible solutions based on the dual solution.Numerical testing is performed for a 6-bus system and a modified IEEE 118-bus system. It is proved that the formulation established in this paper overcomes the unrealizable issue of traditional SCUC formulations in terms of energy delivery. Numerical testing results demonstrate that the energy realizability of generation schedules is guaranteed and the near-optimal generation schedule can be also obtained efficiently by the proposed LR-based method.The energy-realizable schedules obtained by the proposed LR method are also compared with those obtained by MILP-based method in IEEE 118-bus system. It is found that MILP-based method outperforms the LR-based method on small-size instances, but LR method is superior to the MILP method for solving larger-scale problems in term of computational efficiency. This feature is very important for solving large-scale SCUC problems.It should be noted that additional continuous variables are necessarily introduced in this paper to formulate the piecewise-linear power output and the energy output. The increase of the variables in our formulation has low impact on the computational complexity under LR-based solution method since they could be eliminated in the procedure of solving unit subproblems with all systemwide constraints relaxed.With great advances in theory and algorithms associated with other techniques [5, 6, 10–15] in recent years, many successful methods and important results have been obtained based on those methods. The motivation of this work, nevertheless, is not to give a full comparison between LR and other methods for solving the new SCUC problem. In this paper, we only want to suggest that one way is also valuable and important, that is, to design algorithms based on deep analysis and full utilization of the structure of SCUC. In this way, some new characteristics of the problem may be found and we may get a better understanding of the nature of SCUC problem. The algorithms designed may be still efficient since much structure information of the problem is combined with the algorithms.The main contributions of this paper are as follows: (1) an energy-realizable SCUC formulation is presented by modeling power output as piecewise-linear function as well as reformulating individual unit constraints and systemwide constraints; (2) a double dynamic programming algorithm is developed to solve the hard unit subproblem under the new formulation.This paper is organized as follows. The mathematical formulation is presented in Section2, in which an example is firstly given to demonstrate the deficiency of staircase power output, and the piecewise-linear formulation for SCUC is then established. The LR-based solution framework is discussed in Section 3. Numerical testing results are listed and analyzed in Section 4, and the paper is concluded in Section 5.


## 2. Mathematical Formulation

### 2.1. The Deficiency of Staircase Power Output: An Example

Following the examples in our previous work [18], the deficiency of staircase power output in traditional SCUC is presented in this section for self-containing. Let the minimum and maximum generation levels of a thermal unit be 100 MW and 300 MW, and the ramping limit (up or down) is 5 MW/min in an SCUC problem. Assume the generation output in the first hour is maintained at 300 MW.Variablesp(1), p(2) represent the average generation levels (in MW) in the first two hours. If the time period is one hour, they are numerically equal to the energy delivery (in MWh) in the time period, where p(1), p(2) are within their limits and satisfy the ramping constraints [8, 16, 17]:(2.1)100≤p(2)≤300,|p(2)-p(1)|≤5×60=300.It is obvious thatp(2)=100 is a feasible solution to this problem. However, if 100 MWh is taken as the scheduled energy output at the second hour based on the traditional SCUC formulation, it is unrealizable since the generation level is physically constrained and cannot change instantaneously at the beginning of hour 2 (point A in Figure 2). Even if the unit fully ramps down, the practical minimum energy output during hour 2 is 166 MWh, which is numerically equal to the area of ACDEF in Figure 2, and much greater than the scheduled energy output, the area of BDEF. The above example suggests that satisfying the ramping constraints cannot guarantee the desired energy output. In other words, the generation schedule with staircase power output obtained from traditional SCUC formulation may not be realizable in terms of energy delivery.Figure 2
Power generation and energy delivery.


### 2.2. The Piecewise-Linear Formulation for SCUC

Suppose a power system withI thermal units and the horizon of scheduling is partitioned into T time periods. The SCUC problem is formulated as the following mixed-integer optimization problem with the objective to minimize the total operating costs.(2.2)min⁡J=∑i=1I{∑t=1T[Ci(Ei(t))+Si(xi(t),ui(t))]}.
Quadratic fuel cost Ci(·) and piecewise linear start-up cost Si(·) are generally adopted in literature, and the detailed mathematical formulations can be found in [1, 22]. All constraints are listed as follows, in which i=1,…,I, t=1,…,T, l=1,…,L.(a) Discrete State Transition
(2.3)xi(t+1)={xi(t)+ui(t),ifxi(t)⋅ui(t)>0,ui(t),else.(b) Minimum Up/Down Time Limits
(2.4)ui(t)={1,1≤xi(t)<τ̅i,-1,-τ̲i<xi(t)≤-1.(c) Power Generation Limits
(2.5)P̲i≤{pileft(t)≤P̅i,ifui(t)=1,piright(t)≤P̅i,ifui(t)=1.(d) Coincidence Constraints on Power Output
(2.6)pileft(t+1)=piright(t),ifui(t)=1,ui(t+1)=1,(2.7)pileft(t)=piright(t)=0,ifui(t)=-1.
The coincidence constraint (2.6) suggests that piright(t) and pileft(t+1) coincide for each two consecutive ON-state periods as illustrated in Figure 3 and implies that the power output trajectory of each unit must be continuous at the transition point of two adjacent ON-state periods. In comparison with the staircase power output model, the piecewise-linear model has better practicality since sudden changes are not allowed at this transition point.Figure 3
Power output modeled as a piecewise-linear function.(e) Minimum Generation at the First/Last ON-State Period
(2.8)pileft(t)=P̲i,ifui(t-1)=-1,ui(t)=1,(2.9)piright(t)=P̲i,ifui(t)=1,ui(t+1)=-1.
Constraints (2.8) and (2.9) are effective only for some units [23]. As observed in Figure 3, when a unit switches ON at period t, piright(t-1)=0 according to constraint (2.7). If constraint (2.8) is active, we have pileft(t)=P̲i. It is seen that pileft(t) and piright(t-1) do not coincide in the start-up process, neither do they coincide in a shut-down process when the unit switches OFF. The necessity of introducing additional variables can be seen at this point.(f) Relationship between Energy Output and Power Output
As mentioned in introduction, the energy output during periodt (the shadow area in Figure 3) can be easily calculated based on the assumption of linear variation of power output, and it can be clearly expressed as follows:
(2.10)Ei(t)=pileft(t)+piright(t)2⋅η.
It is also seen from Figure 3 that the additional variables are needed in this paper to formulate the energy output when considering ON/OFF-state switches. With the analysis in Section 2.1, it is found that the simplified ramp-rate constraint in traditional SCUC formulation is one of the main factors leading to the unrealizability of staircase generation schedule; a ramping model with realizable energy delivery is therefore established as follows.(g) Ramp-Rate Constraints
(2.11)|pileft(t)-piright(t)|≤Δi,ifui(t)=1.
It is observed in Figure 3 that the ramp-rate constraint (2.11) is formulated as the limit on the difference between pileft(t) and piright(t) within period t. This ramping model is superior to the one used in staircase formulation since the ramping process for implementing the required energy output is in fact obtainable. Note that we adopt fixed unit ramping limit in this paper. However, the stepwise- or piecewise-linear ramping limits presented in [24] can be also included in this formulation.(h) Spinning Reserve Contribution
(2.12)ri(t)={min⁡{P̅i-pileft(t),Δ⋅τ},ifui(t)=1,0,else.
The individual unit operating constraints are listed in (2.3)–(2.12), and the systemwide constraints are formulated as follows.(i) System Energy Balance
(2.13)∑i=1IEi(t)=Pd(t)⋅η.
It is worth emphasizing that (2.13) is given in MWh rather than MW since the transactions are all processed in terms of electric energy in the energy market [18, 19].(j) Spinning Reserve Requirements
(2.14)∑i=1Iri(t)≥R(t).(k) DC Transmission Constraints (Security Constraints)
(2.15)-F̅l≤∑i=1IΓl,iU⋅pileft(t)-∑m=1MΓl,mD⋅dm(t)≤F̅l,(2.16)-F̅l≤∑i=1IΓl,iU⋅piright(t)-∑m=1MΓl,mD⋅dm(t)≤F̅l.
Due to the monotonicity of piecewise-linear power output within period t, if inequalities (2.15) and (2.16) are satisfied, it is guaranteed that each transmission line is not overloaded at any time within the interior of period t. Note that DC power flow model is used in this paper for computational simplicity, and the piecewise-linear power output can be also applied to AC network models [25].(l) Emission Limits
(2.17)∑i=1IHi(Ei(t))=ψi⋅Ei(t)≤Θ(t).
The emission Hi(·) is expressed as a linear function of energy output in this paper, and several emission types (e.g., SO2, NOx) can be considered.
Combining (2.2)–(2.17), a new SCUC formulation with piecewise-linear power output is established. Note that this formulation can be also incorporated into contingency-constrained unit commitment (CCUC) problem [26]. However, the scale of SCUC problem is usually large and hundreds of units, transmission lines, and buses as well as time periods need to be accounted for; even if a limited set of credible contingencies and the n-1 security criterion are considered, the computational burden for doing this is intensive. For the above reasons, we do not consider contingencies in this paper. Although this formulation differs from the traditional SCUC formulation, it can be still efficiently solved within the LR framework. This will be discussed in the next section.


## 2.1. The Deficiency of Staircase Power Output: An Example

Following the examples in our previous work [18], the deficiency of staircase power output in traditional SCUC is presented in this section for self-containing. Let the minimum and maximum generation levels of a thermal unit be 100 MW and 300 MW, and the ramping limit (up or down) is 5 MW/min in an SCUC problem. Assume the generation output in the first hour is maintained at 300 MW.Variablesp(1), p(2) represent the average generation levels (in MW) in the first two hours. If the time period is one hour, they are numerically equal to the energy delivery (in MWh) in the time period, where p(1), p(2) are within their limits and satisfy the ramping constraints [8, 16, 17]:(2.1)100≤p(2)≤300,|p(2)-p(1)|≤5×60=300.It is obvious thatp(2)=100 is a feasible solution to this problem. However, if 100 MWh is taken as the scheduled energy output at the second hour based on the traditional SCUC formulation, it is unrealizable since the generation level is physically constrained and cannot change instantaneously at the beginning of hour 2 (point A in Figure 2). Even if the unit fully ramps down, the practical minimum energy output during hour 2 is 166 MWh, which is numerically equal to the area of ACDEF in Figure 2, and much greater than the scheduled energy output, the area of BDEF. The above example suggests that satisfying the ramping constraints cannot guarantee the desired energy output. In other words, the generation schedule with staircase power output obtained from traditional SCUC formulation may not be realizable in terms of energy delivery.Figure 2
Power generation and energy delivery.


## 2.2. The Piecewise-Linear Formulation for SCUC

Suppose a power system withI thermal units and the horizon of scheduling is partitioned into T time periods. The SCUC problem is formulated as the following mixed-integer optimization problem with the objective to minimize the total operating costs.(2.2)min⁡J=∑i=1I{∑t=1T[Ci(Ei(t))+Si(xi(t),ui(t))]}.
Quadratic fuel cost Ci(·) and piecewise linear start-up cost Si(·) are generally adopted in literature, and the detailed mathematical formulations can be found in [1, 22]. All constraints are listed as follows, in which i=1,…,I, t=1,…,T, l=1,…,L.(a) Discrete State Transition
(2.3)xi(t+1)={xi(t)+ui(t),ifxi(t)⋅ui(t)>0,ui(t),else.(b) Minimum Up/Down Time Limits
(2.4)ui(t)={1,1≤xi(t)<τ̅i,-1,-τ̲i<xi(t)≤-1.(c) Power Generation Limits
(2.5)P̲i≤{pileft(t)≤P̅i,ifui(t)=1,piright(t)≤P̅i,ifui(t)=1.(d) Coincidence Constraints on Power Output
(2.6)pileft(t+1)=piright(t),ifui(t)=1,ui(t+1)=1,(2.7)pileft(t)=piright(t)=0,ifui(t)=-1.
The coincidence constraint (2.6) suggests that piright(t) and pileft(t+1) coincide for each two consecutive ON-state periods as illustrated in Figure 3 and implies that the power output trajectory of each unit must be continuous at the transition point of two adjacent ON-state periods. In comparison with the staircase power output model, the piecewise-linear model has better practicality since sudden changes are not allowed at this transition point.Figure 3
Power output modeled as a piecewise-linear function.(e) Minimum Generation at the First/Last ON-State Period
(2.8)pileft(t)=P̲i,ifui(t-1)=-1,ui(t)=1,(2.9)piright(t)=P̲i,ifui(t)=1,ui(t+1)=-1.
Constraints (2.8) and (2.9) are effective only for some units [23]. As observed in Figure 3, when a unit switches ON at period t, piright(t-1)=0 according to constraint (2.7). If constraint (2.8) is active, we have pileft(t)=P̲i. It is seen that pileft(t) and piright(t-1) do not coincide in the start-up process, neither do they coincide in a shut-down process when the unit switches OFF. The necessity of introducing additional variables can be seen at this point.(f) Relationship between Energy Output and Power Output
As mentioned in introduction, the energy output during periodt (the shadow area in Figure 3) can be easily calculated based on the assumption of linear variation of power output, and it can be clearly expressed as follows:
(2.10)Ei(t)=pileft(t)+piright(t)2⋅η.
It is also seen from Figure 3 that the additional variables are needed in this paper to formulate the energy output when considering ON/OFF-state switches. With the analysis in Section 2.1, it is found that the simplified ramp-rate constraint in traditional SCUC formulation is one of the main factors leading to the unrealizability of staircase generation schedule; a ramping model with realizable energy delivery is therefore established as follows.(g) Ramp-Rate Constraints
(2.11)|pileft(t)-piright(t)|≤Δi,ifui(t)=1.
It is observed in Figure 3 that the ramp-rate constraint (2.11) is formulated as the limit on the difference between pileft(t) and piright(t) within period t. This ramping model is superior to the one used in staircase formulation since the ramping process for implementing the required energy output is in fact obtainable. Note that we adopt fixed unit ramping limit in this paper. However, the stepwise- or piecewise-linear ramping limits presented in [24] can be also included in this formulation.(h) Spinning Reserve Contribution
(2.12)ri(t)={min⁡{P̅i-pileft(t),Δ⋅τ},ifui(t)=1,0,else.
The individual unit operating constraints are listed in (2.3)–(2.12), and the systemwide constraints are formulated as follows.(i) System Energy Balance
(2.13)∑i=1IEi(t)=Pd(t)⋅η.
It is worth emphasizing that (2.13) is given in MWh rather than MW since the transactions are all processed in terms of electric energy in the energy market [18, 19].(j) Spinning Reserve Requirements
(2.14)∑i=1Iri(t)≥R(t).(k) DC Transmission Constraints (Security Constraints)
(2.15)-F̅l≤∑i=1IΓl,iU⋅pileft(t)-∑m=1MΓl,mD⋅dm(t)≤F̅l,(2.16)-F̅l≤∑i=1IΓl,iU⋅piright(t)-∑m=1MΓl,mD⋅dm(t)≤F̅l.
Due to the monotonicity of piecewise-linear power output within period t, if inequalities (2.15) and (2.16) are satisfied, it is guaranteed that each transmission line is not overloaded at any time within the interior of period t. Note that DC power flow model is used in this paper for computational simplicity, and the piecewise-linear power output can be also applied to AC network models [25].(l) Emission Limits
(2.17)∑i=1IHi(Ei(t))=ψi⋅Ei(t)≤Θ(t).
The emission Hi(·) is expressed as a linear function of energy output in this paper, and several emission types (e.g., SO2, NOx) can be considered.
Combining (2.2)–(2.17), a new SCUC formulation with piecewise-linear power output is established. Note that this formulation can be also incorporated into contingency-constrained unit commitment (CCUC) problem [26]. However, the scale of SCUC problem is usually large and hundreds of units, transmission lines, and buses as well as time periods need to be accounted for; even if a limited set of credible contingencies and the n-1 security criterion are considered, the computational burden for doing this is intensive. For the above reasons, we do not consider contingencies in this paper. Although this formulation differs from the traditional SCUC formulation, it can be still efficiently solved within the LR framework. This will be discussed in the next section.


## 3. Solution Methodology

### 3.1. The Lagrangian Relaxation Framework

The basic idea of the LR-based method is to relax systemwide constraints and convert the original problem into a two-level optimization structure [1, 7]. Figure 4 shows the flow chart of the LR-based method. Constraints (2.13)–(2.17) are relaxed by using Lagrange multipliers, and the Lagrangian function is expressed as follows:(3.1)L=∑t=1T∑i=1I[Ci(pileft(t)+piright(t)2)+Si(xi(t),ui(t))]+∑t=1Tλ(t)(Pd(t)⋅η-∑i=1Ipileft(t)+piright(t)2)+∑t=1Tμ(t)[R(t)-ri(t)]+∑t=1T∑l=1L{αl(t)[-F̅l+∑m=1MΓl,mD⋅dm(t)-∑i=1IΓl,iU⋅pileft(t)]}+∑t=1T∑l=1L{βl(t)[-F̅l-∑m=1MΓl,mD⋅dm(t)+∑i=1IΓl,iU⋅pileft(t)]}+∑t=1T∑l=1L{γl(t)[-F̅l+∑m=1MΓl,mD⋅dm(t)-∑i=1IΓl,iU⋅piright(t)]}+∑t=1T∑l=1L{ρl(t)[-F̅l-∑m=1MΓl,mD⋅dm(t)+∑i=1IΓl,iU⋅piright(t)]}+∑t=1Tν(t)[∑i=1Iψi⋅pileft(t)+piright(t)2-Θt].
By using duality theory and the decomposable structure of (3.1), a two-level optimization structure is then formed. Given a set of multipliers, the low-level optimization consists of individual unit subproblems. The ith subproblem is defined as follows:(3.2)min⁡pileft(t),piright(t),ui(t)Li=∑t=1T[Ci(pileft(t)+piright(t)2)+Si(xi(t),ui(t))-λ(t)⋅pileft(t)+piright(t)2-μ(t)⋅ri(t)+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅pileft(t)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(t)+ν(t)⋅ψi⋅pileft(t)+piright(t)2]
subject to constraints (2.3)–(2.12). Let  Subi*(λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t)) denote the optimal objective value of the ith subproblem; then, the dual problem in high level is as follows:(3.3)max⁡λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t)Φ=∑i=1ISubi*(λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t))+∑t=1T{∑m=1MΓl,mDλ(t)Ed(t)+μ(t)R(t)-ν(t)Θ(t)+∑l=1L[αl(t)+γl(t)][-F̅l+∑m=1MΓl,mD⋅dm(t)]+∑l=1L[βl(t)+ρl(t)][-F̅l-∑m=1MΓl,mD⋅dm(t)]}.
The low-level and high-level problems are solved iteratively, and a method for constructing feasible solutions is required after the convergence of the iterative process since the solutions to unit subproblems may not constitute a feasible solution [7, 27].Figure 4
The framework of the Lagrangian relaxation.


### 3.2. Solving Individual Unit Subproblems

It is seen that the individual unit subproblem (3.2) is more complicated than those within the LR framework in traditional SCUC problems. If there are no ramp-rate constraints, the unit subproblem can be efficiently solved by using dynamic programming [1]. However, the unit subproblem (3.2) with ramp rate constraints (2.11) is very difficult to solve since the ramp rate constraints couple all continuous and discrete variables in consecutive periods. The new state transition diagram proposed in [28] is an efficient approach to resolve this difficulty.Supposexi(t0)>τ̅i without loss of generality, and an example of the new state transition diagram is shown in Figure 5, in which t0 represents the initial time period, while t1,t2,…,tn represent the time periods when ON/OFF states switch. Each node corresponds to a switch-ON or switch-OFF decision. The edges connecting t1 and t2 stand for consecutive OFF-state periods, while the edges connecting t2 and t3 stand for consecutive ON-state periods. For uniform representation, the edges connecting the uppermost nodes labeled “tn=T+1” mean the ON/OFF states keep unchanged to the end of the schedule horizon.Figure 5
The new state transition diagram.Based on the new state transition diagram, the entire schedule horizon is divided into several consecutive ON-state periods and several consecutive OFF-state periods. The continuous and discrete decision variables are therefore decoupled, and the solution to subproblem (3.2) is decomposed into determination of the optimal power generation levels in all consecutive ON-state periods (continuous optimization problems) and determination of the optimal switch-ON decisions (a discrete optimization problem). With the above analysis, a double dynamic programming framework that comprises continuous dynamic programming in low level and a discrete dynamic programming in high level is therefore formed. Figure 6 illustrates the framework of the double DP.Figure 6
The framework of double dynamic programming.The start-up cost during the consecutive OFF-state periods can be easily obtained when the piecewise linear formulation ofSi(·) is given. The main difficulty lies in obtaining the optimal power generation levels during the consecutive ON-state periods. If we replace pileft(t+1) with piright(t) according to constraint (2.6) and substitute (2.12) into (3.2), the power generation levels during the consecutive ON-state periods are determined by the following continuous optimization problem:
(3.4)min⁡piright(t),pileft(T1)∑t=T1+1T2{Ci(piright(t-1)+piright(t)2)-λ(t)⋅piright(t-1)+piright(t)2-μ(t)⋅min⁡{P̅i-piright(t-1),Δ⋅τ}+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅piright(t-1)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(t)+ν(t)⋅ψi⋅piright(t-1)+piright(t)2}+Ci(pileft(T1)+piright(T1)2)-λ(t)⋅pileft(T1)+piright(T1)2-μ(t)⋅min⁡{P̅i-pileft(T1),Δ⋅τ}+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅pileft(T1)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(T1)+ν(t)⋅ψi⋅pileft(T1)+piright(T1)2
subject to constraints (2.5), (2.8), (2.9), and (2.11). In the objective function (3.4), T1 and T2 are, respectively, the indexes of the first and last period of the consecutive ON-state periods; {piright(t)}t=T1T2 and pileft(T1) are the continuous decision variables that are to be determined. It is seen that variables {pileft(t)}t=T1+1T2 are eliminated in (3.4) and only one extra variable, namely, pileft(T1), is introduced. Hence, almost no additional computational effort is required to deal with the extra variables in solving unit subproblem (3.2). Note that we use optimal linear approximation (OLA) to the quadratic fuel cost Ci(·), and the linear formulation of fuel cost Ci′(·) is defined as follows:(3.5)Ci′(Ei(t))={b̃Ei(t)+c̃,ifEi(t)≠0,0,ifEi(t)=0,
where constants b̃ and c̃ can be easily determined based on Ci(·). The detailed description of OLA can be found in [29], and the numerical testing results suggest that the relative approximation error of OLA is generally less than 0.5%.Based on the above analysis, the continuous optimization problem (3.4) can be explicitly transformed into the following form (subscript i is dropped for presentation simplicity)(3.6)min⁡=∑t=T1-1T2ft(y(t)),(3.7)s.t.y̲t≤y(t)≤y̅t,t=T1-1,T1,…,T2,(3.8)|y(t)-y(t-1)|≤Δ,t=T1,T1+1,…,T2,
in which y(t) and y(T1-1) represent piright(t) and pileft(T1), respectively. ft(·) denotes the objective function of continuous optimization problem (3.4) at period t. y̲t and y̅t are the minimum and maximum power generation levels at period t. Note that for the units with constraints (2.8) and (2.9), let y̲t=y̅t=P̲ at the first and last ON-state periods such that constraints (2.8) and (2.9) are included in (3.7) implicitly.Step 1 (low-level DP).
As shown in Figure6, the continuous DP algorithm in low level for solving optimization problem (3.6)–(3.8) is summarized as follows.
Substep 1.1 (constructing the cost-to-go functions in backward sweep).
LetCGt(·) denote the cost-to-go function at periodtand initially let CGT2(y(T2))=fT2(y(T2)), where y(T2)∈[y̲T2,y̅T2].  For t=T2-1,T2-2,…,T1-1, let
(3.9)CGt(y(t))=ft(y(t))+min⁡y(t+1)CGt+1(y(t+1))
subject to (3.7) and (3.8).  It is seen that the cost-to-go function CGt(·) is expressed in a recursive form.  Since there exists no feasible solution to optimization problem (3.9) if y(t)>y̅t+1+Δ or y(t)<y̲t+1-Δ, the feasible region of y(t) is redefined by its lower and upper bounds as follows to ensure feasible solutions of problem (3.9):
(3.10)y̅t=min⁡{y̅t+1+Δ,y̅t},y̲t=max⁡{y̲t+1-Δ,y̲t}.
Combining (3.7), (3.8), and (3.10), problem (3.9) can be expressed as follows:
(3.11)CGt(y(t))=ft(y(t))+min⁡y(t+1)CGt+1(y(t+1)),s.t.y(t+1)∈[y̲t+1,y̅t+1]∩[y(t)-Δ,y(t)+Δ],t=T2-1,T2-2,…,T1-1.
The cost-to-go function CGt(·) can be obtained by solving problem (3.11) recursively, and more detailed discussion can be found in [28].Substep 1.2 (obtaining the optimal generation levels in forward sweep).
Lety*(T1-1)=argminy(T1-1)CGT1-1(y(T1-1)), where y(T1-1)∈[y̲T1-1,y̅T1-1].  For t=T1,T1+1,…,T2, let
(3.12)y*(t)=argmin⁡y(t)CGt(y(t)),s.t.y(t)∈[y̲t,y̅t]∩[y*(t-1)-Δ,y*(t-1)+Δ].
According to the theory of dynamic programming, it is clear that {y*(t)}t=T1-1T2 obtained from the above steps is the optimal solution to problem (3.6)–(3.8).Step 2 (high-level DP).
If the optimal generation levels and costs related to all consecutive ON-state periods and the start-up costs associated with all consecutive OFF-state periods are obtained, the optimal switch-ON decisions across the schedule horizon can be easily determined by using a discrete DP algorithm in high level, as seen in Figure6.
The principal advantage of double DP is that the exact optimal solution to the subproblem (3.2) can be obtained without discretizing power generation levels or using intermediate levels of relaxation. Moreover, it is beneficial to the convergence characteristics of dual function since the concavity of the dual problem is only guaranteed by the exact optimal solutions to the unit subproblems [30].


### 3.3. Updating the Lagrange Multipliers

A modified subgradient method with adaptive step size is employed to update the Lagrange multipliers. Lettingg denote a point in the dual space, an iteration relation can be implemented to maximize the dual function (3.3):(3.13)gk+1=gk+skΔgk,
where k denotes iteration number, sk is the adaptive step size, and Δgk is the subgradient at the kth iteration. The Lagrange multipliers regarding transmission line l are updated as follows:(3.14)αlk+1(t)=max⁡(0,αlk(t)+skΔgαlk(t)),γlk+1(t)=max⁡(0,γlk(t)+skΔgγlk(t)),βlk+1(t)=max⁡(0,βlk(t)+skΔgβlk(t)),ρlk+1(t)=max⁡(0,ρlk(t)+skΔgρlk(t)).
The step size used in our implementation has the following form:(3.15)sk+1={skj‖Δgk‖‖Δgk+1‖,ifΦk+1<Φk,sk,else,
where j is a positive scaling constant that is less than 1 and ||Δgk|| and Φk are the norm of subgradient and the dual cost at the kth iteration, respectively. It can be seen that the step size keeps unchanged when the dual cost becomes larger than that at last iteration and decreases when it becomes smaller. The method for updating multipliers stops when k reaches the maximum iteration number or the following stopping criteria are satisfied:(3.16)‖gk+1-gk‖<ε⋅Φk,
where ε is a small positive constant.


### 3.4. Constructing Feasible Solutions

A systematic method including heuristics is developed for constructing feasible solutions since the dual solution obtained usually does not satisfy the relaxed constraints (2.13)–(2.17). This method is summarized as the following major steps [31].Step 1.
Determine the feasibility (satisfying constraints (2.13)–(2.17)) of a UC (u1(t),u2(t),…,uI(t)) at period t by checking whether analytical feasibility conditions proposed in [32] are satisfied. If (u1(t),u2(t),…,uI(t)) is infeasible, go to Step 2; otherwise go to Step 3. Note that the first UC at each time period is exactly the one obtained at the final dual solution.Step 2.
Heuristics combined with “opportunity-cost” based criterion presented in [27] are used to adjust the ON/OFF states of certain units that satisfy the minimum up/down time constraints (2.4), such that the infeasible UC is closer to a feasible one after each adjustment (the degree of infeasibility can be measured by the total violation of system constraints). The UC adjustment is then formulated as a zero-one programming problem, and a branch and bound (B&B) method is developed to solve it. Once a new satisfactory UC is obtained, go back to Step 1.Step 3.
Security-constrained economic dispatch (SCED) is performed for(u1(t),u2(t),…,uI(t)) to obtain the optimal power generation levels. If t<T, let t=t+1 and then go back to Step 1; otherwise stop.


## 3.1. The Lagrangian Relaxation Framework

The basic idea of the LR-based method is to relax systemwide constraints and convert the original problem into a two-level optimization structure [1, 7]. Figure 4 shows the flow chart of the LR-based method. Constraints (2.13)–(2.17) are relaxed by using Lagrange multipliers, and the Lagrangian function is expressed as follows:(3.1)L=∑t=1T∑i=1I[Ci(pileft(t)+piright(t)2)+Si(xi(t),ui(t))]+∑t=1Tλ(t)(Pd(t)⋅η-∑i=1Ipileft(t)+piright(t)2)+∑t=1Tμ(t)[R(t)-ri(t)]+∑t=1T∑l=1L{αl(t)[-F̅l+∑m=1MΓl,mD⋅dm(t)-∑i=1IΓl,iU⋅pileft(t)]}+∑t=1T∑l=1L{βl(t)[-F̅l-∑m=1MΓl,mD⋅dm(t)+∑i=1IΓl,iU⋅pileft(t)]}+∑t=1T∑l=1L{γl(t)[-F̅l+∑m=1MΓl,mD⋅dm(t)-∑i=1IΓl,iU⋅piright(t)]}+∑t=1T∑l=1L{ρl(t)[-F̅l-∑m=1MΓl,mD⋅dm(t)+∑i=1IΓl,iU⋅piright(t)]}+∑t=1Tν(t)[∑i=1Iψi⋅pileft(t)+piright(t)2-Θt].
By using duality theory and the decomposable structure of (3.1), a two-level optimization structure is then formed. Given a set of multipliers, the low-level optimization consists of individual unit subproblems. The ith subproblem is defined as follows:(3.2)min⁡pileft(t),piright(t),ui(t)Li=∑t=1T[Ci(pileft(t)+piright(t)2)+Si(xi(t),ui(t))-λ(t)⋅pileft(t)+piright(t)2-μ(t)⋅ri(t)+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅pileft(t)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(t)+ν(t)⋅ψi⋅pileft(t)+piright(t)2]
subject to constraints (2.3)–(2.12). Let  Subi*(λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t)) denote the optimal objective value of the ith subproblem; then, the dual problem in high level is as follows:(3.3)max⁡λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t)Φ=∑i=1ISubi*(λ(t),μ(t),ν(t),αl(t),βl(t),γl(t),ρl(t))+∑t=1T{∑m=1MΓl,mDλ(t)Ed(t)+μ(t)R(t)-ν(t)Θ(t)+∑l=1L[αl(t)+γl(t)][-F̅l+∑m=1MΓl,mD⋅dm(t)]+∑l=1L[βl(t)+ρl(t)][-F̅l-∑m=1MΓl,mD⋅dm(t)]}.
The low-level and high-level problems are solved iteratively, and a method for constructing feasible solutions is required after the convergence of the iterative process since the solutions to unit subproblems may not constitute a feasible solution [7, 27].Figure 4
The framework of the Lagrangian relaxation.


## 3.2. Solving Individual Unit Subproblems

It is seen that the individual unit subproblem (3.2) is more complicated than those within the LR framework in traditional SCUC problems. If there are no ramp-rate constraints, the unit subproblem can be efficiently solved by using dynamic programming [1]. However, the unit subproblem (3.2) with ramp rate constraints (2.11) is very difficult to solve since the ramp rate constraints couple all continuous and discrete variables in consecutive periods. The new state transition diagram proposed in [28] is an efficient approach to resolve this difficulty.Supposexi(t0)>τ̅i without loss of generality, and an example of the new state transition diagram is shown in Figure 5, in which t0 represents the initial time period, while t1,t2,…,tn represent the time periods when ON/OFF states switch. Each node corresponds to a switch-ON or switch-OFF decision. The edges connecting t1 and t2 stand for consecutive OFF-state periods, while the edges connecting t2 and t3 stand for consecutive ON-state periods. For uniform representation, the edges connecting the uppermost nodes labeled “tn=T+1” mean the ON/OFF states keep unchanged to the end of the schedule horizon.Figure 5
The new state transition diagram.Based on the new state transition diagram, the entire schedule horizon is divided into several consecutive ON-state periods and several consecutive OFF-state periods. The continuous and discrete decision variables are therefore decoupled, and the solution to subproblem (3.2) is decomposed into determination of the optimal power generation levels in all consecutive ON-state periods (continuous optimization problems) and determination of the optimal switch-ON decisions (a discrete optimization problem). With the above analysis, a double dynamic programming framework that comprises continuous dynamic programming in low level and a discrete dynamic programming in high level is therefore formed. Figure 6 illustrates the framework of the double DP.Figure 6
The framework of double dynamic programming.The start-up cost during the consecutive OFF-state periods can be easily obtained when the piecewise linear formulation ofSi(·) is given. The main difficulty lies in obtaining the optimal power generation levels during the consecutive ON-state periods. If we replace pileft(t+1) with piright(t) according to constraint (2.6) and substitute (2.12) into (3.2), the power generation levels during the consecutive ON-state periods are determined by the following continuous optimization problem:
(3.4)min⁡piright(t),pileft(T1)∑t=T1+1T2{Ci(piright(t-1)+piright(t)2)-λ(t)⋅piright(t-1)+piright(t)2-μ(t)⋅min⁡{P̅i-piright(t-1),Δ⋅τ}+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅piright(t-1)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(t)+ν(t)⋅ψi⋅piright(t-1)+piright(t)2}+Ci(pileft(T1)+piright(T1)2)-λ(t)⋅pileft(T1)+piright(T1)2-μ(t)⋅min⁡{P̅i-pileft(T1),Δ⋅τ}+∑l=1L[βl(t)-αl(t)]⋅Γl,iU⋅pileft(T1)+∑l=1L[ρl(t)-γl(t)]⋅Γl,iU⋅piright(T1)+ν(t)⋅ψi⋅pileft(T1)+piright(T1)2
subject to constraints (2.5), (2.8), (2.9), and (2.11). In the objective function (3.4), T1 and T2 are, respectively, the indexes of the first and last period of the consecutive ON-state periods; {piright(t)}t=T1T2 and pileft(T1) are the continuous decision variables that are to be determined. It is seen that variables {pileft(t)}t=T1+1T2 are eliminated in (3.4) and only one extra variable, namely, pileft(T1), is introduced. Hence, almost no additional computational effort is required to deal with the extra variables in solving unit subproblem (3.2). Note that we use optimal linear approximation (OLA) to the quadratic fuel cost Ci(·), and the linear formulation of fuel cost Ci′(·) is defined as follows:(3.5)Ci′(Ei(t))={b̃Ei(t)+c̃,ifEi(t)≠0,0,ifEi(t)=0,
where constants b̃ and c̃ can be easily determined based on Ci(·). The detailed description of OLA can be found in [29], and the numerical testing results suggest that the relative approximation error of OLA is generally less than 0.5%.Based on the above analysis, the continuous optimization problem (3.4) can be explicitly transformed into the following form (subscript i is dropped for presentation simplicity)(3.6)min⁡=∑t=T1-1T2ft(y(t)),(3.7)s.t.y̲t≤y(t)≤y̅t,t=T1-1,T1,…,T2,(3.8)|y(t)-y(t-1)|≤Δ,t=T1,T1+1,…,T2,
in which y(t) and y(T1-1) represent piright(t) and pileft(T1), respectively. ft(·) denotes the objective function of continuous optimization problem (3.4) at period t. y̲t and y̅t are the minimum and maximum power generation levels at period t. Note that for the units with constraints (2.8) and (2.9), let y̲t=y̅t=P̲ at the first and last ON-state periods such that constraints (2.8) and (2.9) are included in (3.7) implicitly.Step 1 (low-level DP).
As shown in Figure6, the continuous DP algorithm in low level for solving optimization problem (3.6)–(3.8) is summarized as follows.
Substep 1.1 (constructing the cost-to-go functions in backward sweep).
LetCGt(·) denote the cost-to-go function at periodtand initially let CGT2(y(T2))=fT2(y(T2)), where y(T2)∈[y̲T2,y̅T2].  For t=T2-1,T2-2,…,T1-1, let
(3.9)CGt(y(t))=ft(y(t))+min⁡y(t+1)CGt+1(y(t+1))
subject to (3.7) and (3.8).  It is seen that the cost-to-go function CGt(·) is expressed in a recursive form.  Since there exists no feasible solution to optimization problem (3.9) if y(t)>y̅t+1+Δ or y(t)<y̲t+1-Δ, the feasible region of y(t) is redefined by its lower and upper bounds as follows to ensure feasible solutions of problem (3.9):
(3.10)y̅t=min⁡{y̅t+1+Δ,y̅t},y̲t=max⁡{y̲t+1-Δ,y̲t}.
Combining (3.7), (3.8), and (3.10), problem (3.9) can be expressed as follows:
(3.11)CGt(y(t))=ft(y(t))+min⁡y(t+1)CGt+1(y(t+1)),s.t.y(t+1)∈[y̲t+1,y̅t+1]∩[y(t)-Δ,y(t)+Δ],t=T2-1,T2-2,…,T1-1.
The cost-to-go function CGt(·) can be obtained by solving problem (3.11) recursively, and more detailed discussion can be found in [28].Substep 1.2 (obtaining the optimal generation levels in forward sweep).
Lety*(T1-1)=argminy(T1-1)CGT1-1(y(T1-1)), where y(T1-1)∈[y̲T1-1,y̅T1-1].  For t=T1,T1+1,…,T2, let
(3.12)y*(t)=argmin⁡y(t)CGt(y(t)),s.t.y(t)∈[y̲t,y̅t]∩[y*(t-1)-Δ,y*(t-1)+Δ].
According to the theory of dynamic programming, it is clear that {y*(t)}t=T1-1T2 obtained from the above steps is the optimal solution to problem (3.6)–(3.8).Step 2 (high-level DP).
If the optimal generation levels and costs related to all consecutive ON-state periods and the start-up costs associated with all consecutive OFF-state periods are obtained, the optimal switch-ON decisions across the schedule horizon can be easily determined by using a discrete DP algorithm in high level, as seen in Figure6.
The principal advantage of double DP is that the exact optimal solution to the subproblem (3.2) can be obtained without discretizing power generation levels or using intermediate levels of relaxation. Moreover, it is beneficial to the convergence characteristics of dual function since the concavity of the dual problem is only guaranteed by the exact optimal solutions to the unit subproblems [30].


## 3.3. Updating the Lagrange Multipliers

A modified subgradient method with adaptive step size is employed to update the Lagrange multipliers. Lettingg denote a point in the dual space, an iteration relation can be implemented to maximize the dual function (3.3):(3.13)gk+1=gk+skΔgk,
where k denotes iteration number, sk is the adaptive step size, and Δgk is the subgradient at the kth iteration. The Lagrange multipliers regarding transmission line l are updated as follows:(3.14)αlk+1(t)=max⁡(0,αlk(t)+skΔgαlk(t)),γlk+1(t)=max⁡(0,γlk(t)+skΔgγlk(t)),βlk+1(t)=max⁡(0,βlk(t)+skΔgβlk(t)),ρlk+1(t)=max⁡(0,ρlk(t)+skΔgρlk(t)).
The step size used in our implementation has the following form:(3.15)sk+1={skj‖Δgk‖‖Δgk+1‖,ifΦk+1<Φk,sk,else,
where j is a positive scaling constant that is less than 1 and ||Δgk|| and Φk are the norm of subgradient and the dual cost at the kth iteration, respectively. It can be seen that the step size keeps unchanged when the dual cost becomes larger than that at last iteration and decreases when it becomes smaller. The method for updating multipliers stops when k reaches the maximum iteration number or the following stopping criteria are satisfied:(3.16)‖gk+1-gk‖<ε⋅Φk,
where ε is a small positive constant.


## 3.4. Constructing Feasible Solutions

A systematic method including heuristics is developed for constructing feasible solutions since the dual solution obtained usually does not satisfy the relaxed constraints (2.13)–(2.17). This method is summarized as the following major steps [31].Step 1.
Determine the feasibility (satisfying constraints (2.13)–(2.17)) of a UC (u1(t),u2(t),…,uI(t)) at period t by checking whether analytical feasibility conditions proposed in [32] are satisfied. If (u1(t),u2(t),…,uI(t)) is infeasible, go to Step 2; otherwise go to Step 3. Note that the first UC at each time period is exactly the one obtained at the final dual solution.Step 2.
Heuristics combined with “opportunity-cost” based criterion presented in [27] are used to adjust the ON/OFF states of certain units that satisfy the minimum up/down time constraints (2.4), such that the infeasible UC is closer to a feasible one after each adjustment (the degree of infeasibility can be measured by the total violation of system constraints). The UC adjustment is then formulated as a zero-one programming problem, and a branch and bound (B&B) method is developed to solve it. Once a new satisfactory UC is obtained, go back to Step 1.Step 3.
Security-constrained economic dispatch (SCED) is performed for(u1(t),u2(t),…,uI(t)) to obtain the optimal power generation levels. If t<T, let t=t+1 and then go back to Step 1; otherwise stop.


## 4. Numerical Testing Results

The new SCUC formulation and LR-based solution method presented in this paper are tested with two cases consisting of a six-bus system and a modified IEEE 118-bus system. The amount of spinning reserve requirement at each time period is set to 2% of the hourly load, reserve responsive time is 10 minutes, andε is set to 0.0001 in each system. The LR-based method is performed in Microsoft Visual C#. NET on a Quad Processor PC with 4 GB RAM.


### 4.1. Six-Bus System

The six-bus system, as shown in Figure7, has three thermal units and seven transmission lines. The characteristics of generators, transmission lines, and the hourly load are listed in Tables 1, 2, and 3, respectively. A comparative case is conducted between the generation schedules obtained from traditional SCUC formulation (denoted by TF) and the formulation presented in this paper (denoted by NF) to show the energy realizability of generation schedule.Table 1
Generator data for example 1.
UnitBus no.Pmax  (MW)Pmin (MW)Initial status (h)Min down (h)Min up (h)Ramp  (MW/h)G1122010044430G2210010−33250G362010−11120Table 2
Transmission line data for example 1.
Line no.From busTo busX (pu)Flow limit (MW)1120.1702002140.2581003230.0371004240.1971005360.0181006450.0371007560.140100Table 3
Hourly load data for example 1.
HLoad (MWh)HLoad (MWh)HLoad (MWh)HLoad (MWh)1175.197168.3913242.1819245.972165.158177.6014243.6020237.353158.679186.8115248.8621237.314154.7310206.9616255.7922215.675155.0611228.6117256.0023185.936160.4812236.1018246.7424195.60Figure 7
The one-line diagram of six-bus system.Commitment states in TF and NF are listed in Tables4 and 5, respectively, in which 1/0 represents ON/OFF state of a unit, and hour 0 represents the initial ON/OFF state of the unit. It is seen from Tables 4 and 5 that in order to minimize the total generation costs, the expensive units, that is, unit 2 and unit 3, are not committed at certain hours, while the cheap unit 1 is always committed over the entire schedule horizon.Table 4
Numerical testing results for example 1: unit commitment in TF.
UnitHours (0–24)11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 120 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 030 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0Table 5
Numerical testing results for example 1: unit commitment in NF.
UnitHours (0–24)11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 120 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 030 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Figure8 compares the power output curve of unit 1 in NF with that in TF. It is seen that the power output curve in NF has a similar profile to that in TF, and the areas under both trajectories are equal at hour 1–9, 16-17, and 20-21. As observed from the curve labeled “TF” in Figure 8, in order to satisfy the energy demand from hour 22–24, the power output of unit 1 (the only ON-state unit during hour 22–24 as highlighted in Table 4) ramps down as the maximum ramp rate from 215 MW at hour 22 to 185 MW at hour 23 and then increases to 195 MW at hour 24. However, the energy output at hour 24 is practically unrealizable since it cannot be greater than the energy output at hour 23 even if unit 1 ramps up in full speed at hour 24. In comparison with TF, it is found that the generation schedule obtained under the piecewise-linear formulation is energy-realizable in the whole schedule horizon, and the ramping processes for implementing the desired energy output are also given as demonstrated in Figure 8. Furthermore, the piecewise-linear power output trajectory is closer to the practical operation of a generator since its power output does not change instantaneously.Figure 8
The power output curve of unit 1.


### 4.2. IEEE 118-Bus System

A much more complicated system is used to show the overall performance of our proposed LR-based method. The system has 54 units, 186 transmission lines, and 91 demand sides. The detailed parameters on generators, transmission network, and system load are given inhttp://motor.ece.iit.edu/Data/.To investigate the computational efficiency of the LR-based solution method proposed in this paper, we extend the schedule horizon from one day to one week by duplicating the daily system load to every day in the horizon. Figure9 shows the convergence behavior of LR for 1-day and 7-day horizons during the first 100 dual iterations. As seen in Figure 9, large fluctuations in the dual function are avoided and the dual function converges within 50 iterations in both cases. The dual function for 1-day planning horizon has better convergence characteristic than that for 7-day planning horizon. In fact, nearly 87% of security constraints are redundant in both cases as reported in [33], which have no influence on the feasible region of SCUC problem. Consequently, the multipliers associated with those redundant security constraints are inactive during the whole dual maximization process. For instance, there are 120792 multipliers in total for 7-day schedule horizon in this system. Among them, 104888 multipliers are inactive, or in other words, only 13.1% of the total Lagrange multipliers are possibly active. The dominant proportions of unbinding constraints and inactive multipliers are the chief factors contributing to the rapid convergences of dual functions. In addition, the true subgradients are obtained since the exact optimal solution to each unit subproblem is attained by the double DP, which is beneficial to the convergence characteristic of dual function.Figure 9
Convergence behavior of LR for 1-day and 7-day horizons (normalized values are obtained by dividing its values by the obtained maximum value).The results with respect to B&B algorithm used in constructing feasible solutions under LR are listed in Table6. It is found that 222 systemwide constraints are infeasible at the end of dual maximization in the IEEE 118-bus system for 1-day horizon, and the total amount of violations against those infeasible constraints is 8675 MW. All infeasibilities are eliminated by our branch and bound algorithm after 124 iterations, and a near-optimal feasible schedule with the duality gap of 0.75% is finally obtained.Table 6
Numerical testing results for example 2: general results with different horizons.
LRMILPDayCPU time1 (s)Feasible cost ($)Duality gap (%)Iteration number (B&B)CPU time2 (s)Feasible cost ($)18.119840810.751246.81979625218.137499900.7324813.93746033327.357138730.8237225.15712852445.775918070.7649663.27591460572.194204390.8962093.69421239692.7108502490.84744138.9108520897130.8122357150.91868199.212236687In order to evaluate the overall performance of the LR-based method, comparative cases are studied between the LR-based method and MIP-based method in this system. The MILP-based method employs branch-and-cut method that combines branch-and-bound and cutting plane technique. Once the model is formulated and represented in the MILP format, the solution is sought by engaging a general-purpose software, that is, CPLEX [10, 17]. Therefore, the new SCUC formulation is also solved based on general-purpose MILP solver with some nonlinearity converted into linear model. The default settings of CPLEX are selected and the maximum threshold of optimality gap is set to 0.5%. Parallel computing techniques are utilized to solve the individual subproblems in our LR implementation.Table6 exhibits the comparative results with the scheduling horizon ranging from 1 day to 7 days. It is seen that as the size of the SCUC problem increases, the duality gap under LR is always less than 1%. Although the duality gap is larger than that set in MILP solver, the total generation cost obtained under LR-based method for the horizon of 5–7 day is slightly less than that obtained in MILP solver.The execution times with different schedule horizons under LR and MILP are also listed in Table6, in which the columns labeled “CPU time1” and “CPU time2” report the computing times of LR and MILP for solving the new SCUC formulation, respectively. Note that the stopping criteria described in (3.16) are activated under LR. It is seen in Table 6 that the computing time increases from 8.1 s to 130.8 s as the schedule horizon increases. For the SCUC problem with 7-day horizon, there are over 18000 decision variables, half of which are discrete decision variables. Although the problem size becomes larger, the computing time of 130.8s under LR is still reasonable for such a medium-scale problem.It is also seen in Table6 that the computing times under LR for the horizon of 1–3 day are greater than those obtained in MILP-based method, but the computational advantage of LR over MILP becomes clear as the problem size (length of scheduling horizon) increases. The above results suggest that MILP-based method outperforms the LR-based method on small-size instances, but the LR method is superior to the general-purpose MILP method for solving large-scale SCUC problems in term of computational efficiency.


## 4.1. Six-Bus System

The six-bus system, as shown in Figure7, has three thermal units and seven transmission lines. The characteristics of generators, transmission lines, and the hourly load are listed in Tables 1, 2, and 3, respectively. A comparative case is conducted between the generation schedules obtained from traditional SCUC formulation (denoted by TF) and the formulation presented in this paper (denoted by NF) to show the energy realizability of generation schedule.Table 1
Generator data for example 1.
UnitBus no.Pmax  (MW)Pmin (MW)Initial status (h)Min down (h)Min up (h)Ramp  (MW/h)G1122010044430G2210010−33250G362010−11120Table 2
Transmission line data for example 1.
Line no.From busTo busX (pu)Flow limit (MW)1120.1702002140.2581003230.0371004240.1971005360.0181006450.0371007560.140100Table 3
Hourly load data for example 1.
HLoad (MWh)HLoad (MWh)HLoad (MWh)HLoad (MWh)1175.197168.3913242.1819245.972165.158177.6014243.6020237.353158.679186.8115248.8621237.314154.7310206.9616255.7922215.675155.0611228.6117256.0023185.936160.4812236.1018246.7424195.60Figure 7
The one-line diagram of six-bus system.Commitment states in TF and NF are listed in Tables4 and 5, respectively, in which 1/0 represents ON/OFF state of a unit, and hour 0 represents the initial ON/OFF state of the unit. It is seen from Tables 4 and 5 that in order to minimize the total generation costs, the expensive units, that is, unit 2 and unit 3, are not committed at certain hours, while the cheap unit 1 is always committed over the entire schedule horizon.Table 4
Numerical testing results for example 1: unit commitment in TF.
UnitHours (0–24)11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 120 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 030 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0Table 5
Numerical testing results for example 1: unit commitment in NF.
UnitHours (0–24)11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 120 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 030 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Figure8 compares the power output curve of unit 1 in NF with that in TF. It is seen that the power output curve in NF has a similar profile to that in TF, and the areas under both trajectories are equal at hour 1–9, 16-17, and 20-21. As observed from the curve labeled “TF” in Figure 8, in order to satisfy the energy demand from hour 22–24, the power output of unit 1 (the only ON-state unit during hour 22–24 as highlighted in Table 4) ramps down as the maximum ramp rate from 215 MW at hour 22 to 185 MW at hour 23 and then increases to 195 MW at hour 24. However, the energy output at hour 24 is practically unrealizable since it cannot be greater than the energy output at hour 23 even if unit 1 ramps up in full speed at hour 24. In comparison with TF, it is found that the generation schedule obtained under the piecewise-linear formulation is energy-realizable in the whole schedule horizon, and the ramping processes for implementing the desired energy output are also given as demonstrated in Figure 8. Furthermore, the piecewise-linear power output trajectory is closer to the practical operation of a generator since its power output does not change instantaneously.Figure 8
The power output curve of unit 1.


## 4.2. IEEE 118-Bus System

A much more complicated system is used to show the overall performance of our proposed LR-based method. The system has 54 units, 186 transmission lines, and 91 demand sides. The detailed parameters on generators, transmission network, and system load are given inhttp://motor.ece.iit.edu/Data/.To investigate the computational efficiency of the LR-based solution method proposed in this paper, we extend the schedule horizon from one day to one week by duplicating the daily system load to every day in the horizon. Figure9 shows the convergence behavior of LR for 1-day and 7-day horizons during the first 100 dual iterations. As seen in Figure 9, large fluctuations in the dual function are avoided and the dual function converges within 50 iterations in both cases. The dual function for 1-day planning horizon has better convergence characteristic than that for 7-day planning horizon. In fact, nearly 87% of security constraints are redundant in both cases as reported in [33], which have no influence on the feasible region of SCUC problem. Consequently, the multipliers associated with those redundant security constraints are inactive during the whole dual maximization process. For instance, there are 120792 multipliers in total for 7-day schedule horizon in this system. Among them, 104888 multipliers are inactive, or in other words, only 13.1% of the total Lagrange multipliers are possibly active. The dominant proportions of unbinding constraints and inactive multipliers are the chief factors contributing to the rapid convergences of dual functions. In addition, the true subgradients are obtained since the exact optimal solution to each unit subproblem is attained by the double DP, which is beneficial to the convergence characteristic of dual function.Figure 9
Convergence behavior of LR for 1-day and 7-day horizons (normalized values are obtained by dividing its values by the obtained maximum value).The results with respect to B&B algorithm used in constructing feasible solutions under LR are listed in Table6. It is found that 222 systemwide constraints are infeasible at the end of dual maximization in the IEEE 118-bus system for 1-day horizon, and the total amount of violations against those infeasible constraints is 8675 MW. All infeasibilities are eliminated by our branch and bound algorithm after 124 iterations, and a near-optimal feasible schedule with the duality gap of 0.75% is finally obtained.Table 6
Numerical testing results for example 2: general results with different horizons.
LRMILPDayCPU time1 (s)Feasible cost ($)Duality gap (%)Iteration number (B&B)CPU time2 (s)Feasible cost ($)18.119840810.751246.81979625218.137499900.7324813.93746033327.357138730.8237225.15712852445.775918070.7649663.27591460572.194204390.8962093.69421239692.7108502490.84744138.9108520897130.8122357150.91868199.212236687In order to evaluate the overall performance of the LR-based method, comparative cases are studied between the LR-based method and MIP-based method in this system. The MILP-based method employs branch-and-cut method that combines branch-and-bound and cutting plane technique. Once the model is formulated and represented in the MILP format, the solution is sought by engaging a general-purpose software, that is, CPLEX [10, 17]. Therefore, the new SCUC formulation is also solved based on general-purpose MILP solver with some nonlinearity converted into linear model. The default settings of CPLEX are selected and the maximum threshold of optimality gap is set to 0.5%. Parallel computing techniques are utilized to solve the individual subproblems in our LR implementation.Table6 exhibits the comparative results with the scheduling horizon ranging from 1 day to 7 days. It is seen that as the size of the SCUC problem increases, the duality gap under LR is always less than 1%. Although the duality gap is larger than that set in MILP solver, the total generation cost obtained under LR-based method for the horizon of 5–7 day is slightly less than that obtained in MILP solver.The execution times with different schedule horizons under LR and MILP are also listed in Table6, in which the columns labeled “CPU time1” and “CPU time2” report the computing times of LR and MILP for solving the new SCUC formulation, respectively. Note that the stopping criteria described in (3.16) are activated under LR. It is seen in Table 6 that the computing time increases from 8.1 s to 130.8 s as the schedule horizon increases. For the SCUC problem with 7-day horizon, there are over 18000 decision variables, half of which are discrete decision variables. Although the problem size becomes larger, the computing time of 130.8s under LR is still reasonable for such a medium-scale problem.It is also seen in Table6 that the computing times under LR for the horizon of 1–3 day are greater than those obtained in MILP-based method, but the computational advantage of LR over MILP becomes clear as the problem size (length of scheduling horizon) increases. The above results suggest that MILP-based method outperforms the LR-based method on small-size instances, but the LR method is superior to the general-purpose MILP method for solving large-scale SCUC problems in term of computational efficiency.


## 5. Conclusions

The realizability of generation schedule is very important to power system operation. Traditional SCUC formulations adopted in literature have a serious issue that the solution may be unrealizable in terms of energy delivery. This issue is analyzed through an example in this paper and a new SCUC formulation is established by modeling power outputs of units with piecewise linear functions. An LR-based method is developed to solve the problem, and the schedules obtained are near optimal, energy-realizable, and closer to practical operation of the thermal unit. Numerical testing results show the validation of the formulation and the effectiveness of the LR-based solution method. The energy-realizable schedules obtained by LR are also compared with those obtained by MILP. It is shown that the proposed LR-based method proposed is still competitive with those based on the general-purpose MILP solvers and even outperforms them for solving large-scale SCUC problems.



---

*Source: 178193-2012-02-26.xml*