×

zbMATH — the first resource for mathematics

An efficient local search algorithm for solving maximum edge weight clique problem in large graphs. (English) Zbl 1442.90159
Summary: Maximum vertex weight clique problem (MVWCP) and maximum edge weight clique problem (MEWCP) are two significant generalizations of maximum clique problem (MCP), and can be widely used in many real-world applications including molecular biology, broadband network design and pattern recognition. Recently, breakthroughs have been made for solving MVWCP in large graphs, resulting in several state-of-the-art algorithms, such as WLMC, FastWClq and LSCC + BMS. However, less attention has been paid to solving MEWCP in large graphs. In this paper, we present an efficient Stochastic Local Search (SLS) algorithm for MEWCP by combining clique construction, local search and graph reduction, resulting in a new algorithm named ReConSLS. We also propose a new upper bound function for edge weighted graphs which is essential for graph reduction. Extensive experiments on a wide range of large graphs demonstrate that ReConSLS surpasses state-of-the-art SLS competitors on the majority of testing graphs.
MSC:
90C27 Combinatorial optimization
Software:
KONECT; CCASat; CCLS; CCEHC; NuMVC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramé, A.; Habet, D.; Toumi, D., Improving configuration checking for satisfiable random k-sat instances, Ann Math Artif Intell, 79, 1-3, 5-24 (2017) · Zbl 1404.68136
[2] Alidaee, B.; Glover, F.; Kochenberger, G.; Wang, H., Solving the maximum edge weight clique problem via unconstrained quadratic programming, Eur J Oper Res, 181, 2, 592-597 (2007) · Zbl 1131.90046
[3] Balasundaram, B.; Butenko, S.; Resende, MGC; Pardalos, PM, Graph domination, coloring and cliques in telecommunications, Handbook of optimization in telecommunications (2006), Boston: Springer, Boston · Zbl 1118.90008
[4] Ballard, DH; Brown, CM, Computer vision (1982), Englewood Cliffs: Prenice-Hall, Englewood Cliffs
[5] Battiti, R.; Protasi, M., Reactive local search for the maximum clique problem 1, Algorithmica, 29, 4, 610-637 (2001) · Zbl 0985.68016
[6] Benlic, U.; Hao, JK, Breakout local search for maximum clique problems, Comput Oper Res, 40, 1, 192-206 (2013) · Zbl 1349.90005
[7] Cai S (2015) Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: Proceedings of IJCAI 2015, pp 747-753
[8] Cai S, Su K (2012) Configuration checking with aspiration in local search for sat. In: AAAI
[9] Cai, S.; Su, K., Local search for boolean satisfiability with configuration checking and subscore, Artif Intell, 204, 75-98 (2013) · Zbl 1334.68200
[10] Cai S, Lin J (2016) Fast solving maximum weight clique problem in massive graphs. In: Proceedings of IJCAI 2016, pp 568-574
[11] Cai, S.; Su, K.; Sattar, A., Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif Intell, 175, 9-10, 1672-1696 (2011) · Zbl 1225.68242
[12] Cai, S.; Su, K.; Luo, C.; Sattar, A., NuMVC: an efficient local search algorithm for minimum vertex cover, J Artif Intell Res, 46, 687-716 (2013) · Zbl 1280.90098
[13] Carraghan, R.; Pardalos, PM, An exact algorithm for the maximum clique problem, Oper Res Lett, 9, 6, 375-382 (1990) · Zbl 0711.90080
[14] Fan Y, Li N, Li C, Ma Z, Latecki LJ, Su K (2017a) Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In: Proceedings of international joint conference on artificial intelligence (IJCAI), pp 622-630
[15] Fan Y, Ma Z, Su K, Li C, Rao C, Liu RH, Latecki L (2017b) A local search algorithm for the maximum weight clique problem in large graphs. In: 29rd IEEE international conference on tools with artificial intelligence (ICTAI) 2017. IEEE, pp 1099-1104
[16] Fang Z, Li CM, Qiao K, Feng X, Xu K (2014) Solving maximum weight clique using maximum satisfiability reasoning. In: Proceedings of the twenty-first European conference on artificial intelligence. IOS Press, pp 303-308 · Zbl 1366.90176
[17] Fomeni, FD, A new family of facet defining inequalities for the maximum edge-weighted clique problem, Optim Lett, 11, 1, 47-54 (2017) · Zbl 1398.90137
[18] Gouveia, L.; Martins, P., Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, EURO J Comput Optim, 3, 1, 1-30 (2015) · Zbl 1307.90109
[19] Jiang H, Li CM, Manya F (2017) An exact algorithm for the maximum weight clique problem in large graphs. In: AAAI, pp 830-838
[20] Karp, RM, Reducibility among combinatorial problems, J Symb Logic, 40, 4, 618-619 (1972)
[21] Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd international conference on world wide web. ACM, pp 1343-1350
[22] Li CM, Quan Z (2010) An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In: AAAI, vol 10, pp 128-133
[23] Li CM, Fang Z, Xu K (2013) Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In: 2013 IEEE 25th international conference on tools with artificial intelligence (ICTAI), pp 939-946. IEEE
[24] Li, R.; Wu, X.; Liu, H.; Wu, J.; Yin, M., An efficient local search for the maximum edge weighted clique problem, IEEE Access, 6, 10743-10753 (2018)
[25] Luo C, Su K, Cai S (2012) Improving local search for random 3-SAT using quantitative configuration checking. In: Proceedings of ECAI 2012, pp 570-575 · Zbl 1327.68225
[26] Luo, C.; Cai, S.; Su, K.; Wu, W., Clause states based configuration checking in local search for satisfiability, IEEE Trans Cybern, 45, 5, 1028-1041 (2015)
[27] Luo, C.; Cai, S.; Wu, W.; Jie, Z.; Su, K., CCLS: an efficient local search algorithm for weighted maximum satisfiability, IEEE Trans Comput, 64, 7, 1830-1843 (2015) · Zbl 1360.68786
[28] Luo, C.; Cai, S.; Su, K.; Huang, W., CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability, Artif Intell, 243, 26-44 (2017) · Zbl 1402.68163
[29] Park, K.; Lee, K.; Park, S., An extended formulation approach to the edge-weighted maximal clique problem, Eur J Oper Res, 95, 3, 671-682 (1996) · Zbl 0926.90086
[30] Pullan, W., Phased local search for the maximum clique problem, J Comb Optim, 12, 3, 303-323 (2006) · Zbl 1255.90122
[31] Pullan, W., Approximating the maximum vertex/edge weighted clique using local search, J Heuristics, 14, 2, 117-134 (2008) · Zbl 1173.90569
[32] Pullan, W.; Hoos, HH, Dynamic local search for the maximum clique problem, J Artif Intell Res, 25, 159-185 (2006) · Zbl 1182.68065
[33] Pullan, W.; Mascia, F.; Brunato, M., Cooperating local search for the maximum clique problem, J Heuristics, 17, 2, 181-199 (2011)
[34] Rossi, RA; Ahmed, NK, Coloring large complex networks, Soc Netw Anal Min, 4, 1, 228 (2014)
[35] San Segundo, P.; Rodríguez-Losada, D.; Jiménez, A., An exact bit-parallel algorithm for the maximum clique problem, Comput Oper Res, 38, 2, 571-581 (2011) · Zbl 1231.90369
[36] Shimizu S, Yamaguchi K, Masuda S (2018) A branch-and-bound based exact algorithm for the maximum edge-weight clique problem. In: International conference on computational science/intelligence & applied informatics. Springer, pp 27-47
[37] Tomita, E.; Kameda, T., An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, J Global Optim, 37, 1, 95-111 (2007) · Zbl 1127.90079
[38] Tomita E, Seki T (2003) An efficient branch-and-bound algorithm for finding a maximum clique. In: International conference on discrete mathematics and theoretical computer science, pp 278-289 · Zbl 1038.68565
[39] Wang Y, Cai S, Yin M (2016) Two efficient local search algorithms for maximum weight clique problem. In: Proceedings of AAAI 2016, pp 805-811
[40] Wu, Q.; Hao, JK; Glover, F., Multi-neighborhood tabu search for the maximum weight clique problem, Ann Oper Res, 196, 1, 611-634 (2012) · Zbl 1251.90378
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.