*Contexte*
Les modèles de tri multicritère offrent une base théorique solide pour la résolution de problèmes de décision résultant de la prise en compte de divers aspects conflictuels. Formellement, un tel modèle est une application qui prend en entrée un ensemble d’options, décrites par un ensemble de critères, et fournit une recommandation finale quant à l’affectation de ces options à une classe parmi un ensemble ordonné.
Afin de prendre en compte le comportement décisionnel spécifique au décideur et à la situation, l’aide à la décision multicritère (MCDA) procède généralement en sélectionnant une classe de modèles paramétriques, puis en calibrant ces paramètres afin de particulariser le modèle (élicitation). En particulier, les approches d’élicitation par désagrégation procèdent de manière indirecte, en ajustant les paramètres de la classe de modèles à des exemples d’apprentissage fournis par le décideur.
Dans le cadre de ce sujet, on se focalisera sur une classe de modèle appelée MR-Sort, où chaque critère se voit associer deux paramètres, un seuil et un poids. Une option est alors jugée bonne ssi ses évaluations dépassent les seuils pour un ensemble de critères de poids total suffisant. Malgré sa simplicité, ce modèle est difficile à désagréger : l’approche directe, par programmation linéaire en nombre entiers, échoue à calculer de manière exacte de grandes instances en temps raisonnable, ce qui a conduit à proposer une méta-heuristique de type génétique. Cependant, l’obtention rapide de résultats exacts est un enjeu important pour les approches interactives de collecte d’information ou d’explication d’une recommandation, qui représentent des défis cruciaux pour les systèmes de recommandation.
*Travail demandé*
Le travail demandé consiste à tenter de faire progresser l’état de l’art concernant la désagrégation de MR-Sort, en cherchant à exploiter les relations qu’entretient la classe MR-Sort avec d’autres, telles que celle des modèles de tri à base de valeurs additives ou de tri non compensatoire. On obtient alors une collection de modèles relâchés dont les diverses formulations sont propices à différentes approches : branch and bound, force brute (avec possibilité de calcul parallèle) ou programmation par contraintes, qu’il s’agira d’implémenter, de comparer sur des jeux de données réels ou synthétiques, voire de combiner.
*Bibliographie*
[1] : Learning the parameters of a multiple criteria sorting method based on a majority rule. Agnes Leroy, Vincent Mousseau and Marc Pirlot. In 2nd International Conference on Algorithmic Decision Theory, pages 219-233, 2011.
[2] : Learning a Majority Rule Model from Large Sets of Assignment Examples. O. Sobrie, V. Mousseau and M. Pirlot. In ADT2013 - Algorithmic Decision Theory, P. Perny, M. Pirlot, and a. Tsoukias (eds.), pages 336-350, 2013.
[3] : An axiomatic approach to noncompensatory sorting methods in MCDM, I: The case of two categories. D. Bouyssou, T. Marchant, European Journal of Operational Research, 178 (1), 217--245, 2007.
[4] : An axiomatic approach to noncompensatory sorting methods in MCDM, I: More than two categories. D. Bouyssou, T. Marchant, European Journal of Operational Research, 178 (1), 217--245, 2007.