Séminaire Zacharie Ales

Jeudi 10 Juillet 2014 (14h00, salle de séminaire)

Zacharie Ales, LMI, INSA de Rouen.

Titre : Approche polyédrale pour le problème de K-partitionnement avec variables de représentants.

Résumé : Le problème de K-partitionnement consiste à regrouper les sommets d'un graphe complet G(V,E) en K parties non vides, tout en minimisant la somme des distances des arêtes à l'intérieur des parties.

Nous présentons une formulation en nombres entiers de ce problème dans laquelle une variable est associée à chaque sommet de V et à chaque arête de E. Les variables associées aux sommets, appelées variables de représentants, prennent la valeur 1 si le sommet concerné est celui possèdant l'indice le plus petit de sa partie et 0 sinon. Nous caractérisons la dimension de l'enveloppe convexe des solutions entières de cette formulation et définissons des conditions nécessaires sous lesquelles des familles d'inégalités valides en définissent des facettes. Le problème est résolu en utilisant un algorithme de type plans coupants.