Report on STSM Report – COST Action IC0602

Applicant: Lucie Galand, LIP6 (Paris, France)
Title: multiobjective combinatorial optimisation
Host Institution: Polytechnic Faculty of Mons (Mons, Belgium), team MathRO
Date: 31/10/2009 – 30/11/2009
Contact person : Marc Pirlot

The goal of this STSM was to initiate some collaboration with the members
of the Mathematics and Operationnal Research (MathRO) team, leaded by Marc
Pirlot. This team has indeed an expertise in multiobjective combinatorial
optimisation, multicriteria decision aiding and decision under
uncertainty, which correspond to my research fields.
During this STSM, I gave a talk on exact methods to search for best
compromise solutions in multiobjective combinatorial optimisation
problems. These methods are dedicated to computing optimal solutions
according to involved decision models (best compromise solutions), which
constitutes the originality of my approach within algorithmic decision
theory. Among the different proposed methods, I have designed a ranking
approach based on a linear relaxation of the objective function. During
the STSM, we studied with Jacques Teghem and his PhD student Thibaut Lust
a ranking approach based on a relaxation of the structure of the problem.
First experiments were carried out during this STSM on Travelling Salesman
Problem (TSP) and Quadratic Assignment Problem (QAP). This joint work
would be continued.
During this stay, I also discussed with Thibaut Lust on designing new
exact methods for searching the Pareto set in bi-objective optimisation.
In particular, we explored new methods for problems TSP and QAP.

We are still working together, and several joint papers are anticipated.
In particular, Thibaut Lust will be visiting the LIP6 for two months in
2010 to reinforce the cooperation.