顶点覆盖问题的强化半定规划松弛92412

《顶点覆盖问题的强化半定规划松弛92412》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、_______________________________________________________________________________www.paper.edu.cn1顶点覆盖问题的强化半定规划松弛2王新辉刘三阳刘红卫（西安电子科技大学数学系，陕西西安710071）摘要对顶点覆盖问题的一种等价模型，利用一般的松弛方法，得到了一个半定规划松弛模型；通过引入算子hsvec，把这个等价模型进行提升，得到了一个强化半定规松弛模型.并从理论上证明了所得到强化松弛模型能比一般松弛模型提供更好的下界，同时数值实验也证明了这一点.关键词顶点覆盖问题半定规划强化半定规划松

2、弛中图分类号：221.21.引言设G=(V,E)是一个无向图，SÍV，对图中任一条边e，若至少一个端点在S中，则称S为G的一个顶点覆盖.若对每一个顶点i都有相应的非负权值w，则寻找包含顶点权i值之和最小的顶点覆盖就是顶点覆盖问题.此问题有广泛的应用，例如在实验数据统计、航[1][1,2]空调度、有效测试等方面.顶点覆盖问题可以归结为下面的整数规划模型：ì*1ïMinw=åiÎVwixiï2(VC)ís.t.xi+xj³1(i,j)ÎEïxÎ{0,1}iÎViïî这个问题是一个典型的NP-hard问题，没有多项式时间算法，本文研究的主要目的是把顶点覆盖问题松弛为半定规划模型，利用

3、多项式时间算法求解所得到半定规划松弛模型，从而得到原问题的一个下界.2.半定规划松弛我们利用下面的定理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—），男，河南汝阳人，西安电子科技大学博士生，研究方向为半定规划的算法及应用______________________________

4、_________________________________________________中国科技论文在线www.paper.edu.cn证明对"x,xÎ{0,1)i,jÎVij由于x+x³1，故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，则可以得到下面整数规划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)的最优值为Q(VCP)，(VCP)的最优值为Q(VCP)，显然'Q(VCP)£Q(VCP)，然而在(VCP)的最优解y中若有y、y满足约束ij***(-1-y)(-1-y)=0，则对所有这样的i、j，令y=-y，y=-y，其余y=y得ijiijjii*''到的y是(VCP)的可行解，并且对应的(VCP)的目标值与(VCP)的目标值相等，这样可'''以得到Q(VCP)³Q(VCP)，由上面证明

6、可知Q(VCP)=Q(VCP),因此(VCP)和(VCP)是等价的.综上所述(VC)和(VCP)是等价的.对于(VCP)，我们可以松弛为下面半定规划模型：_______________________________________________________________________________中国科技论文在线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，其余元素皆