Title: Solving the maximum clique problem with a hybrid algorithm

Authors: Derek H. Smith; Stephanie Perkins; Roberto Montemanni

Addresses: Division of Mathematics and Statistics, University of South Wales, Pontypridd, CF37 1DL, Wales, UK ' Division of Mathematics and Statistics, University of South Wales, Pontypridd, CF37 1DL, Wales, UK ' Dalle Molle Institute for Artificial Intelligence (IDSIA – USI/SUPSI), Galleria 2, 6928 Manno, Switzerland

Abstract: A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimisations and Tabu search. All components of the algorithm make use of an exact algorithm or a pseudoexact algorithm, which is an exact algorithm with some specialised pruning. Pre-processing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.

Keywords: combinatorial optimisation; maximum clique; hybrid algorithm; Tabu search; pseudoexact algorithm; pre-processing; benchmarks.

DOI: 10.1504/IJMHEUR.2019.098270

International Journal of Metaheuristics, 2019 Vol.7 No.2, pp.152 - 175

Received: 28 Nov 2017
Accepted: 04 Nov 2018
Published online: 07 Mar 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article