Kavli Affiliate: David Gross
| First 5 Authors: Birte Ostermann, Taylor Garnowski, Fabian Henze, Vaibhavnath Jha, Asra Dia
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”David Gross”&id_list=&start=0&max_results=3