# Feasible Modified Subgradient Method  for Solving the Thermal Unit Commitment  Problem as a New Approach

Authors: Ummuhan Basaran Filik; Mehmet Kurban
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

The Lagrangian relaxation- (LR-) based methods are commonly used to solve the thermal unit commitment (UC) problem which is an important subject in power system engineering. The main drawback of this group of methods is the difference between the dual and the primal solutions which gives some significant problems on the quality of the feasible solutions.  In this paper, a new approach, feasible modified subgradient (F-MSG) method which does not require finding an unconstrained global minimum of the Lagrangian function and knowing an optimal value of the problem under consideration in order to update dual variables at the each iteration, is firstly used for solving the thermal UC problem. The major advantage of the proposed approach is that it guarantees the zero duality gap and convergence independently from the size of the problem. In order to discuss the advantages of this method, the four-unit Tuncbilek thermal plant, which is located in Kutahya region in Turkey, is chosen as a small test system. The numerical results show that F-MSG gives better solutions as compared to the standard LR method.


---

## Body

## 1. Introduction

Solving thermal UC problem is very important for power system optimization. The thermal UC problem, which is defined as a nonlinear, mixed-integer, and nonconvex, is considered to be an NP (Nonlinear-Programming) hard problem. The high dimension of the possible solution space is the real difficulty in solving the problem.  There have been various methods for solving the thermal UC problem in the literature. They are based on mathematical programming and metaheuristic-based approaches. These methods are priority list [1–3], dynamic programming [4], simulated annealing [5–7], tabu search [8, 9], evolutionary programming [10, 11], constraint logic programming [12], expert systems [13], fuzzy systems [14], genetic algorithms [15–19], LR [20–24], interior point algorithm [25], memetic algorithm [26], neural network [27, 28], and hybrid models [29, 30].LR which is most widely used approach among the aforementioned methodologies solves the thermal UC problem by “relaxing” or temporarily ignoring the coupling constraints and solving the problem as if they did not exist. Based on the duality theory, the LR method subsequently tries to find the values of the Lagrange multipliers that maximize the dual objective function.  The duality gap, a major problem in the nonlinear programming, has been long recognized as an inherent disadvantage of these methods.If the LR-based methods are used for solving the UC problem, dual solution may be far away from the optimal solution. The duality gap for the problem of thermal UC is an important measure of the quality of the solution, which is defined by the smaller gap, the better solution [31].  In [32], different mathematical-based methods LR, penalty function, and augmented Lagrangian penalty function are compared to each other according to feasible cost, dual cost, duality gap, number of iterations, and duration time. According to [32], it is seen that there are differences between primal value and dual value. In the nonlinear programming, the duality gap has been investigated and the theoretical tools for zero duality gap condition have been improved extensively in [33–38].In this paper, one of the methods based on dual optimization technique, F-MSG method, which has the best performance in eliminating the duality gap in the literature, is firstly used for solving the thermal UC problem as a novel approach. A dual problem with respect to the sharp augmented Lagrangian is constructed for this problem.  F-MSG method solves without any duality gap for large class of nonconvex constrained problems.  This proposed approach is compared to LR method to show that F-MSG gives an optimal solution obtaining the zero duality gap value. The LR method chosen in testing of F-MSG methods’ performance lies from the fact that LR method is the most widely used method in solving UC problems in the literature. In order to compare these methods, the UC problem for four-unit Tuncbilek thermal plant, which is in Kutahya region in Turkey, is solved using MATLAB and General Algebraic Modeling System (GAMS).  Note that there is a general acceptance that whenever the system size gets smaller, the duality gap value gets bigger. However, it is shown that this is not the case with the F-MSG method for a small size system [38].The remaining sections are outlined as follows. Section2 addresses the thermal UC problem formulations. This section includes an objective function and constraints of the problem. In Section 3, usage of F-MSG method for solving the thermal UC problem is explained in detail. In Section 4, numerical results for F-MSG and LR methods are provided. Finally the conclusions are presented, the main contributions of this paper are highlighted, and possible research directions are discussed.


## 2. Review of Thermal Unit Commitment Problem

The objective of thermal UC problem is to minimize the production cost over the scheduled time horizon (e.g., 8 hours, 24 hours) under the generator operational and spinning reserve constraints while all generating unit constraints are satisfied. The  objective function of the UC problem can be formulated as(2.1)F(Pit,Uit)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit,
where Fi(Pit)=a(Pit)2+bPit+c is the polynomial function [39].The minimization of the objective function is provided to the following constraints.(a)
Power Balance Constraint. For satisfying the load balance in each stage, the forecasted load demand should be equal to the total power of the generated power for feasible combination:
(2.2)∑i=1NUitPit=Pdt.(b)
Spinning Reserve Constraints. In order to meet any abnormal operating conditions, the spinning reserve must be considered:
(2.3)Pdt+Prt-∑i=1NPi,maxUit≤0.(c)
Generation Limits Constraint. Each unit must satisfy the generation range:
(2.4)Pi,minUit≤Pit≤Pi,maxUit,i=1,2,…,N.(d)
Ramp-Up and Ramp-Down Constraints. For each unit, output is limited by ramp up/down rate at each hour as follows:
(2.5)Pit-1-Pit≤RDi,ifUit=1,Uit-1=1,Pit-Pit-1≤RUi,ifUit=1,Uit-1=1.(e)
Minimum Up-Down Time  Constraint.Once the unit is started up, it should not be shut down before a minimum up-time period is met as follows, and once the unit is shut down, there is a minimum down time before it can be started up again:
(2.6)(Tion(t-1)-Ti,upt)(Uit-1-Uit)≥0,(Tioff(t-1)-Ti,downt)(Uit-Uit-1)≥0.The problem is structured binary variables making it clearly nonconvex. These binary variables cause a great deal of trouble and difficulty in solving the UC.Load balance and spinning reserve constraints are coupling constraints for the thermal UC problem.


## 3. F-MSG Method for Thermal Unit Commitment

The F-MSG method guarantees a zero duality gap for a wide class of nonconvex optimization problems. It does not require finding an unconstrained global minimum of the Lagrangian function and knowing an optimal value of the problem under consideration in order to update dual variables at the each iteration, and it guarantees convergence.


### 3.1. F-MSG Algorithm

Minimizef0(x) subject to x∈S satisfying f(x)=0, where S is a subset of a metric space X, and  f0:X→R and f:X→Rp are given functions.Sharp Augmented Lagrangian is defined as follows:(3.1)Lsa(x,v,c)=f0(x)+c∥f(x)∥-〈v,f(x)〉
and defining the dual function as (3.2)H(v,c)=minx∈ΩL(x,v,c).The dual problem (P*) is
(3.3)max(v,c)∈R3xR+H(v,c).Using the above definitions, the F-MSG is as follows [38].F-MSG Algorithm
Step 1.
Choose positive numbersε1ε2, Δ1, M and a number H1. Set n=1, t=0, and q=0.Step 2.
Choose(v1n,c1n)Rp×R+ and 0<l(1)<M set k=1, vk=v1n, ck=c1n.Step 3.
Given(vk,ck), solve the following constraint satisfaction problem P(Hn): find an element x∈S such that
(3.4)f0(x)+c∥f(x)∥-〈v,f(x)〉≤Hn.
If a solution to (3.4) does not exist, then go to Step 6; otherwise, if a solution xk exists, then check whether f(xk)=0 or not. If  f(xk)=0 (or ∥f(x)∥≤ε1), then go to Step 5; otherwise go to Step 4.Step 4.
Update dual variables as(3.5)vk+1=vk-αskf(xk),ck+1=ck+(1+α)sk∥f(xk)∥.
where sk is a positive step size parameter defined as
(3.6)0<sk=δα(Hn-L(xk,vk,ck))[α2+(1+α)2]∥f(xk)∥2,(3.7)0<sk=[δα(Hn-L(xk,vk,ck))+(c̅-ck)∥f(xk)∥][α2+(1+α)2]∥f(xk)∥2
with α>0, and 0<δ<2.  In this study, (3.7) is used for updating. The appropriate values are replaced for updating in this equation. We will also require the step size sk corresponding to the dual variables (vk,ck) to satisfy the following property:
(3.8)sk∥f(xk)∥+ck-∥vkl∥>l(k).
Set k=k+1, update l(k)  in such a way that l(k)→+∞ as k→+∞, and repeat Step 3.Step 5.
Letxk be a solution to (3.4) with f(xk)=0. In this case L(xk,vk,ck)=f0(xk). Set  q=q+1 and check t. If t=0, then set Δn+1=Δn; otherwise set Δn+1=(1/2)Δn. Check Δn+1<ε2, and then stop. f0(xk) is an approximate optimal value, xk is an approximate primal solution, and (vk,ck) is an approximate dual solution; otherwise set Hn+1=min{f0(xk),Hn-Δn+1}, n=n+1, and go to Step 2.Step 6.
Sett=t+1. If q=0, then set Δn+1=Δn; otherwise set Δn+1=(1/2)Δn. Set Hn+1=Hn+Δn+1, n=n+1, and go to Step 2.According to F-MSG method for solving the UC problem, the objective function and constraints are defined as follows.Object Function
(3.9)minN,Tf(N,T)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit
Slack variables are added to inequality constraints. Equality and inequality constraints can be defined as follows.Generation Limit Constraints
(3.10)h1(N,T)=UitPi,min-Pit+hit=0,h2(N,T)=Pit-UitPi,max+hit=0.Load Balance Constraints.
(3.11)h3(T)=∑i=1NUitPit-Pdt=0.Spinning Reserve Constraints
(3.12)h4(T)=Pdt+Prt-∑i=1NPi,maxUit+hit=0.Ramp-Up and Ramp-Down Constraints
(3.13)h5(N,T)=Pit-1-Pit-RDi,+hit,ifUit=1,Uit-1=1,h6(N,T)=Pit-Pit-1-RUi+hit,ifUit=1,Uit-1=1.Minimum Up and Down Constraints
(3.14)Ton(N,T)=((Ton(N,T-1)+1))×Uit,Toff(N,T)=((Toff(N,T-1)+1))×(1-Uit).H matrix is =[h1(N,T)h2(N,T)h3(T)h4(T)h5(N,T)h6(N,T)]. According to (3.9), sharp augmented Lagrangian is defined as follows:
(3.15)L=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+c·[sqrt((UitPi,min-Pit+hit)2+(Pit-UitPi,max+hit)2+(∑i=1NUit·Pit-Pdt)2+(Pdt+Prt-∑i=1NPi,maxUit+hit)2+(Pit-1-Pit-RDi,+hit)2+(Pit-Pit-1-RUi+hit)2)2]×[-vit·(UitPi,min-Pit+hit)-vit·(Pit-UitPi,max+hit)-vit·(∑i=1NUit·Pit-Pdt)-vit·(Pdt+Prt-∑i=1NPi,maxUit+hit)-vit·(Pit-1-Pit-RDi+hit)-vit·(Pit-Pit-1-RUi+hit)].The epsilon value is chosen as 0.95zj in the thermal UC problem solution. After (3.15) is constructed using the objective function and constraints, all the steps of the F-MSG method are applied to the thermal UC problem.


## 3.1. F-MSG Algorithm

Minimizef0(x) subject to x∈S satisfying f(x)=0, where S is a subset of a metric space X, and  f0:X→R and f:X→Rp are given functions.Sharp Augmented Lagrangian is defined as follows:(3.1)Lsa(x,v,c)=f0(x)+c∥f(x)∥-〈v,f(x)〉
and defining the dual function as (3.2)H(v,c)=minx∈ΩL(x,v,c).The dual problem (P*) is
(3.3)max(v,c)∈R3xR+H(v,c).Using the above definitions, the F-MSG is as follows [38].F-MSG Algorithm
Step 1.
Choose positive numbersε1ε2, Δ1, M and a number H1. Set n=1, t=0, and q=0.Step 2.
Choose(v1n,c1n)Rp×R+ and 0<l(1)<M set k=1, vk=v1n, ck=c1n.Step 3.
Given(vk,ck), solve the following constraint satisfaction problem P(Hn): find an element x∈S such that
(3.4)f0(x)+c∥f(x)∥-〈v,f(x)〉≤Hn.
If a solution to (3.4) does not exist, then go to Step 6; otherwise, if a solution xk exists, then check whether f(xk)=0 or not. If  f(xk)=0 (or ∥f(x)∥≤ε1), then go to Step 5; otherwise go to Step 4.Step 4.
Update dual variables as(3.5)vk+1=vk-αskf(xk),ck+1=ck+(1+α)sk∥f(xk)∥.
where sk is a positive step size parameter defined as
(3.6)0<sk=δα(Hn-L(xk,vk,ck))[α2+(1+α)2]∥f(xk)∥2,(3.7)0<sk=[δα(Hn-L(xk,vk,ck))+(c̅-ck)∥f(xk)∥][α2+(1+α)2]∥f(xk)∥2
with α>0, and 0<δ<2.  In this study, (3.7) is used for updating. The appropriate values are replaced for updating in this equation. We will also require the step size sk corresponding to the dual variables (vk,ck) to satisfy the following property:
(3.8)sk∥f(xk)∥+ck-∥vkl∥>l(k).
Set k=k+1, update l(k)  in such a way that l(k)→+∞ as k→+∞, and repeat Step 3.Step 5.
Letxk be a solution to (3.4) with f(xk)=0. In this case L(xk,vk,ck)=f0(xk). Set  q=q+1 and check t. If t=0, then set Δn+1=Δn; otherwise set Δn+1=(1/2)Δn. Check Δn+1<ε2, and then stop. f0(xk) is an approximate optimal value, xk is an approximate primal solution, and (vk,ck) is an approximate dual solution; otherwise set Hn+1=min{f0(xk),Hn-Δn+1}, n=n+1, and go to Step 2.Step 6.
Sett=t+1. If q=0, then set Δn+1=Δn; otherwise set Δn+1=(1/2)Δn. Set Hn+1=Hn+Δn+1, n=n+1, and go to Step 2.According to F-MSG method for solving the UC problem, the objective function and constraints are defined as follows.Object Function
(3.9)minN,Tf(N,T)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit
Slack variables are added to inequality constraints. Equality and inequality constraints can be defined as follows.Generation Limit Constraints
(3.10)h1(N,T)=UitPi,min-Pit+hit=0,h2(N,T)=Pit-UitPi,max+hit=0.Load Balance Constraints.
(3.11)h3(T)=∑i=1NUitPit-Pdt=0.Spinning Reserve Constraints
(3.12)h4(T)=Pdt+Prt-∑i=1NPi,maxUit+hit=0.Ramp-Up and Ramp-Down Constraints
(3.13)h5(N,T)=Pit-1-Pit-RDi,+hit,ifUit=1,Uit-1=1,h6(N,T)=Pit-Pit-1-RUi+hit,ifUit=1,Uit-1=1.Minimum Up and Down Constraints
(3.14)Ton(N,T)=((Ton(N,T-1)+1))×Uit,Toff(N,T)=((Toff(N,T-1)+1))×(1-Uit).H matrix is =[h1(N,T)h2(N,T)h3(T)h4(T)h5(N,T)h6(N,T)]. According to (3.9), sharp augmented Lagrangian is defined as follows:
(3.15)L=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+c·[sqrt((UitPi,min-Pit+hit)2+(Pit-UitPi,max+hit)2+(∑i=1NUit·Pit-Pdt)2+(Pdt+Prt-∑i=1NPi,maxUit+hit)2+(Pit-1-Pit-RDi,+hit)2+(Pit-Pit-1-RUi+hit)2)2]×[-vit·(UitPi,min-Pit+hit)-vit·(Pit-UitPi,max+hit)-vit·(∑i=1NUit·Pit-Pdt)-vit·(Pdt+Prt-∑i=1NPi,maxUit+hit)-vit·(Pit-1-Pit-RDi+hit)-vit·(Pit-Pit-1-RUi+hit)].The epsilon value is chosen as 0.95zj in the thermal UC problem solution. After (3.15) is constructed using the objective function and constraints, all the steps of the F-MSG method are applied to the thermal UC problem.


## 4. Numerical Results

F-MSG method is applied to the system to find the feasible results and feasible cost, dual cost, and duality gap values. This proposed approach is compared to LR method to show that F-MSG gives an optimal solution obtaining the zero duality gap value. The data used in the analysis is taken from Turkish Electric Power Company and Electricity Generation Company. The system parameters and reserve requirements of four units are given in Table1.Table 1
Unit characteristics for four-unit Tuncbilek thermal plant.
Unit NoPmin (MW)Pmax (MW)SC ($)a ($/h)b ($/MWh)c ($/MW2h)RU ($)RU ($)Tup (h)Tdown (h)1832600.51510.86149.96611217652400.2278.341284.61313223351505500.0829.9441495.83030334301505500.07412.44388.9303033In this study, the 24-hour day is subdivided into 8 discrete stages. The load demands for the stages are given in Table2. The spinning reserve demand is set as 10% of the system demand for each stage. LR method is coded in MATLAB, and F-MSG method is coded in GAMS which is a high-level modeling system for mathematical programming problems [40]. MINOS is used as a GAMS solver. These computer programs are run on Pentium core—1.6 GHz personal computer.Table 2
Load data (MW).
StageLoadStageLoad11685313215063473260730842758231Optimal solution of the dual model set up by the sharp augmented Lagrange function, which is proposed by Gasimov, is equal to the primal solution of the system [37, 38]. The F-MSG method is run until the norm is equal to 7.36×10-12, epsilon is equal to 1.72×107, then all the constraints reduce to zero, and feasible solution is obtained. Primal value is equal to the dual value yielding zero duality gap value. The value for the c parameter is 27182.94 and the UC schedule, feasible cost, dual cost, and duality gap values for the F-MSG method are given in Table 3.Table 3
UC schedule for F-MSG method.
StageUnit Combination10  0  1  120  0  1  130  1  1  140  1  1  151  1  1  161  1  1  171  1  1  180  1  1  1The UC schedule, feasible cost, dual cost, and duality gap values for the LR method are given in Table4.Table 4
UC schedule for LR method.
StageUnit Combination10  0  1  120  0  1  130  1  1  141  1  1  151  1  1  161  1  1  171  1  1  180  1  1  1Feasible cost, dual cost, and duality gap values are found by F-MSG and LR method. These numerical results are given in Table5.Table 5
The numerical results for F-MSG and LR methods.
Compared ItemsF-MSGLRFeasible cost ($)55597.76356443.182Dual cost ($)55597.76355827.735Duality gap (%)01.01102It can be seen from Table5 that LR has the duality gap value and F-MSG performs much better than LR, since duality gap value is reduced to zero. The quality of the solution is improved when the duality gap is decreased. In this paper zero duality gap is achieved and feasible solution is attained by applying the F-MSG method.


## 5. Conclusion

The F-MSG method is firstly applied to solve the thermal UC problem which is an important and hard-solving problem in power system engineering. Feasible cost, dual cost, and duality gap values from F-MSG and LR methods are compared. The most attractive feature of the proposed approach is that the duality gap value of F-MSG method over the scheduled time horizon is zero. Also, the total production cost over the scheduled time horizon of the F-MSG method is less than the ones of the standard LR methods. The results of the F-MSG method for solving the thermal UC problem are very impressive and the quality of feasible solution is significantly improved.   This approach can be applied to the thermal UC problem for any size of systems to obtain the feasible solutions.



---

*Source: 159429-2010-07-15.xml*