Résumé en anglais

In this paper, we are interested in producing discrete and tractable representations of the set of non-dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These representations must satisfy some conditions of coverage, i.e. providing a good approximation of the non-dominated set, spacing, i.e. without redundancies, and cardinality, i.e. with the smallest possible number of points. This leads us to introduce the new concept of (ε, ε′)-kernels, or ε-kernels when ɛ′=ɛ is possible, which correspond to ε-Pareto sets satisfying an additional condition of ε′-stability. Among these, the kernels of small, or possibly optimal, cardinality are claimed to be good representations of the non-dominated set. We first establish some general properties on ε-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an ε-kernel of small size or, for a fixed size k , an ε-kernel with a nearly optimal approximation ratio 1+ɛ. For more than two objectives, we show that ε-kernels do not necessarily exist but that (ε, ε′)-kernels always exist. Nevertheless, we show that the size of a smallest (ε, ε′)-kernel can be very far from the size of a smallest ε-Pareto set.