Projet du Pôle 2 Optimisation combinatoire, algorithmique

Le but du projet est le développement de méthodes efficaces pour formuler, analyser et résoudre très efficacement des problèmes pratiques de grande taille et des problèmes paradigmatiques connus comme étant NP-difficiles.

Nous étudions en particulier des approches polyédrales pour des problèmes d’optimisation combinatoire difficiles. Celles-ci se sont avérées puissantes pour résoudre ce type de problèmes. Se basant sur la programmation linéaire et la programmation en nombres entiers, les approches polyédrales consistent à transformer le problème en un programme linéaire dont les contraintes décrivent l’enveloppe convexe de ses solutions réalisables. Ainsi elles permettent d’élaborer des algorithmes polynomiaux et d’obtenir des relations min-max entre des structures combinatoires. Une grande partie de la recherche développée dans ce projet est liée à ces méthodes et leurs applications.

Nous nous intéressons aussi aux cas où les données d’un problème d’optimisation ne sont pas connues avec certitude, et il est donc nécessaire d’intégrer cette incertitude dans le modèle à optimiser. Dans ce contexte, le but est de déterminer des solutions dites robustes, c’est-à-dire « bonnes » pour les différents valeurs plausibles des données incertaines. Nos recherche ici concernent l’optimisation robuste dans le cadre de la programmation linéaire.

• Mots clés : Approche polyédrale, Conception de réseaux, Théorie des Graphes, Méthode probabiliste, Robustesse, Programmation semi-définie positive, système (box-)TDI, Problèmes de grandes tailles, génération de colonnes, algorithmes de plans coupants