The K-partitioning problem: Formulations and branch-and-cut

摘要

The K-partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node-cluster formulations adapted from the literature on similar problems as well as two edge-representative formulations. We introduced the first edge-representative formulation in a previous work while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge-representative formulations and identify a new family of facet-defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node-cluster formulations which may account for their low performances. Finally, we propose a branch-and-cut strategy, based on the edge-representative formulations, which performs even better.