Une description complète de polytopes liés à l'indice minimum d'une ligne non identiquement nulle d'une matrice d'affectation

Session : PL / Programmation linéaire
Mercredi 10 février 15:00 - 16:00 Salle : CI2-07
Walid Benameur, Antoine Glorieux et José Neto

Considérons un matrice booléenne d'affectation où chaque colonne contient exactement une composante égal à 1 et h l'indice de la ligne la plus basse qui n'est pas identiquement nulle. Nous donnons la description complète de l'enveloppe convexe des matrices d'affectations possibles couplées avec leur paramètre h. Ce polytope et quelques unes de ses variantes apparaissent naturellement dans de nombreux problèmes d'optimisation combinatoire parmi lesquels on retrouve des problèmes d'attribution des fréquences, d'ordonnancement de tâches, d'orientation de graphes, de clique maximum, etc. Nous prouvons également que le problème de séparation intrinsèque à ces polytopes peuvent être résolus en temps polynomial.

Mots clés : graphes, orientation, complexité, programmation linéaire mixte, matrice d'affectation