一種求解度約束最小生成樹問題的混合整數線性規劃方法?

李中興 盧 操 梁海鎮

（華南理工大學電力學院 廣州 510640）

1 引言

最小生成樹問題在組合優化中是一個比較經典的問題，在拓撲設計和最短路連接等方面有廣泛的應用。在工程實際應用中，生成樹頂點的度往往需要滿足某些約束條件。這種頂點帶有度約束的最小生成樹問題稱為度約束最小生成樹問題。

度約束最小生成樹（Degree-constrained Minimum Spanning Tree，DCMST）問題的最早由Narula［1］提出，是組合優化中一個有比較重要意義和應用價值的問題［2］。目前已在通信網絡、電力線網絡、計算機網絡以及大規模集成電路得到廣泛應用［3］。

一直以來，不少學者對度約束問題進行研究。主要用貪婪啟發式算法［4~5］和智能算法［6~7，12~13］求解。文獻［4］在不違反度約束的前提下，提出一種由貪心算法思想而來的啟發式近似算法，通過找距離當前生成樹最近的頂點加入當前生成樹，直到遍歷所有節點。但近似算法并不能得到唯一解。文獻［5］提出分支限界算法，通過求解最小生成樹的方法得到初始生成樹，再通過斷開超過度約束的最大邊，按照一定規則在某些節點連接邊。該方法為一類精確的啟發式算法，但復雜度高。

文獻［6］通過蟻群算法求解度約束最小生成樹問題，如果求解過程時沒有充分考慮度約束的限制條件，經常會得不到可行解。日本學者ZHOU 和GEN 利用Prufer 編碼方式對生成樹進行編碼［7］，并采用遺傳算法求解度約束最小生成樹，該研究是該問題下的一個重要突破，但編碼方式容易導致不可行解產生，求解時間長，結果為局部最優解。

目前鮮有文獻用線性化的思想去求解DCMST問題。文獻［8］在已有的電力網絡中，提出一種線性求解電力系統可靠性的方法，該思想對求解度約束最小生成樹問題提供了很好的思路。

鑒于此，區別于傳統DCMST 問題的求解方法，提出一種包含二進制變量與整型變量的混合整數線 性 規 劃（Mixed-integer Linear Programming，MILP）模型，并對不同節點系統進行比較深入的研究。

2 度約束最小生成樹問題描述

2.1 生成樹描述

對于G=（V，E）的無向連通圖，V=｛v1，v2，…vn｝是節點的集合，n 為節點總數。E=｛e1，e2，…，enp｝是網絡G 的邊集合，np 為邊的總數。滿足np=n-1，沒有孤立節點時網絡連通圖為一棵生成樹。如圖1 所示，7節點系統有6條邊，沒有孤立節點。

對于含有n 個節點的生成樹，生成樹的總個數有T=nn-2種［11］，n=10 時已經有108種不同的連接方式，最小生成樹問題（Minimum Spanning Tree，MST）求解就是在T 中尋找一棵樹，使得對應邊的權重wij之和有最小值，目前常用prim［2］算法和kruskal［14］算法求解。

2.2 度約束最小生成樹的一般數學模型

度約束最小生成樹為在生成樹的基礎上，對于指定的節點vi，令與vi節點所連接的邊的數量為k，即d（vi）=k，則稱此時的網絡G 為關于節點vi的k 度生成樹，含度約束最小生成樹即在所有vi的k 度生成樹中找到一顆使得邊的權重wij之和為最小的生成樹，那么，DCMST的數學模型可以用下式描述［3］：

式中，wij=wji，wii=+∞（i，j=1，2，3，…，n）。|S|為集合S中所含圖G 的節點數。約束（2a）為節點度約束，約束（2b）和約束（2c）保證所得為一棵生成樹。

3 求解度約束最小生成樹問題的線性模型

3.1 相關知識

3.1.1 鄰接矩陣

1）鄰接矩陣A

鄰接矩陣是表示頂點之間連接關系的矩陣。對于n 節點的無向連通圖，其網絡的鄰接矩陣是一個對稱的n 階方陣An×n：記aij為鄰接矩陣A 的元素（即節點i與節點j的連接關系），則aij=aji=1，aii=0，如式（3）所示。由于鄰接矩陣為一個對稱矩陣，一般而言，僅需要存儲上三角元素或者下三角元素的數據即可。本文選取上三角矩陣作為數據分析，則上三角總元素個數為n（n-1）/2個，如式（4）所示。

2）上三角存儲矩陣Z

對鄰接矩陣A 的上三角矩陣按照從左到右，從上到下排列，得到一個上三角存儲矩陣Z1×K。以5階鄰接矩陣為例，上三角元素如圖2 所示，則產生的Z 矩陣為式（5）。同理對應的上三角權值存儲矩陣W1×K，如式（6）所示。

圖2 鄰接矩陣上三角元素說明

3.1.2 關聯矩陣B

生成樹連通圖G 有n個節點，K 條可選支路，當給每條支路規定了正方向后，則<節點—支路>的關聯矩陣Bn×K的元素bik的元素定義為下式［9］，按照關聯矩陣的定義，第k列元素總和為0。

由3.1.1 節可知，鄰接矩陣中每一個元素aij都能生成一條邊，每一條邊都有對應的上三角存儲矩陣Z1×K矩陣元素zk。則對于矩陣元素zk，k 與i，j的關系一一對應，如式（8）所示。

在本研究中，規定當i的發點為i，收點為j，與其一一對應的上三角存儲矩陣元素為zk，對應編號k，則關聯矩陣B 第k 列元素確定為下式。

3.2 度約束最小生成樹問題線性化

3.2.1 度約束的線性化

節點度約束可以表示為某些節點出線度不超過某個最大值，或者不低于某個最小值。為了更好地描述這個約束，可以從鄰接矩陣的上三角矩陣進行分析。還是以5階方陣作為例子，如圖3所示。

圖3 節點3的待選邊在鄰接矩陣的位置

以節點3的出線度為例，對于節點3，其在鄰接矩陣中的相關元素為｛a13，a23，a34，a35｝，由于上三角總元素數量為5*4/2=10 個。k 的計數方式從左往右，從上到下，則節點3 相關元素序號集為V3=｛2，5，8，9｝。

拓展到其他節點m，對于n 節點的無向連接圖，當n 確定，Vm的序列也確定，Vm（m=1，2，3，4，5）序列下式所示：

Vm序列可以事先求出，故能快速求解度約束問題。度約束的約束方程如式（11）。

其中zk為上三角存儲矩陣元素，Vm為節點m 的元素序號集。

為了方便后續的求解，本文將zk拆分為σk，σˉk，后兩個變量為支路k 的正向潮流標志和反向潮流標志，為0-1變量，關系式滿足：

由于zk為0-1 變量，則σk，不能同時為1，即支路k 只能允許出現正向潮流或者反向潮流。經過轉換，度約束的方程可以替換為式（13）：

3.2.2 避免環產生的線性約束

傳統方法中避免環路的約束，如式（2b）所示，一般避免環的產生約束條件為任意節點（2 個及以上）的連接線路滿足一棵生成樹。線性模型中采用直流潮流中功率平衡的方法去避免環路問題。基本思路如下。

隨機挑選一個節點作為電源節點，設置其輸出功率為n-1 個單位功率（p.u.），其他n-1 個節點的負荷都為1 個單位功率。則對于每個節點，都需要滿足節點的功率平衡方程。

1）對于負荷節點的功率平衡約束方程

約束（14）為節點i 的功率平衡約束方程。其中，gk為支路k 的正向功率，為支路k 的反向功率，兩者都大于0 的整數。Di為節點i 的功率值，本文假定都取1 個單位功率。Bik為關聯矩陣元素，L為負荷節點。

約束（15）為支路k的流過的最大功率值。

約束（16），約束（17）為保證同一條線路只出現正向潮流或者反向潮流，M為一個很大的整數。

約束（18）為總出線度約束，保證生成的網絡為一棵生成樹。

2）電源節點功率平衡約束方程

式中，Gi為電源節點i的功率值，本文假定電源節點取n-1 個單位功率，T 為電源節點。其他相關約束參考負荷節點的約束。

3）線性約束圖例

線性約束方法的思想為當有部分節點產生環路時，該部分節點的負荷得不到供應，即不滿足約束條件。

如上圖所示，當節點2 為電源節點時，圖4（a）每一個節點的負荷都得到供應，而圖4（b）因為出現了環，每個節點的功率平衡方程都不滿足，這種網絡滿足不了約束（14）和約束（20），從而解決了避免出現環的問題。

圖4 產生環路情況示意圖

3.3 混合整數線性模型

1）最小生成樹的線性模型

綜上所述，不考慮度約束下的整數規劃模型滿足下式

式中，Wk為第k條支路的邊長。

2）度約束最小生成樹線性模型

增加約束（13），MST 線性模型變為DCMST 線性模型。

對比式（22）與式（24），DCMST 模型比MST 模型僅增加了約束式（13），說明該線性模型對求解生成樹問題具有通用性。

3.4 模型求解

研究的線性模型基于CPLEX平臺，調用yamilp求解器求解。CPLEX 是一個解決線性規劃問題，二次規劃問題以及混合整數規劃問題的求解器平臺，可以處理成千上萬的變量及約束問題。對一定節點規模的DCMST問題有很好的求解效率。

4 算例分析

4.1 數值試驗1［6］

連通圖G 的節點個數n=8 個，度約束b=［1，3，3，1，1，3，1，3］，對應的權值矩陣如下：

求解結果如表1。

表1 數值試驗1的求解結果

DCMST 問題的求解的最優值為169，與現在公布的最優解相同。此外，由于線性模型只有唯一解，可證明，該解為當前實例的最優解。

4.2 數值試驗2［4］

連通圖G 的節點個數n=9，度約束b=［2，2，2，2，2，2，2，1，1］，對應的權值矩陣如下。

求解結果如表2。

表2 數值試驗2的求解結果

度約束的求解的最優值為40，與現在公布的最優解相同。同樣可證明，該解為當前實例的最優解。

4.3 旅行商問題

旅行商問題，即TSP 問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n 個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。

該問題的約束條件需要將式（13）和式（18）作一定修改得到，式（13）修改為每個節點的出線度都等于2，式（18）修改為系統總出線度等于n，如下所示。

采用旅行商問題eil51［10］中的數據進行實例仿真，仿真結果如表3。

表3 eil51系統仿真結果

目前公布的最優數值426，是基于對城市間距離四舍五入取整得到的，本文將從進行取整和不進行取整求解出最優的規劃結果。如表3所示。

標粗黑體的部分為兩者不同的部分，兩者具體連接圖5、6所示。

圖5 進行取整后的最優連接圖

圖6 不進行取整后的最優連接圖

同樣可以證明，對城市距離四舍五入取整后的最優解為426，不進行取整的最優解為428.87。

5 結語

本文提出了一種求解度約束最小生成樹問題的混合整數線性規劃模型，模型適合MST 問題、DCMST問題、TSP問題以及其他有約束的生成樹距離問題，具有一定的通用性。