Forschungsleitung (Direction de recherche) : Patrice PERNY

Méthodes exactes pour l'optimisation multicritère dans les graphes : recherche de solutions de compromis

Cette thèse qui se situe à la croisée de l'intelligence artificielle et de la recherche opérationnelle a pour objectif de fournir des solutions algorithmiques efficaces aux problèmes multicritères admettant un nombre combinatoire de solutions potentielles. Pour cela, nous utilisons des modèles de préférences raffinant la dominance de Pareto et permettant de concentrer la recherche sur une solution de meilleur compromis. Dans cette perspective, nous proposons deux approches pour l'optimisation exacte de problèmes combinatoire multicritères, qui s'appuient sur une approximation linéaire du critère à optimiser. La première approche repose sur une énumération ordonnée des solutions selon cette approximation linéaire, tandis que la seconde approche effectue des coupes dans l'espace de recherche à l'aide de cette approximation linéaire, permettant une réduction considérable du nombre de solutions à explorer. Ces approches nous ont permis, en particulier, de mettre en oeuvre des algorithmes efficaces pour l'optimisation de l'opérateur OWA, de l'intégrale de Choquet et de la norme de Tchebycheff. En complément de ces travaux, nous proposons une exploration interactive de l'ensemble de Pareto à travers l'optimisation de la norme pondérée de Tchebycheff. Nous appliquons ces algorithmes aux problèmes multicritères de plus court chemin, d'arbre couvrant de poids minimal et de recherche dans des graphes d'états, pour lesquels nous avons obtenu des temps d'exécution suffisamment rapides pour établir le caractère opérationnel des approches proposées.

Publikationen 2005-2015