An Iterated Tabu Search Approach for the Clique Partitioning Problem

Autor: Gintaras Palubeckis, Armantas Ostreika, Arūnas Tomkevičius
Jazyk: angličtina
Rok vydání: 2014
Předmět:
Zdroj: The Scientific World Journal, Vol 2014 (2014)
Druh dokumentu: article
ISSN: 2356-6140
1537-744X
DOI: 10.1155/2014/353101
Popis: Given an edge-weighted undirected graph with weights specifying dissimilarities between pairs of objects, represented by the vertices of the graph, the clique partitioning problem (CPP) is to partition the vertex set of the graph into mutually disjoint subsets such that the sum of the edge weights over all cliques induced by the subsets is as small as possible. We develop an iterated tabu search (ITS) algorithm for solving this problem. The proposed algorithm incorporates tabu search, local search, and solution perturbation procedures. We report computational results on CPP instances of size up to 2000 vertices. Performance comparisons of ITS against state-of-the-art methods from the literature demonstrate the competitiveness of our approach.
Databáze: Directory of Open Access Journals
Externí odkaz: