帶有頂點權重約束的圖劃分問題研究*

丁玉婉，劉紅衛(wèi)，王 婷，王曉瑜，游海龍

（西安電子科技大學）

0 引言

圖劃分問題是經(jīng)典的組合優(yōu)化問題，其目標是將一個具有邊權值的圖的頂點按照約束條件分成k個不相交的子集，同時最小化集合間的互連邊權之和，該問題被廣泛應用于并行計算處理［1］，圖像處理［2］，超大規(guī)模集成電路設計［3］，移動無線通信［4］等眾多領域.

自20世紀60年代以來，國內外學者不斷對圖劃分問題進行研究，提出了許多性能較好的圖劃分算法.文獻［5］提出了一種譜方法用于求解圖的二劃分問題，其基本思想是利用圖矩陣的第二大特征值和特征向量來實現(xiàn)圖劃分.文獻［6］提出了一類KL算法，這是一種典型的啟發(fā)式算法，該算法先將圖隨機二分，再高效地選擇收益最高的點進行交換.文獻［7］在KL 算法的基礎上進行改進提出了FM 算法，該算法采用單點移動策略且引入了桶列表數(shù)據(jù)結構，降低了算法的時間復雜度.智能優(yōu)化算法，如遺傳算法［8］、禁忌搜索算法［9］等，也被用于求解圖劃分問題.一些學者還用整數(shù)規(guī)劃的方法來求解圖劃分問題，文獻［10］描述了連通圖上的整數(shù)規(guī)劃公式.文獻［11］提出了一種使用分支定界框架來求解最小圖二劃分的精確組合算法.文獻［12］給出了多約束圖劃分問題的兩個整數(shù)規(guī)劃公式，并提出了一種基于分支定界和切平面的精確算法.

半定規(guī)劃是凸優(yōu)化中一個相對較新的子領域，由于它在運籌學和組合優(yōu)化問題中有非常成功的應用，因此許多學者利用半定規(guī)劃松弛來求解圖劃分問題.文獻［13］引入了幾個組合優(yōu)化問題的半定規(guī)劃松弛，包括圖劃分和最大割問題.文獻［14］提出了一般圖劃分問題的一種新的半定規(guī)劃松弛方法.文獻［15］介紹了一種基于分支定界法求解圖劃分問題的精確算法，且一系列數(shù)值實驗表明，半定規(guī)劃方法通常會導致更緊的下界.文獻［16］用一種基于半定規(guī)劃松弛的分支定界法來計算圖劃分問題的全局最優(yōu)解.文獻［17］基于矩陣的提升推導出了一種新的用于圖劃分的半定規(guī)劃松弛，并從理論和數(shù)值兩方面與其他半定規(guī)劃松弛進行了比較.

近年來一些學者對帶有頂點權重約束的圖劃分問題展開了研究，其中最著名的是背包約束下的圖劃分問題（GPKC）.文獻［18］結合嚴格的線性規(guī)劃松弛方法和啟發(fā)式方法建立了GPKC問題的上界.文獻［19］將GPKC 問題的0，1整數(shù)模型轉化為半定規(guī)劃松弛模型，并利用擴展的乘子交替方向法（eADMM）來求解該模型，并利用啟發(fā)式算法得到了GPKC 問題的較好的下界.注意到文獻［19］中提到，對于大規(guī)模實例，內點法并不適用于求解其半定規(guī)劃松弛模型，并在數(shù)值實驗部分進一步說明了內點法求解器Mosek［20］由于內存需求不足而無法求解頂點數(shù)超過300的大規(guī)模實例.

由于內點法是求解半定規(guī)劃最經(jīng)典有效的算法，因此，基于文獻［19］的思想考慮使用改良的內點算法求解半定規(guī)劃松弛問題，以進一步優(yōu)化圖劃分求解算法.由于圖的k劃分問題能通過遞歸的二劃分進行求解，而該策略的性能主要取決于二劃分算法的選擇，因此該文主要對k ＝2時的圖劃分問題展開深入研究，并進一步研究了帶有頂點權重約束的圖劃分問題.受文獻［19］的啟發(fā)，該文首先基于矩陣的提升將原問題的－1，1整數(shù)規(guī)劃模型轉化為一個新的半定規(guī)劃松弛模型，并使用改進的半定規(guī)劃內點法進行模型求解，其中給出了具體的初始點選取策略和步長選取策略.隨后利用改進的隨機超平面舍入算法和文獻［19］中提出的2opt啟發(fā)式算法得到原問題的近似最優(yōu)解.數(shù)值實驗表明的算法可有效求解帶有頂點權重約束的圖劃分問題，且提出的改進的內點法對于大規(guī)模實例依然是可行的，且在稀疏圖上表現(xiàn)出了良好的性能.

1 圖劃分問題描述

給定一個無向圖G ＝（V，E），V 代表頂點集合，E代表邊的集合，wij≥0為連接頂點vi，vj邊的權重，其中wij＝0表示頂點vi，vj無邊連接.圖劃分的目標即找到一個頂點子集S，使得連接兩個子集S和V＼S的割邊權重最小，即

引入分割向量x ∈｛－1，1｝N，若頂點vi∈S，則記xi＝1，否則，記xi＝－ 1.令W ＝［wij］，則

其中，Diag（x）表示以x ∈RN為對角元，其余元素為0的矩陣，Diag（X）表示以矩陣X ∈RN×N的對角元為元素的向量.令L ＝Diag（We）－W表示Laplacian矩陣，則問題（P）等價于如下的整數(shù)規(guī)劃模型：

該文中，在已有的圖模型基礎上增加頂點權重約束，即在劃分集合S和V＼S中，頂點vi的第j維權重和小于等于給定的上限.若每個頂點有m維權重，令第i個頂點vi的權重為［vi1，vi2，…，vim］則N個頂點的權重矩陣為Z ＝［z1，z2，…，zm］N×m，其中zj＝［v1j，v2j，…，vNj］T，j ＝1，2，…m，因此集合S中的頂點約束可表示為：

其中，U1＝［u11，u12，…，u1m］，u1j表示第j維頂點權重的上限，由此可推出：

同理，集合V＼S中的頂點約束可表示為：

其中，U2＝［u21，u22，…，u2m］，u2j表示第j維頂點權重的上限，由此可推出：

令M ＝（xT，1）T，X ＝MMT，n ＝N ＋1，因此帶有頂點權重約束的圖劃分模型為：

2 改進的半定規(guī)劃內點法

該節(jié)中，對求解半定規(guī)劃的原對偶內點法進行改進，給出了具體的初始點選取策略和步長更新策略.

令Sn 表示n × n 對稱的向量空間，假設A：Mn →Rn，B：Mn →R2m為兩個線性算子，且C ∈Sn，b ∈Rn，s ∈R2m，因此，第1節(jié)中帶有頂點權重約束的圖劃分模型（SDP1）可被抽象為如下的優(yōu)化問題：

利用拉格朗日方法易得到（SDP）的對偶問題為：

引入（DSDP）的對偶障礙問題為：

其中，μ ＞0為障礙參數(shù).此障礙問題的拉格朗日函數(shù)為：

因此，（5）的一階最優(yōu)性條件為：

由log detZ和log ti的嚴格凹凸性可知，系統(tǒng)（6）存在唯一解（Xμ，yμ，tμ，Zμ）.此單參數(shù)族｛（Xμ，yμ，tμ，Zμ）：0 ≤μ ≤∞｝被稱為中心路徑.

2.1 初始點的選取

選取一個初始點（X，y，t，Z），原對偶內點法要求初始點滿足X ＞0，Z ＞0，t ＞0 以及s－B（X）＞0.令

其中I ∈Rn×n為單位陣.若ρ ＞1.1，令X ＝I；否則，令X ＝0.5ρI，則此時X滿足原問題的嚴格可行性，即s－B（X）＞0，X ＞0.令初始點t ＝（s－B（X））－1即滿足t ＞0.在選定初始點Z ＞0時，保持其一階最優(yōu)性條件（6）成立，則有

通過上述方式找到了一個滿足條件的初始點（X，y，t，Z），并由式（8）估計當前的μ 值［21］：

其中對偶間隙為gap ＝Tr（ZX）＋tT（s－B（X））.

2.2 搜索方向的推導

初始點選定后，接下來找搜索方向（ΔX，Δy，Δt，ΔZ），使得下一個迭代點（X ＋ΔX，y ＋Δy，t ＋Δt，Z ＋ΔZ）位于μ的中心路徑上.為簡化表示，將系統(tǒng)（6）重寫為：

因此Fμ（ψ）＝0的解ψ*滿足一階最優(yōu)性條件且是障礙問題的最優(yōu)解.為找到指向ψ*的一個方向Δψ ＝（ΔX，Δy，Δt，ΔZ），使用牛頓方向法，則

因此，方向Δψ 滿足：

求解該系統(tǒng)可得到方向（ΔX，Δy，Δt，ΔZ）.

在選定初始點Z ＞0 時，一階最優(yōu)性條件（6）成立，且由（10）（i）易得對稱矩陣

然后將其代入到（10）（iv）中得到：

將（12）分別代入到（10）（ii）和（10）（iii）得到對稱正定線性方程組：

2.3 選取步長的策略

在確定搜索方向之后，利用線搜索來尋找合適的步長α，關于步長α 的選取，主要基于以下考慮：

A1 步長α 要使對偶間隙gap（α）不斷減小.

A2 步長α要滿足X ＋αΔX ＞0，Z ＋αΔZ＞0，t ＋αΔt ＞0，以及s－B（X ＋αΔX）＞0.

為找到一個步長α滿足條件A1和s－B（X ＋αΔX）＞0，t ＋αΔt ＞0，給出下面的引理.

引理2.1 令ˉα為初始步長，當更新的步長α 滿足

其中

時，對偶間隙gap（α）不斷減小，且滿足s－B（X ＋αΔX）＞0，t ＋αΔt ＞0.

證明若（14）成立，顯然有s－B（X ＋αΔX）＞0，t ＋αΔt ＞0，下面只需證對偶間隙gap（α）不斷減小即可.由前面的分析可知，在點（X，y，t，Z）處的對偶間隙為

則下一個迭代點（X ＋αΔX，y ＋αΔy，t ＋αΔt，Z ＋αΔZ）的對偶間隙為：

由（9），（10）（iii）和（10）（iv）可得，

又

因此有，

由（8）可得（n ＋2m）μ－gap ＜0，因此當步長α滿足（15）式時，對偶間隙gap（α）不斷減小.

由引理2.1 得到初始更新步長后通過線搜索尋找最終步長α，使其滿足X ＋αΔX ＞0，Z－αΔZ ＞0，即滿足正定性.

2.4 改進的半定規(guī)劃內點算法

根據(jù)上面幾節(jié)的分析，表1 給出求解（SDP1）改進的半定規(guī)劃內點法的算法框架.

表1

3 隨機超平面舍入算法

在得到了圖劃分模型（SDP1）的最優(yōu)解X之后，基于文獻［22，23］的隨機超平面舍入算法來得到原問題的近似解.在此算法的基礎上，將最優(yōu)解X的最大特征值所對應的特征向量也作為一組解.在算法過程中增加了可行性判斷，并在可行解中找到使原問題目標值最小的一組解，從而得到劃分集合.利用改進的隨機超平面舍入算法得到了原問題的近似解后，再應用文獻［19］中的2opt啟發(fā)式算法進行調整.在2opt 啟發(fā)式算法中，遍歷劃分集合中的頂點進行交換，交換頂點的原則是在保證可行解的條件下使原問題目標函數(shù)值減小，從而得到原問題的最佳近似解.其中具體的改進的隨機超平面舍入算法見表2.

表2

4 數(shù)值實驗

在本節(jié)，為了測試算法的整體性能，通過數(shù)值實驗和文獻［19］中提出的Vc ＋2opt算法進行比較，并引入文獻［19］中的兩組測試集GPKCrand50和GPKCrand20 分別進行測試，其中GPKCrand50、GPKCrand20指的是非零邊權占比為50%、20%的隨機矩陣，邊權值為區(qū)間［0，100］上的數(shù)，頂點權重為區(qū)間（0，1000］上的整數(shù).為了避免隨機性，每組實驗獨立運行10 次，時間取平均值.算法和文獻［19］中的Vc ＋2opt算法計算得到的原問題的近似解分別記為obj1和obj2，時間記為time1和time2，單位為秒.所得實驗結果見表3、表4.

表3 在GPKCrand50上的性能比較

表4 在GPKCrand20上的性能比較

通過表3可以發(fā)現(xiàn)，在GPKCrand50圖上，的算法和Vc ＋2opt算法得到的原問題的近似解沒有明顯的差異，但在運行時間上該文的算法明顯優(yōu)于Vc ＋2opt 算法.通過表4 可以發(fā)現(xiàn)，在GPKCrand20圖上，該文的算法在原問題的近似最優(yōu)解和運行時間上均表現(xiàn)出了很好的性能.數(shù)值實驗表明該文的算法可有效求解帶有頂點權重約束的圖劃分問題，且在稀疏圖上表現(xiàn)出了良好的性能.

5 結論

該文將帶有頂點權重的圖劃分問題轉化為新的半定規(guī)劃松弛模型，利用半定規(guī)劃內點法求解該模型，并在求解過程中給出了具體的初始點選取策略和步長更新策略.隨后利用改進的隨機超平面舍入算法和2opt啟發(fā)式算法得到原問題的近似最優(yōu)解.數(shù)值實驗表明該文的算法可有效求解帶有頂點權重約束的圖劃分問題，且對于稀疏圖的求解表現(xiàn)出了良好的性能.由于k ＝2時的圖劃分是k 分的基礎，如何有效的遞歸二分得到圖的k劃分，有待進一步研究.