求解最小支配集的線性混合整型規(guī)劃算法

程詠鋒，吳歆韻，熊才權(quán)

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430068)

最小支配集問題為NP難問題，是一類重要的組合優(yōu)化問題。對(duì)于最小支配集問題的求解不可能出現(xiàn)多項(xiàng)時(shí)間精確算法。最小支配集問題及其各種拓展問題在多文檔摘要[1]，社會(huì)網(wǎng)絡(luò)的建模和研究[2]，通信網(wǎng)絡(luò)[3]等諸多領(lǐng)域具有廣泛的應(yīng)用。

目前，求解最小支配集問題精確算法均為非多項(xiàng)式時(shí)間算法，F(xiàn)omin F V[4]等提出一種分支簡(jiǎn)化(FKW)算法，盡管最早突破O(2n)界限,但FKW仍難令人滿意,如果圖中沒有低于2度的節(jié)點(diǎn),算法將回歸平凡的枚舉。Grandoni F[5]等人提出了求最小支配集的Grandoni算法，但該算法只能求最小支配集的大小，不能求具體的最小支配集；Lu gang[6]等對(duì)該算法提出了修改，應(yīng)用于求解具體的最小支配集；Headar[7]等提出一種混合遺傳算法，與局部搜索算法相結(jié)合，設(shè)計(jì)出特定的適應(yīng)度函數(shù)求解最小支配集，該算法在文獻(xiàn)[8]中得到改進(jìn)。David[9]等針對(duì)大型圖的最小支配集問題，提出一種新的基于順序的隨機(jī)局部搜索算法。Zhu X[10]提出求解最小支配集的多項(xiàng)式時(shí)間近似方案，但這些算法不能在一般圖上得到應(yīng)用。Yuan Fuyu[11]通過分析大規(guī)模實(shí)例，結(jié)合支配集問題的特點(diǎn)提出一個(gè)快速高效地求解最小支配集問題的算法(Fast MDS)，其他最小連通支配集算法參見文獻(xiàn)[12-14]。

本文根據(jù)最小支配集問題的性質(zhì)，構(gòu)造出一種求解該問題的數(shù)學(xué)模型，采用java語(yǔ)言實(shí)現(xiàn)鄰接支配矩陣的存儲(chǔ)和根據(jù)數(shù)學(xué)模型利用Gurobi優(yōu)化器進(jìn)行線性求解，并與文獻(xiàn)[6]提及到的FKW算法，Grandoni算法和改進(jìn)的Grandoni算法在當(dāng)前國(guó)際文獻(xiàn)公開的共74個(gè)算例上進(jìn)行比較，該算法的計(jì)算效率明顯優(yōu)于其它的精確算法，并且在所有算例上都能得到較好的精確解。

1 最小支配集問題的描述

1.1 問題定義

對(duì)于無(wú)向不連通圖G=(V,E)，圖G的頂點(diǎn)集合為V=V(G)，圖G的邊集合為E=E(G)。若頂點(diǎn)集合V當(dāng)中存在一個(gè)子集D?V,對(duì)于集合V當(dāng)中的任意一個(gè)頂點(diǎn)Vp，要么Vp∈D，要么Vp與集合D當(dāng)中某個(gè)頂點(diǎn)相鄰，則將集合D稱為圖G=(V,E)的一個(gè)支配集。當(dāng)集合D當(dāng)中任意一個(gè)真子集都為非支配集時(shí)，則稱集合D為圖G的一個(gè)極小支配集。

設(shè)集合D是圖G=(V,E)的一個(gè)支配集，當(dāng)圖G當(dāng)中不存在任何一個(gè)支配集D1，使得|D1|<|D|，此時(shí)的集合D稱為圖G=(V,E)的一個(gè)最小支配集，圖G當(dāng)中所有最小支配集的大小稱為圖G=(V,E)的支配數(shù)，表示為γ(G)。

以下給出最小支配集問題的相關(guān)定義:

定義1 支配集(Dominating Set)：集合D?V(G)，若任意的Vp∈V(G)-D，存在一個(gè)頂點(diǎn)Vq∈D，使得頂點(diǎn)Vp與頂點(diǎn)Vq之間有邊相連，滿足這樣條件的集合D就構(gòu)成了圖G的一個(gè)支配集,簡(jiǎn)記為DS。

定義2 極小值支配集(Minimal DS)：設(shè)集合D為圖G=(V,E)的一個(gè)支配集，當(dāng)集合D當(dāng)中的任意一個(gè)真子集都無(wú)法構(gòu)成圖G=(V,E)的一個(gè)支配集，則稱集合D為圖G=(V,E)的一個(gè)極小支配集。

定義3 最小支配集(Minimum DS)：在圖G=(V,E)的所有支配集當(dāng)中，頂點(diǎn)個(gè)數(shù)最少的那個(gè)支配集稱為圖G=(V,E)的最小支配集。簡(jiǎn)稱MDS。

由相關(guān)支配集的定義可知極小支配集和最小支配集的相關(guān)性質(zhì)：

1)對(duì)于一個(gè)任意的非空?qǐng)DG=(V,E),可以找到若干個(gè)極小支配集，這些極小支配集的階(頂點(diǎn)數(shù))不一定相同。

2)對(duì)于一個(gè)任意的非空?qǐng)DG=(V,E)，可以找到若干個(gè)最小支配集，這些最小支配集的階(頂點(diǎn)數(shù))一定相同。

3)如果一個(gè)集合X，滿足最小支配集的條件，那么集合X一定滿足極小支配集的條件；反之，若集合X滿足極小支配集的條件，那么集合X未必滿足最小支配集的條件。

1.2 整數(shù)規(guī)劃模型

最小支配集問題指的是對(duì)于給定的圖G=(V,E)，在集合V中找到一個(gè)支配集D,使得支配集D中所含節(jié)點(diǎn)的個(gè)數(shù)達(dá)到最小。通過引入n維0-1向量X=(x1，x2，x3，…，xn)，xp=1表示頂點(diǎn)p∈D，xp=0表示頂點(diǎn)p?D，則最小支配集的整數(shù)規(guī)劃模型可以描述為式(1)-(4)：

(1)

s.t.

(2)

(3)

(4)

四個(gè)公式分別表示為：1)f(X)作為目標(biāo)函數(shù)表示以最少的頂點(diǎn)集合作為支配點(diǎn)，2)為約束條件表示任意一個(gè)頂點(diǎn)Vp要么是支配點(diǎn)，要么被支配集和當(dāng)中的點(diǎn)所支配，n表示圖頂點(diǎn)的個(gè)數(shù)。3)LP,q為常量，表示第p節(jié)點(diǎn)是否可以與第q節(jié)點(diǎn)互相支配，是則為1，否則為0。4)變量xp表示是否選取第p個(gè)節(jié)點(diǎn)作為最小支配集，是則為1，否則為0。

2 圖的最小支配集的多項(xiàng)式方程組模型與Gurobi求解器求解

Gurobi是由美國(guó)Gurobi公司開發(fā)的新一代大規(guī)模優(yōu)化器，綜合能力強(qiáng)，性價(jià)比較優(yōu)。它支持Windows,Linux,MacOSX等多種平臺(tái),采用了 最新的優(yōu)化技術(shù),充分利用多核處理器優(yōu)勢(shì),支持并行計(jì)算;問題尺度只受限制于計(jì)算機(jī)內(nèi)存容量,不對(duì)變量數(shù)量和約束數(shù)量有限制;提供了方便輕巧的Java接口;能夠快速高效地解決大規(guī)模線性問題、二次型目標(biāo)問題、混合整數(shù)線性和二次型問題等數(shù)學(xué)問題。

設(shè)圖G=(V,E)是無(wú)向圖，則圖G的鄰接矩陣定義為A=[vpq]n×n，其中

(1)

通常將A的第i行記為Ai，1≤i≤n。此外在此基礎(chǔ)上定義鄰接支配矩陣

A*=[vpq]n×n

其中

(2)

對(duì)于給定具有n個(gè)頂點(diǎn)的無(wú)向圖G=(V,E)，其鄰接支配矩陣為A*=[vpq]n×n。由最小支配集的定義可知，求解一個(gè)多元多項(xiàng)式方程組的0-1解與求解圖G的最小支配集這兩個(gè)問題是等價(jià)的，即n維向量X中所含1的個(gè)數(shù)達(dá)到最小。

(3)

設(shè)n維向量Xk=(x1，x2，x3…xn)expT,若該n維向量滿足(Ck)的所有不等式，故向量Xk是方程組(Ck)的一個(gè)解。則其中取值為1的變量所對(duì)應(yīng)的頂點(diǎn)構(gòu)成的集合為支配點(diǎn)集合，取值為0的變量所對(duì)應(yīng)的頂點(diǎn)構(gòu)成的集合為被支配點(diǎn)集合。

通過Java語(yǔ)言實(shí)現(xiàn)無(wú)向圖的支配矩陣存儲(chǔ)，設(shè)置最優(yōu)化模型的系數(shù)列表，調(diào)用Gurobi優(yōu)化器進(jìn)行優(yōu)化求解。首先使用grbModel.addVar函數(shù)構(gòu)建目標(biāo)函數(shù)系數(shù)列表；其次使用grbModel.addConst構(gòu)建約束條件的系數(shù)列表；最后使用grbModel.setObjective函數(shù)優(yōu)化求解。利用公共線性規(guī)劃求解器對(duì)其進(jìn)行求解, 使得目標(biāo)函數(shù)值不斷減小，最終可求得一個(gè)最小的k值。

3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)主要是對(duì)求解最小支配集的MILP算法的性能進(jìn)行實(shí)驗(yàn)分析。并與文獻(xiàn)[6]提及到的FKW算法和Grandoni算法以及改進(jìn)的Grandoni算法在當(dāng)前國(guó)際文獻(xiàn)公開的共74組算例上進(jìn)行比較。第一組算例為文獻(xiàn)中作者[15]隨機(jī)生成的大規(guī)模算例。第二組算例，包含廣泛的真實(shí)圖，研究于許多領(lǐng)域，特別是在圖染色問題上[16]。

實(shí)驗(yàn)環(huán)境:本次實(shí)驗(yàn)所涉及的算法均以Java語(yǔ)言進(jìn)行編程實(shí)現(xiàn), 測(cè)試運(yùn)行的 PC 機(jī)運(yùn)行環(huán)境為 Core i5 3.4 GHz CPU 和 8.0 GB RAM, 操作系統(tǒng)為 Windows 10,JVM 為 Oracle JRE 1.8。為了驗(yàn)證算法的性能,采用兩組算例進(jìn)行實(shí)驗(yàn)驗(yàn)證。

3.1 隨機(jī)算例的測(cè)試

第一組算例為隨機(jī)生成的24組小規(guī)模算例，算例生成方法為：在一個(gè)N×N的固定區(qū)域中隨機(jī)選取一定數(shù)量的節(jié)點(diǎn)作為算例的圖節(jié)點(diǎn)；當(dāng)區(qū)域內(nèi)的兩節(jié)點(diǎn)p，q之間的距離小于某個(gè)設(shè)定的常數(shù)k值時(shí)，將{p，q}作為算例圖中的一條邊，即兩節(jié)點(diǎn)p，q之間相互連通。該組隨機(jī)算例節(jié)點(diǎn)數(shù)從20-120，每組算例運(yùn)行10次，求出最優(yōu)解的時(shí)間并取平均值，結(jié)果見表1。表1前兩列分別表示算例的名稱和最小支配集個(gè)數(shù)，其余列表示每個(gè)算法運(yùn)行10次找到最小支配集個(gè)數(shù)時(shí)所需要的平均時(shí)間。

表1 隨機(jī)算例對(duì)比 s

圖1為表1的信息匯總。通過圖1，可以明顯看到，求出24組小規(guī)模算例的最小支配集，F(xiàn)KW算法用了16.239 s，Grandoni算法用了1257.115 s，改進(jìn)的Grandoni算法用了1217.891 s，而提出的MILP算法給出了2.674 s的最好結(jié)果，根據(jù)在隨機(jī)生成的24組小規(guī)模算例上的結(jié)果，MILP算法具有更好的性能。

圖 1 精確算法的總耗時(shí)

3.2 圖著色算例測(cè)試

由于第一組圖的最小支配集較小，實(shí)驗(yàn)結(jié)果具有局限性。因此對(duì)第二組圖進(jìn)行測(cè)試，這個(gè)測(cè)試涉及到寬面圖，該50組算例頂點(diǎn)規(guī)模從11到864個(gè)頂點(diǎn)不等，這些算例已經(jīng)在許多研究中使用，特別是在圖著色的問題上。這次測(cè)試包含50組算例，每組算例運(yùn)行10次，測(cè)試結(jié)果見表2。

在圖著色算例上的測(cè)試結(jié)果見表2，前四列分別表示算例的名稱，頂點(diǎn)個(gè)數(shù)，邊數(shù)，最小支配集個(gè)數(shù)，后四列分別表示FKW算法，GR算法，IGR算法，以及MILP算法求出最優(yōu)解所需花費(fèi)的時(shí)間?！?”表示未能給出最優(yōu)解，“>3600”表示程序運(yùn)行時(shí)間超過一小時(shí)，表3是表2的匯總，顯示了各算法在1小時(shí)內(nèi)成功求出最優(yōu)解算例的個(gè)數(shù)。

從表2的結(jié)果可以看出，對(duì)于復(fù)雜算例的計(jì)算，IGR算法的性能要優(yōu)于GR算法，F(xiàn)KW算法在計(jì)算時(shí)會(huì)造成程序崩潰。在除Le450-5c外的所有算例上，MILP算法對(duì)于其余49個(gè)算例均能在一小時(shí)內(nèi)找到最優(yōu)解。通過表3的匯總可以看出，對(duì)比其他三個(gè)算法，MILP算法在一小時(shí)的計(jì)算時(shí)間內(nèi)成功率達(dá)到98%，在所有算例上MILP算法的求解速度均快于其他算法，并且對(duì)于比較復(fù)雜的算例，MILP算法求解的速度更快，這些數(shù)據(jù)表明，MILP算法是求解最小支配集問題的一種高效的精確算法。

表2 圖著色算例對(duì)比

表3 圖著色算例結(jié)果匯總

4 結(jié)論

本文提出了一種求解最小支配集問題的線性混合整數(shù)規(guī)劃算法,在MILP算法中，根據(jù)最小支配集問題的特點(diǎn)，提出一種新的整數(shù)規(guī)劃模型，將該問題轉(zhuǎn)化為線性規(guī)劃問題，運(yùn)用Gurobi求解器進(jìn)行線性求解。采用當(dāng)前國(guó)際文獻(xiàn)公開的共74組算例作為算法測(cè)試實(shí)驗(yàn)集，在與文獻(xiàn)中介紹的其他精確算法進(jìn)行比較后發(fā)現(xiàn)，MILP算法在中小規(guī)模的算例上能夠以較快的時(shí)間求出最優(yōu)解，對(duì)于較為復(fù)雜的算例，MILP算法都能求出最優(yōu)解，并且在計(jì)算出最優(yōu)解的時(shí)間上具有明顯優(yōu)勢(shì)。