基于原對偶內(nèi)點法和分枝定界算法的配網(wǎng)無功優(yōu)化計算及其并行實現(xiàn)

王 云，江全元

（浙江大學 電氣工程學院，浙江 杭州 310027）

0 引言

無功優(yōu)化是指在滿足各種約束條件下，利用無功控制手段，如控制可調(diào)變壓器的分接頭、可投切電容器投切數(shù)量等，來提高電壓水平，降低系統(tǒng)有功損耗。但變壓器變比和并聯(lián)電容器組都不能進行連續(xù)的調(diào)節(jié)，因此，無功優(yōu)化實質(zhì)是一類非線性混合整數(shù)規(guī)劃問題。如何有效地處理這些離散變量一直是該類問題的一個難點。多年來，國內(nèi)外學者對此進行了大量的學術研究，并提出了一系列優(yōu)化算法。

一種處理方法是先將離散變量作為連續(xù)變量參與優(yōu)化，求得優(yōu)化解后再進行簡單的就近取整，但可能會導致某些約束越限。文獻［1］提出了將無功優(yōu)化問題中的離散變量進行二進制編碼的連續(xù)化處理，從而把該混合整數(shù)優(yōu)化問題轉(zhuǎn)化為一個等價的連續(xù)優(yōu)化問題來求解。文獻［2-4］采用二次罰函數(shù)來處理離散變量，并將其嵌入到非線性原對偶內(nèi)點法中。分枝定界法是一種求解混合整數(shù)規(guī)劃問題的有效方法，學者們對此進行了大量的研究。文獻［5］對分枝定界算法選擇規(guī)則進行了較為深入的研究，提出一種快速分枝定界算法。文獻［6］用常規(guī)的分枝定界法求解，計算量較大。文獻［7］采用簡化分枝定界法進行求解，計算量有所減少，但是不能保證獲得最優(yōu)解。文獻［8］將原對偶內(nèi)點法和分枝定界法結(jié)合起來求解最優(yōu)潮流問題，實現(xiàn)了精確求解嚴格最優(yōu)潮流問題，但是當離散量較多時，計算相當耗時。文獻［9］運用原對偶內(nèi)點法和分枝定界法解決電力系統(tǒng)無功優(yōu)化問題，找到了比傳統(tǒng)無功優(yōu)化更加合理的全局最優(yōu)解，針對大規(guī)模系統(tǒng)計算耗時，提出了簡化分枝定界算法。并行分枝定界算法在整數(shù)規(guī)劃問題中獲得了大量的運用［10-12］：文獻［10-11］深入研究了分枝定界并行策略，獲得了良好的并行效果；文獻［12］提出一種負荷平衡策略，獲得較好的并行性能。

本文采用分枝定界法求解混合整數(shù)優(yōu)化問題，采用原對偶內(nèi)點法求解整數(shù)規(guī)劃的松弛問題。由于完全分枝定界分枝數(shù)龐大，計算量大，本文提出一種并行分枝定界策略，采用主從機模式和異步通信策略，測試算例表明，該并行策略有效地提高了計算效率，各從機負荷平衡性好，獲得良好的加速比。

1 配網(wǎng)無功優(yōu)化數(shù)學模型

以系統(tǒng)有功損耗為目標函數(shù)，配電網(wǎng)絡無功優(yōu)化的非線性模型可表示成如下形式：

其中，f（x，u）為目標函數(shù)，表示配網(wǎng)有功損耗；h（x，u）=0表示配網(wǎng)潮流方程表示電壓上下限約束，x是連續(xù)變量，由節(jié)點電壓組成表示離散變量上下限約束，u表示離散變量，由可調(diào)變壓器變比和無功補償電容器投切組數(shù)構成?？梢?，這是一個混合整數(shù)規(guī)劃問題。

1.1 目標函數(shù)值

以網(wǎng)絡損耗最小為目標函數(shù)：

其中，Ploss（Q，T）表示電容器投切為 Q、變壓器分接頭檔位為T時的網(wǎng)絡損耗。

1.2 潮流方程約束

配網(wǎng)潮流方程約束采用電流不平衡形式：

其中，PDi、QDi為節(jié)點 i有功和無功負荷；Gij、Bij為對應節(jié)點導納；nB為節(jié)點數(shù)。

1.3 電壓上下限約束

電壓上下限約束表示為：

1.4 控制變量約束

其中，Qi、Ti為離散變量，mSVC為裝設電容器節(jié)點數(shù)；ltr為可調(diào)變壓器臺數(shù)。

2 原對偶內(nèi)點法求解非線性規(guī)劃問題

分枝定界法求解該混合整數(shù)規(guī)劃問題時，需要求解大量的連續(xù)變量非線性規(guī)劃問題，即不考慮離散變量約束的松弛問題，本文用原對偶內(nèi)點法求解該非線性規(guī)劃問題。原對偶內(nèi)點法是現(xiàn)代內(nèi)點算法中最好的算法，該方法魯棒性強，收斂迅速。原對偶內(nèi)點法求解非線性規(guī)劃問題可參考文獻［13］。

3 分枝定界法求解整數(shù)規(guī)劃問題

分枝定界算法的基本思想就是對于可行解為有限數(shù)的有約束條件的最優(yōu)化問題，把整個可行解空間反復地分割為越來越小的子集（稱為分枝），并且為每個子集的目標函數(shù)值計算一個下界（稱為定界）；在每次分枝后，凡是界限不優(yōu)于已知可行解集目標函數(shù)值的子集不再進一步分枝（稱為剪枝），這樣許多子集可不予考慮。分枝定界算法具有以下4個基本定則。

a.分枝定則。

分枝定則定義如何將問題劃分為子問題。一般選用二分法進行分枝，對未達到整數(shù)值的離散變量進行松馳，假如松馳子問題最優(yōu)解中某一離散變量Xr的值不是整數(shù)，則構造Xr≤Ir和Xr≥Ir+1這2個約束分別加入原松馳子問題中形成2個新的子問題，Ir是Xr的整數(shù)部分。

b.定界定則。

定界定則定義如何計算一個子問題最優(yōu)解的上下界。對已達到整數(shù)可行解的子問題最優(yōu)解，判斷其是否小于已知下界，若滿足條件則進行修改。

c.選擇定則。

選擇定則定義應選擇哪個子問題進行分枝。節(jié)點的選取方法就是考察一次分枝后，下一步應選擇哪個或哪些節(jié)點繼續(xù)進行分枝計算。主要有深度優(yōu)先搜索和廣度優(yōu)先搜索。

d.削除定則。

削除定則定義如何識別和消去不可能產(chǎn)生原始問題的最優(yōu)解的子問題，即識別和刪除其中不良分枝。子問題無可行解、找到整數(shù)要求的可行解或者其目標函數(shù)值大于已知上界，則進行剪枝操作。

分枝定界算法求解混合整數(shù)規(guī)劃問題基本步驟可概括如下［7］。

a.松馳原問題，即將離散變量連續(xù)化，并用原對偶內(nèi)點法求解該非線性連續(xù)規(guī)劃問題。若無解，則原問題無解；否則，置下界z為連續(xù)規(guī)劃問題的目標函數(shù)值，置上界z為一足夠大數(shù)。

b.若無可行解或解的目標函數(shù)值已超過z，轉(zhuǎn)至步驟g；否則繼續(xù)下一步。

c.若滿足整數(shù)條件，轉(zhuǎn)至步驟f；否則繼續(xù)下一步。

d.分枝并記錄分枝信息。選擇父問題的最優(yōu)解中某一非整數(shù)變量，構造Xr≤Ir和 Xr≥Ir+1這 2個新的約束，分別加入原松馳子問題中形成2個新的子問題。

e.選擇其中一個分枝，用原對偶內(nèi)點法求解，然后轉(zhuǎn)至步驟b。

f.保存目前的最優(yōu)解，并更新z。

g.若所有分枝都已檢索完畢，則停止計算，至此得到的最優(yōu)解就是原問題的最優(yōu)解。

h.沿分枝回溯到最近一個尚未檢索的分枝（后進先出），用原對偶內(nèi)點法求解，然后轉(zhuǎn)至步驟b。

由上可知，分枝定界算法在理論上可以找到最優(yōu)解。實際計算中，當變量較少時，可以獲得滿意的結(jié)果，但當系統(tǒng)較大，尤其是整型變量較多時，分枝數(shù)較多，決策樹龐大，需要占據(jù)較大內(nèi)存，計算相當耗時，算法流程圖如圖1所示。

圖1 分枝定界算法流程圖Fig．1 Flowchart of branch&bound algorithm

4 并行分枝定界策略

為了應對串行分枝定界占用內(nèi)存嚴重、計算耗時等問題，本文提出一種并行分枝定界策略，各工作機并行產(chǎn)生決策樹，并行對各自的子問題執(zhí)行分枝定界操作。分枝定界有多種并行策略，各并行策略與所使用的并行平臺有很大關聯(lián)。根據(jù)各機通信協(xié)議的不同可劃分為同步和異步并行算法；根據(jù)工作內(nèi)存數(shù)量的不同可劃分為中央存儲（共享內(nèi)存）、分布式內(nèi)存和混合存儲策略。共享內(nèi)存模式下，全部子問題保存在一個內(nèi)存下；分布式內(nèi)存下，各工作機保存各自的子問題并分別進行分枝定界搜索；混合存儲，各工作機有各自的內(nèi)存，同時有一個共享內(nèi)存，供所有工作機共享。

本文使用分布式并行機平臺、分布式內(nèi)存存儲策略。各并行機有各自的內(nèi)存，存儲各自的子問題并分別進行分枝定界搜索，各并行機采用異步通信模式。并行機控制采用主從模式，在并行機中選擇一臺作為主機，其余為工作從機。主機負責初始任務的產(chǎn)生和分配，協(xié)調(diào)從機工作進度，平衡各從機負荷，各工作從機對各自的子問題執(zhí)行分枝定界操作。分枝定界并行算法需要解決的問題主要有：初始問題產(chǎn)生和任務分配，各工作從機負荷動態(tài)平衡，最優(yōu)值上限交互，終止條件。

a.初始問題產(chǎn)生和任務分配。在算法執(zhí)行起始階段，只有一個子問題，因此，不可避免地存在一個并行起始階段；另一方面，產(chǎn)生一些子問題就立刻啟動并行未必是一個好策略，因為串行計算可能產(chǎn)生的最優(yōu)值上下界會消除一些節(jié)點，從而導致并行時某些子樹是無意義的計算。本文初始策略為：工作主機串行搜索根節(jié)點，直到產(chǎn)生K個子節(jié)點（子問題），K定義為工作從機的數(shù)量，然后把所得的K個子問題分配給各工作從機。

b.各工作從機負荷動態(tài)平衡。各工作從機負荷量一般以其子問題數(shù)量計量即可，工作從機負荷量發(fā)生變化都將其新的負荷量通知主機。主機負責任務的動態(tài)分配，平衡各工作從機負荷。當從機負荷量為零后，從機向主機請求分配任務，主機接到消息后，選擇任務數(shù)最多的一個從機，請求其給該空閑機發(fā)送任務（N個），若從機發(fā)送N個任務后自身負荷量低于某設定值La，將通知發(fā)送任務失敗。本文中，La、N均取為1。顯然，該負荷平衡策略下，各工作機為異步通信模式，工作機間的通信可能發(fā)生在任何時刻。

c.最優(yōu)值上下界交互。當某從機找到一個更好的最優(yōu)值上界，其將該值廣播給其他所有工作從機。

d.終止條件。在分布式內(nèi)存消息模式下，終止條件一般設定為從機工作內(nèi)存子問題都為空，并保證沒有消息在機群間傳送。

為了評價并行策略的有效性，提出如下并行分枝定界性能評價標準。

a.搜索樹懲罰因子：定義并行子問題數(shù)與串行子問題數(shù)之比為搜索樹懲罰因子Ps。

b.負荷平衡因子：各從機最小有效計算時間與最大有效計算時間之比為負荷平衡因子Lf。有效時間指的是進行分枝定界操作時間，不包括通信時間。

c.加速比：串行分枝定界計算時間與并行分枝定界計算時間之比為加速比S。

5 算例分析

5.1 測試算例

本文采用2個試驗系統(tǒng)作為算例，對算法進行分析和驗證，表1給出了2個測試算例的參數(shù)，其中，nL為系統(tǒng)線路數(shù)。試驗系統(tǒng)1為23節(jié)點系統(tǒng)，有12臺可調(diào)變壓器，可調(diào)檔位均為9檔，有10個節(jié)點裝設有可補償電容器，電容器組數(shù)均為5組；試驗系統(tǒng)2為25節(jié)點系統(tǒng)，有5臺可調(diào)變壓器，檔位均為5檔，5個節(jié)點裝有可投切電容器，電容器組數(shù)均為6組。

表1 測試算例參數(shù)Tab.1 Parameters of tests

5.2 測試結(jié)果

根據(jù)上面提出的并行分枝定界策略，在19核和33核下測試以上2個算例，分析其性能，同時運用串行分枝定界算法對以上2個算例進行測試，分析其運行性能。工作主機硬件為2×Intel Xeon E5520 CPU，6×1 GB DDR3 1333 MHz內(nèi)存，其他工作從機硬件為 2×Intel Xeon X5550 CPU，6×2 GB DDR3 1333 MHz內(nèi)存。并行環(huán)境在MATLAB2009b環(huán)境下測試。所得結(jié)果如表2所示，表中M是并行起始階段工作主機初始問題產(chǎn)生的個數(shù)；P是核的數(shù)目，包括1個工作主機和P-1個工作從機。運用串行分枝定界算法對這2個算例進行測試，分枝定界法用深度優(yōu)先搜索策略，測試結(jié)果如表3所示。

表2 并行分枝定界算法性能分析Tab.2 Performance analysis of parallel branch&bound algorithm

表3 串行分枝定界算法性能分析Tab.3 Performance analysis of series branch&bound algorithm

根據(jù)上面提出的并行分枝定界策略，并行起始階段，工作主機串行產(chǎn)生P-1個子問題，并分配給P-1個工作從機，此后工作從機對各自的問題并行計算。從表2可以看出，2個試驗系統(tǒng)的并行效果均較好，各從機負荷平衡性好，子問題數(shù)少于串行分枝定界算法問題數(shù)，獲得良好的加速比，加速比甚至大于并行機數(shù)目，這是因為與串行分枝定界法相比，并行分枝定界算法可能提前找到更好的最優(yōu)解從而避免了一些子問題的求解，由此減少計算時間，獲得良好的加速比。此外，從表2可以看出，各工作從機平衡因子接近1，負荷平衡性好，因此，本文提出的負荷平衡策略是有效的。為了分析核的數(shù)量對該并行策略的影響，對25節(jié)點系統(tǒng)分別在3核、7核、13核、19核、25核和33核下進行測試。圖2和圖3分別描述加速比和負荷平衡因子隨核的數(shù)量變化折線。從圖2可以看出，該并行分枝定界算法幾乎可獲得超線性加速比，核的利用數(shù)量達33。異步通信模式下的并行算法，各工作從機負荷動態(tài)平衡是一個很重要的問題，從圖3可看出，該并行分枝定界策略能適應不同核的數(shù)量，負荷平衡因子隨核的數(shù)量增加有減少趨勢，其值不低于0.955，負荷平衡性良好。

圖2 加速比S變化折線Fig.2 Broken line graph of speedup ratio S

圖3 負荷平衡因子Lf變化折線Fig.3 Broken line graph of load balancing factor Lf

6 結(jié)論

無功優(yōu)化是一類非線性混合整數(shù)規(guī)劃問題，對于離散變量的處理一直是該問題的難點。本文提出一種并行分枝定界算法，各工作從機并行產(chǎn)生決策樹，分別進行分枝定界操作，主機負責初始任務產(chǎn)生和分配、各工作從機任務動態(tài)分配和負荷平衡等。測試結(jié)果表明，該并行分枝定界策略運行效果良好，搜索樹懲罰因子低，負荷平衡因子接近1，獲得良好的加速比。本文算法有如下特色：

a.本文中各并行機通信采用異步通信模式，各從機通信可能發(fā)生在任何時間，與同步通信模式相比，可有效地降低等待時間；

b.本文并行策略中分配一臺計算機為主機，負責初始任務分配和負荷動態(tài)平衡，測試算例表明，本文提出的分枝定界算法負荷平衡性好，可獲得良好的加速比；

c.與串行分枝定界算法相比，本文提出的并行分枝定界策略產(chǎn)生的子問題數(shù)有所減少，甚至可獲得超線性加速比，這是因為并行分枝定界算法可能提前找到一個更好的最優(yōu)解從而避免一些子問題的計算；

d.本文提出的分枝定界并行策略采用異步通信模式，異步通信模式下的并行算法需要解決各并行機負荷平衡問題，測試算例表明，本文提出的并行分枝定界策略負荷平衡性良好，能適應不同數(shù)量的并行機。