, Jin-Kao Hao, Adrien Goëffon. "A Three-Phased Local Search Approach for the Clique Partition Problem"
Journal of Combinatorial Optimization 32(2): 469-491, 2016. DOI 10.1007/s10878-015-9964-9
The source code will be available here. The
source code is distributed for academic puposes only. If you wish to use this code
for commercial applications, please obtain a permission from Yi Zhou (email@example.com) or Jin-Kao
Problem definition (Informal)
Given a complete edge-weighted undirected graph, the Clique Partition
Problem is to clustering all the vertices into k(unfixed) disjoint
subsets, such that the sum of edge weights between each two vertices in
each group is as large as possible. Note that the weights may be
postive or negative values. As listed in the paper, there are four groups of instances.
Group I: Created by Irene Charon and Olivier Hudry. Download
Group II: Created by Michael Brusco and H.F. Köhn. Download
Group III: Created by Gintaras Palubeckis et al. Download
Group IV: The edge weights of 5 instances are generated in Gaussian distribution N(0,52)
(the prefix of the instances name is "gauss"). The edge weights of 10
instances are generated in uniformly ditribution in range [-5, 5] (the
prefix of the instances name is "unif"). Download.
Input file format
n: the number of vertices. wi,j: weight value of edge <i,j>,(1<=i<=n,i<=j<=n).
line 1: n (number of vertices)
line 2: w1,1 w1,2 ........w1,n
line 3: w2,2 w2,3 ......w2,n
line 4: w3,3 w3,4 ...w3,n
line n: w2,2