Nos tutelles

PSL * CNRS Dauphine

Rechercher





Accueil > Projets

Optimisation combinatoire multicritère

publié le , mis à jour le

De nombreux problèmes d’optimisation combinatoire nécessitent la prise en compte de critères multiples. Dès lors, une étape préalable importante consiste à déterminer l’ensemble des solutions efficaces (encore appelées non-dominées ou Pareto-optimales). Déterminer l’ensemble des solutions efficaces permet d’une part de mieux appréhender les arbitrages à effectuer entre les différents critères, d’autre part d’identifier le sous-ensemble des solutions parmi lesquelles il convient de sélectionner une solution de meilleur compromis.
Il apparaît cependant que le nombre de solutions efficaces peut croître exponentiellement avec la taille de certaines instances du problème. De plus, il ne s’avère pas pertinent en pratique d’énumérer exhaustivement l’ensemble efficace. Il est souvent bien plus utile d’en fournir une "bonne" représentation de taille réduite, quitte à explorer exhaustivement, dans une seconde phase, certaines zones d’intérêt.

Les principaux axes de recherche du projet sont :

  • Concevoir des algorithmes exacts ou approchés, mais avec garantie de qualité et/ou de performance, pour déterminer l’ensemble des solutions efficaces pour divers problèmes d’optimisation combinatoire multicritères (chemin, arbre couvrant, affectation, sac-à-dos, TSP,...)
  • Concevoir des algorithmes exacts ou approchés, mais avec garantie de qualité et/ou de performance, pour déterminer des solutions de bon compromis
  • Appliquer les démarches proposées dans des contextes réels

Mots clés : Ensemble efficace, Pareto, approximation, énumération, compromis.

Membres permanents du projet : Hassene Aissi, Lucie Galand, Daniel Vanderpooten.

+ membres du pôle "Optimisation combinatoire, algorithmique, données" :
Cristina Bazgan, Laurent Gourvès, Jérôme Monnot.