基于半定規劃的多約束圖劃分問題

王曉瑜,劉紅衛,王 婷,丁玉婉,游海龍

(1.西安電子科技大學 數學與統計學院,西安 710126; 2.西安電子科技大學 微電子學院,西安 710071)

超大規模集成電路(VLSI)設計[1]、電信[2]和并行運算[3]等問題在數學建模時通常被抽象為圖的形式,圖分割是其基本算法之一.但隨著數據規模的不斷增長,圖劃分問題變得更具有多面性和挑戰性.該問題旨在將圖G=(V,E)的頂點在一定容量或基數的約束下劃分為幾個組,使得所求最優解的割邊總權重最小.由于該問題是NP-完備的,因此研究尋找近似解的方法有一定的意義.

圖劃分問題源于針對圖的k劃分問題設計的一個二次程序.隨著新的圖劃分問題的不斷發展,多種求解方法也應時而生,例如: Kernighan等[4]考慮將圖劃分為給定大小的子集,并設計了一種啟發式方法進行求解; Christofides等[5]對圖的二分問題提出了樹搜索方法,有效地限制了子集中節點的數目; Labbé等[6]針對團劃分問題,利用分支定界算法將圖劃分為有上下界的子集.

通過將圖劃分問題重新表述為一個非凸二次規劃問題,人們提出了一些有效的近似算法.Goemans等[7]對非負加權圖提出了基于半定松弛的舍入算法,該算法對k=2可實現0.878的近似界; Frieze等[8]針對圖的多分問題擴展了文獻[7]的舍入算法,并分析了所設計算法在不同劃分塊下的理論近似比.在近似算法的基礎上,分支定界法也被設計用于求解圖劃分問題.Rendl等[9]利用基于半定松弛的分支定界算法Biq Mac求解了經典的最大割問題; Delling等[10]根據分支定界框架提出了求解最小圖二分的精確組合算法,其下界是通過啟發式方法得到的; Lu等[11]提出了一種新的分支定界算法,直接選擇一個合適的向量生成k個子問題,設計了減少枚舉過程中子問題冗余性的策略.

背包問題作為組合優化問題的基本問題之一,已在多學科領域得到廣泛研究.本文主要關注具有背包約束的圖劃分(GPKC)問題,圖中的每個頂點都被賦予一個權值,每個劃分集合都需滿足背包約束.Recalde等[12]將背包問題轉化為整數規劃問題,并設計了一種基于分支定界的精確算法來求解該問題.Nguyen[13]針對GPKC問題提出了一個嚴格的LP松弛方法,并利用啟發式方法建立解的上界.由于基于半定規劃在生成具有背包約束[14]和k-均分問題的二次問題緊下界方面性能較好,因此研究者們將半定規劃松弛應用于GPKC問題中.Wiegele等[15]通過引入帶有非負約束的緊的半定松弛,得到了多達500個頂點的GPKC問題的高質量下界,同時,所設計的啟發式算法相比于文獻[13]可得到一個更嚴格的上界,但該算法尚未考慮在給定劃分塊數的情形下是否能滿足劃分結果.

對于大規模劃分的實際應用,也可考慮將啟發式和元啟發式方法用于尋找足夠好的次優解.Arriz等[16]將模擬退火和禁忌搜索方法相結合求解圖二分問題,其算法可花費較小的計算代價而得到高質量的解.Benlic等[17]基于多級劃分和禁忌搜索提出了一種混合算法,把禁忌搜索作為多級框架的細化算法,用于解決圖的平衡劃分問題,其算法性能優于圖劃分軟件Metis和Chaco.

基于此,本文考慮帶有頂點權重約束的圖的二劃分問題,利用圖的二劃分方法遞歸地進行圖的多分,并將所設計的算法與Wiegele等[15]提出的圖的多分算法進行比較,驗證該算法的有效性.

1 圖的二劃分

1.1 模型的建立

給定一個賦權無向圖G=(V,E),其中V={1,2,…,n}為點集,n為圖G中的頂點個數,E為邊集,W為圖G的鄰接矩陣,ωij為對應邊[i,j]∈E的權值,則?i≠j,有ωij=ωji,且ωii=0.記bi為頂點i的非負權重,U為劃分集合容量上限.GPKC問題要求將圖的頂點V劃分為兩部分,即S和VS,使得在不同集合中的頂點滿足切邊總權重最小,且每組的頂點權重和不超過容量上限U,則目標函數可寫為

(1)

令xi表示頂點i,若頂點i屬于集合S,則xi取值為1,反之,xi取值為-1.于是未考慮頂點權重約束的圖二劃分問題可寫為如下二次函數形式:

(2)

引入與W相關的Laplace矩陣L=diag(We)-W,其中e∈n是一個分量全為1的列向量,diag(We)是一個對角矩陣,其對角項為向量We中的元素.于是圖二劃分模型(2)等價于如下二次整數規劃形式(IQP):

令B表示頂點的權重向量,則第i個頂點的權重為bi,U=(u1,u2)T表示劃分集合的資源上限,ur(r∈{1,2})表示第r塊劃分集合的上限,則求解模型(GPKC)為

xTLx=tr(xTLx)=tr(LxxT)=tr(LX),

(3)

因此利用文獻[18]中矩陣跡運算的性質,可將問題(GPKC)重寫為

(4)

其中矩陣

(5)

是半正定的秩1矩陣,且對角線元素均為1.

上述半定規劃松弛模型(GPKC1)求解較復雜,但在不考慮頂點權重約束的情形下,原問題可行,半定規劃及其對應的對偶模型是嚴格可行的,且易找到其嚴格可行點,因此本文考慮使用內點法求解去掉頂點權重約束的更松弛的半定規劃,再對求得的解進行隨機擾動,并在隨機擾動過程中增加對解的可行性判定,以保證所得解滿足頂點權重約束.

去掉頂點權重約束的半定規劃松弛模型(SDP)為

其對應的對偶形式(DSDP)為

本文采用內點法[19]求解模型(SDP)和(DSDP),起始點Y∶=In×n,y∶=μe,Z∶=μI-C/4是可行的且在內部,其中μ是使得Z為正定矩陣的常數.

1.2 超平面舍入算法

計算最小化問題的上界通常利用啟發式方法確定原問題的可行解.對于求得的模型(SDP)的最優解,主要利用Goemans等[7]對最大割問題提出的算法以及Frieze等[8]提出的改進的隨機舍入算法,設計圖二分的超平面舍入算法以得到問題(GPKC)的近似最優解,即圖二分的初始劃分.下面給出完整的圖二分超平面舍入算法.

算法1圖二分的超平面舍入算法.

輸入: 模型(SDP)的最優解Y,目標矩陣C,頂點權重向量B,資源上限U,抽樣次數p;

初始化:x=[ ],f=[ ];

步驟1) 對Y做Cholesky分解DTD=Y得到D;

步驟2) fort=1,2,…,p

步驟3) 取單位球面Sn上服從均勻分布的單位向量st;

步驟5) end

步驟6) 取min(f)對應的x賦值于y,并令err=max{(y+e)TB-2u1,0}+max{(e-y)TB-2u2,0};

步驟7) if ? err=0

步驟8) 輸出對應的y;

步驟9) else

步驟11) 令err=max{(x+e)TB-2u1,0}+max{(e-x)TB-2u2,0};

步驟12) if ?err1=0

步驟13) 若?err=0,則輸出min(f)和min(f1)對應的[x,y1];

步驟14) else

步驟15) 若?err=0,輸出min(f)對應的x; 反之,對x做一鄰域調整得x1,計算相應的f和err值;

步驟16) 若?err=0,輸出min(f)對應的x1; 反之,輸出調整后min(f)和min(err)值對應的[x1,y1];

步驟17) end

步驟18) end

輸出: 目標值最優的劃分.

算法1中步驟10)的鄰域調整是指: 令P1={i|y(i)=1},P2={i|y(i)=-1},將P1中單點逐次移動到P2,再將P2中單點逐次移動到P1,得到相應的y1.

1.3 均衡因子

在對問題(2)中目標函數值進行極小化時,由于在實際問題中常將ωij視為非負數,因此當xi和xj均為1或均為-1,即頂點全劃分在同一個集合時,可得最小目標值0,與本文劃分思想不符.為避免上述情形發生,同時減少劃分導致的資源浪費,本文考慮在目標函數中添加一個均衡因子,用于控制劃分結果的均衡性.用頂點權重向量B除以頂點權重的最大值,得列向量β,進一步可得矩陣A=ββT,此時由模型(SDP)可得新的目標矩陣C=C+aA,其中a是均衡因子,本文令a=300.

1.4 二分圖的啟發式算法

二分圖啟發式算法可用于提高各種組合問題的解決方案質量[20].在利用超平面舍入算法得到初始劃分后,本文用該方法進一步改進劃分的質量,下面給出改進的二分圖啟發式算法.給定劃分結果(P1,P2),在滿足容量限制的條件下,尋找使目標函數值更小的劃分結果.

算法2圖劃分問題的啟發式算法.

輸入: 劃分組合(P1,P2),目標值f*,目標矩陣C,劃分矩陣R,停止誤差ε;

初始化:δ=0;

步驟3) whileΔcost>ε

步驟4)P1←P1-{s}+{t},P2←P2-{t}+{s};

步驟7) end

步驟8) fort=1∶length(Pi),其中i∈{1,2},j∈{1,2}i

步驟9)r←Pi(t),令Pi←Pi-{r},Pj←Pj+{r};

步驟10)H=CR,δ1=C(r,r)-H(r,i)+H(r,j);

步驟11) ifδ1<δ

步驟13) end

步驟14) end

2 圖的多分問題

圖的多分問題是將圖的頂點集劃分為多個集合,使得各劃分集合在頂點權重不超過資源上限的情形下,連接不同子集的邊的總權值最小化.由于所建模型有多個約束條件,而內點算法又因內存問題無法求解大規模實例,因此針對圖的多分問題,本文利用改進的圖二分算法設計遞歸二分的圖多分算法.

在圖二劃分不可行的情形下,需額外增加資源滿足圖二分的可行性.為避免后續劃分時因資源不足而導致劃分結果不可行的情況,本文引進縮小資源的參數m,利用增加資源后新資源的m倍進行劃分,令m=0.7.從而在保證二分可行的同時,避免出現資源不足的情況.下面給出增加資源的全過程.

算法3資源變更算法.

輸入: 前兩塊資源二分的結果x*,資源上限U,剩余的資源塊φ,縮小資源參數m;

步驟1) 判斷x*的可行性,即頂點權重是否滿足資源約束,將不可行的塊記入ψ;

步驟2) whileψ非空

步驟3) whileφ非空&ψ非空

步驟4)uψ(1)=m[uψ(1)+uφ(1)],φ(1)=[ ],ψ(1)=[ ];

步驟5) end

步驟8) end

步驟9) 當資源增加使得二分可行時,將增加資源后的大塊及其對應的頂點按相應的初始資源大小繼續二分,直至得到最后的劃分結果P;

輸出: 劃分結果P.

算法4遞歸二劃分求解圖多分問題.

步驟1) 建立模型(GPKC),利用內點法求解半定規劃松弛模型(SDP),對模型(SDP)最優解Y用超平面舍入算法(算法1)得到圖二分的初始劃分;

步驟2) 若二分不可行,則轉步驟3);

步驟3) 利用算法3對不可行的劃分集合增加劃分資源,直至二分可行,再將增加資源后的二劃分集合繼續進行二分,最后得到圖的k劃分結果;

步驟4) 利用圖的啟發式算法(算法2)對圖的k劃分中每兩個劃分集合的頂點進行調整,以得到使目標函數值更小的劃分;

步驟5) 合并未充分利用資源的集合.

3 數值模擬

下面用MATLAB R2021b實現本文算法,數據來源于文獻[15]中部分隨機生成圖數據以及文獻[13]中生成的大規模數據,其中(GPKCrand20),(GPKCrand50),(GPKCrand80)分別表示鄰接矩陣中非零邊權值占比20%,50%,80%的圖.將利用遞歸二劃分算法求得的最小切邊權值與文獻[15]中對GPKC問題DNN松弛模型所設計的Vc+2opt算法求得的切邊權值進行比較,并用gap表示兩者切邊權值之間的差距,其中gap=(遞歸二劃分算法所得目標函數值-(Vc+2opt算法所得目標函數值))/(Vc+2opt算法所得目標函數值).為保證實驗結果的合理性,本文對每個測試樣例均進行10次實驗,取實驗最好結果及平均的CPU時間,結果列于表1.

表1 遞歸二劃分算法與Vc+2opt算法的實驗結果

表1給出了遞歸二劃分算法和Vc+2opt算法對500和1 173個頂點的劃分結果以及各算法所花費的CPU時間.由表1可見: 遞歸二劃分算法隨著容量上限的減少,劃分所需時間逐漸增加; 由于本文提出的遞歸二劃分算法是在考慮去掉頂點權重約束的情形下求解半定規劃松弛模型,大幅度減小了求解模型的次數,且計算過程中迭代次數較少,從而在較短的時間內可得到遞歸二劃分算法的較優解.此外,由兩種算法所得函數值的差距gap可知: 當gap為正,即遞歸二劃分算法所得目標函數值比Vc+2opt算法所得函數值大時,遞歸二劃分算法可在較短時間內得到與Vc+2opt算法函數值差距最大為1.19%的較優目標函數值; 當gap為負時,表示遞歸二劃分算法的函數值優于Vc+2opt算法所得目標函數值,且兩者所得目標函數值差距最多為5.87%.

綜上所述,本文針對帶有頂點權重約束的圖多分問題,設計了遞歸的二劃分算法.首先,考慮用內點法求解不加頂點權重約束的半定規劃松弛模型; 其次,通過隨機擾動得到滿足頂點權重約束的可行解; 最后,利用啟發式算法,對可行解進行局部改進得到更緊的上界.同時加入均衡因子以避免半定規劃目標值為0以及因劃分不均衡導致的資源浪費,并設計了求解后的劃分合并算法.實驗結果表明,本文提出的遞歸二劃分算法可高效地求解帶約束的圖多分問題,得到了較優的劃分結果.