Contributions to natural and extended formulations for Combinatorial Optimization Problems: Applications to exact and approximation algorithms

Dans cette habilitation à diriger des recherches, nous présentons nos contributions aux formulationsmathématiques pour des problèmes d’optimisation combinatoire impliquant des structures de basesde la théorie des graphes comme cycles, trees, paths, étoiles, couvertures, coupes, partitions, …Nous nous intéressons à la caractérisation de l’enveloppe convexe des vecteurs caractéristiques dessolutions dans l’espace natuelle de leur description or dans des espaces étendues. En particulier,nous montrons que l’enveloppe convexe des arbres de Huffman peut avoir une complexité plus queexponentielle. Nous obtenons également une généralisation du théorème de König en caractérisantl’enveloppe convexe des (sous)-étoiles. Nous considérons le polytope des métriques qui est unerelaxation de base de nombreux problèmes comme coupe maximum, multiflots, partitionnement degraphes, … pour lequel une formulations étendue de O(n³) intégalités de triangle est connue. Nousmontrons que pour les graphes peu denses, on peut réduire la taille de cette formulation à O(n²),voire à O(n) pour les graphes séries-parallèle.Nous nous intéressons ensuite à la conception des algorithmes exacts ou approché avec garantie deperformance avec l’utilisation des formulations mathématiques. En particulier, nous proposons desanalyses plus fines des formulations mathématiques existants permettant de dériver de nouvelalgorithme ou de les renforcer et/ou de réduire leur taille. En particulier, nous présentons un nouvelalgorithme pour la détection des cycles de coût négatif dans un graphe non-orienté basée sur unecaractérisation du cône des cycles de Paul Seymour. De plus, cet algorithme permet d’améliorer lacomplexité du problème. Nous concevons également des algorithmes exacts pour des problèmesayant des applications dans la conception des réseaux de télécommunications ou dans le domain ducalcul de haute performance comme le problème Anneau-Etoile, conception des réseauxSONET/SDH, partitionnement de graphes avec contraintes de capacité et/ou de sac-à-dos avec ounon de l’incertitude. Enfin, nous proposons des algorithmes approchés de type primal-dual oucutting-planes pour des problèmes comme le voyageur de commerce avec pénalité, l’arborescenceou cycle de couverture de poids minimum dans un graphe orienté