Etant donné un graphe complet valué G=(V, E, w), le problème de K-partitionnement consiste à partitionner V en exactement K parties non vides tout en minimisant la somme du poids des arêtes à l'intérieur des parties.

La résolution exacte de problèmes de partitionnement dans lesquels le nombre de parties est contraint est souvent effectuée par le biais de formulations dites sommet-partie qui associent une variable binaire z_i^k égale à 1 si et seulement si le sommet i de V est assigné à la partie numéro k dans {1, ..., K_{max}}.

Nous prouvons que ces formulations ont également comme second désavantage de fournir des valeurs optimales de leur relaxation linéaire de mauvaise qualité et proposons deux formulations fournissant expérimentallement des relaxations de très bonne qualité. Nous déterminons les inégalités de ces deux formulations qui définissent des facettes de l'enveloppe convexe de leurs points entiers. Nous présentons des résultats numériques qui montrent l'efficacité de nos formulations arête-représentant comparé aux deux formulations sommet-partie en termes de gap de temps de résolution optimale. Enfin, nous montrons que les performances de nos formulations peuvent être améliorées en considérant un algorithme de branch-and-cut.