Des méthodes interactives pour la résolution de problèmes d’optimisation combinatoire multi-objectifs - Nawal Benabbou, Sorbonne Université, LIP 6

Salle A304 - 13h45-15h15

Dans cet exposé, nous considérons des problèmes d’optimisation combinatoire multi-objectifs dans lesquels les préférences du décideur sont représentées par une fonction d’agrégation dont les paramètres sont imprécisément connus. Dans ce contexte, nous proposons différentes méthodes de résolution interactives dont le principe général est de réduire l’imprécision sur les paramètres du modèle pendant l’exploration implicite des solutions du problème, en posant des questions au décideur à des moments clés de la résolution, dans le but de focaliser l’effort d’élicitation sur les informations vraiment utiles pour trouver la solution préférée du décideur. Ce principe général nous a conduit à proposer des versions interactives de paradigmes de résolution classiques (programmation dynamique, approche gloutonne, branch and bound, recherche locale, algorithmes génétiques), et de concevoir de nouvelles méthodes exploitant l’espace des paramètres admissibles pour trouver rapidement des solutions prometteuses. Toutes ces méthodes ont été testées sur des instances de différentes tailles, et les résultats numériques montrent qu’elles réalisent de bons compromis entre les temps de résolution et le nombre de questions posées en pratique.