第61卷 第3期吉林大学学报(理学版)V o l .61 N o .32023年5月J o u r n a l o f J i l i nU n i v e r s i t y (S c i e n c eE d i t i o n )M a y2023d o i :10.13413/j .c n k i .jd x b l x b .2022255基于半定规划的多约束图划分问题王晓瑜1,刘红卫1,王 婷1,丁玉婉1,游海龙2(1.西安电子科技大学数学与统计学院,西安710126;2.西安电子科技大学微电子学院,西安710071)摘要:提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.关键词:图划分;半定规划;背包问题;组合优化中图分类号:O 221.7 文献标志码:A 文章编号:1671-5489(2023)03-0540-07M u l t i -c o n s t r a i n tG r a p hP a r t i t i o n i n g Pr o b l e m B a s e d o nS e m i d e f i n i t eP r o g r a m m i n gWA N G X i a o y u 1,L I U H o n g w e i 1,WA N G T i n g 1,D I N G Y u w a n 1,Y O U H a i l o n g2(1.S c h o o l o f M a t h e m a t i c s a n dS t a t i s t i c s ,X i d i a nU n i v e r s i t y ,X i a n 710126,C h i n a ;2.S c h o o l o f M i c r o e l e c t r o n i c s ,X i d i a nU n i v e r s i t y ,X i a n 710071,C h i n a )A b s t r a c t :W e p r o p o s e d a r e c u r s i v e d i c h o t o m y a l g o r i t h mt os o l v e t h e g r a p h p a r t i t i o n i n gpr o b l e m w i t h v e r t e x w e i g h tc o n s t r a i n t .F i r s t l y ,t h ei n t e r i o r p o i n t m e t h o d w a s u s e dt os o l v et h es e m i d e f i n i t e p r o g r a mm i n g r e l a x a t i o n m o d e l w i t h o u t v e r t e x w e i g h t c o n s t r a i n t .S e c o n d l y,t h ei n i t i a lf e a s i b l e s o l u t i o ns a t i s f y i n g t h ev e r t e x w e i g h tc o n s t r a i n t w a so b t a i n e d b y h y p e r p l a n er o u n d i n g a l go r i t h m.T h i r d l y ,t h e h e u r i s t i c a l g o r i t h m w a s f u r t h e r d e s i g n e d t o l o c a l l y i m p r o v e t h e i n i t i a l f e a s i b l e p a r t i t i o n t o o b t a i n t h eo p t i m a l p a r t i t i o nr e s u l t .T h ee x p e r i m e n t a l r e s u l t ss h o wt h a t t h e p r o p o s e da l g o r i t h m c a n o b t a i n t h eh i g h q u a l i t y s o l u t i o n t o t h em u l t i -c o n s t r a i n t g r a p h p a r t i t i o n i n gp r o b l e mi na s h o r t t i m e .K e y w o r d s :g r a p h p a r t i t i o n i n g ;s e m i d e f i n i t e p r o g r a mm i n g ;k n a p s a c k p r o b l e m ;c o m b i n a t o r i a l o p t i m i z a t i o n 收稿日期:2022-06-11.第一作者简介:王晓瑜(1998 ),女,汉族,硕士研究生,从事图划分问题的研究,E -m a i l :w x yh n d w l @163.c o m.通信作者简介:刘红卫(1967 ),男,汉族,博士,教授,博士生导师,从事最优化理论的研究,E -m a i l :h w l i u x i d i a n @163.c o m.基金项目:广东省重点领域研发计划项目(批准号:2019B 010140001).超大规模集成电路(V L S I)设计[1]㊁电信[2]和并行运算[3]等问题在数学建模时通常被抽象为图的形式,图分割是其基本算法之一.但随着数据规模的不断增长,图划分问题变得更具有多面性和挑战性.该问题旨在将图G =(V ,E )的顶点在一定容量或基数的约束下划分为几个组,使得所求最优解的割边总权重最小.由于该问题是N P -完备的,因此研究寻找近似解的方法有一定的意义.图划分问题源于针对图的k 划分问题设计的一个二次程序.随着新的图划分问题的不断发展,多种求解方法也应时而生,例如:K e r n i g h a n 等[4]考虑将图划分为给定大小的子集,并设计了一种启发式方法进行求解;C h r i s t o f i d e s 等[5]对图的二分问题提出了树搜索方法,有效地限制了子集中节点的数目;L a b b é等[6]针对团划分问题,利用分支定界算法将图划分为有上下界的子集.通过将图划分问题重新表述为一个非凸二次规划问题,人们提出了一些有效的近似算法.Copyright ©博看网. All Rights Reserved.G o e m a n s 等[7]对非负加权图提出了基于半定松弛的舍入算法,该算法对k =2可实现0.878的近似界;F r i e z e 等[8]针对图的多分问题扩展了文献[7]的舍入算法,并分析了所设计算法在不同划分块下的理论近似比.在近似算法的基础上,分支定界法也被设计用于求解图划分问题.R e n d l 等[9]利用基于半定松弛的分支定界算法B i q M a c 求解了经典的最大割问题;D e l l i n g 等[10]根据分支定界框架提出了求解最小图二分的精确组合算法,其下界是通过启发式方法得到的;L u 等[11]提出了一种新的分支定界算法,直接选择一个合适的向量生成k 个子问题,设计了减少枚举过程中子问题冗余性的策略.背包问题作为组合优化问题的基本问题之一,已在多学科领域得到广泛研究.本文主要关注具有背包约束的图划分(G P K C )问题,图中的每个顶点都被赋予一个权值,每个划分集合都需满足背包约束.R e c a l d e 等[12]将背包问题转化为整数规划问题,并设计了一种基于分支定界的精确算法来求解该问题.N g u ye n [13]针对G P K C 问题提出了一个严格的L P 松弛方法,并利用启发式方法建立解的上界.由于基于半定规划在生成具有背包约束[14]和k -均分问题的二次问题紧下界方面性能较好,因此研究者们将半定规划松弛应用于G P K C 问题中.W i e g e l e 等[15]通过引入带有非负约束的紧的半定松弛,得到了多达500个顶点的G P K C 问题的高质量下界,同时,所设计的启发式算法相比于文献[13]可得到一个更严格的上界,但该算法尚未考虑在给定划分块数的情形下是否能满足划分结果.对于大规模划分的实际应用,也可考虑将启发式和元启发式方法用于寻找足够好的次优解.A r r 췍i z 等[16]将模拟退火和禁忌搜索方法相结合求解图二分问题,其算法可花费较小的计算代价而得到高质量的解.B e n l i c 等[17]基于多级划分和禁忌搜索提出了一种混合算法,把禁忌搜索作为多级框架的细化算法,用于解决图的平衡划分问题,其算法性能优于图划分软件M e t i s 和C h a c o .基于此,本文考虑带有顶点权重约束的图的二划分问题,利用图的二划分方法递归地进行图的多分,并将所设计的算法与W i e ge l e 等[15]提出的图的多分算法进行比较,验证该算法的有效性.1 图的二划分1.1 模型的建立给定一个赋权无向图G =(V ,E ),其中V ={1,2, ,n }为点集,n 为图G 中的顶点个数,E 为边集,W 为图G 的邻接矩阵,ωi j 为对应边[i ,j ]ɪE 的权值,则∀i ʂj ,有ωi j =ωji ,且ωi i =0.记b i 为顶点i 的非负权重,U 为划分集合容量上限.G P K C 问题要求将图的顶点V 划分为两部分,即S 和V \S ,使得在不同集合中的顶点满足切边总权重最小,且每组的顶点权重和不超过容量上限U ,则目标函数可写为f (S ,V \S )=m i n ði ɪS ,j ɪV\S ωi j .(1) 令x i 表示顶点i ,若顶点i 属于集合S ,则x i 取值为1,反之,x i 取值为-1.于是未考虑顶点权重约束的图二划分问题可写为如下二次函数形式:f (x )=m i n 14ði ,j ɪVωi j (1-x i x j ), x ɪ{-1,1}n .(2) 引入与W 相关的L a p l a c e 矩阵L =d i a g (W e )-W ,其中e ɪℝn 是一个分量全为1的列向量,d i a g (W e )是一个对角矩阵,其对角项为向量W e 中的元素.于是图二划分模型(2)等价于如下二次整数规划形式(I Q P ):m i n f (x )=14x T Lx ,s .t .x ɪ{-1,1}nìîíïïï. 令B 表示顶点的权重向量,则第i 个顶点的权重为b i ,U =(u 1,u 2)T表示划分集合的资源上限,u r (r ɪ{1,2})表示第r 块划分集合的上限,则求解模型(G P K C )为m i n 14x T{}L x ,s .t .x +e æèçöø÷2T B ɤu 1,e -x æèçöø÷2T B ɤu 2,x ɪ{-1,1}n ìîíïïïï.145 第3期 王晓瑜,等:基于半定规划的多约束图划分问题Copyright ©博看网. All Rights Reserved.令X =x x T ,其中x ɪ{-1,1}n ,则有X ⪰0,X i i =x 2i =1且X 是秩1矩阵.反之,若任意对称矩阵X 具有X ⪰0,X i i =1,r a n k (X )=1的性质,则存在x ɪ{-1,1}n,使得X =x x T .由于x T L x =t r (x T L x )=t r (L x x T )=t r (L X ),(3)因此利用文献[18]中矩阵迹运算的性质,可将问题(G P K C )重写为m i n 14tr (L X {}),s .t .d i a g (X )=e , t r 0B B T 2B Tæèçöø÷e x x T x x T æèçöø÷1ɤ4u 1, t r 0-B -B T 2B T æèçöø÷e x x T x x T æèçöø÷1ɤ4u 2, X ⪰0, r a n k (X )=1ìîíïïïïïïïïïïïï,(4)其中矩阵x x T x xTæèçöø÷1⇔x æèçöø÷1(x T 1)(5)是半正定的秩1矩阵,且对角线元素均为1.记C =L 0æèçöø÷00,Y =x x T x xTæèçöø÷1,Q =0B B T2B Tæèçöø÷e ,P =0-B -B T2B Tæèçöø÷e ,若去掉r a n k (X )=1的约束,则可得增加顶点约束后的半定规划松弛模型(G P K C 1):m i n14t r (C Y {}),s .t .d i a g (Y )=e ,t r (QY )ɤ4u 1,t r (P Y )ɤ4u 2,Y ⪰0{. 上述半定规划松弛模型(G P K C 1)求解较复杂,但在不考虑顶点权重约束的情形下,原问题可行,半定规划及其对应的对偶模型是严格可行的,且易找到其严格可行点,因此本文考虑使用内点法求解去掉顶点权重约束的更松弛的半定规划,再对求得的解进行随机扰动,并在随机扰动过程中增加对解的可行性判定,以保证所得解满足顶点权重约束.去掉顶点权重约束的半定规划松弛模型(S D P )为m i n14t r (C Y {}),s .t .d i a g(Y )=e ,Y ⪰0{,其对应的对偶形式(D S D P )为m a x 14e T{}y ,s .t .d i a g (y )-C =Z , Z ⪰0ìîíïïïï.本文采用内点法[19]求解模型(S D P )和(D S D P ),起始点Y ʒ=I n ˑn ,y ʒ=μe ,Z ʒ=μI -C /4是可行的且在内部,其中μ是使得Z 为正定矩阵的常数.1.2 超平面舍入算法计算最小化问题的上界通常利用启发式方法确定原问题的可行解.对于求得的模型(S D P )的最优解,主要利用G o e m a n s 等[7]对最大割问题提出的算法以及F r i e z e 等[8]提出的改进的随机舍入算法,设计图二分的超平面舍入算法以得到问题(G P K C )的近似最优解,即图二分的初始划分.下面给出完整的图二分超平面舍入算法.算法1 图二分的超平面舍入算法.输入:模型(S D P )的最优解Y ,目标矩阵C ,顶点权重向量B ,资源上限U ,抽样次数p ;初始化:x =[],f =[];245 吉林大学学报(理学版) 第61卷Copyright ©博看网. All Rights Reserved.步骤1)对Y 做C h o l e s k y 分解D TD =Y 得到D ;步骤2)f o r t =1,2, ,p步骤3) 取单位球面S n 上服从均匀分布的单位向量s t ;步骤4) x t =s g n (D T s t ),f t =x T t C x t ,x =[x ,x t ],f =[f ,ft ];步骤5)e n d步骤6)取m i n (f )对应的x 赋值于y ,并令e r r =m a x {(y +e )T B -2u 1,0}+m a x {(e -y )TB -2u 2,0};步骤7)i f∃e r r =0步骤8) 输出对应的y ;步骤9)e l s e步骤10) 对y 做一邻域调整得y 1,令f 1=y T1C y1,计算相应的e r r 1值;步骤11) 令e r r =m a x {(x +e )T B -2u 1,0}+m a x {(e -x )T B -2u 2,0};步骤12) i f∃e r r 1=0步骤13) 若∃e r r =0,则输出m i n (f )和m i n (f 1)对应的[x ,y 1];步骤14) e l s e步骤15)若∃e r r =0,输出m i n (f )对应的x ;反之,对x 做一邻域调整得x 1,计算相应的f 和e r r 值;步骤16)若∃e r r =0,输出m i n (f )对应的x 1;反之,输出调整后m i n (f )和m i n (e r r )值对应的[x 1,y1];步骤17) e n d步骤18)e n d输出:目标值最优的划分.算法1中步骤10)的邻域调整是指:令P 1={i y (i )=1},P 2={i y (i )=-1},将P 1中单点逐次移动到P 2,再将P 2中单点逐次移动到P 1,得到相应的y 1.1.3 均衡因子在对问题(2)中目标函数值进行极小化时,由于在实际问题中常将ωi j 视为非负数,因此当x i 和x j 均为1或均为-1,即顶点全划分在同一个集合时,可得最小目标值0,与本文划分思想不符.为避免上述情形发生,同时减少划分导致的资源浪费,本文考虑在目标函数中添加一个均衡因子,用于控制划分结果的均衡性.用顶点权重向量B 除以顶点权重的最大值,得列向量β,进一步可得矩阵A =ββT,此时由模型(S D P )可得新的目标矩阵C =C +a A ,其中a 是均衡因子,本文令a =300.1.4 二分图的启发式算法二分图启发式算法可用于提高各种组合问题的解决方案质量[20].在利用超平面舍入算法得到初始划分后,本文用该方法进一步改进划分的质量,下面给出改进的二分图启发式算法.给定划分结果(P 1,P 2),在满足容量限制的条件下,寻找使目标函数值更小的划分结果.算法2 图划分问题的启发式算法.输入:划分组合(P 1,P 2),目标值f *,目标矩阵C ,划分矩阵R ,停止误差ε;初始化:δ=0;步骤1)(s ,t )ѳa r g m a x i ɪP 1,j ɪP 2ðk ʂi ,k ɪP 1L jk -ðk ʂj ,k ɪP 2L jk +ðk ʂj ,k ɪP 2L i k -ðk ʂi ,k ɪP 1L {}i k ;步骤2)Δc o s t ѳðk ʂs ,k ɪP 1L t k -ðk ʂt ,k ɪP 2L t k +ðk ʂt ,k ɪP 2L s k -ðk ʂs ,k ɪP 1L s k ;步骤3)w h i l e Δc o s t >ε步骤4) P 1ѳP 1-{s }+{t },P 2ѳP 2-{t }+{s };步骤5) (s ,t )ѳa r g m a x i ɪP 1,j ɪP 2ðk ʂi ,k ɪP 1L jk -ðk ʂj ,k ɪP 2L jk +ðk ʂj ,k ɪP 2L i k -ðk ʂi ,k ɪP 1L {}i k ;步骤6) Δc o s t ѳðk ʂs ,k ɪP 1L t k -ðk ʂt ,k ɪP 2L t k +ðk ʂt ,k ɪP 2L s k -ðk ʂs ,k ɪP 1L s k ;345 第3期 王晓瑜,等:基于半定规划的多约束图划分问题 Copyright ©博看网. All Rights Reserved.445吉林大学学报(理学版)第61卷步骤7)e n d步骤8)f o r t=1ʒl e n g t h(P i),其中iɪ{1,2},jɪ{1,2}\i步骤9)rѳP i(t),令P iѳP i-{r},P jѳP j+{r};步骤10)H=C R,δ1=C(r,r)-H(r,i)+H(r,j);步骤11)i fδ1<δ步骤12)δѳδ1,(P*1,P*2)ѳ(P1,P2),f*ѳf*+δ;步骤13)e n d步骤14)e n d输出:改进的划分结果(P*1,P*2)及其对应的目标值f*.2图的多分问题图的多分问题是将图的顶点集划分为多个集合,使得各划分集合在顶点权重不超过资源上限的情形下,连接不同子集的边的总权值最小化.由于所建模型有多个约束条件,而内点算法又因内存问题无法求解大规模实例,因此针对图的多分问题,本文利用改进的图二分算法设计递归二分的图多分算法.在图二划分不可行的情形下,需额外增加资源满足图二分的可行性.为避免后续划分时因资源不足而导致划分结果不可行的情况,本文引进缩小资源的参数m,利用增加资源后新资源的m倍进行划分,令m=0.7.从而在保证二分可行的同时,避免出现资源不足的情况.下面给出增加资源的全过程.算法3资源变更算法.输入:前两块资源二分的结果x*,资源上限U,剩余的资源块φ,缩小资源参数m;步骤1)判断x*的可行性,即顶点权重是否满足资源约束,将不可行的块记入ψ;步骤2)w h i l eψ非空步骤3) w h i l eφ非空&ψ非空步骤4)uψ(1)=m[uψ(1)+uφ(1)],φ(1)=[],ψ(1)=[];步骤5)e n d步骤6)进行随机扰动,得到新的划分结果x;步骤7)判断x的可行性,将不可行的块记入ψ;步骤8)e n d步骤9)当资源增加使得二分可行时,将增加资源后的大块及其对应的顶点按相应的初始资源大小继续二分,直至得到最后的划分结果P;输出:划分结果P.在得到图多分的划分结果后,对划分的子集数k进行排列组合C2k,分别对组合中每对(P i,P j)用二分图的的启发式算法,使划分集合在满足资源限制的条件下,得到更优的目标函数值.最后将未充分利用资源的集合在保证划分可行的前提下进行合并,减少资源浪费的同时改进目标函数值.下面给出利用递归二分求解图多分问题的全过程.算法4递归二划分求解图多分问题.步骤1)建立模型(G P K C),利用内点法求解半定规划松弛模型(S D P),对模型(S D P)最优解Y用超平面舍入算法(算法1)得到图二分的初始划分;步骤2)若二分不可行,则转步骤3);步骤3)利用算法3对不可行的划分集合增加划分资源,直至二分可行,再将增加资源后的二划分集合继续进行二分,最后得到图的k划分结果;步骤4)利用图的启发式算法(算法2)对图的k划分中每两个划分集合的顶点进行调整,以得到使目标函数值更小的划分;Copyright©博看网. All Rights Reserved.步骤5)合并未充分利用资源的集合.3 数值模拟下面用MA T L A BR 2021b 实现本文算法,数据来源于文献[15]中部分随机生成图数据以及文献[13]中生成的大规模数据,其中(G P K C r a n d 20),(G P K C r a n d 50),(G P K C r a n d 80)分别表示邻接矩阵中非零边权值占比20%,50%,80%的图.将利用递归二划分算法求得的最小切边权值与文献[15]中对G P K C 问题D N N 松弛模型所设计的V c +2o p t 算法求得的切边权值进行比较,并用g a p 表示两者切边权值之间的差距,其中g a p =(递归二划分算法所得目标函数值-(V c +2o p t 算法所得目标函数值))/(V c +2o p t 算法所得目标函数值).为保证实验结果的合理性,本文对每个测试样例均进行10次实验,取实验最好结果及平均的C P U 时间,结果列于表1.表1 递归二划分算法与V c +2o pt 算法的实验结果T a b l e 1 E x p e r i m e n t a l r e s u l t s o f r e c u r s i v e b i s e c t i o na l g o r i t h ma n dV c +2o p t a l go r i t h m 划分图的顶点个数给定划分块的容量上限V c +2o pt 算法目标函数值C P U 时间/s 递归二划分算法目标函数值C P U 时间/sg a p /%50013356149048474184896914-0.161677037(G P K C r a n d 20)54084846353159484677850.05021545428866980799149398410060.336562333148401074286137310734737-0.0756781711292310882801370108955080.116697909746811375231481113502711-0.2194241353975116882518051171719200.24759908550013128613018297394130446550.202484351(G P K C r a n d 50)561012183890156021833378-0.0253217882924425322051462254125490.35735653315747275330314742754371100.03878977413176279626014742800167110.139722343792028980631580289730215-0.0262589184249297915718052982538250.1134884805001321351986063752319842186-0.092897355(G P K C r a n d 80)5318635212443778351433910-0.19609547126965413247731344135674120.07736280215049445287632394463604140.24092294512806451933736754529146150.2170451117312469418826134703839200.2055946634071481458824844817132320.0528394121173321807826551072778029-5.868118572102563185878451288183233553-1.422919500540392470894515132477605670.27160210031751283686252390283211577-0.1673327781684230645875407731010741081.190600887 表1给出了递归二划分算法和V c +2o p t 算法对500和1173个顶点的划分结果以及各算法所花费的C P U 时间.由表1可见:递归二划分算法随着容量上限的减少,划分所需时间逐渐增加;由于本文提出的递归二划分算法是在考虑去掉顶点权重约束的情形下求解半定规划松弛模型,大幅度减小了求解模型的次数,且计算过程中迭代次数较少,从而在较短的时间内可得到递归二划分算法的较优解.此外,由两种算法所得函数值的差距g a p 可知:当g a p 为正,即递归二划分算法所得目标函数值比V c +2o p t 算法所得函数值大时,递归二划分算法可在较短时间内得到与V c +2o p t 算法函数值差距最大为1.19%的较优目标函数值;当g a p 为负时,表示递归二划分算法的函数值优于V c +2o p t 算法所得目标函数值,且两者所得目标函数值差距最多为5.87%.545 第3期 王晓瑜,等:基于半定规划的多约束图划分问题 Copyright ©博看网. All Rights Reserved.645吉林大学学报(理学版)第61卷综上所述,本文针对带有顶点权重约束的图多分问题,设计了递归的二划分算法.首先,考虑用内点法求解不加顶点权重约束的半定规划松弛模型;其次,通过随机扰动得到满足顶点权重约束的可行解;最后,利用启发式算法,对可行解进行局部改进得到更紧的上界.同时加入均衡因子以避免半定规划目标值为0以及因划分不均衡导致的资源浪费,并设计了求解后的划分合并算法.实验结果表明,本文提出的递归二划分算法可高效地求解带约束的图多分问题,得到了较优的划分结果.参考文献[1] C HOJD,R A J ES,S A R R A F Z A D E H M.F a s tA p p r o x i m a t i o nA l g o r i t h m so n M a x c u t,k-C o l o r i n g,a n d k-C o l o rO r d e r i n g f o rV L S IA p p l i c a t i o n s[J].I E E ET t r a n s a c t i o n s o nC o m p u t e r s,1998,47(11):1253-1266. [2] L I S S E R A,R E N D L F.G r a p h P a r t i t i o n i n g U s i n g L i n e a ra n d S e m i d e f i n i t e P r o g r a mm i n g[J].M a t h e m a t i c a lP r o g r a mm i n g,2003,95(1):91-101.[3] H E N D R I C K S O NB,K O L D A T G.G r a p hP a r t i t i o n i n g M o d e l s f o rP a r a l l e lC o m p u t i n g[J].P a r a l l e lC o m p u t i n g,2000,26(12):1519-1534.[4] K E R N I G HA NB W,L I N S.A n E f f i c i e n t H e u r i s t i cP r o c e d u r ef o rP a r t i t i o n i n g G r a p h s[J].T h eB e l lS y s t e mT e c h n i c a l J o u r n a l,1970,49(2):291-307.[5] C H R I S T O F I D E S N,B R O O K E R P.T h e O p t i m a l P a r t i t i o n i n g o f G r a p h s[J].S I AM J o u r n a lo n A p p l i e dM a t h e m a t i c s,1976,30(1):55-69.[6] L A B BÉM,ÖZ S O Y F A.S i z e-C o n s t r a i n e d G r a p h P a r t i t i o n i n g P o l y t o p e s[J].D i s c r e t e M a t h e m a t i c s,2010,310(24):3473-3493.[7] G O E MA N S M X,W I L L I AM S O NDP.I m p r o v e dA p p r o x i m a t i o nA l g o r i t h m s f o rM a x i m u mC u t a n dS a t i s f i a b i l i t yP r o b l e m sU s i n g S e m i d e f i n i t eP r o g r a mm i n g[J].J o u r n a l o f t h eA C M,1995,42(6):1115-1145.[8] F R I E Z E A,J E R R UM M.I m p r o v e d A p p r o x i m a t i o n A l g o r i t h m sf o r M a x k-C u t a n d M a x B i s e c t i o n[J].A l g o r i t h m i c a,1997,18(1):67-81.[9] R E N D L F,R I N A L D I G,W I E G E L E A.S o l v i n g M a x-C u tt o O p t i m a l i t y b y I n t e r s e c t i n g S e m i d e f i n i t e a n dP o l y h e d r a lR e l a x a t i o n s[J].M a t h e m a t i c a l P r o g r a mm i n g,2010,121(2):307-335.[10] D E L L I N GD,F L E I S C HMA N D,G O L D B E R G A V,e ta l.A n E x a c tC o m b i n a t o r i a lA l g o r i t h mf o r M i n i m u mG r a p hB i s e c t i o n[J].M a t h e m a t i c a l P r o g r a mm i n g,2015,153(2):417-458.[11] L U C,D E N G Z B.A B r a n c h-a n d-B o u n d A l g o r i t h m f o rS o l v i n g M a x-k-C u tP r o b l e m[J].J o u r n a lo f G l o b a lO p t i m i z a t i o n,2021,81(2):367-389.[12] R E C A L D ED,T O R R E SR,V A C A P.A nE x a c tA p p r o a c h f o r t h e M u l t i-c o n s t r a i n tG r a p hP a r t i t i o n i n g P r o b l e m[J].E U R OJ o u r n a l o nC o m p u t a t i o n a lO p t i m i z a t i o n,2020,8(3/4):289-308.[13] N G U Y E N DP.C o n t r i b u t i o n s t oG r a p hP a r t i t i o n i n g P r o b l e m s u n d e rR e s o u r c eC o n s t r a i n t s[D].P a r i s:U n i v e r s i téP i e r r e e tM a r i eC u r i e,2016.[14] H E L M B E R G C,R E N D L F,W E I S MA N T E L R.Q u a d r a t i c K n a p s a c k R e l a x a t i o n s U s i n g C u t t i n g P l a n e sa n dS e m i d e f i n i t e P r o g r a mm i n g[C]//I n t e r n a t i o n a l C o n f e r e n c e o n I n t e g e r P r o g r a mm i n g a n d C o m b i n a t o r i a l O p t i m i z a t i o n.B e r l i n:S p r i n g e r,1996:175-189.[15] W I E G E L E A,Z HA O S D.S D P-B a s e dB o u n d sf o rG r a p h P a r t i t i o nv i aE x t e n d e d A D MM[J].C o m p u t a t i o n a lO p t i m i z a t i o na n dA p p l i c a t i o n s,2022,82(1):251-291.[16] A R RÁI ZE,O L I V O O.C o m p e t i t i v e S i m u l a t e dA n n e a l i n g a n dT a b uS e a r c hA l g o r i t h m s f o r t h eM a x-C u t P r o b l e m[C]//P r o c e e d i n g s o ft h e11t h A n n u a l C o n f e r e n c e o n G e n e t i c a n d E v o l u t i o n a r y C o m p u t a t i o n.N e w Y o r k:A s s o c i a t i o n f o rC o m p u t i n g M a c h i n e r y,2009:1797-1798.[17] B E N L I C U,HA O JK.A n E f f e c t i v e M u l t i l e v e lT a b uS e a r c h A p p r o a c hf o rB a l a n c e d G r a p h P a r t i t i o n i n g[J].C o m p u t e r s&O p e r a t i o n sR e s e a r c h,2011,38(7):1066-1075.[18] K L E R K ED.A s p e c t s o f S e m i d e f i n i t eP r o g r a mm i n g[M].2n de d.N e w Y o r k:S p r i n g e r,2002:214-216.[19] H E L M B E R GC,R E N D LF,V A N D E R B E IRJ,e t a l.A nI n t e r i o r-P o i n tM e t h o df o rS e m i d e f i n i t eP r o g r a mm i n g[J].S I AMJ o u r n a l o nO p t i m i z a t i o n,1996,6(2):342-361.[20] L I NS.C o m p u t e rS o l u t i o n so ft h e T r a v e l i n g S a l e s m a n P r o b l e m[J].B e l lS y s t e m T e c h n i c a lJ o u r n a l,1965,44(10):2245-2269.(责任编辑:李琦)Copyright©博看网. All Rights Reserved.。
