頂點覆蓋問題的強化半定規(guī)劃松弛92412

《頂點覆蓋問題的強化半定規(guī)劃松弛92412》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、_______________________________________________________________________________www.paper.edu.cn1頂點覆蓋問題的強化半定規(guī)劃松弛2王新輝劉三陽劉紅衛(wèi)（西安電子科技大學數(shù)學系，陜西西安710071）摘要對頂點覆蓋問題的一種等價模型，利用一般的松弛方法，得到了一個半定規(guī)劃松弛模型；通過引入算子hsvec，把這個等價模型進行提升，得到了一個強化半定規(guī)松弛模型.并從理論上證明了所得到強化松弛模型能比一般松弛模型提供更好的下界，同時數(shù)值實驗也證明了這一點.關鍵詞頂點覆蓋問題半定規(guī)劃強化半定規(guī)劃松

2、弛中圖分類號：221.21.引言設G=(V,E)是一個無向圖，SíV，對圖中任一條邊e，若至少一個端點在S中，則稱S為G的一個頂點覆蓋.若對每一個頂點i都有相應的非負權值w，則尋找包含頂點權i值之和最小的頂點覆蓋就是頂點覆蓋問題.此問題有廣泛的應用，例如在實驗數(shù)據(jù)統(tǒng)計、航[1][1,2]空調(diào)度、有效測試等方面.頂點覆蓋問題可以歸結為下面的整數(shù)規(guī)劃模型：ì*1?Minw=?i?Vwixi?2(VC)ís.t.xi+xj31(i,j)?E?x?{0,1}i?Vi??這個問題是一個典型的NP-hard問題，沒有多項式時間算法，本文研究的主要目的是把頂點覆蓋問題松弛為半定規(guī)劃模型，利用

3、多項式時間算法求解所得到半定規(guī)劃松弛模型，從而得到原問題的一個下界.2.半定規(guī)劃松弛我們利用下面的定理1，可以得到(VC)的一個等價模型：ì1Min?w(1+yy)?2i?Vi0i?s.t.(y-y)(y-y)=0(i,j)?E(VCP)í0i0j?y,y?{-1,1}i,j?Vij??y0?{-1,1}定理1.(VC)和(VCP)是等價的.1國家自然科學基金資助（69972036）和陜西省自然科學基金資助（2000SL03）2王新輝（1978—），男，河南汝陽人，西安電子科技大學博士生，研究方向為半定規(guī)劃的算法及應用______________________________

4、_________________________________________________中國科技論文在線www.paper.edu.cn證明對"x,x?{0,1)i,j?Vij由于x+x31，故x+x=1或x+x=2ijijij321不論那種情形，總可得到(x+x-)=ij24且恒有x+x-xx=1,ijijyi+1yj+1令y=2x-1,y=2x-1，即x=，x=，iijjij22則上式可化為(y-1)(y-1)=0y,y?{-1,1}i,j?V.ijij令y=1，則可以得到下面整數(shù)規(guī)劃0ì1Min?w(1+yy)?2i?Vi0i?s.t.(y-y)(y-y)=0(

5、i,j)?E(VCP')í0i0j?y,y?{-1,1}i,j?Vij??y0=1'以上各步皆可逆，故(VC)和(VCP)是等價的.下面證明(VCP)和(VCP')是等價的：''設(VCP)的最優(yōu)值為Q(VCP)，(VCP)的最優(yōu)值為Q(VCP)，顯然'Q(VCP)￡Q(VCP)，然而在(VCP)的最優(yōu)解y中若有y、y滿足約束ij***(-1-y)(-1-y)=0，則對所有這樣的i、j，令y=-y，y=-y，其余y=y得ijiijjii*''到的y是(VCP)的可行解，并且對應的(VCP)的目標值與(VCP)的目標值相等，這樣可'''以得到Q(VCP)3Q(VCP)，由上面證明

6、可知Q(VCP)=Q(VCP),因此(VCP)和(VCP)是等價的.綜上所述(VC)和(VCP)是等價的.對于(VCP)，我們可以松弛為下面半定規(guī)劃模型：_______________________________________________________________________________中國科技論文在線www.paper.edu.cnì1t?Min?i?Vwi(1+y0yi)2?t(SDP')ís.t.(y0-yi)(y0-yj)=0(i,j)?E?

7、

8、y

9、

10、=1i?Vi??

11、

12、y0

13、

14、=1n+1其中y,y?R.■i0't對于(SDP)，為了便于討論，令

15、y=(y,y,...,y),Y=yy120?0L0L0L0??1??÷?00L0w1÷?L÷?4÷?11÷?1÷?0L0LL-÷?00L0w2÷224?L÷L=?O÷Aij=?÷?1÷?0L1L0L-1÷?00L0wn÷?22÷?4÷?L÷?1w1wL1wwi÷?11÷?è41424n?i?V2÷??0L-L-L1÷è22?1其中A表示第i行第j列，第j行第i列元素皆為，第(n+1)行的第i列第j列，第ij21n+1列的第i行第j行的元素皆為-，且第(n+1)行第(n+1)列為1，其余元素皆