Solving the maximum vertex weight clique problem via binary quadratic programming

详细信息    查看全文

• 作者：Yang Wang ; Jin-Kao Hao ; Fred Glover ; Zhipeng Lü…
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：32
• 期：2
• 页码：531-549
• 全文大小：472 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886
• 卷排序：32

文摘

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.KeywordsMaximum vertex weight cliqueBinary quadratic programmingProbabilistic tabu search