Applicant: Thibaut Lust, University of Mons (Mons, Belgium)
Title: Branch and bound methods for multiobjective optimization
Host Institution: University "Pierre et Marie Curie", LIP6
Date: 15/03/10 - 15/05/10
Contact person : Patrice Penry

The goal of this STSM was to reinforce the cooperation between our team,
the Mathematics and Operationnal Research laboratory (MathRO) and the LIP6 team,
leaded by Patrice Perny. We have especially worked with Lucie Galand,
who had visited our laboratory in November 2009.
We first have given a talk, about metaheuristics for combinatorial
multiobjective optimization. Three lines of cooperation have been
identified after this talk: branch and bound methods integrated into
metaheuristics, approximation algorithms and Lorenz optimization.
After having considered these three streams, this is finally the last
one that has been particularly studied. Indeed, very few exact methods
are known to compute all the Lorenz optimal solutions of multiobjective
combinatorial problems. Lorenz optimal solutions, also called equitable
efficient solutions, form a subset of the Pareto optimal solutions.
Contrary to Pareto optimal solutions, Lorenz optimal solutions respect
the transfer principle. That means, for example in biobjective minimization,
that the cost-vector (10,10) will be prefer to the cost-vector (14,6) as
there is an admissible transfer of size 4.
With Lucie Galand, we have defined new exact methods based on the classic
two-phase method for Pareto optimization, to generate all the Lorenz optimal
solutions. The method is based, in the first phase, on the generation of ordered
weighted averaging (OWA) optimal solutions and in the second phaese, on a
branch and bound methods or ranking algorithms. Indeed, OWA optimal solutions
are Lorenz optimal solutions but unfortunately not all Lorenz optimal solutions
are OWA optimal solutions, that is why the second phase is needed. However,
it can be very time-consuming to generate all the OWA optimal solutions.
We have thus defined new notions and properties concerning the Lorenz optimal
solutions that allow to speed up the method. Preliminary results have been
obtained for the biobjective minimum spanning tree problem and for the biobjective
knapsack problem. We intend to perform more experiments before considering
these results for publication.