Nos tutelles

CNRS Dauphine PSL *


Accueil > RECHERCHE > Projets Scientifiques

Multi-criteria combinatorial optimisation

publié le , mis à jour le

A number of combinatorial optimisation problems require consideration of multiple criteria. Therefore, an important preliminary step consists in determining the set of efficient solutions (non-dominated or Pareto-optimal). Determining the efficient solutions firstly helps in understanding the trade-offs between different criteria, secondly allows identification of a subset of solutions from which the best compromise solution can be selected.
It appears however that the number of effective solutions can grow exponentially with the size of certain problem instances. In fact, in practice it is often not necessary to find all efficient solutions. It is often more useful to provide a "good" representation of reduced size, then to explore exhaustively, in a second phase, certain zones of interest.

The main axes of the project are :

- To develop exact or approximate algorithms with guaranteed bounds on performance or quality in order to determine the overall effective solutions for various multi-criterea combinatorial optimization problems (path, spanning tree, assignment, packing, TSP, ...)
- To develop exact or approximate algorithms or approaches with guaranteed bounds on performance or quality in order to determine good compromise solutions
- To apply these approaches in real settings

Key words : Efficient set, Pareto, approximation, enumeration, compromise.