Résolution de problèmes d'optimisation combinatoire multiobjectifs par élicitation incrémentale de préférences - Nawal Benabbou (LIP6 - Sorbonne Université)

Dans cet exposé, nous présentons une approche générale permettant de résoudre des problèmes d'optimisation combinatoire multiobjectifs en élicitant les préférences du décideur de manière incrémentale en cours de résolution. Nous illustrons cette approche sur des problèmes d'optimisation dans les graphes multivalués (plus court chemin, arbre couvrant de poids minimum, affectation) dans lesquels les préférences du décideur sont représentables par une somme pondérée de jeu de poids imprécisément connu. Ces problèmes nous conduisent à proposer des versions interactives de la programmation dynamique, de l'approche gloutonne et de la méthode par séparation et évaluation. Nous présentons aussi des résultats numériques permettant de montrer que cette approche réalise un bon compromis entre les temps de résolution et le nombre de questions posées en pratique.