Combining Clustered Adaptive Multistart and Discrete Dynamic Convexized Method for the Max-Cut Problem  

作　　者：Geng Lin Wenxing Zhu 

机构地区：[1]Department of Mathematics,Minjiang University,Fuzhou 350108,China [2]Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University,Fuzhou 350002,China

出　　处：《Journal of the Operations Research Society of China》2014年第2期237-262,共26页中国运筹学会会刊（英文）

基　　金：supported partially by the National Natural Science Foundation of China(Nos.11226236 and 11301255);the Natural Science Foundation of Fujian Province of China(No.2012J05007);the Science and Technology Project of the Education Bureau of Fujian,China(Nos.JA13246 and JK2012037).

摘　　要：Given an undirected graph with edge weights,the max-cut problem is to find a partition of the vertices into twosubsets,such that the sumof theweights of the edges crossing different subsets ismaximized.Heuristics based on auxiliary function can obtain high-quality solutions of the max-cut problem,but suffer high solution cost when instances grow large.In this paper,we combine clustered adaptive multistart and discrete dynamic convexized method to obtain high-quality solutions in a reasonable time.Computational experiments on two sets of benchmark instances from the literature were performed.Numerical results and comparisons with some heuristics based on auxiliary function show that the proposed algorithm is much faster and can obtain better solutions.Comparisons with several state-ofthe-science heuristics demonstrate that the proposed algorithm is competitive.

关 键 词：MAX-CUT Local search Dynamic convexized method Clustered adaptive multistart 

分 类 号：O15[理学—数学]