# Solving Unit Commitment Problem Using Modified Subgradient Method Combined with Simulated Annealing Algorithm

Authors: Ümmühan Başaran Filik; Mehmet Kurban
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper presents the solving unit commitment (UC) problem using Modified Subgradient Method (MSG) method combined with Simulated Annealing (SA) algorithm. UC problem is one of the important power system engineering hard-solving problems. The Lagrangian relaxation (LR) based methods are commonly used to solve the UC problem. The main disadvantage of this group of methods is the difference between the dual and the primal solution which gives some significant problems on the quality of the feasible solution. In this paper, MSG method which does not require any convexity and differentiability assumptions is used for solving the UC problem. MSG method depending on the initial value reaches zero duality gap. SA algorithm is used in order to assign the appropriate initial value for MSG method. The major advantage of the proposed approach is that it guarantees the zero duality gap independently from the size of the problem. In order to show the advantages of this proposed approach, the four-unit Tuncbilek thermal plant and ten-unit thermal plant which is usually used in literature are chosen as test systems. Penalty function (PF) method is also used to compare with our proposed method in terms of total cost and UC schedule.


---

## Body

## 1. Introduction

UC is very important problem for power system engineering. The problem can be described as a nonlinear, mixed-integer, and nonconvex and is considered to be a nondeterministic polynomial-time hard (NP-hard) problem [1]. The real difficulty in solving the problem is the high dimension of the possible solution space.  Meta-heuristic and mathematical based methods have been developed for solving the thermal and hydrothermal UC problem in the literature. The most used metaheuristic methods are SA [2–5], expert systems [6], tabu search [7–9], evolutionary programming [10, 11], genetic algorithms [12–15], memetic algorithm [16], particle swarm optimization [17], interior point method [18], neural network [19, 20], and greedy randomized adaptive search procedure [21]. The mathematical-based methods depend on the duality theory [22–28]. The other methods used for solving the UC problem are dynamic programming [29, 30], mixed-integer programming [31], benders decomposition [32], and some hybrid methods [33–35].Meta-heuristic methods are used for solving difficult combinatorial optimization problems. To solve UC problem by using these methods, priority list is precalculated and all the constraints are heuristically incorporated.The LR method subsequently tries to find the values of the Lagrange multipliers that maximize the dual objective function based on the duality theory. 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 UC is an important measure of the quality of the solution. When the gap is smaller, the solution is better [36].  In [37], 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 [37], it is seen that there are differences between primal value and dual value. MSG method does not require any convexity and differentiability assumptions. In the nonlinear NP, the duality gap has been investigated and the theoretical tools for zero duality gap condition have been improved extensively in [38–42].In this paper, one of the methods based on dual optimization technique, MSG method, which has the best performance in eliminating the duality gap in the literature, is used for solving the UC problem. A dual problem with respect to the sharp augmented Lagrangian is constructed for UC problem.  The disadvantage of the MSG method is that the zero-duality gap value depends on the initial value of the upper dual value. This dual value is found by using SA algorithm. In this proposal approach constructs the dual problem and solves it without any duality gap for large class of nonconvex constrained problems.  This proposed approach is compared to PF method because the MSG method removes some of the problems occurred in this method.The remaining sections are outlined as follows. Section2 provides a description of the UC problem formulation. This section includes an objective function and the constraints of the problem. In Section 3, MSG method with SA algorithm Explained in detailed. In Section 4, applications and numerical results are presented and discussed. Finally the conclusion is given.


## 2. Unit Commitment Problem Formulation

UC has been used to plan over a given time horizon the most economical schedule of committing and dispatching generating units to meet forecasted demand levels and spinning reserve requirements while all generating unit constraints are satisfied. The objective function can be represented mathematically as(2.1)F(Pit,Uit)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+∑t=1T∑i=1NSDit×(1-Uit-1)Uit-1.
In (2.1), T is period, N is the number of generators, Pit is the generation power output of unit i at hour t, Fi(Pit) is quadratic fuel cost function of generating unit i (Fi(Pit)=ai+biPit+ci(Pit)2), Uit is status of unit i at hour t (on = 1, off = 0), SCit is startup cost of unit i at hour t, SDit is shutdown cost of unit i at hour t  [43].The minimization of the objective function is provided to the following constraints.System Constraints
Power Balance Constraints. 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.
In (2.2), Pdt is system load demand at hour t.Unit Constraints
Generation Limits. Each unit must satisfy the generation range
(2.3)Pi,minUit≤Pit≤Pi,maxUit,i=1,2,…,N.
In (2.3), Pi,min is minimum power output of unit i, and Pi,max is maximum power output of unit i.
Ramp Up and Ramp Down Constraints. For each unit, output is limited by ramp up/down rate at each hour as follows:
(2.4)Pit-1-Pit≤RDi,ifUit=1&Uit-1=1,Pit-Pit-1≤RUi,ifUit=1&Uit-1=1,RDi is ramp down rate limit of unit i, and RUi is ramp up rate limit of unit i.The problem is nonconvex because it is structured binary variables. These variables cause a great deal of trouble and difficulty in solving the UC. Load balance is coupling constraint for the UC problem. The coupling constraints across the unit so that one unit affects what will happen on other units if the coupling constraints are met.


## 3. Modified Subgradient Method Combined with Simulated Annealing Algorithm

### 3.1. Simulated Annealing Algorithm for Unit Commitment

SA algorithm is a strong technique for solving hard combinatorial optimization problems without specific structure. This method has the ability of escaping local minima by performing uphill moves. The main advantage of SA algorithm is that it does not need large computer memory. SA is based on the iterative method, originally proposed by Metropolis et al. [44], which simulates the transition of atoms in equilibrium at a given temperature. The main disadvantage of this method is very greedy regarding computation time requirements, due to the large number of iterations needed for the convergence of the method. All the generating and acceptance distributions depend on the temperature [3].One of the measure steps in the SA is the cooling schedule. This schedule has three components: the initial temperature setting, the temperature decreasing scheme, and a finite number of initial value of temperature should be large enough to allow all transients to be accepted for unconstrained optimization problem. On the other hand, the temperature is lowered based on multiplying the temperature in which typical values lie between 0.8 and 0.99. If the acceptance ratio is low or the sampled mean and variance of cost values at current temperature have big drops, then the factor is adjusted to a higher value in order to avoid getting stuck at a local optimal configuration. Otherwise, the factor is adjusted to a lower value to increase the convergence speed. The number of moves at each temperature is based on the requirement that at each temperature quasiequilibrium is to be restored. The final temperature is obtained if, at five consecutive temperatures, either the sampled mean values of cost function do not change or the acceptance ratio is small enough [2, 3].In solving the UC problem by using SA algorithm, two types of variables need to be determined: the unit status (binary) variablesU and the units output power (continuous) variables P. Then, this problem can be considered into two subproblems, a combinatorial optimization problem in U and a nonlinear optimization problem in P. The flow diagram of SA algorithm for UC problem is given in Figure 1 [3]. The economic dispatch problem is solved by using lambda-iteration method in the SA.Figure 1
SA algorithm for UC problem.


### 3.2. Modified Subgradient Method for Unit Commitment

The MSG method proposed by Gasimov has a notable performance in having zero duality gaps for large class of nonconvex problems [38, 39].   In the standard form the nonlinear programming problem can be expressed as follows: (3.1)minKf(K)(3.2)subjectto{h(K)≤0,K∈Ω,whereh(K)=[h1(K)h2(K)⋯hn(K)] is the constraint vector.The primal problem is (3.1). Sharp augmented Lagrangian is defined as follows:(3.3)L(K,v,c)=f(K)+c∥h(K)∥-vTh(K),
where v∈R3 and c∈R+. Define the dual function as (3.4)H(v,c)=minK∈ΩL(K,v,c).The dual problem (P*) is(3.5)max(v,c)∈R3×R+H(v,c).
Dual function H(v,c) is not a definite function; however it is a convex function for continuous  f(K), h(K) and compact set S.  Inequality constraints can be converted to standard form by adding nonnegative slack variables to left hand sides of inequalities; one of the advantages of the MSG method is that the fact that the solution convergence is proved. Thus, in each iteration a better solution can be found. This method differs from the classical LR functions, scans the solution with conics, and hence obtains zero dual gap value. In other words, there is no difference between primal and dual problems. Thus it gives an optimal solution. Another advantage of this method is that it does not require any convexity and differentiability assumptions.Using the definitions, the MSG method is as follows.Initialization
Choose a pair (v1,c1) with  v1∈R3andc∈R+, c1≥0and letj=1, and go to Step 1.Step 1.
Given (cj,vj), solve the following subproblem:
(3.6)minKf(K)+cj∥h(K)∥-vjh(K)=H(vj,cj)
subject to k∈Ω.In (3.6) (cj,vj) is multiplier of sharp augmented Lagrangian, f(K) is objective function, ∥h(K)∥ is  norm of the constraint vector, and H(vj,cj) is dual function of the problem. Let Kj be a solution of (3.6). If h(Kj)=0, then stop; (vj,cj) is an optimal solution to the dual problem and Kj is a solution to (3.1); so f(Kj) is the optimal value of problem (3.1). Otherwise, go to Step 2.Step 2.
Update(vj,cj) by
(3.7)vj+1=vj-zjh(Kj),cj+1=cj+(zj+εj)∥h(Kj)∥,
where zj and εj are positive scalar step sizes defined below. Replace j by j+1 and go to Step 1.Step Size Calculation
Let us consider the pair (vj,cj) and calculate
(3.8)H(vj,cj)=minK∈ΩL(K,v,c),
and let H(Kj)≠0 for the corresponding Kj, which means that Kj is not optimal. Then the step size parameter zj can be calculated as
(3.9)0<zj<2(H̅-H(vj,cj))5∥h(Kj)∥2,0<εj<zj,
where H¯ is an upper bound for the dual function. Considering the dual function formed by using the sharp Lagrangian, its value at any feasible point is not larger than primal problems’ objective function value. The equality occurs at a point when both primal and dual problems achieve their optimal values. It has been proven in [38] that if h(K)=0 for any K obtained from (3.6), then it is the solution of the primal problem. If h(K)≠0, then the value of H calculated from (3.6) is strictly less than the optimal value of (3.1). In this case we update dual variables using Step 2, which leads to an increase in the value of the dual function. Solution of (3.6) corresponding to the updated (v,c) is always greater than the value obtained in the previous step. Note that this property is not guaranteed by the multiplier and penalty methods [43, 45].   According to MSG method for solving the UC problem, the objective function and constraints are defined as follows.Objective Function
One has(3.10)minF(Pit,Uit)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+∑t=1T∑i=1NSDit×(1-Uit)Uit-1.
Slack variables are added to inequality constraints. Equality and inequality constraints can be defined as follows.Generation Limit Constraints
One has(3.11)h1(N,T)=UitPi,min-Pit+hit=0,h2(N,T)=Pit-UitPi,max+hit=0.Load Balance Constraints
One has(3.12)h3(T)=∑i=1NUitPit-Pdt=0.Ramp Up and Ramp Down Constraints
One has(3.13)h4(N,T)=Pit-1-Pit-RDi,+hit,ifUit=1&Uit-1=1,h5(N,T)=Pit-Pit-1-RUit+hit,ifUit=1&Uit-1=1.hit shows slack variables from (3.11) to (3.13).
H= [h1(N,T)h2(N,T)h3(T)h4(N,T)h5(N,T)]. According to (3.3), sharp augmented Lagrangian LSAL is defined as follows:(3.14)LSAL=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+∑t=1T∑i=1NSDit×(1-Uit)Uit-1+c·[{+(Pit-Pit-1-RUit+hit)2(∑i=1NUit·Pit-Pdt)2)2}sqrt((∑i=1NUit·Pit-Pdt)(UitPi,min-Pit+hit)2+(Pit-UitPi,max+hit)2+(∑i=1NUit·Pit-Pdt)2+(Pit-1-Pit-RDit+hit)2+(Pit-Pit-1-RUit+hit)2(∑i=1NUit·Pit-Pdt)2)]-vit[{∑i=1NUit·Pit-Pdt}(UitPi,min-Pit+hit)+(Pit-UitPi,max+hit)+(∑i=1NUit·Pit-Pdt)+(Pit-1-Pit-RDi+hit)+(Pit-Pit-1-RUit+hit){∑i=1NUit·Pit-Pdt}].The epsilon value is chosen as 0.95zj in the UC problem solution. After (3.14) is constructed using the objective function and constraints, all the steps of the MSG method are applied to the UC problem. In this study, SA algorithm is used in order to assign the appropriate initial value H¯ for MSG method. Then, the UC problem is solved using this proposed method for finding the optimal solution.


## 3.1. Simulated Annealing Algorithm for Unit Commitment

SA algorithm is a strong technique for solving hard combinatorial optimization problems without specific structure. This method has the ability of escaping local minima by performing uphill moves. The main advantage of SA algorithm is that it does not need large computer memory. SA is based on the iterative method, originally proposed by Metropolis et al. [44], which simulates the transition of atoms in equilibrium at a given temperature. The main disadvantage of this method is very greedy regarding computation time requirements, due to the large number of iterations needed for the convergence of the method. All the generating and acceptance distributions depend on the temperature [3].One of the measure steps in the SA is the cooling schedule. This schedule has three components: the initial temperature setting, the temperature decreasing scheme, and a finite number of initial value of temperature should be large enough to allow all transients to be accepted for unconstrained optimization problem. On the other hand, the temperature is lowered based on multiplying the temperature in which typical values lie between 0.8 and 0.99. If the acceptance ratio is low or the sampled mean and variance of cost values at current temperature have big drops, then the factor is adjusted to a higher value in order to avoid getting stuck at a local optimal configuration. Otherwise, the factor is adjusted to a lower value to increase the convergence speed. The number of moves at each temperature is based on the requirement that at each temperature quasiequilibrium is to be restored. The final temperature is obtained if, at five consecutive temperatures, either the sampled mean values of cost function do not change or the acceptance ratio is small enough [2, 3].In solving the UC problem by using SA algorithm, two types of variables need to be determined: the unit status (binary) variablesU and the units output power (continuous) variables P. Then, this problem can be considered into two subproblems, a combinatorial optimization problem in U and a nonlinear optimization problem in P. The flow diagram of SA algorithm for UC problem is given in Figure 1 [3]. The economic dispatch problem is solved by using lambda-iteration method in the SA.Figure 1
SA algorithm for UC problem.


## 3.2. Modified Subgradient Method for Unit Commitment

The MSG method proposed by Gasimov has a notable performance in having zero duality gaps for large class of nonconvex problems [38, 39].   In the standard form the nonlinear programming problem can be expressed as follows: (3.1)minKf(K)(3.2)subjectto{h(K)≤0,K∈Ω,whereh(K)=[h1(K)h2(K)⋯hn(K)] is the constraint vector.The primal problem is (3.1). Sharp augmented Lagrangian is defined as follows:(3.3)L(K,v,c)=f(K)+c∥h(K)∥-vTh(K),
where v∈R3 and c∈R+. Define the dual function as (3.4)H(v,c)=minK∈ΩL(K,v,c).The dual problem (P*) is(3.5)max(v,c)∈R3×R+H(v,c).
Dual function H(v,c) is not a definite function; however it is a convex function for continuous  f(K), h(K) and compact set S.  Inequality constraints can be converted to standard form by adding nonnegative slack variables to left hand sides of inequalities; one of the advantages of the MSG method is that the fact that the solution convergence is proved. Thus, in each iteration a better solution can be found. This method differs from the classical LR functions, scans the solution with conics, and hence obtains zero dual gap value. In other words, there is no difference between primal and dual problems. Thus it gives an optimal solution. Another advantage of this method is that it does not require any convexity and differentiability assumptions.Using the definitions, the MSG method is as follows.Initialization
Choose a pair (v1,c1) with  v1∈R3andc∈R+, c1≥0and letj=1, and go to Step 1.Step 1.
Given (cj,vj), solve the following subproblem:
(3.6)minKf(K)+cj∥h(K)∥-vjh(K)=H(vj,cj)
subject to k∈Ω.In (3.6) (cj,vj) is multiplier of sharp augmented Lagrangian, f(K) is objective function, ∥h(K)∥ is  norm of the constraint vector, and H(vj,cj) is dual function of the problem. Let Kj be a solution of (3.6). If h(Kj)=0, then stop; (vj,cj) is an optimal solution to the dual problem and Kj is a solution to (3.1); so f(Kj) is the optimal value of problem (3.1). Otherwise, go to Step 2.Step 2.
Update(vj,cj) by
(3.7)vj+1=vj-zjh(Kj),cj+1=cj+(zj+εj)∥h(Kj)∥,
where zj and εj are positive scalar step sizes defined below. Replace j by j+1 and go to Step 1.Step Size Calculation
Let us consider the pair (vj,cj) and calculate
(3.8)H(vj,cj)=minK∈ΩL(K,v,c),
and let H(Kj)≠0 for the corresponding Kj, which means that Kj is not optimal. Then the step size parameter zj can be calculated as
(3.9)0<zj<2(H̅-H(vj,cj))5∥h(Kj)∥2,0<εj<zj,
where H¯ is an upper bound for the dual function. Considering the dual function formed by using the sharp Lagrangian, its value at any feasible point is not larger than primal problems’ objective function value. The equality occurs at a point when both primal and dual problems achieve their optimal values. It has been proven in [38] that if h(K)=0 for any K obtained from (3.6), then it is the solution of the primal problem. If h(K)≠0, then the value of H calculated from (3.6) is strictly less than the optimal value of (3.1). In this case we update dual variables using Step 2, which leads to an increase in the value of the dual function. Solution of (3.6) corresponding to the updated (v,c) is always greater than the value obtained in the previous step. Note that this property is not guaranteed by the multiplier and penalty methods [43, 45].   According to MSG method for solving the UC problem, the objective function and constraints are defined as follows.Objective Function
One has(3.10)minF(Pit,Uit)=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+∑t=1T∑i=1NSDit×(1-Uit)Uit-1.
Slack variables are added to inequality constraints. Equality and inequality constraints can be defined as follows.Generation Limit Constraints
One has(3.11)h1(N,T)=UitPi,min-Pit+hit=0,h2(N,T)=Pit-UitPi,max+hit=0.Load Balance Constraints
One has(3.12)h3(T)=∑i=1NUitPit-Pdt=0.Ramp Up and Ramp Down Constraints
One has(3.13)h4(N,T)=Pit-1-Pit-RDi,+hit,ifUit=1&Uit-1=1,h5(N,T)=Pit-Pit-1-RUit+hit,ifUit=1&Uit-1=1.hit shows slack variables from (3.11) to (3.13).
H= [h1(N,T)h2(N,T)h3(T)h4(N,T)h5(N,T)]. According to (3.3), sharp augmented Lagrangian LSAL is defined as follows:(3.14)LSAL=∑t=1T∑i=1N[Fi(Pit)+SCit(1-Uit-1)]Uit+∑t=1T∑i=1NSDit×(1-Uit)Uit-1+c·[{+(Pit-Pit-1-RUit+hit)2(∑i=1NUit·Pit-Pdt)2)2}sqrt((∑i=1NUit·Pit-Pdt)(UitPi,min-Pit+hit)2+(Pit-UitPi,max+hit)2+(∑i=1NUit·Pit-Pdt)2+(Pit-1-Pit-RDit+hit)2+(Pit-Pit-1-RUit+hit)2(∑i=1NUit·Pit-Pdt)2)]-vit[{∑i=1NUit·Pit-Pdt}(UitPi,min-Pit+hit)+(Pit-UitPi,max+hit)+(∑i=1NUit·Pit-Pdt)+(Pit-1-Pit-RDi+hit)+(Pit-Pit-1-RUit+hit){∑i=1NUit·Pit-Pdt}].The epsilon value is chosen as 0.95zj in the UC problem solution. After (3.14) is constructed using the objective function and constraints, all the steps of the MSG method are applied to the UC problem. In this study, SA algorithm is used in order to assign the appropriate initial value H¯ for MSG method. Then, the UC problem is solved using this proposed method for finding the optimal solution.


## 4. Applications and Numerical Results

The UC problem for four-unit Tuncbilek thermal plant is solved by using the MSG method combined with SA algorithm. First the SA algorithm is applied to the UC problem and then the cost function value found from the SA algorithm is used as upper dual value in MSG method for four-unit Tuncbilek thermal plant and ten-unit  thermal plant. SA algorithm is coded in MATLAB PF and MSG methods are coded in GAMS which is a high-level modeling system for mathematical programming problems [46]. The data for four-unit Tuncbilek thermal plant is taken from Turkish Electric Power Company and Electricity Generation Company. The unit characteristics for four-unit Tuncbilek thermal plant are given in Table 1. In this study, a 24-hour day is subdivided into 8 discrete stages for four-unit Tuncbilek thermal plant. The load demands for the stages are given in Table 2. The unit characteristics for ten-unit thermal plant are given in Table 3. The load demands for each period are given in Table 4 for ten unit thermal plant. UC schedule for the SA algorithm for four-unit Tuncbilek thermal plant is given in Table 5. UC schedule for the SA algorithm for ten-unit thermal plant is given in Table 6.Table 1
Unit characteristics for four-unit Tuncbilek thermal plant.
UnitPminPmaxSCabCSDRDiRUiNo(MW)(MW)($)($/h)($/MWh)($/MW2h)($)(MW/h)(MW/h)1832600.51510.86149.912066217652400.2278.341284.648013133351505500.0829.9441495.8110030304301505500.07412.44388.911003030Table 2
Load data for four-unit Tuncbilek thermal plant (MW).
StageLoadStageLoad11685313215063473260730842758231Table 3
Unit characteristics for ten-unit thermal plant.
UnitPminPmaxSCSCabCRDiRUiNo(MW)(MW)(hot)($)(cold)($)($/h)($/MWh)($/MW2h)(MW/h)(MW/h)115045545009000100016.190.00048130130215045550001000097017.260.00031130130320130550110070016.600.002006060420130560112068016.500.002116060525162900180045019.700.0039890906208017034037022.260.0071240407258526052048027.740.0079404081055306066025.920.00413404091055306066527.270.002224040101055306067027.790.001734040Table 4
Load data for ten-unit thermal plant (MW).
StageLoadStageLoadStageLoad170091300171000275010140018110038501114501912004950121500201400510001314002113006110014130022110071150151200239008120016105024800Table 5
UC schedule for SA algorithm for four-unit Tuncbilek thermal plant.
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 1TC = $56249.9.Table 6
UC schedule for SA algorithm for ten-unit thermal plant.
PeriodUnit CombinationPeriodUnit Combination11 1 0 0 0 0 0 0 0 0131 1 1 1 1 1 1 1 0 021 1 0 0 0 0 0 0 0 0141 1 1 1 1 1 1 0 0 031 1 0 0 1 0 0 0 0 0151 1 1 1 1 0 0 0 0 041 1 0 0 1 0 0 0 0 0161 1 1 1 1 0 0 0 0 051 1 0 1 1 0 0 0 0 0171 1 1 1 1 0 0 0 0 061 1 1 1 1 0 0 0 0 0181 1 1 1 1 0 0 0 0 071 1 1 1 1 0 0 0 0 0191 1 1 1 1 1 0 0 0 081 1 1 1 1 0 0 0 0 0201 1 1 1 1 1 1 1 0 091 1 1 1 1 1 1 1 0 0211 1 1 1 1 1 1 0 0 0101 1 1 1 1 1 1 1 0 0221 1 0 0 1 1 1 0 0 0111 1 1 1 1 1 1 1 1 0231 1 0 0 1 0 0 0 0 0121 1 1 1 1 1 1 1 1 1241 1 0 0 0 0 0 0 0 0TC =  $565907.9.The cost value $56249.9 found from the SA algorithm is used for upper dual value in MSG method for four-unit Tuncbilek thermal plant. The cost value $565907.9 found from the SA algorithm for ten-unit thermal plant. Optimal solution of the dual model set up by the augmented Lagrange function, which is proposed by Azimov and Gasimov for nonconvex problems, is equal to the primal solution of the system [38–40]. CONOPT2 is used as a GAMS solver for MSG and PF methods. The MSG method is run until the norm is equal to 9.713717×10-7 for four-unit Tuncbilek thermal plant; the norm is equal to 6.61489×10-4 for ten-unit thermal plant. 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 for both of these systems. The value for the c parameter is 9957.327 for four-unit Tuncbilek thermal plant; c parameter is 13468.451 for ten-unit thermal plant.  The UC schedule for MSG method combined with SA algorithm is given for four-unit Tuncbilek thermal plant and ten-unit thermal plant in Tables 7 and 8, respectively.Table 7
UC schedule for MSG method combined with SA algorithm for four-unit Tuncbilek thermal plant.
StageUnit Combination10 0 1 120 1 1 030 1 1 140 1 1 151 1 1 161 1 1 171 1 1 180 1 1 1TC = $55581.683 (primal value = dual value).Table 8
UC schedule for MSG method combined with SA algorithm for ten-unit thermal plant.
PeriodUnit CombinationPeriodUnit Combination11 1 0 0 0 0 0 0 0 0131 1 1 1 1 1 1 1 0 021 1 0 0 0 0 0 0 0 0141 1 1 1 1 1 1 0 0 031 1 0 0 1 0 0 0 0 0151 1 1 1 1 0 0 0 0 041 1 0 0 1 0 0 0 0 0161 1 1 1 1 0 0 0 0 051 1 0 1 1 0 0 0 0 0171 1 1 1 1 0 0 0 0 061 1 1 1 1 0 0 0 0 0181 1 1 1 1 0 0 0 0 071 1 1 1 1 0 0 0 0 0191 1 1 1 1 1 0 0 0 081 1 1 1 1 0 0 0 0 0201 1 1 1 1 1 1 0 0 091 1 1 1 1 1 0 0 0 0211 1 1 1 1 1 1 0 0 0101 1 1 1 1 1 1 1 0 0221 1 0 0 1 1 1 0 0 0111 1 1 1 1 1 1 1 1 0231 1 0 0 1 0 0 0 0 0121 1 1 1 1 1 1 1 1 1241 1 0 0 0 0 0 0 0 0TC = $563986.5 (primal value = dual value).In Table7, the total cost value is found $55581.683 and in Table 8 total cost value is found $563986.5 for MSG method combined with SA algorithm. It can be seen from Tables 7 and 8 that MSG reaches to zero duality gap value (primal value = dual value) for UC problem.To show the advantages of this method, PF method is used. UC schedule, primal-dual values for PF method are given in Tables9 and 10 for four-unit Tuncbilek thermal plant and for ten-unit thermal plant, respectively.Table 9
UC schedule for PF method for four-unit Tuncbilek thermal plant.
StageUnit Combination10 0 1 120 0 1 130 0 1 140 1 1 151 1 1 161 1 1 170 1 1 180 1 1 1Primal value = $55917.13, Dual value = $55407.38.Table 10
UC schedule for PF method for ten-unit thermal plant.
PeriodUnit CombinationPeriodUnit Combination11 1 0 0 0 0 0 0 0 0131 1 1 1 1 1 1 1 0 021 1 0 0 0 0 0 0 0 0141 1 1 1 1 1 1 0 0 031 1 0 0 1 0 0 0 0 0151 1 1 1 1 0 0 0 0 041 1 0 0 1 0 0 0 0 0161 1 1 1 1 0 0 0 0 051 1 0 1 1 0 0 0 0 0171 1 1 1 1 0 0 0 0 061 1 1 1 1 0 0 0 0 0181 1 1 1 1 0 0 0 0 071 1 1 1 1 0 0 0 0 0191 1 1 1 1 1 0 0 0 081 1 1 1 1 0 0 0 0 0201 1 1 1 1 1 1 0 0 091 1 1 1 1 1 1 0 0 0211 1 1 1 1 1 1 0 0 0101 1 1 1 1 1 1 1 1 0221 1 0 0 1 1 1 0 0 0111 1 1 1 1 1 1 1 1 0231 1 0 0 1 0 0 0 0 0121 1 1 1 1 1 1 1 1 1241 1 0 0 0 0 0 0 0 0Primal value = $565282.9, Dual value = $559741.45.It is seen that there are differences between primal value and dual value in the PF method. 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 using total cost value of the SA algorithm as an upper dual value for the MSG method.


## 5. Conclusion

The quality of the solution of UC problem is improved when the duality gap is decreased. In this paper zero duality gap is achieved and feasible solution is attained by applying the novel proposed method, MSG method combined with SA algorithm, to solving the UC problem. The cost function found from the SA algorithm is used for upper dual value in MSG method. The most attractive feature of the proposed approach is that the duality gap value of MSG method over the scheduled time horizon is zero. Note that there is a general acceptance that whenever the system size gets smaller, the duality gap value gets bigger for UC problem. However, it is shown that this is not the case with the MSG method for a small size system. The results of the proposed method for solving the UC problem are very impressive, and the quality of feasible solution is significantly improved. This approach can be applied to UC problem for any size of systems to obtain the feasible schedule.



---

*Source: 295645-2010-07-08.xml*