Cet article aborde un problème d'optimisation combinatoire concret impliquant de multiples objectifs contradictoires, tels que le prix, la qualité du produit et la durabilité. Bien qu'il existe des méthodes performantes en termes de calcul pour agréger plusieurs objectifs en une seule fonction objective (par exemple, une combinaison linéaire), prédéfinir les pondérations de ces combinaisons linéaires est complexe. Des méthodes d'apprentissage interactif demandant aux utilisateurs de comparer des solutions candidates sont une alternative prometteuse. Les principaux défis consistent à générer rapidement des solutions candidates, à apprendre une fonction objective conduisant à des solutions de haute qualité et à minimiser les interactions utilisateur. Cet article propose une méthode basée sur le cadre d'élicitation constructive des préférences (CPE) qui améliore trois attributs : la vitesse d'interaction, les performances d'apprentissage et le nombre d'interactions utilisateur. Pour améliorer la vitesse d'interaction, nous utilisons un pool de solutions (relaxé). Pour améliorer les performances d'apprentissage, nous utilisons l'estimation par maximum de vraisemblance du modèle de préférence Bradley-Terry. Pour réduire le nombre d'interactions utilisateur, nous utilisons une fonction d'acquisition basée sur un ensemble inspirée de l'apprentissage actif. Des expériences sur des tâches de configuration de PC et des problèmes de routage multi-instances réalistes démontrent que notre méthode permet une sélection de requêtes plus rapide, moins de requêtes et des solutions combinatoires de meilleure qualité que les méthodes CPE existantes.
