GALAND Lucie
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)
2005-2015 Publications
-
2015
- L. Galand, Th. Lust : “Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems”, Algorithmic Decision Theory, vol. 9346, Lecture Notes in Computer Science, Lexington, United States, pp. 305-321, (Springer) (2015)
- L. Galand, Th. Lust : “Multiagent Fair Optimization with Lorenz Dominance”, Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 15), Istanbul, Turkey, pp. 1895-1896 (2015)
-
2013
- L. Galand, J. Lesca, P. Perny : “Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming”, Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China, pp. 538-544 (2013)
- D. Cornaz, L. Galand, O. Spanjaard : “Kemeny Elections with Bounded Single-peaked or Single-crossing Width”, Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China, pp. 76-82 (2013)
- L. Galand, A. Ismaili, P. Perny, O. Spanjaard : “Bidirectional Preference-based Search for Multiobjective State Space Graph Problems”, Proceedings of the 6th Annual Symposium on Combinatorial Search (SoCS 2013), Leavenworth, Washington, United States, pp. 80-88 (2013)
- L. Galand, Th. Lust : “Two phase method for Lorenz dominance in biobjective combinatorial optimization”, 26th European Conference on Operational Research (EURO 2013), Rome, Italy (2013)
- L. Galand, A. Ismaili, P. Perny, O. Spanjaard : “Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs”, 22nd International Conference on Multiple Criteria Decision Making (MCDM 2013), Malaga, Spain (2013)
-
2012
- D. Cornaz, L. Galand, O. Spanjaard : “Bounded Single-Peaked Width and Proportional Representation”, 4th International Workshop on Computational Social Choice (COMSOC-2012), KrakĂłw, Poland (2012)
- L. Galand, O. Spanjaard : “Exact algorithms for OWA-optimization in multiobjective spanning tree problems”, Computers and Operations Research, vol. 39 (7), pp. 1540-1554, (Elsevier) (2012)
- D. Cornaz, L. Galand, O. Spanjaard : “Bounded Single-Peaked Width and Proportional Representation”, ECAI 2012, 20th European Conference on Artificial Intelligence, vol. 242, Frontiers in Artificial Intelligence and Applications, Montpellier, France, pp. 270-275, (IOS Press) (2012)
-
2011
- L. Galand, J. Lesca, P. Perny : “Multiobjective dynamic programming versus linear programming for compromise search with Choquet integral”, International Conference on Multiple Criteria Decision Making, Jyvaskyla, Finland, pp. 175-175 (2011)
-
2010
- L. Galand, P. Perny, O. Spanjaard : “Choquet-based optimisation in multiobjective shortest path and spanning tree problems”, European Journal of Operational Research, vol. 204 (2), pp. 303-315, (Elsevier) (2010)
-
2008
- L. Galand : “MĂ©thodes exactes pour l’optimisation multicritère dans les graphes : recherche de solutions de compromis”, thesis, defence 07/10/2008, supervision Perny, Patrice (2008)
- L. Galand, P. Perny, O. Spanjaard : “A branch and bound algorithm for Choquet optimization in multicriteria problems”, Proceedings of the 19th International Conference on Multiple Criteria Decision Making, vol. 634, Lecture Notes in Economics and Mathematical Systems, Auckland, New Zealand, pp. 355-365, (Springer) (2008)
- L. Galand, P. Perny, O. Spanjaard : “Optimization of the Choquet integral in multicriteria combinatorial problems”, 19th International Conference on Multiple Criteria Decision Making, Auckland, New Zealand (2008)
-
2007
- L. Galand, P. Perny : “Search for Choquet-optimal paths under uncertainty”, Proceedings of the 23rd conference on Uncertainty in Artificial Intelligence, Vancouver, Canada, pp. 125-132, (AUAI Press) (2007)
- L. Galand, O. Spanjaard : “OWA-based Search in State Space Graphs with Multiple Cost Functions”, 20th International Florida Artificial Intelligence Research Society Conference, Key West, Florida, United States, pp. 86-91, (AAAI Press) (2007)
- L. Galand, O. Spanjaard : “Deux approches complĂ©mentaires pour un problème d’arbre couvrant robuste”, 8e Congrès de la SociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d'Aide Ă la DĂ©cision (ROADEF 2007), Grenoble, France, pp. 129-137, (Presses Universitaires de Grenoble) (2007)
-
2006
- L. Galand, P. Perny : “Search for Compromise Solutions in Multiobjective State Space Graphs”, 17th European Conference on Artificial Intelligence, vol. 141, Frontiers in Artificial Intelligence and Applications, Riva del Garda, Italy, pp. 93-97, (IOS Press) (2006)
- L. Galand : “Interactive search for compromise solutions in multicriteria graph problems”, 9th IFAC Symposium on Automated Systems Based on Human Skill And Knowledge , 22-25 mai, vol. 39 (4), IFAC Proceedings Volumes, Nancy, France, pp. 129-134, (Elsevier Ltd) (2006)
- L. Galand : “Recherche d’un chemin de meilleur compromis dans un graphe multicritère”, 7e Congrès de la SociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d'Aide Ă la DĂ©cision (ROADEF 2006), Lille, France, pp. 121-136, (Presses Universitaires de Valenciennes) (2006)
-
2005
- L. Galand : “Interactive search for compromise solutions in multicriteria spanning trees and paths problems”, 61th Meeting of the European Working Group "Multiple Criteria Decision Aiding", Luxembourg, Luxembourg, pp. 36-37 (2005)