Discrete representation of the Pareto set in multi-objective optimization
This thesis focuses on the discrete representation of the set of the non-dominated points for problems in multi-objective optimization. In multi-objective optimization, a point is the vector of objective values linked to a solution. In this field, it is rare for a problem to have a unique optimal solution, in other words the point associated with this solution is usually not the best for each objective. It is then common to consider a set of points, called non-dominated (or Pareto set) such that, for each of these points, there is no other feasible point which is better on each of the objectives. These points form a set whose cardinality can be exponential with the size of the instance or even infinite. The large cardinality of the non-dominated is a crucial issue in order to be able to provide the decision maker with a tractable set of points. Moreover, generating this set requires prohibitive computation times. Therefore, the objective of the thesis is to propose methods which determine efficiently a representation of the set of the non-dominated points according to quality criteria: coverage, uniformity and cardinality. The work will be based on recent works concerning the preference relation called ε-dominance, (ε, ε ′) - kernels and approximation algorithms which are specific to them. On this basis and taking into account the previous quality criteria, efficient algorithms will be developed for problems with more than 2 objectives and for preference relations specific to decision-makers. We also plan to determine personalized representations for problems with particular structures such as combinatorial optimization problems with multiple objectives.