Projet transversal du Pôle 1 Aide à la
décision et du Pôle 2 Optimisation combinatoire, algorithmique

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.Retour ligne manuel
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.