GUaranteed Efficiency for PAReto optimal solutions Determination in multiobjective combinatorial optimization problems – GUEPARD

The growing complexity of real world applications in various domains (e.g. optimization of communication networks, transportation and location problems, therapy planning, elaboration of public policies, web search) has led researchers in Operations Research (OR) and Decision Aiding to formulate problems where the interest of a solution must be analysed with respect to multiple objectives. Besides the difficulty of exploring large size solution spaces, the explicit introduction of several possibly conflicting objectives is an additional source of complexity, bringing new problems and new algorithmic challenges for computer scientists. As soon as multiple criteria are considered in the evaluation of a solution, the notion of optimality is not straightforward and various alternative definitions are available in the literature on decision theory and multicriteria analysis. Among them, the concept of Pareto optimality or efficiency is the most widely used. A solution is said to be Pareto-optimal or efficient if it cannot be improved on one criterion without being depreciated on another one. However, in combinatorial optimization problems, the complete enumeration of Pareto-optimal solutions may become intractable since, in the worst case, the size of the Pareto set grows exponentially with the size of the instance. Hence, computing the set of Pareto-optimal solutions induces prohibitive response times and requires very large memory space. For this reason, in many real world applications, people facing such complexity resort to artificial simplifications of the problem, either by focusing on the most important criterion (as in route planning assistants), or by performing a prior linear aggregation of criteria to get a single objective version of the problem, or by generating samples of good solutions using heuristics, which in any case does not provide formal guarantees on the quality of solutions. Considering the practical need for efficient tools to solve multiobjective combinatorial optimization problems in various contexts, the GUEPARD project brings together the main OR French teams involved in multiobjective optimization and algorithmic decision theory, with the aim of developing new operational approaches to solve multiobjective combinatorial optimization problems with performance guarantees on the quality of returned solutions. More precisely, the main problems we want to tackle are the exact determination of the set of efficient or Pareto optimal solutions (when it remains tractable), the approximation of the set of efficient or Pareto optimal solutions and the determination of the best compromise solutions with respect to a given preference model. The definition of the project clearly states a new position in the field of multiobjective optimization, as a compromise between theoretical computer science, decision theory and practice of operations research. Relying on recent theoretical results developed in computer science and preference modeling, we aim at developing new operational approaches for solving multiobjective combinatorial optimization problems that remain largely unsolved in the current practice. Besides the elaboration of new algorithms for the exact determination of Pareto-optimal solutions, the strength and originality of the project lie in a double specificity: 1) a new positioning between theoretical computer science and heuristic search keeping advantages of both sides for the approximation of Pareto-optimal solutions with performance guarantees. 2) a new positioning between decision theory and combinatorial optimization for preference-based search in multiobjective combinatorial problems, with various possible applications to compromise search, but also to robust optimization and fair division problems. We believe prior research works carried out in LIP6, LAMSADE and LINA on multiobjective optimization and recent preliminary results obtained by each partner on the topics of this project demonstrate the relevance of the consortium.