Un ensemble d'apprentissage de préférences consiste en la donnée d'un ensemble de vecteurs caractéristiques, décrivant typiquement des individus, et des préférences de ces individus sur un même ensemble d'objets (ouvrages, films, produits technologiques, candidats à une élection, etc.), préférences exprimées sous la forme d'un rangement. Les préférences sont dites <em> structurées </em> si elles s'articulent autour d'une structure commune sur les objets. Par exemple, dans un contexte politique, il est classique de supposer que les préférences de chaque individu sont décroissantes lorsque l'on s'éloigne de son candidat préféré le long d'un axe gauche-droite sur les candidats, axe sur lequel les individus s'accordent tous. Les préférences sont alors dites unimodales.
Ce stage vise à étudier les préférences unimodales sur un graphe quelconque. En termes algorithmiques, nous dirons que des préférences sont unimodales sur un graphe quelconque si ce sont toutes des <em> parcours </em> d'un graphe commun sur les objets, où un parcours est un rangement des sommets du graphe tel que chaque sommet figure dans la bordure des sommets qui le précèdent dans le rangement (la bordure d'un ensemble X de sommets est l'ensemble des sommets voisins d'au moins un sommet de X). Par exemple, dans le cas des préférences unimodales sur un axe, le graphe est une chaîne (axe gauche-droite).
A la différence du cas des préférences unimodales sur une classe spécifique de graphes, il existe <em> toujours </em> un graphe par rapport auquel les préférence sont unimodales, puisque toutes les préférences sont unimodales sur un graphe complet (car tous les rangements des sommets d'un graphe complet sont des parcours de ce graphe). Ainsi, bien que la notion de préférences unimodales sur un graphe quelconque ne permette pas de contourner des résultats d'impossibilité (comme c'est le cas pour les préférences unimodales sur un axe), elle est par contre plus opérationnelle car les préférences unimodales sur des classes particulières de graphes se rencontrent rarement en pratique.
Le fait que des préférences soient unimodales sur un graphe complet n'apprend bien sûr rien sur la structure des préférences. C'est pourquoi nous nous proposons de chercher à identifier un graphe qui <em> optimise </em> une caractéristique donnée (ou une combinaison de caractéristiques), par exemple le degré maximum d'un sommet, le nombre d'arêtes, la largeur d'arbre, etc... Autrement dit, dans l'ensemble des graphes compatibles avec les préférences observées, on recherche un graphe optimal au sens de la fonction objectif que l'on a définie.
L'objectif de ce stage est d'étudier la complexité des problèmes d'optimisation selon les caractéristiques du graphe que l'on vise à optimiser, et de proposer des algorithmes pour déterminer effectivement un graphe optimal. Des implémentations algorithmiques des méthodes envisagées (e.g., programmation mathématique) seront réalisées afin d'évaluer les algorithmes proposés d'un point de vue opérationnel. Une librairie de données préférentielles est disponible sur le web (http://www.preflib.org), qui devrait permettre de tester les algorithmes sur des données réelles.