BLANC - Blanc

– GUEPARD

Résumé de soumission

La complexité croissante des applications réelles dans divers domaines (e.g. optimisation des réseaux de communication, problèmes de transport et de localisation, planification des traitements thérapeutiques, élaboration de politiques publiques, recherche sur le web) a conduit les chercheurs opérationnels et les chercheurs en aide à la décision à formuler des problèmes dans lesquels l?intérêt d?une solution doit être analysé selon plusieurs critères. Outre la difficulté d?explorer des espaces de solutions de grande taille, l?introduction explicite de plusieurs critères conflictuels est une source supplémentaire de complexité, offrant de nouveaux challenges algorithmiques aux informaticiens. Dès lors que plusieurs critères sont considérés dans l?évaluation d?une solution, la notion d?optimalité ne va pas de soi et diverses définitions alternatives sont proposées dans la littérature sur la théorie de la décision et l?analyse multicritère. Parmi elles, la notion d?optimalité de Pareto ou efficacité est la plus largement utilisée. Une solution est dite Pareto-optimale ou efficace si on ne peut l?améliorer sur un critère sans la détériorer sur un autre. Dans les problèmes d?optimisation combinatoire, l?énumération complète des solutions Pareto-optimales est intraitable puisque, dans le pire des cas, la taille de l?ensemble de ces solutions croît exponentiellement avec la taille de l?instance. Ainsi, calculer l?ensemble des solutions Pareto-optimales peut induire des temps de réponses prohibitifs et nécessiter un espace mémoire très important. Pour cette raison, dans de nombreuses applications les personnes confrontées à de telles difficultés ont recours à des simplifications artificielles du problème, soit en se focalisant sur le critère le plus important (comme dans les systèmes d?aide à la planification d?itinéraires), soit en agrégeant a priori les critères par une combinaison linéaire pour obtenir une version monocritère du problème à résoudre, soit encore en utilisant une heuristique pour engendrer des échantillons de bonnes solutions, ce qui dans tous les cas ne produit aucune garantie sur la qualité des solutions obtenues. Compte-tenu de la nécessité pratique de disposer d?outils efficaces pour résoudre les problèmes d?optimisation multiobjectifs dans divers contextes, le projet GUEPARD réunit les principales équipes de recherche opérationnelle françaises travaillant sur l?optimisation multiobjectif et la théorie de la décision algorithmique, avec l?objectif de développer de nouvelles approches opérationnelles pour résoudre les problèmes combinatoires multicritères en fournissant des garanties sur la qualité des solutions retournées. Plus précisément, les principaux problèmes que nous souhaitons aborder concernent la détermination exacte de l?ensemble de Pareto (dans les cas où sa taille reste raisonnable), l?approximation de cet ensemble et la détermination de solutions de meilleurs compromis selon un modèle de préférences donné. La définition du projet relève clairement d?un nouveau positionnement dans le domaine de l?optimisation multiobjectif, au carrefour des préoccupations de l?informatique théorique, de la théorie de la décision et de la pratique de la recherche opérationnelle. En exploitant des résultats théoriques récents développés en informatique et en modélisation des préférences, nous souhaitons développer de nouvelles approches opérationnelles pour résoudre les problèmes d?optimisation multiobjectifs qui restent largement non résolus dans la pratique actuelle. Outre l?élaboration de nouveaux algorithmes pour la détermination exacte de l?ensemble des solutions Pareto-optimales, la force et l?originalité du projet résident dans une double spécificité: 1) un nouveau positionnement entre informatique théorique et recherche heuristique, en s?efforçant de garder les avantages des deux approches pour l?approximation des solutions Pareto-optimales avec garantie de performances ; 2) un nouveau positionnement entre théorie de la décision et optimisation combinatoire pour la recherche fondée sur les préférences, avec de nombreuses applications possibles à la recherche de compromis dans les problèmes multicritères, mais aussi pour la recherche de solutions robustes et la résolution de problèmes de partage équitable. Des travaux de recherches sur l?optimisation multiobjectif, menés antérieurement au LIP6, au LAMSADE et au LINA, ainsi que des résultats préliminaires récents obtenus par chacun des partenaires du projet nous semblent démontrer la pertinence du consortium proposé.

Coordination du projet

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Aide de l'ANR 0 euros
Début et durée du projet scientifique : - 0 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter