An extended edge-representative formulation for the K-partitioning problem

We introduce an edge-representative formulation for the K-partitioning problem and show how it can be extended to improve its linear relaxation.A branch-and-cut algorithm based on a polyhedral study and a thorough cutting-plane strategy at the root node is described. We illustrate our approach with numerical results on some random hard instances.