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

王 彬, 孫德峰

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

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

王 彬1, 孫德峰2

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

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

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

0 引 言

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

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

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

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

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

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

Subject to

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

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

1 Benders分解算法

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

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

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

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

1.1 Benders割

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

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

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

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

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

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

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

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

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

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

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

1.2 改進的Benders算法

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

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

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

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

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

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

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

將得到的問題記為MP_R。

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

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

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

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

步驟1 采用文獻[12]中給出的動態(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。

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

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

2 計算實驗

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

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

表1 不同算法的計算時間對比Tab.1 Comparisons between different approaches

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

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

3 結(jié) 論

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

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

[ 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]. 中國科學(信息科學), 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]彭偉,盧錫城. 一個新的分布式最小連通支配集近似算法[J]. 計算機學報, 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。

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

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

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

1673-5862(2017)04-0419-06

0221.4

A

10.3969/ j.issn.1673-5862.2017.04.008