GALAND Lucie

PhD graduated
Team : DECISION
Departure date : 01/31/2010
https://lip6.fr/Lucie.Galand

Supervision : 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.

Defence : 07/10/2008

Jury members :

Patrice PERNY (Professeur à l'Université Paris VI)
Jérôme LANG (Chargé de Recherche CNRS à l'Université Toulouse III) [Rapporteur]
Daniel VANDERPOOTEN (Professeur à l'Université Paris-Dauphine) [Rapporteur]
Michel GRABISCH (Professeur à l'Université Paris I)
Michel MINOUX (Professeur à l'Université Paris VI)
Jacques TEGHEM (Professeur à la Faculté Polytechnique de Mons)

Departure date : 01/31/2010

2005-2015 Publications

Mentions légales
Site map