Aller au menu Aller au contenu
UGA
Optimisation Combinatoire
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Optimisation Combinatoire

Analyse de problèmes : bonnes caractérisations, complexité et algorithmes

Pour les problèmes les plus difficiles de l'optimisation combinatoire, la solution algorithmique est souvent précédée de théorèmes qui révèlent la structure du problème, ou qui donnent une « bonne caractérisation », notion clé qui permet de justifier la réponse. Nous développons aussi bien ces théorèmes que leurs conséquences algorithmiques, ou des résultats négatifs qui permettent à nos collègues et quelquefois à nous-mêmes, de construire des algorithmes d'approximation. Sur un plan purement théorique, nous nous intéressons à des objets mathématiques dont les solutions contribuent à une bibliothèque de connaissances prête à être utilisée le moment venu. Ainsi, nous travaillons sur la théorie des couplages (T-joins, maxfix covers), les chemins disjoints dans les graphes (routage, multiflots), ou des problèmes de couvertures optimales.
 
Moats
Sur un plan plus appliqué, nous traitons aussi des problèmes théoriquement difficiles comme le « problème du voyageur de commerce » ou ses variantes, comme le « routage des véhicules ». Pour ces problèmes, l'approche polyédrale est privilégiée et des techniques branch and cut développées. La généricité de nos travaux nous amène également à travailler avec des physiciens pour résoudre certains de leurs problèmes. Ainsi, nous avons développé une méthode permettant de traiter des problèmes avec plusieurs centaines de milliers de variables, là ou les approches précédentes n'en traitaient que vingt. Ce problème nous pose d'ailleurs de nouvelles questions théoriques auxquelles nous souhaitons répondre à l'avenir.

Rédigé par Louis Esperet

mise à jour le 27 janvier 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Communauté Université Grenoble Alpes
×
Afin d'améliorer la qualité de ce site et le service rendu à l'utilisateur, nous utilisons des cookies de mesure d’audience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies à cette fin. Pour en savoir plus