A Study of Scalarisation Techniques for Multi-Objective QUBO Solving

• URL: http://arxiv.org/abs/2210.11321v1
• Date: Thu, 20 Oct 2022 14:54:37 GMT
• Title: A Study of Scalarisation Techniques for Multi-Objective QUBO Solving
• Authors: Mayowa Ayodele, Richard Allmendinger, Manuel L\'opez-Ib\'a\~nez, Matthieu Parizy
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In recent years, there has been significant research interest in solving Quadratic Unconstrained Binary Optimisation (QUBO) problems. Physics-inspired optimisation algorithms have been proposed for deriving optimal or sub-optimal solutions to QUBOs. These methods are particularly attractive within the context of using specialised hardware, such as quantum computers, application specific CMOS and other high performance computing resources for solving optimisation problems. These solvers are then applied to QUBO formulations of combinatorial optimisation problems. 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. In this study, we compare methods of deriving scalarisation weights when combining two objectives of the cardinality constrained mean-variance portfolio optimisation problem into one. We show significant performance improvement (measured in terms of hypervolume) when using a method that iteratively fills the largest space in the Pareto front compared to a n\"aive approach using uniformly generated weights.

Related papers

• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario. We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
  arXiv  Detail & Related papers  (2024-06-11T19:59:05Z)
• 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)
• Smooth Tchebycheff Scalarization for Multi-Objective Optimization [15.047246588148495]
  Multi-objective optimization problems can be found in many real-world applications, where the objectives often conflict each other and cannot be optimized by a single solution. We propose a lightweight and efficient smooth Tchebycheff scalarization approach for gradient-based multi-objective optimization.
  arXiv  Detail & Related papers  (2024-02-29T12:03:05Z)
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers [0.2150989251218736]
  We develop a scheme with which near-term quantum computers can be applied to solve multi-objective optimization problems. We focus on an implementation based on the quantum approximate optimization algorithm (QAOA)
  arXiv  Detail & Related papers  (2023-08-16T09:22:01Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA [4.670374869377859]
  A core step in solving optimization problems with quantum algorithms is the problem formulation. Recent studies show that many problems can be solved more efficiently in their native Polynomial Unconstrained Optimization forms. Our evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits.
  arXiv  Detail & Related papers  (2023-05-05T09:37:48Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Multi-objective QUBO Solver: Bi-objective Quadratic Assignment [0.0]
  We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem.
  arXiv  Detail & Related papers  (2022-05-26T14:48:03Z)
• 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)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.