Tabu Search Algorithms for the Maximum Clique Problem

Tabu search is a relatively new general heuristic framework successfully applied to a wide variety of hard combinatorial optimization points. In two previous projects, three variants of this approach were developed for the unweighted maximum clique problem, two deterministic ones and a probabilistic one. These algorithms were extensively tested on randomly-generated problems and were found to be very effective in that context. This paper evaluates the performance of these algorithms on the benchmark instances of the second DIMACS Challenge that, along with the results reported previously, will provide a fairly precise assessment of the merits of the heuristics.