NGUYEN Viet Hung
Équipe : DECISION
Date de départ : 07/12/2016
https://lip6.fr/Hung.Nguyen
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é.
Soutenance : 07/12/2016
Membres du jury :
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