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

• URL: http://arxiv.org/abs/2503.11435v1
• Date: Fri, 14 Mar 2025 14:24:27 GMT
• Title: Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation
• Authors: Marianne Defresne, Jayanta Mandi, Tias Guns,
• Abstract summary: Real-life optimization problems often involve several conflicting objectives, such as price, product quality and sustainability.<n>A computationally-efficient way to tackle multiple objectives is to aggregate them into a single-objective function, such as a linear combination.<n>We build upon the Constructive Preference Elicitation framework and show how each of the three properties can be improved.
• Score: 8.033273941848254
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Self-Supervised Penalty-Based Learning for Robust Constrained Optimization [4.297070083645049]
  We propose a new methodology for parameterized constrained robust optimization, based on learning with a self-supervised penalty-based loss function. Our approach is able to effectively learn neural network approximations whose inference time is significantly smaller than the time of traditional solvers.
  arXiv  Detail & Related papers  (2025-03-07T06:42:17Z)
• A Systematic Examination of Preference Learning through the Lens of Instruction-Following [83.71180850955679]
  We use a novel synthetic data generation pipeline to generate 48,000 instruction unique-following prompts. With our synthetic prompts, we use two preference dataset curation methods - rejection sampling (RS) and Monte Carlo Tree Search (MCTS) Experiments reveal that shared prefixes in preference pairs, as generated by MCTS, provide marginal but consistent improvements. High-contrast preference pairs generally outperform low-contrast pairs; however, combining both often yields the best performance.
  arXiv  Detail & Related papers  (2024-12-18T15:38:39Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.<n>We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.<n>We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• AQA: Adaptive Question Answering in a Society of LLMs via Contextual Multi-Armed Bandit [59.10281630985958]
  In question answering (QA), different questions can be effectively addressed with different answering strategies. We develop a dynamic method that adaptively selects the most suitable QA strategy for each question. Our experiments show that the proposed solution is viable for adaptive orchestration of a QA system with multiple modules.
  arXiv  Detail & Related papers  (2024-09-20T12:28:18Z)
• Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization [17.392822956504848]
  We propose a reinforcement learning framework designed to construct high-quality solutions for multi-agent tasks efficiently.<n>PARCO integrates three key components: (1) transformer-based communication layers to enable effective agent collaboration during parallel solution construction, (2) a multiple pointer mechanism for low-latency, parallel agent decision-making, and (3) priority-based conflict handlers to resolve decision conflicts via learned priorities.<n>We evaluate PARCO in multi-agent vehicle routing and scheduling problems where our approach outperforms state-of-the-art learning methods and demonstrates strong generalization ability and remarkable computational efficiency.
  arXiv  Detail & Related papers  (2024-09-05T17:49:18Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• PMGDA: A Preference-based Multiple Gradient Descent Algorithm [12.600588000788214]
  It is desirable in many multi-objective machine learning applications, such as multi-task learning, to find a solution that fits a given preference of a decision maker. This paper proposes a novel predict-and-correct framework for locating a solution that fits the preference of a decision maker.
  arXiv  Detail & Related papers  (2024-02-14T11:27:31Z)
• Continuous Tensor Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems [0.6906005491572401]
  This study introduces Continual Anne Relaxationing (CTRA) for unsupervised-learning (UL)-based CO solvers. CTRA is a computationally efficient framework for finding diverse solutions in a single training run. Numerical experiments show that CTRA enables UL-based solvers to find these diverse solutions much faster than repeatedly running existing solvers.
  arXiv  Detail & Related papers  (2024-02-03T15:31:05Z)
• Batch Multi-Fidelity Active Learning with Budget Constraints [37.420149663263835]
  Batch Multi-Fidelity Active Learning with Budget Constraints (BMFAL-BC) We propose a novel batch acquisition function that measures the mutual information between a batch of multi-fidelity queries and the target function. We show the advantage of our method in several computational physics and engineering applications.
  arXiv  Detail & Related papers  (2022-10-23T11:39:56Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  Multiobjective optimization (MOCO) problems can be found in many real-world applications. We develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. Our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiconditioned vehicle routing problem and multi knapsack problem in terms of solution quality, speed, and model efficiency.
  arXiv  Detail & Related papers  (2022-03-29T09:26:22Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Pareto Multi-Task Learning [53.90732663046125]
  Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. It is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization.
  arXiv  Detail & Related papers  (2019-12-30T08:58:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.