鄭海艷

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，廣西南寧　530004)

?

計及CO2排放機組組合問題的加速廣義Benders分解法*

鄭海艷

(廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，廣西南寧530004)

(College of Mathematics and Information Science,Guangxi University,Nanning,Guangxi,530004,China)

摘要：提出求解計及CO2排放機組組合(unit commitment,UC)問題的一個加速廣義Benders分解法：首先建立相關(guān)問題的一個近似混合整數(shù)二次規(guī)劃模型；然后根據(jù)UC問題特點提出一類簡單卻非常有效的整數(shù)割平面，并基于該割平面以及其他一些加速技術(shù)構(gòu)造求解UC問題相應(yīng)模型的加速廣義Benders分解法；最后將所提方法在10～100臺機組24時段等6個系統(tǒng)上進行數(shù)值測試。與其他方法相比較,本文所提方法測試結(jié)果較優(yōu),說明所提方法是有效的，從而為有效求解相關(guān)UC問題提供了一條新的途徑。

關(guān)鍵詞：機組組合混合整數(shù)二次規(guī)劃整數(shù)割平面加速廣義Benders分解

0　引言

【研究意義】機組組合(unit commitment,UC)是電力系統(tǒng)運行調(diào)度一個非常重要的方面，同時也是一個非常活躍的研究領(lǐng)域。經(jīng)典的UC問題是指在一個調(diào)度周期內(nèi)滿足系統(tǒng)預(yù)測負荷需求和旋轉(zhuǎn)備用等約束條件下，確定機組的啟停計劃和機組出力情況，從而使發(fā)電總費用最小[1]。UC問題在數(shù)學(xué)上常被描述成一個大規(guī)模的混合整數(shù)組合優(yōu)化問題，含有大量表示機組啟停狀態(tài)的0-1變量和表示機組出力的連續(xù)變量?！厩叭搜芯窟M展】迄今為止，幾乎所有用于求解混合整數(shù)規(guī)劃問題的確定性方法[2-7]以及源于對一些生物和社會現(xiàn)象的模擬而產(chǎn)生的智能算法[8-9]都被嘗試用于求解UC問題，但由于其可行解集的組合性質(zhì)，該問題很難在多項式時間內(nèi)有效求解。此外，近年來由于大量溫室氣體排放所導(dǎo)致的全球變暖已成為全世界共同關(guān)心的重點問題，而電力工業(yè)是溫室氣體的排放大戶，占全球二氧化碳(CO2)總排放的40%，因此， 考慮計及CO2排放的UC問題并進行有效求解具有非常重要的應(yīng)用價值[10-12]?！颈狙芯壳腥朦c】分解法是求解大規(guī)模復(fù)雜問題的一種常用技術(shù)，其基本思想是先將復(fù)雜問題分解為相對容易求解的主問題和子問題，然后通過逐次交替迭代求解這兩個問題來達到求解原復(fù)雜問題的目的。這類方法主要包括Benders分解法[13-14]和外逼近法[15]，并且已被嘗試用于求解經(jīng)典的UC問題[16-19]。然而當前Benders分解法在求解各類復(fù)雜問題時存在一個計算方面的瓶頸——由于其在每次迭代中僅加入一個相應(yīng)的Benders割平面，所以該方法計算效率較低?！緮M解決的關(guān)鍵問題】本文提出能有效求解計及CO2排放UC問題的一個加速廣義Benders分解法,并將其在10～100臺機組24時段等6個系統(tǒng)上進行數(shù)值測試,同時將測試結(jié)果與其他方法的結(jié)果進行比較。

1　計及CO2排放UC問題的混合整數(shù)二次規(guī)劃模型

計及CO2排放UC問題的目標函數(shù)是讓發(fā)電機組的運行成本Fc與排放成本Ec加權(quán)和求最小，即

minTc=wfFc+weEc,

(1)

式中wf,we為各成本所占權(quán)重系數(shù)，F(xiàn)c與Ec的具體表達式如下：

(2)

(3)

其中N為機組總數(shù)，i=1,2,…,N為機組標號；T為時段總數(shù)，t=1,2,…,T為時段標號；αi,βi,γi為機組i的發(fā)電費用參數(shù)；Ci,t為機組啟動費用；πi為機組i的排放懲罰因子；ai,bi,ci為機組i的耗量特性參數(shù)。此外，ui,t為0-1整數(shù)變量，表示機組i在第t時段的狀態(tài)，值為1時表示機組i處于運行狀態(tài)，值為0時表示機組i處于停機狀態(tài)；Pi,t為連續(xù)變量，表示機組i在第t時段的出力。

計及CO2排放UC問題的約束條件如下：

(4)

(5)

③爬坡約束

(6)

(7)

⑤最小啟停時間約束

(8)

式中NDi是給定參數(shù)，系數(shù)Ki,τ則由下述分段函數(shù)表示：

其中Chot,i、Ccold,i分別為機組i的熱啟動費用與冷啟動費用；Tcold,i為機組i的冷啟動時間。此外，對于時間耦合且離散的非線性最小啟停時間約束(8)，則利用文獻[20]中方法進行線性化處理，具體表示如下：

式中Wi,t是新引進的變量，其表示機組i在第t時段的啟動狀態(tài)，其余參數(shù)定義如下：

基于以上分析，計及CO2排放UC問題可方便地描述為如下近似混合整數(shù)二次規(guī)劃(mixed integer quadratic programming,MIQP)模型：

s.t.Auu+APP+ASS+AWW≤auc,

u=(ui,t),P=(Pi,t),S=(Si,t),W=(Wi,t),

ui,t∈{0,1},Pi,t,Si,t≥0,Wi,t∈[0,1],

i=1,…,N,t=1,…,T,

(9)

式中u,P,S,W為相應(yīng)變量所組成的向量，Au,AP,AS,AW是相應(yīng)變量所對應(yīng)的系數(shù)矩陣,auc則為右端常數(shù)向量。

2　計及CO2排放UC問題的加速廣義Benders分解法

2.1廣義Benders分解法

廣義Benders分解法(generalized Benders decomposition method,GBDM)[14]可直接用于求解混合整數(shù)非線性規(guī)劃(mixed integer nonlinear programming,MINLP)問題，下面結(jié)合UC問題特點，以如下形式的MINLP問題為例簡單介紹GBDM：

mincTy+f(x)

s.t.h(x)=0,

By+Cx≤b,

Dy≤d,

x∈Rn,y∈{0,1}m,

(10)

其中f(x)是光滑的非線性函數(shù)，h(x)是非線性向量值函數(shù)，B,C,D是相應(yīng)系數(shù)矩陣，c,b,d是常數(shù)向量。對于當前給定的整數(shù)變量值yk，GBDM形成如下非線性子問題：

mincTyk+f(x)

s.t.h(x)=0,

Byk+Cx≤b。

(11)

如果子問題(11)有解，并記其解為xk，且λk為對應(yīng)于不等式約束Byk+Cx≤b的乘子向量，則根據(jù)這些數(shù)據(jù)可得到下述最優(yōu)性Benders割平面：

cTy+f(xk)+(λk)T(Cxk+By-b)≤μ。

(12)

相反，若子問題(11)無解，則求解下述可行性子問題

minη

s.t.h(x)=0,

Byk+Cx-η≤b。

(13)

(14)

此外，GBDM中的主問題形式如下：

minμ

Dy≤d

cTy+f(xk)+(λk)T(By+Cxk-b)≤μ,

μ∈R,y∈{0,1}m。

(15)

下面給出GBDM求解問題(10)的基本步驟。

初始步取初始上界UB=∞，同時選取初始整數(shù)變量值yk，并令k∶=0。

步驟1形成并求解子問題。

若子問題(11)有最優(yōu)解，則可得到相應(yīng)最優(yōu)性Benders割平面，若進一步還有

UB>cTyk+f(xk)，

則令UB=cTyk+f(xk),x*=xk,y*=yk；

若子問題(11)無解，則求解可行性子問題(13)，并得到可行性Benders割平面或者直接計算如下組合Benders割平面[21],

∑j∈Soneyj-∑j∈Szeroyj≤|Sone|-1,

(16)

步驟2求解主問題。

將步驟1中所產(chǎn)生的割平面加入到上一次的主問題(15)中，重新求解主問題，并記yk+1為主問題最優(yōu)解中對應(yīng)于整數(shù)變量的值，zmilp為相應(yīng)的最優(yōu)值。若zmilp≥UB，則算法終止，當前(x*,y*)就是原MINLP問題(10)的最優(yōu)解；否則，令k∶=k+1，返回步驟1。

2.2UC問題的整數(shù)割平面

UC問題整數(shù)割平面的導(dǎo)出是源于對其一種非常自然的理解，即先去找每個時段必須投入運行機組數(shù)的有效下界，因此對于每個時段先求解如下線性規(guī)劃問題：

minUt

Auu+APP+ASS+AWW≤auc,

u=(ui,t),P=(Pi,t),S=(Si,t),W=(Wi,t),

ui,t∈[0,1],Pi,t,Si,t≥0,Wi,t∈[0,1],

i=1,…,N,t=1,…,T。

(17)

(18)

2.3求解計及CO2排放UC問題的加速GBDM

首先根據(jù)前面所述內(nèi)容可知計及CO2排放UC問題的近似MIQP模型中僅在目標函數(shù)中出現(xiàn)非線性項，若將該項除去，所求問題便變成一個混合整數(shù)線性規(guī)劃(mixed integer linear programming,MILP)，其與原MIQP有相同的可行域，因此在不追求精度的情況下，可調(diào)用著名商業(yè)軟件CPLEX快速得到MILP的一個可行解，從而計算出原MIQP目標函數(shù)值的一個上界。其次，在應(yīng)用GBDM求解MIQP時，初始主問題是原MIQP的一個松弛問題，僅包含原問題的部分約束和變量，故其最優(yōu)值是原MIQP目標函數(shù)值的一個下界。而2.2節(jié)所提的整數(shù)割平面僅含有0-1整數(shù)變量，并且加入這些割平面可以使得原MIQP的連續(xù)松弛問題變緊，故在應(yīng)用GBDM求解相關(guān)UC問題時，相應(yīng)的主問題也會變緊，從而能夠提供一個更好的下界。此外，為進一步減少計算量，當相應(yīng)的非線性子問題(11)不可行時，不去計算相應(yīng)的可行性子問題，而是直接利用顯式公式(16)計算相應(yīng)的組合Benders割平面?；谇笆黾夹g(shù)，可得到求解計及CO2排放UC問題的一個加速廣義Benders分解法，具體算法流程如圖1所示。

3　數(shù)值仿真

為方便起見，將本文所提出的加速廣義Benders分解法簡記為AGBDM，為驗證其計算效率，下面就不計CO2排放UC問題情形在10～100臺機組24時段等6個系統(tǒng)上進行測試，并將測試結(jié)果與已有的Berders分解法以及另外一些有效方法進行比較，同時以10臺機組24時段系統(tǒng)為例詳細說明該方法求解計及CO2排放UC問題的有效性。10臺機組24時段系統(tǒng)的基本數(shù)據(jù)取自文獻[2]，20～100臺機組的相關(guān)數(shù)據(jù)是通過復(fù)制10臺機組24時段系統(tǒng)的基本數(shù)據(jù)得到，而CO2排放數(shù)據(jù)則來源于文獻[22]。旋轉(zhuǎn)備用取總負荷的10%。運行環(huán)境為AMD Athlon Dual Core Processor 4400+ 2.3 GHz,1 GB RAM，并在Matlab 2010環(huán)境下調(diào)用CPLEX 11[23]求解主問題與子問題以及相應(yīng)線性規(guī)劃問題。此外，在調(diào)用CPLEX得到相應(yīng)可行解時精度取為0.05。

圖1算法流程圖

Fig.1Flow chat of algorithm

3.1不計CO2排放UC問題情形

為驗證本文所提AGBDM在求解不計CO2排放UC(此時wf=1,we=0)問題時的加速效果，對于不計爬坡約束情形，將相同精度下的測試結(jié)果同時與廣義Benders分解法[18](簡記為GBDM) 以及松弛型Benders分解法[19](簡記為RBDM) 所得結(jié)果進行比較(表1)，其中Niter表示迭代次數(shù)，CPU表示計算時間，Cost表示總費用，數(shù)據(jù)中的粗體部分表示最好結(jié)果，后面表格中的記法類似。通過表1可以看出本文所提AGBDM均能在合理的時間內(nèi)經(jīng)過一次迭代后便收斂，說明該方法具有良好的穩(wěn)定性。此外，除10臺機組與20臺機組24時段兩個較小的系統(tǒng)外，其他系統(tǒng)的測試結(jié)果均優(yōu)于另外兩種方法，這也說明整數(shù)割平面以及2.3節(jié)所介紹的加速技術(shù)能很好地改進Benders分解法求解UC問題的計算效果，也正是因為AGBDM在求解相關(guān)問題時可得到更好的上下界，所以整個算法的迭代次數(shù)要少。

表110～100臺機組24時段系統(tǒng)3種算法結(jié)果比較

Table 1 The results of three algorithms for 10～100 units and 24 hours

機組數(shù)NumberofunitsGBDMRBDMAGBDMNiterCost($)NiterCost($)NiterCPU(s)Cost($)105565,5372563,93812.73564,2092051,123,61921,123,642112.331,124,3854042,243,64622,243,787119.772,242,2856043,363,87623,363,760123.973,362,1608044,485,44324,481,813144.704,480,72110035,603,49625,603,450165.315,601,020

為進一步說明本文所提AGBDM求解相關(guān)UC問題的有效性，對于不計爬坡約束情形，將其測試結(jié)果同當前一些數(shù)值表現(xiàn)良好的確定性方法如拉格朗日松弛(LR)法[2]、混合整數(shù)線性規(guī)劃(MILP)法[3]、二階錐規(guī)劃(CONE)法[5]、外逼近法(OAM)[16]、內(nèi)外逼近法(OIAM)[17]等進行比較(表2)，表中記號“—”表示原文中沒有給出相應(yīng)結(jié)果。通過表2可以看出：對于40臺機組與80臺機組這兩個系統(tǒng)，AGBDM的測試結(jié)果優(yōu)于當前最好的內(nèi)外逼近法，而其余系統(tǒng)的計算結(jié)果稍稍遜于最好結(jié)果。此外，作為測試效果優(yōu)秀的外逼近與內(nèi)外逼近，在求解相關(guān)UC問題時其迭代次數(shù)均為兩次，而本文所提AGBDM由于加入整數(shù)割平面，并利用2.3節(jié)所介紹的加速技術(shù)，其迭代次數(shù)均為1次。

表210～100臺機組24時段系統(tǒng)不同算法結(jié)果比較(＄)

Table 2The results of different algorithms for 10～100 units and 24 hours (＄)

表310～100臺機組24時段系統(tǒng)(計及爬坡約束)

Table 3System for 10～100 units and 24 hours(with ramp rate constraints)

機組數(shù)NumberofunitsCPU(s)NiterCost($)102.531568,8712014.1211,133,9654024.8912,264,3506065.9713,394,2528087.1914,526,773100110.1715,660,380

3.2計及CO2排放UC問題情形

類似于文獻[22]，下面僅以10臺機組24時段系統(tǒng)并計及爬坡約束為例，詳細說明本文所提AGBDM求解計及CO2排放UC問題的有效性。在數(shù)值測試中取權(quán)重因子wf=we=1。根據(jù)表4可以看出所考察系統(tǒng)在24時段內(nèi)所排放的CO2總額為260 067(Ton)，若取排放懲罰因子πi=1＄Ton(i=1,…,N)，則排放費用為260 067＄。由此可見，排放費用不容忽視，特別是在大力倡導(dǎo)節(jié)能減排以及高科技發(fā)展迅速的今天，很有必要在經(jīng)典電力系統(tǒng)機組組合問題中考慮一些清潔可再生能源，如結(jié)合太陽能發(fā)電、風(fēng)力發(fā)電以及可入網(wǎng)電動汽車等。

4　結(jié)論

本文提出計及CO2排放UC問題的一個加速廣義Benders分解法，首先利用線性化技術(shù)建立一個近似MIQP模型，然后結(jié)合UC問題特點提出一個針對機組組合問題而言非常簡單卻效果很明顯的有效割平面——整數(shù)割平面，同時基于該整數(shù)割平面以及文中所介紹的加速技術(shù)提出求解相關(guān)UC問題近似MIQP模型的加速廣義Benders分解法，最后將所提方法在不同系統(tǒng)上進行數(shù)值測試。不同情形下的測試結(jié)果以及與當前其他一些有效方法的比較表明，本文所提方法能有效求解相關(guān)UC問題，并且具有良好的穩(wěn)定性和收斂性。

表410臺機組24時段系統(tǒng)調(diào)度計劃及CO2排放情況

Table 4Unit scheduling and corresponding costs for the 10 units and 24 hours system

時段Hour機組Unit12345678910CO2排放CO2emission(Ton)1455250000000006827245529500000000754734552650130000000772844552351301300000007965545528513013000000086546455360130130250000010226745541013013025000001130584554551301302500000124109455455130130852025000129271045545513013016233251000135581145545513013016273251010013866124554551301301628025431010141541345545513013016233251000135581445545513013085202500012927154554551301302500000124101645531013013025000009302174552601301302500000853618455360130130250000010226194554551301302500000124102045545513013016233251000135582145545513013085202500012927224553401301300202500010113234553151300000000851024455345000000008423

參考文獻:

[1]SHEBLé G B,FAHD G N.Unit commitment literature synopsis[J].IEEE Transactions on Power Systems，1994，9(1)：128-135.

[2]ONGSAKUL W，PETCHARAKS N.Unit commitment by enhanced adaptive lagrangian relaxation[J].IEEE Transactions on Power Systems，2004，19(1)：620-628.

[3]CARRION M，ARROYO J M.A computationally effi- cient mixed-integer linear formulation for the thermal unit commitment problem[J].IEEE Transactions on Power Systems，2006，21(3):1371-1378.

[4]全然,簡金寶,韋化,等.基于特殊有效不等式求解機組組合問題的內(nèi)點割平面法[J].中國電機工程學(xué)報,2011,31(19):51-59. QUAN R,JIAN J B,WEI H，et al.An interior-point cutting plane method for unit commitment based on special valid inequalities[J].Proceedings of the CSEE,2011,31(19):51-59.

[5]YUAN X H,TIAN H,ZHANG S Q.Second-order cone programming for solving unit commitment strategy of thermal generators[J].Energy Conversion and Management,2013,76:20-25.

[6]YANG L F，JIAN J B，ZHU Y N，et al.Tight relaxation method for unit commitment problem using reformulation and lift-and-project[J].IEEE Transactions on Power Systems,2015,30(1):13-23.

[7]ZHENG H Y，JIAN J B，YANG L F,et al.A deterministic method for the unit commitment problem in power systems[J].Computers & Operations Research， 2016，66：241-247.

[8]KAZARLIS S A,BAKIRTZIS A G,PETRIDIS V.A genetic algorithm solution to the unit commitment problem[J].IEEE Transactions on Power Systems,1996,11(1)：83-92.

[9]MANTAWY A H,ABDEL-MAGID Y L,SELIM S Z.Unit commitment by tabu search[J].IEE Proceedings-Generation,Transmission and Distribution,1998,145(1):56-64.

[10]GJENGEDAL T.Emission constrained unit-commitm- ent(FCUC)[J].IEEE Transactions on Energy Conversion,1996,11(1):132-138.

[11]張曉花，趙晉泉，陳星鶯.節(jié)能減排多目標機組組合問題的模糊建模及優(yōu)化[J].中國電機工程學(xué)報，2010，30(22)：71-76. ZHANG X H,ZHAO J Q,CHEN X Y.Multi-objective unit commitment fuzzy modeling and optimization for energy-saving and emission reduction[J].Proceedings of the CSEE,2010，30(22)：71-76.

[12]XIE J,ZHONG J,LI Z,et al.Environmental-economic unit commitment using mixed-integer linear programming[J].European Transactions on Electrical Power,2011,21(1):772-786.

[13]BENDERS J F.Partitioning procedures for solving mixed-variables programming problems[J].Numerische Mathematik,1962,4(1):238-252.

[14]GEOFFRION A M.Generalized benders decomposition[J].Journal of Optimization Theory and Applications,1972,10(4):237-260.

[15]DURAN M A,GROSSMANN I E.An outer-approximation algorithm for a class of mixed-integer nonlinear programs[J].Mathematical Programming,1986,36(3):307-339.

[16]全然，簡金寶，鄭海艷.基于外逼近方法的中期機組組合問題[J].電力系統(tǒng)自動化,2009,33(11)：24-28,103. QUAN R,JIAN J B,ZHENG H Y.Medium term unit commitment based on outer approximation method[J].Automation of Electric Power Systems,2009,33(11)：24-28,103.

[17]HAN D L,JIAN J B,YANG L F.Outer approximation and outer-inner approximation approaches for unit commitment problem[J].IEEE Transactions on Power Systems,2014,29(2):505-513.

[18]RAHIMI S,NIKNAM T,FALLAHI F.A new approa- ch based on Benders decomposition for unit commitment problem[J].World Applied Sciences Journal,2009,6(12):1665-1672.

[19]鄭海艷，簡金寶，全然，等.基于改進的Benders分解與透視割平面的機組組合算法[J].電力自動化設(shè)備，2015，35(1)：133-138. ZHENG H Y，JIAN J B，QUAN R,et al.Unit commitment algorithm based on improved Benders decomposition and perspective cut[J].Electric Power Automation Equipment,2015，35(1)：133-138.

[20]OSTROWSKI J,ANJOS M F,VANNELLI A.Tight mixed integer linear programming formulations for the unit commitment problem[J].IEEE Transactions on Power Systems，2012，27(1)：39-46.

[21]CODATO G,FISCHETTI M.Combinatorial Benders’ cuts for mixed-integer linear programming[J].Operations Research,2006 54(4):756-766.

[22]陸凌蓉，文福栓，薛禹勝，等.計及可入網(wǎng)電動汽車的電力系統(tǒng)機組最優(yōu)組合[J].電力系統(tǒng)自動化，2011，35(21):16-20. LU L R,WEN F S,XUE Y S,et al.Unit commitment in power systems with plug-in electric vehicles[J].Automation of Electric Power Systems,2011，35(21):16-20.

[23]KENNETH H,ANDERS O G,MARCUS M E.User’s guide for TOMLAB /CPLEX v11.2[EB/OL].[2008-02-08].http://tomopt.com/tomlab/download/manuals.php.

(責任編輯：米慧芝)

Accelerating Generalized Benders Decomposition Method for the Unit Commitment Problem with CO2-Emission

ZHENG Haiyan

Key words：unit commitment,mixed integer quadratic programming,integer cut,accelerating generalized Benders decomposition

Abstract：An accelerating generalized Benders decomposition method(AGBDM) is presented for the unit commitment (UC) problem with CO2-emission:An approximate mixed integer quadratic programming model for the related problem is established by some linearization technique first;then an integer cut is put forward according to the characteristics of the UC problem,which is simple but highly efficient,and AGBDM is proposed for solving the corresponding model of the UC problem,which is based on the integer cut and some other strengthening techniques;the proposed AGBDM is used to solve the six systems which range in size from 10 to 100 units with 24 h finally.The simulation results and the comparison results with other methods show that the proposed method is efficient,and it proposes a new approach for solving the relevant unit commitment problem.

收稿日期：2016-08-05

作者簡介：鄭海艷(1977-)，女，博士，主要從事最優(yōu)化理論與方法及其在電力系統(tǒng)中的應(yīng)用研究，E-mail:zhenghaiyan166@126.com。

中圖分類號：TM76

文獻標識碼：A

文章編號：1005-9164(2016)05-0409-07

修回日期：2016-09-19

*國家自然科學(xué)基金項目(11271086)和廣西自然科學(xué)基金創(chuàng)新研究團隊項目(2014GXNSFFA118001)資助。

廣西科學(xué)Guangxi Sciences 2016,23(5):409～415

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.017

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1546.034.html