Project belonging to both Pole 1 Decision Aiding and Pole 2 Combinatorial Optimization, Algorithms

Many combinatorial optimisation problems require the consideration of multiple criteria. Therefore, an important preliminary step is to determine the set of efficient solutions (also called non-dominated or Pareto-optimal solutions). Determining the set of efficient solutions allows, on the one hand, to better understand the trade-offs to be made between the different criteria and, on the other hand, to identify the subset of solutions from which a best compromise solution should be selected.
It turns out, however, that the number of efficient solutions can grow exponentially with the size of certain problem instances. Moreover, it is not relevant in practice to exhaustively enumerate the efficient set. It is often much more useful to provide a "good" representation of it in a reduced size, even if it means exploring exhaustively, in a second phase, certain areas of interest.

The main research areas of the project are

- Designing exact or approximate algorithms, but with quality and/or performance guarantees, to determine the set of efficient solutions for various multi-criteria combinatorial optimisation problems (path, spanning tree, assignment, knapsack, TSP,...)
- Designing exact or approximate algorithms, but with quality and/or performance guarantees, to determine good compromise solutions
- Applying the proposed approaches in real-world contexts

Key words: Efficient set, Pareto, approximation, enumeration, trade-off.