×

A simple simulated annealing algorithm for the maximum clique problem. (English) Zbl 1121.90412

Summary: Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.

MSC:

90C35 Programming involving graphs or networks
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C59 Approximation methods and heuristics in mathematical programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C60 Abstract computational complexity for mathematical programming problems

Software:

QUALEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balas, E.; Yu, C. S., Finding a maximum clique in an arbitrary graph, SIAM Journal on Computing, 15, 4, 1054-1068 (1986) · Zbl 0604.05024
[2] Bandyopadhyay, S.; Pal, S. K.; Murthy, C. A., Simulated annealing based pattern classification, Information Sciences, 109, 165-184 (1998)
[3] Bomze, I. M.; Budinich, M.; Pelillo, M.; Rossi, C., Annealed replication: a new heuristic for the maximum clique problem, Discrete Applied Mathematics, 121, 27-49 (2002) · Zbl 1019.90032
[4] Busygin, S., A new trust region technique for the maximum weight clique problem, Discrete Applied Mathematics, 154, 2080-2096 (2006) · Zbl 1111.90020
[5] Carraghan, R.; Pardalos, P. M., An exact algorithm for the maximum clique problem, Operations Research Letters, 9, 375-382 (1990) · Zbl 0711.90080
[6] Dukanovic, I.; Rendl, F., Semi-definite programming relaxations for graph coloring and maximal clique problems, Mathematical Programming, Series B, 109, 345-365 (2007) · Zbl 1278.90299
[7] Galán-Marı´n, G.; Mérida-Casermeiro, E.; Muñoz-Pérez, J., Modelling competitive Hopfield networks for the maximum clique problem, Computers and Operations Research, 30, 603-624 (2003) · Zbl 1026.90075
[8] Hansen, P.; Mladenovic, N.; Uroševic, D., Variable neighborhood search for the maximum clique, Discrete Applied Mathematics, 145, 117-125 (2004) · Zbl 1058.90053
[9] Hastad, J., Clique is hard to approximate within \(n^{1− &z.epsiv; } \), Acta Mathematica, 182, 105-142 (1999) · Zbl 0989.68060
[10] Katayama, K.; Hamamoto, A.; Narihisa, H., An effective local search for the maximum clique problem, Information Processing Letters, 95, 503-511 (2005) · Zbl 1185.68283
[11] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[12] Lin, R. B.; Chen, S. Y., Conjugate conflict continuation graphs for multi-layer constrained via minimization, Information Sciences, 177, 2436-2447 (2007) · Zbl 1116.68062
[13] Nalini, N.; Raghavendra Rao, G., Attacks of simple block ciphers via efficient heuristics, Information Sciences, 177, 2553-2569 (2007) · Zbl 1116.68036
[14] Östergård, P. R.J., A fast algorithm for the maximum clique problem, Discrete Applied Mathematics, 120, 197-207 (2002) · Zbl 1019.05054
[15] Pardalos, P. M.; Rodger, G. P., A branch and bound algorithm for the maximum clique problem, Computers and Operations Research, 19, 5, 363-375 (1992) · Zbl 0757.90082
[16] Poranen, T., A simulated annealing algorithm for determining the thickness of a graph, Information Sciences, 172, 155-172 (2005) · Zbl 1087.68074
[17] Sánchez, L.; Couso, I.; Corrales, J. A., Combining GP operators with SA search to evolve fuzzy rule based classifiers, Information Sciences, 136, 175-191 (2001) · Zbl 0996.68176
[18] Tomita, E.; Kameda, T., An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, Journal of Global Optimization, 37, 95-111 (2007) · Zbl 1127.90079
[19] Van-Laarhoven, P. J.M.; Aarts, E., Simulated Annealing: Theory and Applications (1987), Kluwer: Kluwer Dordrecht · Zbl 0643.65028
[20] Xu, X. S.; Ma, J., An efficient simulated annealing algorithm for the minimum vertex cover problem, Neurocomputing, 69, 913-916 (2006)
[21] Zhang, X. D.; Li, Z. L., Graph Theory and Its Applications (2005), Higher Education Publishing Company: Higher Education Publishing Company Beijing
[22] Zhang, Q. F.; Sun, J. Y.; Tsang, E., An evolutionary algorithm with guided mutation for the maximum clique problem, IEEE Transactions on Evolutionary Computation, 9, 2, 192-200 (2005)
[23] Zhang, J. Y.; Xu, J.; Bao, Z., Algorithm for the maximum clique and independent set of graphs based on Hopfield networks, Journal of Electronics, 18, 122-127 (1996)
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.