Yi Zhou , 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 (zhou@info.univ-angers.fr) or Jin-Kao Hao (hao@info.univ-angers.fr).

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.

Instance files : Download here

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