Le but de cette thèse est de proposer des méthodes générales afin de contourner l’intractabilité de problèmes d’optimisation multi-objectifs.Dans un premier temps, nous essayons d’apprécier la portée de cette intractabilité en déterminant une borne supérieure, facilement calculable, sur le nombre de points non dominés, connaissant le nombre de valeurs prises par chaque critère.Nous nous attachons ensuite à produire des représentations discrètes et tractables de l’ensemble des points non dominés de toute instance de problèmes d’optimisation multi-objectifs. Ces représentations doivent satisfaire des conditions de couverture, i.e. fournir une bonne approximation, de cardinalité, i.e. ne pas contenir trop de points, et si possible de stabilité, i.e. ne pas contenir de redondances. En s’inspirant de travaux visant à produire des ensembles ε-Pareto de petite taille, nous proposons tout d’abord une extension directe de ces travaux, puis nous axons notre recherche sur des ensembles ε-Pareto satisfaisant une condition supplémentaire de stabilité. Formellement, nous considérons des ensembles ε-Pareto particuliers, appelés (ε, ε′)-noyaux, qui satisfont une propriété de stabilité liée à ε′. Nous établissons des résultats généraux sur les (ε, ε′)-noyaux puis nous proposons des algorithmes polynomiaux qui produisent des (ε, ε′)-noyaux de petite taille pour le cas bi-objectif et nous donnons des résultats négatifs pour plus de deux objectifs. / The goal of this thesis is to propose new general methods to get around the intractability of multi-objective optimization problems.First, we try to give some insight on this intractability by determining an, easily computable, upper bound on the number of nondominated points, knowing the number of values taken on each criterion. Then, we are interested in producingsome discrete and tractable representations of the set of nondominated points for each instance of multi-objective optimization problems. These representations must satisfy some conditions of coverage, i.e. providing a good approximation, cardinality, i.e. it does not contain too many points, and if possible spacing, i.e. it does not include any redundancies. Starting from works aiming to produce ε-Pareto sets of small size, we first propose a direct extension of these works then we focus our research on ε-Pareto sets satisfying an additional condition of stability. Formally, we consider special ε-Pareto sets, called (ε, ε′)-kernels, which satisfy a property of stability related to ε′. We give some general results on (ε, ε′)-kernels and propose some polynomial time algorithms that produce small (ε, ε′)-kernels for the bicriteria case and we give some negative results for the tricriteria case and beyond.

Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting with a decision maker (DM), the heuristic algorithm first approximately identifies the region that is of interest to the DM. Then, the exact algorithm is employed to generate all true nondominated points in this region. We conduct experiments on Multi-objective Assignment Problems (MOAP), Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path (MOSP) Problems / and the algorithms work well. Finding the worst possible value for each criterion among the set of efficient solutions has important uses in multi-criteria problems since the proper scaling of each criterion is required by many approaches. Such points are called nadir points. v It is not straightforward to find the nadir points, especially for large problems with more than two criteria. We develop an exact algorithm to find the nadir values for multi-objective integer programming problems. We also find bounds with performance guarantees. We demonstrate that our algorithms work well in our experiments on MOAP, MOKP and MOSP problems. Assuming that the DM&#039 / s preferences are consistent with a quasiconcave value function, we develop an interactive exact algorithm to solve MIP problems. Based on the convex cones derived from pairwise comparisons of the DM, we generate constraints to prevent points in the implied inferior regions. We guarantee finding the most preferred point and our computational experiments on MOAP, MOKP and MOSP problems show that a reasonable number of pairwise comparisons are required.