王 彬, 孫德峰

(1. 山西大同大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 山西 大同 037009;2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 沈陽 110819)

最小連通支配集問題的分解算法

王 彬1, 孫德峰2

(1. 山西大同大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 山西 大同 037009;2. 東北大學(xué) 信息科學(xué)與工程學(xué)院, 沈陽 110819)

在無線網(wǎng)絡(luò)設(shè)計(jì)中,連通支配集(CDS)有著廣泛的應(yīng)用。針對(duì)最小連通支配集問題(MCDSP),提出了基于Benders的分解算法進(jìn)行最優(yōu)求解。將原問題分解為較易求解的最小支配集主問題和連通性子問題,其中主問題能夠生成最小支配集,子問題負(fù)責(zé)判斷所生成的最小支配集的連通性。若不連通,生成相應(yīng)的Benders cut對(duì)主問題進(jìn)行修正和進(jìn)一步限定。在上述Benders算法中,主問題與子問題均為純整數(shù)規(guī)劃。在此基礎(chǔ)上,分析了最小連通支配集問題的上下界性質(zhì),通過構(gòu)造容易求解的輔助問題,并結(jié)合二分法思想進(jìn)一步降低問題的搜索空間,設(shè)計(jì)了改進(jìn)的Benders分解算法,加速算法收斂速度。通過計(jì)算實(shí)驗(yàn)與現(xiàn)有文獻(xiàn)中的分解算法進(jìn)行對(duì)比,證明了所提分解算法的優(yōu)越性。

最小連通支配集; Benders分解; 組合割; 整數(shù)規(guī)劃

0 引 言

最小連通支配集問題因其在無線傳感器網(wǎng)絡(luò)領(lǐng)域的重要作用受到了學(xué)者越來越多的關(guān)注。它能夠作為一個(gè)“虛擬骨干網(wǎng)”來降低網(wǎng)絡(luò)節(jié)點(diǎn)的能量損耗、拓?fù)渚W(wǎng)絡(luò)的維護(hù)費(fèi)用,并能夠減輕廣播風(fēng)暴的影響。

(a)—支配集; (b)—連通支配集。圖1 支配集及連通支配集示意圖Fig.1 Dominating set and connected dominating set

MCDSP問題被證明是NP難的[1], 并且與最多葉子生成樹問題(MLSTP)等價(jià)[2]。最小連通支配集問題被廣泛地應(yīng)用于無線傳感器網(wǎng)絡(luò)的規(guī)劃問題[3],同時(shí)也被應(yīng)用在光纖網(wǎng)絡(luò)設(shè)計(jì)[4]等一系列網(wǎng)絡(luò)問題中。

Simonetti等[5]給出了MCDSP的整數(shù)規(guī)劃表達(dá)形式,使用分支割算法進(jìn)行最優(yōu)求解,并提出了一系列有效不等式對(duì)所提算法進(jìn)行加速。Fan等[6]也給出了MCDSP的一個(gè)較緊的數(shù)學(xué)規(guī)劃模型,這些已有的關(guān)于MCDSP的模型主要區(qū)別在于表達(dá)和求解連通性的方法不同,例如Miller-Tucker-Zemlin(MTZ)不等式、單一/多商品流、以及子環(huán)消除約束等。在大多數(shù)文獻(xiàn)中,對(duì)MCDSP模型的最優(yōu)求解,依賴于使用標(biāo)準(zhǔn)化商業(yè)求解軟件CPLEX直接求解。Fernau等[7]針對(duì)等價(jià)的MLSTP問題給出了復(fù)雜度為O(1.896 6N)的基于分支策略的精確算法。Gendron等[8]開發(fā)了Benders分解和分支割算法以及基于二者的混合算法對(duì)MCDSP問題進(jìn)行最優(yōu)求解,是目前已知的求解性能最好的精確算法。其中,文獻(xiàn)[8]給出的2種Benders分解算法,其思想也契合了MCDSP問題的2種主流求解思路,即:1)首先尋找一個(gè)支配集,然后尋求方法將其改造為連通集;2)首先找出一個(gè)連通支配集CDS,然后尋求方法逐步減少此CDS的節(jié)點(diǎn)基數(shù)。

由于MCDSP問題的復(fù)雜性,大多數(shù)關(guān)于MCDSP的文獻(xiàn)采用啟發(fā)式方法進(jìn)行近似求解,例如Guha等[9]和Marathe等[10]給出的分別基于單位原圖和常規(guī)圖的近似算法,Ruan等[9]提出的基于生成樹思想的單步貪婪近似算法等。王靈敏等[11]提出了一種基于變深度鄰域搜索的算法,采用了一種適合最小連通支配集問題的鄰域結(jié)構(gòu),并給出了適用于此結(jié)構(gòu)的增量更新評(píng)估方法。Lucena 等[12]研究了動(dòng)態(tài)貪婪啟發(fā)式算法,并給出了一系列標(biāo)準(zhǔn)測試算例,其算法能獲得較緊的上界。除了以上提到的運(yùn)用全網(wǎng)信息進(jìn)行計(jì)算的集中式算法,啟發(fā)式的另一種類型是分布式算法,其劃分依據(jù)是所運(yùn)用的計(jì)算資源不同[13]。

MCSDP問題的一般性模型可表述如下:

Subject to

其中yi為0-1變量,當(dāng)節(jié)點(diǎn)i被選擇時(shí)取1,否則取0;約束(2)保證得到的集合是支配集,約束(3)保證得到的集合是連通的。

本文提出了一個(gè)基于Benders分解算法的精確算法來最優(yōu)求解MCDSP問題,然后通過分析MCDSP問題的上下界性質(zhì),利用二分法將MCDSP的2種主流求解思路有機(jī)結(jié)合在一起,進(jìn)一步開發(fā)了改進(jìn)的Benders分解算法。

1 Benders分解算法

Benders[4]于1962年提出了Benders分解算法用于求解大規(guī)?；旌险麛?shù)規(guī)劃問題。這是一種迭代算法,其核心思想包括分離策略和延遲約束生成(即割)。

對(duì)于難以有效求解的混合整數(shù)規(guī)劃問題 (MIP),首先是執(zhí)行分離策略,將原始MIP 分解為2個(gè)相對(duì)容易求解的問題,即Benders主問題和子問題。通常的分離策略是將僅包含整數(shù)變量的目標(biāo)函數(shù)項(xiàng)和約束放入主問題中,剩余的既含有整數(shù)變量又含有連續(xù)變量(或者僅連續(xù)變量)的目標(biāo)函數(shù)項(xiàng)和約束放入子問題中。因部分約束缺失,主問題是原始MIP的松弛問題,對(duì)于最小化問題而言,其求解能夠?yàn)樵瓎栴}提供下界。在迭代求解過程中,首先求解主問題得到整數(shù)變量的解,傳遞給子問題,使得子問題變?yōu)橐粋€(gè)容易求解的線性規(guī)劃問題,其解與主問題的整數(shù)解一起構(gòu)成原問題的可行解,因此可以為原問題提供上界。在求解子問題時(shí),可通過對(duì)偶理論生成由對(duì)偶變量值構(gòu)成的Benders 割加入到主問題中。Benders割是由整數(shù)變量和已求得的子問題對(duì)偶變量值構(gòu)成的約束表達(dá)式,包含了子問題的當(dāng)前求解信息,是對(duì)主問題所缺失的約束信息的補(bǔ)償,即延遲約束策略,因此當(dāng)所有的Benders 割均加入到主問題中時(shí),主問題與原問題等價(jià),可得到原問題的最優(yōu)解。

在實(shí)際計(jì)算過程中,隨著迭代過程的不斷進(jìn)行,主問題和子問題交替迭代求解后得到的上界和下界的值如果相等,那么此時(shí)Benders分解方法得到的解就是原始混合整數(shù)規(guī)劃問題的最優(yōu)解,算法即可提前結(jié)束。

在本文中,將MCDSP中的約束(3)劃為子問題SP,剩余目標(biāo)及約束(1)、(2)、(4)作為主問題MP,從而分解為2個(gè)較易求解的問題。在每次迭代過程中,求解最小支配集主問題MP能夠得到最小支配集D,求解子問題SP可判斷MP所生成的最小支配集D是否連通(可通過圖形遍歷算法)。若不連通,則應(yīng)用割生成策略生成Benders割,加入到主問題MP中,從而將MP已生成的不連通的最小支配集去除,即實(shí)施約束(3),如此迭代求解直到得到最小連通支配集。

1.1 Benders割

由于MCDSP中,支配集的個(gè)數(shù)是有限的,因此割(5)的個(gè)數(shù)也是有限的,所以最終所有不連通的支配集都可以通過向主問題MP中加入割(5)而除去,即符合Benders分解算法的延遲約束思想。事實(shí)上,將所有存在的不連通的支配集所對(duì)應(yīng)的割(5)均加入MP中,則構(gòu)成了約束(3),即此時(shí)MP與MCDSP等價(jià)。最終,Benders算法能夠收斂得到MCDSP的最優(yōu)解。

割(5) 與文獻(xiàn)[15]中給出的組合Benders割思想類似。文獻(xiàn)[8]指出大多數(shù)情況下,不連通的支配集D需要多于一個(gè)節(jié)點(diǎn)的加入才能夠連通,因此組合Benders割(4) 對(duì)主問題MP的限制效果較弱。文獻(xiàn)[8]中提出了基于最小不連通子集(MDS)的加強(qiáng)Benders割的生成策略。

由于最小不連通子集T較難獲得,與文獻(xiàn)[8]中所述的加強(qiáng)Benders割生成策略相似,本文給出如下的加強(qiáng)Benders割:

顯然,割(5)包含于割(6)。由于D是支配集,而mD是將D擴(kuò)展為連通支配集所需的最少的節(jié)點(diǎn)數(shù)的下界,因此割(6)對(duì)MCDSP有效。割(6)是本文中實(shí)際采用的Benders割形式。

因此,上述所提基本Benders算法流程如下:

步驟1 初始化迭代數(shù)iter = 1;

步驟2 求解主問題MP,得到當(dāng)前最小連通集D;

步驟3 求解子問題SP,判斷當(dāng)前MP得到的支配集D是否連通,若連通,算法結(jié)束;否則,轉(zhuǎn)到步驟4;

步驟4 利用當(dāng)前最小連通集D生成割 (6),將其加入主問題MP中,令iter = iter + 1,轉(zhuǎn)到步驟2;

在Benders算法開始前,可加入有效不等式對(duì)MP作出更緊的限定:

有效不等式(7)可以避免支配集D中出現(xiàn)與其他節(jié)點(diǎn)均不連通的孤立點(diǎn),部分地收緊了MP中因約束(3) 缺失而缺乏的連通性要求,因此可以避免產(chǎn)生一部分不合要求的支配集,能夠加速Benders算法的收斂速度。

1.2 改進(jìn)的Benders算法

顯然,|D| +mD是MCDSP的一個(gè)上界,記為UB,其中|D|為支配集D中包含的節(jié)點(diǎn)的個(gè)數(shù),即D的基數(shù)。

考慮通過分析MCDSP的上界及下界性質(zhì),從而設(shè)計(jì)改進(jìn)策略加速Benders分解算法的收斂速度。

首先,給出如下2條性質(zhì):

性質(zhì)1 若存在一個(gè)支配連通集,其基數(shù)d滿足d< |V|,則一定存在一個(gè)基數(shù)等于d+1的支配連通集。

性質(zhì)2 若不存在一個(gè)基數(shù)等于d+1的支配連通集,則一定不存在一個(gè)基數(shù)等于d的支配連通集。

對(duì)于性質(zhì)1,很顯然,假設(shè)D是所涉及的支配連通集,則從V/D中任意挑選一個(gè)節(jié)點(diǎn)加入D中,新的D集合仍是支配連通集,但基數(shù)為d+1。性質(zhì)2是性質(zhì)1的逆否命題,因此也成立。

記d為一個(gè)給定參數(shù),向主問題MP中加入如下約束:

將得到的問題記為MP_R。

求解問題MP_R有且僅有3種情況:1)MP_R無解;2)MP_R有解,但所有滿足式(7)的解(即節(jié)點(diǎn)基數(shù)為d的所有可能支配集),均不連通;3)MP_R有解,且解中存在連通集。對(duì)于第1種和第2種情況,根據(jù)性質(zhì)2可知,d為MCDSP的下界;;對(duì)于第3種情況,根據(jù)性質(zhì)1可知,d為MCDSP的上界。

記求解MP_R得到的支配集為S,值得指出的是,求解基于支配集S的SP子問題所得到的割(6)對(duì)于MCDSP仍有效。

基于以上結(jié)論,很容易可以得出改進(jìn)策略:若已知MCDSP問題的上界和下界,則可在此上下界之間選擇合適的基數(shù)參數(shù)d,求解相對(duì)應(yīng)的MP_R問題,從而根據(jù)上述的MP_R問題的3種解情況獲得新的上界或下界,從而減小分解算法的搜索空間。

結(jié)合二分法思想,本文提出如下的改進(jìn)Benders算法:

步驟1 采用文獻(xiàn)[12]中給出的動(dòng)態(tài)貪婪啟發(fā)式算法初始化上界UB,初始化迭代數(shù)iter=1;

步驟2 求解MP,得到支配集D,求解SP,若可行,算法結(jié)束;否則,初始化下界LB=|D|,并生成割(6);

步驟5 求解SP,若不可行,生成割(6)加入MP_R中,令iter=iter+1,轉(zhuǎn)到步驟4;若可行(即連通),更新UB=d,轉(zhuǎn)到步驟3;

步驟6 若UB=LB,則算法結(jié)束;否則,轉(zhuǎn)到步驟3。

事實(shí)上,上述算法仍可進(jìn)一步改進(jìn)。在上述步驟5中,當(dāng)UB得到更新且更新后的UB=LB+1或UB=LB+2時(shí),則對(duì)于新生成的MP_R,由于d=UB-1,如下有效不等式一定成立:

其中S1表示上述步驟4中獲得的節(jié)點(diǎn)基數(shù)為UB的支配連通集。式(9)雖然被包含在新生成的主問題MP的約束(8)中,但仍有可能被改進(jìn)。考慮如下情況:當(dāng)將S1中的任何一個(gè)節(jié)點(diǎn)去除,若得到的集合均不是支配集或者連通集中的一種,則式(9)右項(xiàng)可改為UB-2。

2 計(jì)算實(shí)驗(yàn)

本文中的計(jì)算實(shí)驗(yàn)采用文獻(xiàn)[8]及文獻(xiàn)[12]中使用的針對(duì)MCDSP問題的標(biāo)準(zhǔn)測試實(shí)例。計(jì)算實(shí)驗(yàn)共生成16個(gè)測試實(shí)例,其節(jié)點(diǎn)個(gè)數(shù)規(guī)模分別為50、100、150和 200,節(jié)點(diǎn)密度(%)分別為5、10、20和30。所有的算例均在一臺(tái)擁有 Intel Core i5-6200U 2.30 GHz CPU及 8.00 GB 內(nèi)存的計(jì)算機(jī)上進(jìn)行測試。

為進(jìn)行算法性能對(duì)比,本文對(duì)比了所提出的改進(jìn)Benders算法(記為IBD)與文獻(xiàn)[8]中給出的獨(dú)立Benders(記為SABE)和反向探查Benders(記為IPBE)這2種算法。以上2種算法是目前已有文獻(xiàn)中求解效果最好的幾種最優(yōu)算法中的2種,分別從LB和UB這2個(gè)方向開始進(jìn)行迭代求解。值得指出的是,文獻(xiàn)[8]中給出的SABE算法同樣也使用了文獻(xiàn)[12]中給出的動(dòng)態(tài)貪婪啟發(fā)式算法得到較緊的初始上界UB。

表1 不同算法的計(jì)算時(shí)間對(duì)比Tab.1 Comparisons between different approaches

對(duì)比結(jié)果如表1所示,包括計(jì)算時(shí)間(單位: 秒,記為Time)及迭代次數(shù)(主問題MP或MP_R的求解次數(shù),記為#)。所有的計(jì)算實(shí)驗(yàn)均限定3 600 s的計(jì)算時(shí)間上限,下表中“—”表示算法無法在限定時(shí)間內(nèi)求得最優(yōu)解。

由表1中可以看出,當(dāng)節(jié)點(diǎn)密度較高時(shí),3種算法的求解效果均比較快速,部分算例僅一次迭代就可得到最優(yōu)解;當(dāng)節(jié)點(diǎn)密度較低時(shí),本文所提IBD算法在求解時(shí)間和收斂速度上要明顯優(yōu)于前2種算法。本文所提IBD算法能在合理時(shí)間內(nèi)最優(yōu)求解12個(gè)算例中的10個(gè),而SABE和IPBE算法在限定時(shí)間內(nèi)能夠最優(yōu)求解的算例分別為7個(gè)和9個(gè)。

3 結(jié) 論

本文針對(duì)最小連通支配集問題,提出了一個(gè)新的分解算法進(jìn)行最優(yōu)求解,能夠通過上下界的二分法迭代更新策略將2種主流的解空間搜索策略進(jìn)行混合,加快收斂速度。計(jì)算結(jié)果表明,本文提出的改進(jìn)分解算法,在計(jì)算時(shí)間上的性能優(yōu)于目前已知的最好的分解算法。

由于影響B(tài)enders算法求解速度主要有2方面的因素,首先是主子問題的求解速度(影響每次迭代的求解時(shí)間),其次是Benders割的質(zhì)量(影響迭代次數(shù))。未來的工作主要是針對(duì)提升主問題MP的求解速度,通過開發(fā)多種有效不等式(例如消除子環(huán)約束)等加速手段開發(fā)高效的分支割算法對(duì)MP進(jìn)行有效求解。

[ 1 ]GAREY M R,JOHNSON D S. Computers and Intractability: a Guide to NP-Completeness[M]. New York:WH Freeman, 1979.

[ 2 ]LUCENA A,MACULAN N,SIMONETTI L. Reformulations and solution algorithms for the maximum leaf spanning tree problem[J]. Comput Manag Sci, 2010,7:289-311.

[ 3 ]BALASUNDARAM B,BUTENKO S. Handbook of Optimization in Telecommunications[M]. New York: Springer, 2006:865-890.

[ 4 ]CHEN S,LJUBIC I,RAGHAVAN S. The regenerator location problem[J]. Networks, 2010,55(3):205-220.

[ 5 ]SIMONETTI L,CUNHA A S,LUCENA A. The minimum connected dominating set problem: Formulation, valid inequalities and branch-and-cut algorithm[J]. Network Optimization, Lecture Notes in Computer Science, 2011,6701:162-169.

[ 6 ]FAN N,WATON J P. Solving the connected dominating set problem and power dominating set problem by integer programming[J]. Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 2012,7402:371-383.

[ 7 ]FERNAU H,KNEIS J,KRATSCH D, et al. An exact algorithm for the maximum leaf spanning tree problem[J]. Theoretical Computer Science, 2011,412(45):6290-6302.

[ 8 ]GENDRON B,LUCENA A,CUNHA A S D,et al. Benders, Branch-and-Cut, and Hybrid Algorithms for MCDSP[J]. INFORMS Journal on Computing, 2014,26(4):645-657.

[ 9 ]GUHA S,KHULLER S. Approximation algorithms for connected dominating sets[J]. Algorithmica, 1998,20(4):374-387.

[10]MARATHE M V,BREU H,HUNT III HB,et al. Simple heuristics for unit disc graphs[J]. Networks, 1995,25(2):59-68.

[11]王靈敏,周淘晴,吳歆韻,等. 求解最小連通支配集問題的變深度鄰域搜索算法[J]. 中國科學(xué)(信息科學(xué)), 2016,46(4):445-460.

[12]RUAN L,DU H,JIA X. A greedy approximation for minimum connected dominating sets[J]. Theoritical Computer Science, 2004,329:325-330.

[13]彭偉,盧錫城. 一個(gè)新的分布式最小連通支配集近似算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2001,24(3):254-258.

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

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

AdecompositionapproachfortheMinimumConnectedDominatingSetProblem

WANGBin1,SUNDefeng2

(1. School of Mathematics and Computer Science, Datong University, Datong 037009, China; 2. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China)

The Connected Dominating Set (CDS) is significant in the area of wireless network design. This paper investigates the Minimum Connected Dominating Set Problem (MCDSP), and proposes a Benders-based decomposition approach to solve it optimally. The problem is decomposed into a master problem which generates minimum dominating set, and a slave problem which is solved to check the generated dominating set is connected or not. If not connected, the Benders cut will be generated and added into the master problem. Note that in the resulting Benders approach, the master problem and slave problem are both integer programming. Moreover, this paper analyzes the lower-and upper-bound properties of MCDSP to reduce the searching space of the problem by constructing an easier auxiliary problem and applying a dichotomy-iterative updating strategy, and finally proposes an accelerated Benders approach which is fast in convergence. The computational tests show that the proposed approach outperforms other decomposition approaches in previous literature, especially for low density instances.

minimum connected dominating set;Benders decomposition; combinatorial cut; integer programing

2017-05-10。

中國博士后基金資助項(xiàng)目(2017M552213)。

王 彬(1982-),女,山西大同人,山西大同大學(xué)講師,碩士;

孫德峰(1986-),男,山東煙臺(tái)人,東北大學(xué)講師,博士。

1673-5862(2017)04-0419-06

0221.4

A

10.3969/ j.issn.1673-5862.2017.04.008