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.

2010-2013 Publications

• 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”, thesis, phd defence 10/19/2011, supervision Perny, Patrice, co-supervision : Spanjaard, Olivier (2011)
  • Ch. Delort, O. Spanjaard, P. Weng : “Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation”, 2^nd 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”, 21^st 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”, 12^e 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”, 9^th 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”, 11^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010), Toulouse, France (2010)