L’Optimisation Combinatoire regroupe l’ensemble des questions théoriques posées, à l’origine, par un certain type d’applications. Les réponses se traduisent en algorithmes dont l’efficacité se mesure par l’expérimentation et par la théorie de la complexité.
Membres
Le pôle "Optimisation, Structure & Algorithmes" anime la recherche autour des projets :
- AGaPe (Algorithmique à Garanties de Performance)
- Jeux et choix social : aspects axiomatiques et algorithmiques
- Optimisation Combinatoire Multicritère
- Mathis (Programmation Mathématique et Structures Discrètes)
- Optimisation combinatoire multicritère
AGaPe et Mathis sont les principaux projets scientifiques du pôle, ils ont en commun d’étudier les relaxations des problèmes NP-durs. La relaxation porte sur la structure des instances considérées (Mathis/AGaPe), l’ensemble des solutions réalisables (Mathis), l’optimalité de la solution fournie (AGaPe/Mathis), et le temps que l’on met à l’obtenir (AGaPe). Les projets étudient aussi les généralisations des problèmes polynomiaux. La généralisation porte sur les critères d’optimalité (Multicritère), l’optimisation de critères en concurrence (Jeux), la dynamique des données (Services), et la fiabilité des données (Mathis).
Liens :
Applications :
Systèmes de production, télécommunications, simulation de mouvements dynamiques, Services Web, traitement de données multimédia, gestion de bibliothèques numériques musicales, etc.
Mots clés :
Programmation Mathématique (programmation linéaire et en nombres entiers, les approches polyédrales en optimisation combinatoire), l’approximation polynomiale et faiblement exponentielle (la complexité paramétrée, les algorithmes FPT), la robustesse (optimisation stochastique, instances évolutives, algorithmique on-line, réoptimisation), Optimisation pour les données massives, les métaheuristiques, la simulation, les chaînes logistiques, l’optimisation des ressources et la production de services.