Une formulation arête-représentant pour le problème de K-partitionnement

Session : PPP-1 / Placement, Partionnement, Packing
Mercredi 10 février 11:00 - 12:20 Salle : CI2-22
Zacharie Ales et Arnaud Knippel

Le problème de K-partitionnement consiste à regrouper les sommets d’un graphe complet G = (V, E) en exactement K parties tout en minimisant la somme des poids des arêtes à l’intérieur des parties. Nous proposons pour ce problème le programme linéaire en nombres entiers (Fext) qui étend la formulation (Fer) précédemment définie par l’addition de variables d’arêtes. Nous comparons la structure des polytopes Per et Pext associés à ces formulations et présentons une nouvelle famille d'inégalités définissant des facettes de Pext. L'efficacité de ces deux formulations - en terme de qualité de relaxation linéaire et de résolution optimale - est comparée avec celle de deux variantes de formulations sommet-partie.

Mots clés : approche polyédrale, branch-and-cut, K-partitionnement, optimisation combinatoire