Breakout Local Search for maximum clique problems

Breakout Local Search for maximum clique problems

0.00 Avg rating0 Votes
Article ID: iaor20125423
Volume: 40
Issue: 1
Start Page Number: 192
End Page Number: 206
Publication Date: Jan 2013
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics: local search
Abstract:

The maximum clique problem (MCP) is one of the most popular combinatorial optimization problems with various practical applications. An important generalization of MCP is the maximum weight clique problem (MWCP) where a positive weight is associate to each vertex. In this paper, we present Breakout Local Search (BLS) which can be applied to both MC and MWC problems without any particular adaptation. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. Extensive experimental evaluations using the DIMACS and BOSHLIB benchmarks show that the proposed approach competes favourably with the current state‐of‐art heuristic methods for MCP. Moreover, it is able to provide some new improved results for a number of MWCP instances. This paper also reports for the first time a detailed landscape analysis, which has been missing in the literature. This analysis not only explains the difficulty of several benchmark instances, but also justifies to some extent the behaviour of the proposed approach and the used parameter settings.

Reviews

Required fields are marked *. Your email address will not be published.