Compact mathematical formulation for graph partitioning

The graph partitioning problem consists of dividing the vertices of a graph into clusters, such that the weight of the edges crossing between clusters is minimized. We present a new compact mathematical formulation of this problem, based on the use of binary representation for the index of clusters assigned to vertices. This new formulation is almost minimal in terms of the number of variables and constraints and of the density of the constraint matrix. Its linear relaxation brings a very fast computational resolution, compared with the standard one. Experiments were conducted on classical large benchmark graphs designed for comparing heuristic methods. On one hand, these experiments show that the new formulation is surprisingly less time efficient than expected on general k-partitioning problems. On the other hand, the new formulation applied on bisection problems allows to obtain the optimum solution for about ten instances, where only best upper bounds were previously known.