Fixed set search applied to the clique partitioning problem

The Clique Partitioning Problem (CPP) seeks to decompose a set of vertices into disjoint subsets (cliques) maximizing the sum of edge weights over all the cliques. The interest for the CPP comes from the fact that it represents well many practical problems from areas like data mining, engineering, bio-informatics, etc. To address this NP-hard combinatorial optimization problem, the novel fixed set search (FSS) metaheuristic is applied. This is performed, firstly, by developing a greedy randomized adaptive search procedure (GRASP) using a new type of neighborhood in the local search. The GRASP is further extended to the FSS by adding a learning mechanism. The FSS application to the CPP provides a new approach for generating fixed sets for problems with solution symmetries. This approach opens the application of the FSS to new families of combinatorial optimization problems. The conducted computational experiments show that the FSS significantly outperforms state-of-the-art metaheuristics for the CPP. The proposed approach obtains a large number of new best solutions for commonly used CPP test instances.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This passage introduces the Clique Partitioning Problem (CPP), which aims to maximize the sum of edge weights over disjoint subsets (cliques) of vertices. The novel fixed set search (FSS) metaheuristic, including a greedy randomized adaptive search procedure (GRASP) and a learning mechanism, is applied to solve the NP-hard problem efficiently. The proposed approach outperforms state-of-the-art metaheuristics for the CPP, generating numerous new best solutions for commonly used test instances.