Speeding up branch and bound algorithms for solving the maximum clique problem
详细信息 查看全文
- 作者：Evgeny Maslov (1)
Mikhail Batsyn (1)
Panos M. Pardalos (1) (2) - 关键词：Maximum clique problem ; Branch and bound algorithm ; Heuristic solution ; Graph colouring ; 05C69 ; 05C85 ; 90C27 ; 90C59 ; 90 ; 08
- 刊名：Journal of Global Optimization
- 出版年：2014
- 出版时间：May 2014
- 年：2014
- 卷：59
- 期：1
- 页码：1-21
- 全文大小：436 KB
- 参考文献：1. Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525-47 (2012). doi:10.1007/s10732-012-9196-4 CrossRef
2. Balas, E., Yu, C.S.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15(4), 1054-068 (1986) CrossRef
3. Bertoni, A., Campadelli, P., Grossi, G.: A discrete neural algorithm for the maximum clique problem: analysis and circuit implementation. In: Proceedings of Workshop on Algorithm, Engineering, WAE-7, pp. 84-1 (1997)
4. Boginski, V., Butenko, S., Pardalos, P.M.: On structural properties of the market graph. In: Nagurney, A. (ed.) Innovations in Financial and Economic Networks, pp 29-5. Edward Elgar Publishing, London (2003)
5. Bomze, I., Budinich, M., Pardalos, P.M., Pelillo, M.: The Maximum Clique Problem. Handbook of Combinatorial Optimization. Kluwer, Dordrecht (1999)
6. Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575-77 (1973). doi:10.1145/362342.362367 CrossRef
7. Brouwer, A., Shearer, J., Sloane, N., Smith, W.: A new table of constant weight codes. IEEE Trans. Inf. Theory 36(6), 1334-380 (1990). doi:10.1109/18.59932 CrossRef
8. Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics. Eur. J. Oper. Res. 173(1), 1-7 (2006). doi:10.1016/j.ejor.2005.05.026 CrossRef
9. Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375-82 (1990). doi:10.1016/0167-6377(90)90057-C CrossRef
10. Du, D., Pardalos, P.M.: Handbook of Combinatorial Optimization, Supplement vol A, p. 648. Springer, Berlin (1999)
11. Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA -2), pp 485-98. Springer, London, UK (2002)
12. Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6(2), 109-33 (1995). doi:10.1007/BF01096763 CrossRef
13. Funabiki, N., Takefuji, Y., Lee, K.C.: A neural network model for finding a near-maximum clique. J. Parallel Distrib. Comput. 14(3), 340-44 (1992). doi:10.1016/0743-7315(92)90072-U
14. Glover, F., Laguna, M.: Tabu Search. Kluwer, Dordrecht (1997) CrossRef
15. Grosso, A., Locatelli, M., Pullan, W.: Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14(6), 587-12 (2008). doi:10.1007/s10732-007-9055-x CrossRef
16. Jenelius, E., Petersen, T., Mattsson, L.: Importance and exposure in road network vulnerability analysis. Transp. Res. Part A: Policy Pract. 40(7), 537-60 (2006). doi:10.1016/j.tra.2005.11.003
17. Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347-59 (1992). doi:10.1002/rsa.3240030402 CrossRef
18. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85-03. Plenum, New York (1972) CrossRef
19. Konc, J., Janezic, D.: An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58, 569-90 (2007)
20. Kopf, R., Ruhe, G.: A computational study of the weighted independent set problem for general graphs. Found. Control Eng. 12, 167-80 (1987)
21. Li, C.M., Quan, Z.: Combining graph structure exploitation and propositional reasoning for the maximum clique problem. In: Proceedings of the 2010 22nd IEEE International Conference on Tools with Artificial Intelligence—Volume 01 (ICTAI-0), pp 344-51. IEEE, Arras, France (2010a)
22. Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), pp. 128-33. AAAI Press, Atlanta, USA (2010b)
23. Marchiori, E.: Genetic, iterated and multistart local search for the maximum clique problem. In: Applications of Evolutionary Computing, Springer, LNCS, pp. 112-21. Springer, Berlin (2002)
24. Matula, D.W., Marble, G., Isaacson, J.D.: Graph coloring algorithms. In: Read, R.C. (ed.) Graph Theory and Computing, pp 109-22. Academic Press, New York (1972)
25. Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161-62 (1955)
26. Pullan, W., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Int. Res. 25(1), 159-85 (2006)
27. Singh, A., Gupta, A.K.: A hybrid heuristic for the maximum clique problem. J. Heuristics 12(1-), 5-2 (2006). doi:10.1007/s10732-006-3750-x CrossRef
28. Sloane, N.J.A.: Unsolved problems in graph theory arising from the study of codes. Graph Theory Notes NY 18(11), 11-0 (1989)
29. Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95-11 (2007) CrossRef
30. Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the 4th International Conference on Discrete Mathematics and Theoretical Computer Science (DMTCS-3), pp. 278-89. Springer, Berlin, Heidelberg (2003)
31. Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., Wakatsuki, M.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of the 4th International Conference on Algorithms and Computation (WALCOM-0), pp. 191-03. Springer, Berlin, Heidelberg (2010). doi:?10.1007/978-3-642-11440-3_18 - 作者单位：Evgeny Maslov (1)
Mikhail Batsyn (1)
Panos M. Pardalos (1) (2)
1. Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, 136 Rodionova Street, Niznhy Novgorod, Russia
2. Center of Applied Optimization, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA - ISSN：1573-2916
文摘
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-47, 2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.