An iterated tabu search approach for the clique partitioning problem

Area of Science:

• Graph theory
• Combinatorial optimization
• Computer science

Background:

• The clique partitioning problem (CPP) involves dividing graph vertices into subsets to minimize edge weights within induced cliques.
• Existing methods face challenges with large-scale graph partitioning problems.

Purpose of the Study:

• To develop and evaluate an efficient algorithm for the clique partitioning problem.
• To address the challenge of partitioning large graphs up to 2000 vertices.

Main Methods:

• Development of an Iterated Tabu Search (ITS) algorithm.
• Integration of tabu search, local search, and solution perturbation techniques.
• Computational testing on various CPP instances.

Main Results:

• The proposed ITS algorithm demonstrates effectiveness in solving CPP instances.
• Performance comparisons indicate ITS is competitive with state-of-the-art methods.
• The algorithm scales effectively to graphs with up to 2000 vertices.

Conclusions:

• The Iterated Tabu Search algorithm provides a competitive approach for the clique partitioning problem.
• ITS offers an efficient solution for partitioning large, edge-weighted undirected graphs.
• This research contributes a valuable tool for combinatorial optimization problems.