Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems

• URL: http://arxiv.org/abs/2503.10801v1
• Date: Thu, 13 Mar 2025 18:51:45 GMT
• Title: Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
• Authors: Birte Ostermann, Taylor Garnowski, Fabian Henze, Vaibhavnath Jha, Asra Dia, Frederik Fiand, David Gross, Wendelin Gross, Julian Nowak, Timo de Wolff,
• Abstract summary: We provide a vast experimental study of semidefinite programming relaxations of Quadratic unconstrained binary optimization problems.<n>We test on QUBO reformulations of industry-based instances of the (open) vehicle routing problem and the (affinity-based) slotting problem.
• Score: 0.4636927061010061
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic unconstrained binary optimization problems (QUBOs) are intensively discussed in the realm of quantum computing and polynomial optimization. We provide a vast experimental study of semidefinite programming (SDP) relaxations of QUBOs using sums of squares methods and on Hamiltonian Updates. We test on QUBO reformulations of industry-based instances of the (open) vehicle routing problem and the (affinity-based) slotting problem -- two common combinatorial optimization problems in logistics. Beyond comparing the performance of various methods and software, our results reaffirm that optimizing over non-generic, real-world instances provides additional challenges. In consequence, this study underscores recent developments towards structure exploitation and specialized solver development for the used methods and simultaneously shows that further research is necessary in this direction both on the classical and the quantum side.

Related papers

• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization [0.0]
  Combinatorial optimization problems are ubiquitous in industrial applications. Tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades. Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms.
  arXiv  Detail & Related papers  (2025-03-19T17:08:55Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  We describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization problems. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance.
  arXiv  Detail & Related papers  (2024-07-29T17:13:01Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• 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)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• 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)
• 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)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  We develop a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate unconstrained binary optimization problems. We showcase the framework's performance on two inverse design problems by optimizing thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering.
  arXiv  Detail & Related papers  (2021-05-06T02:22:23Z)

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.