This paper addresses a real-world combinatorial optimization problem involving multiple conflicting objectives, such as price, product quality, and sustainability. While computationally efficient methods exist for aggregating multiple objectives into a single objective function (e.g., linear combination), predefining the weights of linear combinations is challenging. As an alternative, interactive learning methods that ask users to compare candidate solutions offer promise. The key challenges are to rapidly generate candidates, learn an objective function that leads to high-quality solutions, and minimize user interactions. This paper proposes a method based on the Constructive Preference Elicitation (CPE) framework that improves three attributes: interaction speed, learning performance, and the number of user interactions. To improve interaction speed, we use a (relaxed) solution pool. To enhance learning performance, we employ maximum likelihood estimation of the Bradley-Terry preference model. To reduce the number of user interactions, we employ an ensemble-based acquisition function inspired by active learning. Experiments on PC configuration tasks and realistic multi-instance routing problems demonstrate that our method achieves faster query selection, fewer queries, and higher-quality combinatorial solutions than existing CPE methods.
