Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation

Marianne Defresne, Jayanta Mandi, Tias Guns · 2025

Read Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation by Marianne Defresne, Jayanta Mandi, Tias Guns (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11435.txt.

Introduction

Marianne Defresne and co-authors speed up how solvers learn user tastes in a 2025 paper. Real design tasks juggle clashing aims like price, quality, and green cost, and users rarely can state trade weights up front. Asking users to compare pairs of options can teach those weights, if each round stays cheap.

Their upgrades work on three fronts at once. Pools of near solutions make each query fast to build. A Bradley Terry model fit by likelihood sharpens what pairs teach. An ensemble pick, drawn from active learning, cuts the count of rounds. Tests on a PC build task and a routing case beat past methods on all three fronts.

Catalog record

CREATORMarianne Defresne, Jayanta Mandi, Tias Guns
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-11435

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation Marianne Defresne, Jayanta Mandi, Tias Guns Abstract Real-life combinatorial optimization problems often involve several conflicting objectives, such as price, product quality and sustainability. A computationally-efficient way to tackle multiple objectives is to aggregate them into a single-objective function, such as a linear combination. However, defining the weights of the linear combination upfront is hard; alternatively, the use of interactive learning methods that ask users to compare candidate solutions is highly promising. The key challenges are to generate candidates quickly, to learn an objective function that leads to high-quality solutions and to do so with few user interactions. We build upon the Constructive Preference Elicitation framework and show how each of the three properties can be improved: to increase the interaction speed we investigate using pools of (relaxed) solutions, to improve the learning we adopt Maximum Likelihood Estimation of a Bradley-Terry preference model; and to reduce the number of user interactions, we select the pair of candidates to compare with an ensemble-based acquisition function inspired from Active Learning. Our careful experimentation demonstrates each of these improvements: on a PC configuration task and a realistic multi-instance routing problem, our method selects queries faster, needs fewer queries and synthesizes higher-quality combinatorial solutions than previous CPE methods. 1 Introduction Combinatorial optimization (CO) problems are omnipresent in real-life decision-making, such as scheduling and routing. They often require balancing multiple objectives. For instance, for a routing problem, a Decision Maker (DM) may wish to balance duration, fuel consumption and driver familiarity. One computationally-efficient way to tackle such a multi-objective CO problem is to build an approximate single-objective function aggregating individual (sub)objectives. The simplest and most common aggregation is a linear combination of sub-objectives Aneja and Nair 1978 ; Halffmann et al. 2022 . The main challenge lies in defining a set of weights leading to desirable solutions. For a DM, explicitly stating how sub-objectives should be balanced is difficult. However, comparing two solutions is an easier task, and a choice for one over the other implicitly informs about underlying preferences. We aim to learn a linear objective function from such pairwise comparisons, where that linear function can then be used to synthesize new desirable solutions by calling a CO solver. The goal fits within the general preference elicitation framework Guo and Sanner 2010 . Preferences are captured in a utility function, often a weighted average over attributes of an object. In the general preference elicitation framework, the learning task is to estimate weights such that after learning, the DM’s choice from a pool of alternative objects has the highest estimated utility. In CO, the utility is the single-objective function, an attribute is a sub-objective and an object is a solution. In this case, there is no explicit pool of objects. Indeed, feasible solutions are implicitly defined by the set of constraints and there can be exponentially many solutions. The learning task is then to estimate weights such that the resulting utility function leads to desirable solutions when used as an objective function for the multi-objective CO problem. Constructive Preference Elicitation (CPE) Dragone et al. 2018a was introduced for this setting. As in regular preference elicitation, weights are estimated in a two-step loop: first, a query, e.g. objects to compare, is selected and the DM is asked to express a preference. Second, the weight estimates are updated accordingly. What makes this setting constructive is that the learned utility function is then used to synthesize the best possible solution by calling a CO solver. Such preference elicitation involves interacting with a human DM. Among the target properties listed by Guo and Sanner Guo and Sanner 2010 , the one that comes first is the ability to propose queries in real-time . Yet, existing CPE methods select a query by using a CO solver to generate the objects Teso et al. 2016 ; Dragone et al. 2018b . When learning preferences over NP-hard problems, this can become prohibitively time intensive. The other target properties listed are 2) multi-attribute in utility function, 3) inducing a low cognitive load as difficult queries have noisy answers, 4) robust to noise in the responses and 5) requiring a minimal number of queries. For CO problems, we add that the method should be 6) constructive and 7) contextual to adapt to multiple instances of the same CO. Indeed, the DM’s preferences depend on the CO problem but not on a specific instance. For instance, a DM is likely to balance total distance and fuel consumption similarly for different sets of stops. We propose a new CPE approach that follows these properties. Our main insight is that real-time interaction on NP-hard problems requires to bypass the need for a solver during query selection. For this we propose using a pool of precomputed (relaxed) solutions. After learning, a CO solver is still required to synthesize a new desirable solution by optimizing the learned objective function over the feasible space; thus, the method is constructive . Queries prompt the user to compare two solutions; pairwise comparisons keep the cognitive load low Conitzer 2007 . For robust learning, both with respect to solution quality and number of queries , we adopt a Maximum Likelihood Estimation (MLE) of the Bradley-Terry preference model Bradley and Terry 1952 . Finally, our method learns preferences over multiple instances of similar CO problem instances, making it contextual . Our main contributions are: 1. We propose to select queries from a precomputed pool of (relaxed) solutions; it bypasses the need of solving CO problems during training; 2. For query selection, we adapt the ensemble-based Upper Confidence Bound acquisition function from the active learning literature, a non-linear function that would be difficult for a CO solver to optimize directly; 3. Inspired by Deep Reinforcement Learning, we learn the weights by maximizing the likelihood of a Bradley-Terry model. We draw connections with Noise Contrastive Estimation (NCE) and the previously-used Structured Perceptron, which shows that MLE can be interpreted as a smooth version thereof; 4. We assess our method by extensive experiments on two multi-objective CO problems: a previously-used PC configuration problem and a multi-instance Prize-Collecting Traveling Salesperson Problem (PC-TSP). On both tasks, our method is orders of magnitude faster, requires fewer queries and synthesizes higher-quality solutions than existing CPE approaches. 2 Related work Preference Elicitation. It aims to estimate the parameters of a utility function representing preferences. It relies on an incremental interactive approach of selecting a query and updating the parameter estimate based on the feedback received Pigozzi et al. 2016 . Most approaches aim to select the best choice out of an explicit finite set of alternatives. As such, they are not constructive as we consider here. Examples include multi-attribute utility theory Braziunas and Boutilier 2007 and multi-criteria decision-making Martyn and Kadziński 2023 ; Guo et al. 2021 . Moreover, these approaches are either Bayesian and thus computationally expensive to train Guo and Sanner 2010 , or exact regret-based and not robust to inconsistent answers Boutilier 2013 ; Toffano et al. 2022 . All these works are non-contextual as they consider single-instance problems. Preference elicitation for CO. The dominating approach to elicit preference weights in the context of multi-objective CO is

Read the complete text