Speeding up branch and bound algorithms for solving the maximum clique problem

被引：22

作者：

Maslov, Evgeny ^{[1
]}

Batsyn, Mikhail ^{[1
]}

Pardalos, Panos M. ^{[1
,2
]}

机构：

[1] Natl Res Univ, Higher Sch Econ, Lab Algorithms & Technol Networks Anal, Niznhy Novgorod, Russia

[2] Univ Florida, Ctr Appl Optimizat, Gainesville, FL 32611 USA

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2014年 / 59卷 / 01期

关键词：

Maximum clique problem; Branch and bound algorithm; Heuristic solution; Graph colouring; SEARCH;

D O I：

10.1007/s10898-013-0075-9

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (J Heuristics 18(4):525-547, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.

引用

页码：1 / 21

页数：21

共 31 条

[1] Fast local search for the maximum independent set problem [J].