NGUYEN Viet Hung

Contributions à des formulations naturelles et étendues en Optimisation Combinatoire - Applications à la conception des algorithmes exacts et approchés

Dans cette habilitation à diriger des recherches, nous présentons nos contributions aux formulations mathématiques pour des problèmes d’optimisation combinatoire impliquant des structures de bases de la théorie des graphes comme cycles, arbres, chemins, étoiles, couvertures, coupes, partitions, …
Nous nous intéressons à la caractérisation de l’enveloppe convexe des vecteurs caractéristiques des solutions dans l’espace naturelle de leur description ou dans des espaces étendues. En particulier, nous montrons que l’enveloppe convexe des arbres de Huffman peut avoir une complexité plus que exponentielle. Nous obtenons également une généralisation du théorème de König en caractérisant l’enveloppe convexe des (sous)-étoiles. Nous considérons le polytope des métriques qui est une relaxation de base de nombreux problèmes comme coupe maximum, multiflots, partitionnement de graphes, … pour lequel une formulations étendue de O(n³) inégalités de triangle est connue. Nous montrons 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 de performance avec l’utilisation des formulations mathématiques. Nous proposons des analyses plus approfondies des formulations mathématiques existants permettant de les renforcer et/ou de réduire leur taille dans le but de dériver de nouvel algorithmes. En particulier, nous présentons un nouvel algorithme pour la détection des cycles de coût négatif dans un graphe non-orienté basée sur une caractérisation du cône des cycles de Paul Seymour qui permet d’améliorer la complexité du problème. Nous concevons également des algorithmes exacts pour des problèmes ayant des applications dans la conception des réseaux de télécommunications ou dans le domaine du calcul de haute performance comme le problème Anneau-Etoile, conception des réseaux SONET/SDH, partitionnement de graphes avec contraintes de capacité et/ou de sac-à-dos avec ou non de l’incertitude. Enfin, nous proposons des algorithmes approchés de type primal-dual ou cutting-planes pour des problèmes comme le voyageur de commerce avec pénalité, l’arborescence ou cycle de couverture de poids minimum, dans un graphe orienté.

Defence : 12/07/2016 - 14h - Site Jussieu 55-56/211

Jury members :

Francisco Barahona, Directeur de Recherche, IBM J. Watson Research Center [Rapporteur]
Gérard Cornuéjols, Professeur - Tepper School of Business, Carnegie Mellon University [rapporteur]
Alain Quilliot, Professeur - LIMOS, Université Blaise Pascal [rapporteur]
Ridha Mahjoub, Professeur - LAMSADE, Université Paris Dauphine
Jean-François Maurras, Professeur - LIF, Université Aix-Marseille
Michel Minoux, Professeur - LIP6, Université Pierre and Marie Curie
Patrice Perny, Professeur - LIP6, Université Pierre and Marie Curie
Andras Sebö Directeur de Recherche- G-SCOP, CNRS, Grenoble

3 PhD graduated 2010 - 2022