A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy

¹ Instituto Federal de Educação, Ciência e Tecnologia do Triângulo Mineiro, Uberlândia, MG 38411-104, Brazil
² Institute of Computing, Universidade Federal Fluminense, Niterói, RJ 24210-346, Brazil

^* Corresponding author: celso@ic.uff.br

Received: 10 June 2019
Accepted: 4 January 2020

Abstract

Given a graph G = (V, E) and a threshold γ ∈ (0, 1], the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset C* of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold γ. This problem has a number of applications in data mining, e.g., in social networks or phone call graphs. We propose a matheuristic for solving the maximum cardinality quasi-clique problem, based on the hybridization of a biased random-key genetic algorithm (BRKGA) with an exact local search strategy. The newly proposed approach is compared with a pure biased random-key genetic algorithm, which was the best heuristic in the literature at the time of writing. Computational results show that the hybrid BRKGA outperforms the pure BRKGA.