Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916652349652992 |
|---|---|
| author | Ostermann, Birte Garnowski, Taylor Henze, Fabian Jha, Vaibhavnath Dia, Asra Fiand, Frederik Gross, David Gross, Wendelin Nowak, Julian de Wolff, Timo |
| author_facet | Ostermann, Birte Garnowski, Taylor Henze, Fabian Jha, Vaibhavnath Dia, Asra Fiand, Frederik Gross, David Gross, Wendelin Nowak, Julian de Wolff, Timo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10801 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems Ostermann, Birte Garnowski, Taylor Henze, Fabian Jha, Vaibhavnath Dia, Asra Fiand, Frederik Gross, David Gross, Wendelin Nowak, Julian de Wolff, Timo Optimization and Control Quantum Physics 81Q99, 90-05, 90C10 90C20, 90C22, 90C23 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. |
| title | Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems |
| topic | Optimization and Control Quantum Physics 81Q99, 90-05, 90C10 90C20, 90C22, 90C23 |
| url | https://arxiv.org/abs/2503.10801 |