Polyhedral combinatorics of the K-partitioning problem with representative variables

The K-partitioning problem consists in partitioning the vertices of a weighted graph in K sets in order to minimize a function related to the edge weights. We introduce a linear mixed integer formulation with edge variables and representative variables. We investigate the polyhedral combinatorics of the problem, study several families of facet-defining inequalities and evaluate their efficiency on the linear relaxation.