Document Zbl 1173.90565

Grosso, Andrea; Locatelli, Marco; Pullan, Wayne

Simple ingredients leading to very efficient heuristics for the maximum clique problem. (English) Zbl 1173.90565

J. Heuristics 14, No. 6, 587-612 (2008).

Summary: Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).

Cited in 27 Documents

MSC:

90C35	Programming involving graphs or networks
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

maximum clique; randomness;plateau search; penalties; restart rules

Software:

Max-AO; DIMACS; QUALEX

Cite Review PDF

Full Text: DOI

References:

[1]	Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem. Algorithmica 29(4), 610–637 (2001) · Zbl 0985.68016 · doi:10.1007/s004530010074
[2]	Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability–towards tight results. SIAM J. Comput. 27(3), 804–915 (1998) · Zbl 0912.68041 · doi:10.1137/S0097539796302531
[3]	Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, suppl. vol. A, pp. 1–74 (1999) · Zbl 1253.90188
[4]	Bomze, I.M., Pelillo, M., Stix, V.: Approximating the maximum weight clique using replicator dynamic. IEEE Trans. Neural Netw. 11(6), 1228–1241 (2000) · doi:10.1109/72.883403
[5]	Brockington, M., Culberson, J.C.: Camouflaging independent sets in quasi-random graphs, in Johnson and Trick (1996) · Zbl 0859.68066
[6]	Burer, S., Monteiro, R.D.C., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Prog. 94, 137–166 (2002) · Zbl 1023.90071 · doi:10.1007/s10107-002-0356-4
[7]	Busygin, S.: A new trust region technique for the maximum clique problem. Discrete Appl. Math. 154, 2080–2096 (2006) · Zbl 1111.90020 · doi:10.1016/j.dam.2005.04.010
[8]	de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[9]	Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Working paper, Univ. of Klagenfurt, available at http://www.optimization-online.org/DB_HTML/2005/03/1081.html (2005) · Zbl 1278.90299
[10]	Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. LNCS, vol. 2461, pp. 485–498 (2002) · Zbl 1019.90517
[11]	Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Wiley, New York (1977) · Zbl 0411.68039
[12]	Grosso, A., Locatelli, M., Della Croce, F.: Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. J. Heuristics 10, 135–152 (2004) · doi:10.1023/B:HEUR.0000026264.51747.7f
[13]	Grosso, A., Locatelli, M., Pullan, W.J.: Short communication, larger cliques for a DIMACS test. http://www.optimization-online.org/DB_HTML/2005/02/1054.html (2005)
[14]	Gvozdenovic, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. In: Integer Programming and Combinatorial Optimization: 11th International IPCO Conference. Lecture Notes in Computer Science, vols. 3509/2005, pp. 136–151. (2005) · Zbl 1119.05323
[15]	Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search for the maximum clique. Discrete Appl. Math. 145, 117–125 (2004) · Zbl 1058.90053 · doi:10.1016/j.dam.2003.09.012
[16]	Jagota, A., Sanchis, L.A.: Adaptive, restart, randomized greedy heuristics for maximum clique. J. Heuristics 7, 565–585 (2001) · Zbl 0987.68612 · doi:10.1023/A:1011925109392
[17]	Johnson, D.S., Trick, M. (eds.): Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series, vol. 26. American Mathematical Society, Providence (1996) · Zbl 0875.68678
[18]	Katayama, K., Hamamoto, A., Narihisa, H.: An effective local search for the maximum clique problem. Inform. Process. Lett. 95, 503–511 (2005) · Zbl 1185.68283 · doi:10.1016/j.ipl.2005.05.010
[19]	Östergard, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197–207 (2002) · Zbl 1019.05054 · doi:10.1016/S0166-218X(01)00290-6
[20]	Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[21]	Massaro, A., Pelillo, M., Bomze, I.M.: A complementary pivoting approach to the maximum weight clique problem. SIAM J. Optim 12(4), 928–948 (2002) · Zbl 1035.90072 · doi:10.1137/S1052623400381413
[22]	Pena, J., Vera, J., Zuluaga, L.: Computing the stability number of a graph via linear and semidefinite programming. Working Paper, Tepper School of Business, Carnegie Mellon Univ., available at http://www.optimization-online.org/DB_HTML/2005/04/1106.html (2005)
[23]	Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Intell. Res. 25, 159–185 (2006) · Zbl 1182.68065
[24]	Regin, J.-C.: Solving the maximum clique problem with constraint programming. In: LNCS, vol. 2883, pp. 634–648 (2003)
[25]	Sanchis, L., Jagota, A.: Some experimental and theoretical results on test case generators for the maximum clique problem. INFORMS J. Comput. 8(2), 87–102 (1996) · Zbl 0866.90132 · doi:10.1287/ijoc.8.2.87
[26]	SAT’04 Competition, http://www.lri.fr/\(\sim\)simon/contest04/results/ (2004) · Zbl 1042.05068
[27]	Schrijver, A.: A comparison of the Delsarte and Lovasz bounds. IEEE Trans. Inform. Theory 25, 425–429 (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072
[28]	Shinano, Y., Fujie, T., Ikebe, Y., Hirabayashi, R.: Solving the maximum clique problem using PUBB. In: Proceedings 12th IPPS/ 9th SPDP, pp. 326–332 (1998)
[29]	Singh, A., Gupta, A.K.: A hybrid heuristics for the maximum clique problem. J. Heuristics 12, 5–22 (2006) · Zbl 1122.90070 · doi:10.1007/s10732-006-3750-x
[30]	Solnon, C., Fenet, S.: A study of ACO capabilities for solving the maximum clique problem. J. Heuristics 12, 155–180 (2006) · Zbl 1163.90817 · doi:10.1007/s10732-006-4295-8
[31]	Wood, D.R.: An algorithm for finding a maximum clique in a graph. Oper. Res. Lett. 21(5), 211–217 (1997) · Zbl 0908.90264 · doi:10.1016/S0167-6377(97)00054-0

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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.