Direction de recherche : Patrice PERNY
Co-encadrement : SPANJAARD Olivier
Algorithmes d'énumération implicite pour l'optimisation multi-objectifs exacte : exploitation d'ensembles bornant et application aux problèmes de sac à dos et d'affectation
Dans cette thèse, nous nous intéressons à des méthodes permettant de calculer le front de Pareto dans des problèmes d'optimisation combinatoire multi-objectifs. Ce genre de problème se pose quotidiennement, par exemple lorsque l'on souhaite trouver un itinéraire minimisant à la fois le temps de parcours et le prix de cet itinéraire. L'objectif de nos travaux est double. Dans un premier temps, nous développons des algorithmes d'énumération implicite (branch and bound, programmation dynamique, ...) adaptés au cadre multi-objectifs, pour résoudre efficacement certains problèmes d'optimisation combinatoire multi-objectifs, à savoir le problème du sac à dos bi-objectifs et le problème d'affectation bi-objectifs. Dans un second temps, nous élargissons le champ d'application de ces méthodes à un problème d'optimisation combinatoire ordinale : le problème de sélection de comité avec contrainte de budget. Pour résoudre ce problème nous le réduisons à un problème multi-objectifs, ce qui nous permet d'exploiter les travaux conduits sur le sac à dos multi-objectifs. En outre, nous proposons également un algorithme dédié pour ce problème de sélection de comité.
Soutenance : 19/10/2011
Membres du jury :
Patrice PERNY, Professeur UPMCOlivier SPANJAARD, Maître de Conférence UPMC
Xavier GANDIBLEUX, Professeur à l'Université de Nantes [rapporteur]
Daniel VANDERPOOTEN, Professeur à l'Université Paris-Dauphine (Paris 9) [rapporteur]
Christian ARTIGUES, Chargé de recherche HDR, LAAS CNRS
Evripidis BAMPIS, Professeur UPMC
Date de départ : 01/10/2012
Publications 2010-2013
-
2013
- Ch. Delort, O. Spanjaard : “A hybrid dynamic programming approach to the biobjective binary knapsack problem”, ACM Journal of Experimental Algorithmics, vol. 18, pp. 1.2, (Association for Computing Machinery) (2013)
-
2011
- Ch. Delort : “Algorithmes d’énumération implicite pour l’optimisation multi-objectifs exacte : exploitation d’ensembles bornant et application aux problèmes de sac à dos et d’affectation”, soutenance de thèse, soutenance 19/10/2011, direction de recherche Perny, Patrice, co-encadrement : Spanjaard, Olivier (2011)
- Ch. Delort, O. Spanjaard, P. Weng : “Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation”, 2nd International Conference on Algorithmic Decision Theory (ADT'11), vol. 6992, Lecture Notes in Artificial Intelligence, Piscataway, NJ, United States, pp. 28-41, (Springer) (2011)
- Ch. Delort, O. Spanjaard : “Yet another two-phase method for the biobjective assignment problem”, 21st International Conference on Multiple Criteria Decision Making (MCDM 2011), Jyvaskyla, Finland (2011)
- Ch. Delort, O. Spanjaard, P. Weng : “Sélection d’un comité fondée sur une classification ordinale des individus”, 12e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Saint-Etienne, France (2011)
-
2010
- Ch. Delort, O. Spanjaard : “Using bound sets in multiobjective optimization: Application to the biobjective binary knapsack problem”, 9th International Symposium on Experimental Algorithms (SEA 2010), vol. 6049, Lecture Notes in Computer Science, Naples, Italy, pp. 253-265, (Springer) (2010)
- Ch. Delort : “Prétraitement dans les méthodes en deux phases pour la résolution de problèmes bi-objectifs”, 11e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010), Toulouse, France (2010)