Description
Date depot: 3 avril 2025
Titre: Optimisation combinatoire ordinale par reformulation multi-objectifs : complexité, résolution et élicitation
Directeur de thèse:
Thibaut LUST (LIP6)
Directeur de thèse:
Olivier SPANJAARD (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Aide à la décision et recherche opérationnelle
Resumé: Ce projet de recherche doctoral porte sur les problèmes d'optimisation combinatoire ordinale. Dans ces problèmes, chaque élément du problème combinatoire considéré appartient à une classe de préférence. Par exemple on pourrait modéliser la qualité d'une route pour un cycliste à l'aide de trois classes de préférences : classe 1 (piste cyclable protégée), classe 2 (bande cyclable), classe 3 (route partagée avec les autres véhicules) et tenter de déterminer le trajet le plus sûr pour le cycliste. Ces problèmes peuvent également être reformulés en problèmes d'optimisation multi-objectifs particuliers où les vecteurs de valuation des éléments ont des composantes binaires.
L’objectif de ce projet de recherche doctoral est triple : (1) étudier la complexité des problèmes d'optimisation combinatoire ordinale, (2) adapter les méthodes de résolution existantes afin de prendre en compte les spécificités des préférences ordinales (3) proposer des approches interactives afin de déterminer, parmi l'ensemble des solutions non-dominées au sens ordinal, la solution préférée d'un décideur. Ce projet vise donc à améliorer la prise de décision dans des contextes où les informations dont on dispose sont de nature ordinale, en explorant à la fois des aspects théoriques et algorithmiques.
Résumé dans une autre langue: This doctoral research project focuses on ordinal combinatorial optimization problems. In these problems, each element of the combinatorial problem under consideration belongs to a preference class. For example, we could model the quality of a road for a cyclist using three preference classes: class 1 (protected cycle track), class 2 (cycle lane), class 3 (road shared with other vehicles) and try to determine the safest route for the cyclist. These problems can also be reformulated as special multi-objective optimization problems where the feature evaluation vectors have binary components.
The aim of this doctoral research project is threefold: (1) to study the complexity of ordinal combinatorial optimization problems, (2) to adapt existing solution methods to take into account the specificities of ordinal preferences (3) to propose interactive approaches for determining, from the set of solutions not dominated in the ordinal sense, a decision-maker's preferred solution. This project therefore aims to improve decision-making in contexts where the available information is ordinal in nature, by exploring both theoretical and algorithmic aspects.