DELORT Charles

PhD graduated
Departure date : 10/01/2012

Supervision : Patrice PERNY

Co-supervision : 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

In this thesis, we are interested in methods computing the Pareto front of multiobjective combinatorial optimization problems. This kind of problem arises everyday, for instance, when one wants to find a route minimizing both the time taken and the price of this route. The goal of this thesis is twofold. First, we develop new implicit enumeration algorithms (branch and bound, dynamic programming, ...) adapted to the multiobjective case, in order to solve efficiently some multiobjective combinatorial optimization problems, namely the biobjective knapsack problem and the biobjective assignment problem. The second goal of our thesis is to enlarge the scope of these methods to a ordinal optimization problem : the committee selection with a weight constraint problem. We give a reduction from this problem to a multiobjective problem, enabling us to use the previous methods to solve it. Besides, we also propose a dedicated solution algorithm for this committee selection problem.

Defence : 10/19/2011 - 14h00 - Site Jussieu - Salle Jean-Louis Laurière - 25-26/101

Jury members :

Patrice PERNY, Professeur UPMC
Olivier 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

2010-2013 Publications