Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
Authors:
- Taylor GarnowskiTGTaylor Garnowski
- Wendelin GrossWGWendelin Gross
- Timo de WolffTWTimo de Wolff
Preprint
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.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Solving Low-Rank Semidefinite Programs via Manifold OptimizationJournal of Scientific Computing, 2025
- Convex hulls of monomial curves, and a sparse positivstellensatzMathematical Programming, 2024
- Faster exact solution of sparse MaxCut and QUBO problemsMathematical Programming Computation, 2023
- COSMO: A Conic Operator Splitting Method for Convex Conic ProblemsJournal of Optimization Theory and Applications, 2021
- Dynamic storage assignment with product affinity and ABC classification—a case studyThe International Journal of Advanced Manufacturing Technology, 2015
- The unconstrained binary quadratic programming problem: a surveyJournal of Combinatorial Optimization, 2014
- Item-associated cluster assignment model on storage allocation problemsComputers & Industrial Engineering, 2012
- Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxationsMathematical Programming, 2008
- Detecting Global Optimality and Extracting Solutions in GloptiPoly2005
- Adaptive memory programming: A unified view of metaheuristicsEuropean Journal of Operational Research, 2001