Nos tutelles

CNRS Dauphine PSL *

Rechercher





Accueil > RECHERCHE > Pôles

Optimisation combinatoire, algorithmique

publié le , mis à jour le

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

Le pôle "Optimisation Combinatoire, Algorithmique" anime la recherche autour des projets :

AGaPe et Mathis sont les projets propres au 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.