GSCOP-RUB-OC-poster

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.
 
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.