Standardization of Multi-Objective QUBOs

• URL: http://arxiv.org/abs/2504.12419v1
• Date: Wed, 16 Apr 2025 18:35:07 GMT
• Title: Standardization of Multi-Objective QUBOs
• Authors: Loong Kuan Lee, Thore Thassilo Gerlach, Nico Piatkowski,
• Abstract summary: Multi-objective optimization involving Quadratic Unconstrained Binary Optimization (QUBO) problems arises in various domains.<n>We propose a novel technique for scaling QUBO objectives that uses an exact computation of the variance of each individual QUBO objective.
• Score: 2.285821277711785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-objective optimization involving Quadratic Unconstrained Binary Optimization (QUBO) problems arises in various domains. A fundamental challenge in this context is the effective balancing of multiple objectives, each potentially operating on very different scales. This imbalance introduces complications such as the selection of appropriate weights when scalarizing multiple objectives into a single objective function. In this paper, we propose a novel technique for scaling QUBO objectives that uses an exact computation of the variance of each individual QUBO objective. By scaling each objective to have unit variance, we align all objectives onto a common scale, thereby allowing for more balanced solutions to be found when scalarizing the objectives with equal weights, as well as potentially assisting in the search or choice of weights during scalarization. Finally, we demonstrate its advantages through empirical evaluations on various multi-objective optimization problems. Our results are noteworthy since manually selecting scalarization weights is cumbersome, and reliable, efficient solutions are scarce.

Related papers

• Deep Pareto Reinforcement Learning for Multi-Objective Recommender Systems [60.91599969408029]
  optimizing multiple objectives simultaneously is an important task for recommendation platforms. Existing multi-objective recommender systems do not systematically consider such dynamic relationships.
  arXiv  Detail & Related papers  (2024-07-04T02:19:49Z)
• Decoding-Time Language Model Alignment with Multiple Objectives [116.42095026960598]
  Existing methods primarily focus on optimizing LMs for a single reward function, limiting their adaptability to varied objectives. Here, we propose $textbfmulti-objective decoding (MOD)$, a decoding-time algorithm that outputs the next token from a linear combination of predictions. We show why existing approaches can be sub-optimal even in natural settings and obtain optimality guarantees for our method.
  arXiv  Detail & Related papers  (2024-06-27T02:46:30Z)
• 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)
• Many-Objective Multi-Solution Transport [36.07360460509921]
  Many-objective multi-solution Transport (MosT) is a framework that finds multiple diverse solutions in the Pareto front of many objectives. MosT formulates the problem as a bi-level optimization of weighted objectives for each solution, where the weights are defined by an optimal transport between the objectives and solutions.
  arXiv  Detail & Related papers  (2024-03-06T23:03:12Z)
• Controllable Preference Optimization: Toward Controllable Multi-Objective Alignment [103.12563033438715]
  Alignment in artificial intelligence pursues consistency between model responses and human preferences as well as values. Existing alignment techniques are mostly unidirectional, leading to suboptimal trade-offs and poor flexibility over various objectives. We introduce controllable preference optimization (CPO), which explicitly specifies preference scores for different objectives.
  arXiv  Detail & Related papers  (2024-02-29T12:12:30Z)
• Beyond One-Preference-Fits-All Alignment: Multi-Objective Direct Preference Optimization [76.09576643028362]
  We present Multi-Objective Direct Preference Optimization (MODPO) for multiple alignment objectives. MODPO folds language modeling directly into reward modeling, training language models as implicit collective reward models. It theoretically yields the same optimal solutions as MORLHF but is practically more stable and efficient.
  arXiv  Detail & Related papers  (2023-10-05T17:35:26Z)
• Parallel Multi-Objective Hyperparameter Optimization with Uniform Normalization and Bounded Objectives [5.94867851915494]
  We propose a multi-objective Bayesian optimization (MoBO) algorithm that addresses these problems. We increase the efficiency of our approach by imposing constraints on the objective to avoid exploring unnecessary configurations. Finally, we leverage an approach to parallelize the MoBO which results in a 5x speed-up when using 16x more workers.
  arXiv  Detail & Related papers  (2023-09-26T13:48:04Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• Applying Ising Machines to Multi-objective QUBOs [0.0]
  We extend the adaptive method of deriving scalarisation weights for problems with two or more objectives. We show that it leads to the best performance on multi-objective Unconstrained Binary Quadratic Programming (mUBQP) instances with 3 and 4 objectives.
  arXiv  Detail & Related papers  (2023-05-19T12:53:48Z)
• Multi-Objective GFlowNets [59.16787189214784]
  We study the problem of generating diverse candidates in the context of Multi-Objective Optimization. In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives. We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
  arXiv  Detail & Related papers  (2022-10-23T16:15:36Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
  arXiv  Detail & Related papers  (2022-10-20T14:54:37Z)
• Alleviating Search Bias in Bayesian Evolutionary Optimization with Many Heterogeneous Objectives [9.139734850798124]
  We deal with multi-objective optimization problems with heterogeneous objectives (HE-MOPs) A new acquisition function that mitigates search bias towards the fast objectives is suggested. We demonstrate the effectiveness of the proposed algorithm by testing it on widely used multi-/many-objective benchmark problems.
  arXiv  Detail & Related papers  (2022-08-25T17:07:40Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  We consider optimization problems, where multiple differentiable losses have to be minimized. The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
  arXiv  Detail & Related papers  (2020-07-14T09:50:33Z)

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.