Paper Info
Title
Simple ingredients leading to very efficient heuristics for the maximum clique problem
Abstract
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).
Year
DOI
Venue
2008
10.1007/s10732-007-9055-x
J. Heuristics
Keywords
Field
DocType
Maximum clique,Randomness,Plateau search,Penalties,Restart rules
Mathematical optimization,Heuristics,Neighbourhood (mathematics),Artificial intelligence,Sampling (statistics),Strengths and weaknesses,Mathematics,Iterated local search,Clique problem,Machine learning,Randomness
Journal
Volume
Issue
ISSN
14
6
1381-1231
Citations 
PageRank 
References 
49
1.67
25
Authors
3
Name
Order
Citations
PageRank
Andrea Grosso145028.55
Marco Locatelli292680.28
Wayne J. Pullan323212.73