pith. sign in

arxiv: 2412.15665 · v2 · submitted 2024-12-20 · 🪐 quant-ph · cs.DM

Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing

Friedrich Wagner , Frauke Liers This is my paper

Pith reviewed 2026-05-23 06:59 UTC · model grok-4.3

classification 🪐 quant-ph cs.DM
keywords vehicle routingbranch-price-and-cutquantum heuristicsQUBOquantum annealinghybrid quantum-classicalpricing problemseparation problem
0
0 comments X

The pith

Modeling pricing and separation as QUBO problems allows quantum heuristics to serve as subroutines inside exact branch-price-and-cut algorithms for vehicle routing.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how quantum heuristics can be embedded into classical exact solvers for the vehicle routing problem. It does this by reformulating the pricing and separation steps inside a branch-price-and-cut algorithm as quadratic unconstrained binary optimization instances. Quantum methods such as annealing or QAOA are then applied to these smaller subproblems. The approach collects every solution whose cost lies below a chosen threshold rather than only the single best one. This lets the hybrid solver profit from the randomness inherent in quantum algorithms while keeping the overall procedure exact.

Core claim

By modeling the pricing and separation subproblems arising in a branch-price-and-cut algorithm as QUBO problems, quantum heuristics like quantum annealing or QAOA can generate candidate solutions for the exact solver; the algorithm benefits from the full set of solutions below a cost threshold, which reduces hardware-size requirements because only the smaller subproblems are handed to the quantum device.

What carries the argument

Reformulation of pricing and separation subproblems as QUBO instances solved by quantum heuristics, with the exact solver collecting and using all solutions below a cost threshold.

If this is right

  • The subproblems remain smaller than the original routing instance, lowering the qubit or connectivity demands on quantum hardware.
  • Both the pricing problem and the separation problem appear suitable targets for quantum heuristics once hardware improves.
  • The overall branch-price-and-cut procedure stays exact while potentially exploiting the distribution of solutions produced by quantum randomness.
  • Current experiments show the hybrid method is still slower than pure classical solvers but establish a concrete integration pathway.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same QUBO modeling of column-generation subproblems could allow quantum subroutines in other exact combinatorial solvers that rely on pricing.
  • Collecting multiple solutions below threshold may favor quantum devices that produce broad low-energy distributions over those returning only the ground state.
  • If hardware scales, the approach could be tested on larger real-world routing instances to measure actual speedups in node exploration.

Load-bearing premise

The quantum heuristics must return distributions of solutions for the QUBO models that contain enough low-cost candidates to reduce iterations or nodes in the branch-price-and-cut tree instead of adding net overhead.

What would settle it

Running the hybrid algorithm and a purely classical counterpart on standard vehicle-routing benchmark sets and checking whether total runtime or the number of pricing and separation calls decreases when the quantum heuristic is used.

Figures

Figures reproduced from arXiv: 2412.15665 by Frauke Liers, Friedrich Wagner.

Figure 1
Figure 1. Figure 1: Schematic workflow of branch-price-and-cut. The algorithm builds a branch-and-bound tree [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a): Schematic algorithm workflow for benchmarking pricing heuristics. We compare exclus [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a): Schematic algorithm workflow for benchmarking separation heuristics. (b): Decrease in [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
read the original abstract

Motivated by recent progress in quantum hardware and algorithms researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As however quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide an experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proposes embedding quantum heuristics (quantum annealing and QAOA) as oracles inside a branch-price-and-cut solver for the vehicle routing problem. Pricing and separation subproblems are reformulated as QUBOs so that established quantum methods can be applied; the framework explicitly uses the entire distribution of solutions below a cost threshold rather than only the best solution, and it reduces qubit requirements by operating on smaller subproblems. An experimental comparison against simulated annealing and classical methods is reported, with the authors candidly noting that the hybrid solver remains slower than pure classical BPC on the tested instances and framing the work as a proof-of-concept for future hardware.

Significance. If the central claim holds, the work supplies a concrete, non-circular algorithmic template for inserting limited quantum resources into exact solvers for NP-hard combinatorial problems. The explicit exploitation of the full low-cost solution distribution and the reduction of subproblem size are practical design choices that could become advantageous once quantum hardware improves. The manuscript also demonstrates that exactness of the overall BPC procedure is preserved because the quantum subroutines are used only to generate candidate columns or cuts that are subsequently verified classically.

major comments (1)
  1. [Abstract / Experimental Study] Abstract and experimental section: the claim that 'pricing and separation may be well suited for quantum heuristics' is presented without any reported quantitative metrics (run times, number of instances solved, gap closures, or instance sizes), error bars, or comparison tables. This absence makes it impossible to evaluate whether the quantum subroutines accelerate convergence or merely add overhead on the tested instances.
minor comments (2)
  1. [Experimental Study] The manuscript should include a short table or paragraph in the experimental section that lists the instance sizes, number of QUBO variables per subproblem, and at least one performance metric (e.g., time to first feasible solution or number of columns generated) for the quantum versus classical variants.
  2. [Modeling Pricing and Separation as QUBOs] Notation for the QUBO formulation of the pricing problem should be cross-referenced to the classical column-generation pricing oracle so that readers can verify equivalence.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation of minor revision. The positive assessment of the framework's design choices is appreciated. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract / Experimental Study] Abstract and experimental section: the claim that 'pricing and separation may be well suited for quantum heuristics' is presented without any reported quantitative metrics (run times, number of instances solved, gap closures, or instance sizes), error bars, or comparison tables. This absence makes it impossible to evaluate whether the quantum subroutines accelerate convergence or merely add overhead on the tested instances.

    Authors: We agree that the abstract would be strengthened by including concrete quantitative metrics from the experimental study. The manuscript's experimental section reports comparisons of quantum annealing against simulated annealing and classical methods, including run times on specific instance sizes and the observation that the hybrid approach remains slower; however, these details are not summarized with tables, error bars or explicit numbers in the abstract. We will revise the abstract to incorporate key metrics (e.g., number of instances tested, average run times, and performance relative to classical baselines) so that readers can directly assess the current overhead versus potential future advantage. revision: yes

Circularity Check

0 steps flagged

No significant circularity; algorithmic framework is self-contained

full rationale

The manuscript proposes a hybrid framework embedding quantum heuristics (QA, QAOA) as oracles inside branch-price-and-cut by casting pricing and separation as QUBOs, exploiting the full distribution of solutions below a cost threshold. No equations, predictions, or derivations are present that reduce by construction to fitted inputs, self-definitions, or self-citation chains. The contribution is the modeling choice and integration strategy itself, which remains independent of any internal circular reduction and is presented as a proof-of-concept without load-bearing uniqueness claims or ansatzes imported from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone.

pith-pipeline@v0.9.0 · 5793 in / 1008 out tokens · 25500 ms · 2026-05-23T06:59:31.771789+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

75 extracted references · 75 canonical work pages · 1 internal anchor

  1. [1]

    Robert E. Bixby. Solving real-world linear programs: A decade and more of progress.Operations Research, 50(1):3–15, 2002.doi:10.1287/opre.50.1.3.17780

    work page doi:10.1287/opre.50.1.3.17780 2002

  2. [2]

    Progress in mathematical programming solvers from 2001 to 2020.EURO Journal on Computational Optimization, 10:100031,

    Thorsten Koch, Timo Berthold, Jaap Pedersen, and Charlie Vanaret. Progress in mathematical programming solvers from 2001 to 2020.EURO Journal on Computational Optimization, 10:100031,

    work page 2001

  3. [3]

    doi:10.1016/j.ejco.2022.100031

    work page doi:10.1016/j.ejco.2022.100031 2022

  4. [4]

    The exact residual is computed using the exact active set, not the initial ε0-active set

    Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MI- PLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library.Mat...

    work page doi:10.1007/s12532-020-00194-3 2017

  5. [5]

    Abbas, A

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, 16 Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten...

    work page arXiv 2023

  6. [6]

    Quantum com- puting for discrete optimization: A highlight of three technologies, 2024.arXiv:2409.01373

    Alexey Bochkarev, Raoul Heese, Sven Jäger, Philine Schiewe, and Anita Schöbel. Quantum com- puting for discrete optimization: A highlight of three technologies, 2024.arXiv:2409.01373

    work page arXiv 2024

  7. [7]

    Fekete, Paulina L

    Sabrina Ammann, Maximilian Hess, Debora Ramacciotti, Sándor P. Fekete, Paulina L. A. Goedicke, David Gross, Andreea Lefterovici, Tobias J. Osborne, Michael Perk, Antonio Rotundo, S. E. Skelton, Sebastian Stiller, and Timo de Wolff. Realistic runtime analysis for quantum simplex computation,

    work page

  8. [8]

    Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation.Reviews of Modern Physics, 90(1), January 2018.doi:10.1103/revmodphys.90.015002

    work page doi:10.1103/revmodphys.90.015002 2018

  9. [9]

    McGeoch and Pau Farré

    Catherine C. McGeoch and Pau Farré. Milestones on the quantum utility highway: Quantum annealing case study.ACM Transactions on Quantum Computing, 5(1), dec 2023. doi:10.1145/ 3625307

    work page 2023

  10. [10]

    A Quantum Approximate Optimization Algorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization al- gorithm, 2014. arXiv:1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  11. [11]

    Harrigan, Kevin J

    Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, A...

    work page

  12. [12]

    doi:10.1038/s41567-020-01105-y

    work page doi:10.1038/s41567-020-01105-y

  13. [13]

    G. G. Guerreschi and A. Y. Matsuura. Qaoa for max-cut requires hundreds of qubits for quantum speed-up. Scientific Reports, 9(1), May 2019.doi:10.1038/s41598-019-43176-9

    work page doi:10.1038/s41598-019-43176-9 2019

  14. [14]

    Quantum annealing versus digital computing: An experimental comparison

    Michael Jünger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi, and Tobias Stollenwerk. Quantum annealing versus digital computing: An experimental comparison. ACM J. Exp. Algorithmics, 26, jul 2021.doi:10.1145/3459606

    work page doi:10.1145/3459606 2021

  15. [15]

    Lokhov, Sidhant Misra, and Carleton Coffrin

    Byron Tasseff, Tameem Albash, Zachary Morrell, Marc Vuffray, Andrey Y. Lokhov, Sidhant Misra, and Carleton Coffrin. On the emerging potential of quantum annealing hardware for combinatorial optimization, 2022. arXiv:2210.04291

    work page arXiv 2022

  16. [16]

    A new branch-and-cut algorithm for the capacitated vehicle routing problem

    Jens Lysgaard, Adam Letchford, and Richard Eglese. A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming, 100:423–445, 06 2004. doi: 10.1007/s10107-003-0481-8

    work page doi:10.1007/s10107-003-0481-8 2004

  17. [17]

    Improved branch-cut-and-price for capacitated vehicle routing.Mathematical Programming Computation, 9(1):61–100, Mar 2017

    Diego Pecin, Artur Pessoa, Marcus Poggi, and Eduardo Uchoa. Improved branch-cut-and-price for capacitated vehicle routing.Mathematical Programming Computation, 9(1):61–100, Mar 2017. doi:10.1007/s12532-016-0108-8. 17

    work page doi:10.1007/s12532-016-0108-8 2017

  18. [18]

    A generic exact solver for vehicle routing and related problems.Mathematical Programming, 183:483 – 523, 2019

    Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. A generic exact solver for vehicle routing and related problems.Mathematical Programming, 183:483 – 523, 2019. doi:10.1007/s10107-020-01523-z

    work page doi:10.1007/s10107-020-01523-z 2019

  19. [19]

    The vehicle routing problem

    Paolo Toth and Daniele Vigo. The vehicle routing problem. Society for Industrial and Applied Mathematics, 2002. doi:10.1137/1.9780898718515

    work page doi:10.1137/1.9780898718515 2002

  20. [20]

    Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.doi:10.1137/1.9781611973594

    Paolo Toth and Daniele Vigo.Vehicle Routing. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014.doi:10.1137/1.9781611973594

    work page doi:10.1137/1.9781611973594 2014

  21. [21]

    Cutting planes in integer and mixed integer programming.Discrete Applied Mathematics, 123(1):397–446, 2002

    Hugues Marchand, Alexander Martin, Robert Weismantel, and Laurence Wolsey. Cutting planes in integer and mixed integer programming.Discrete Applied Mathematics, 123(1):397–446, 2002. doi:10.1016/S0166-218X(01)00348-1

    work page doi:10.1016/s0166-218x(01)00348-1 2002

  22. [22]

    Quantum annealing of vehicle routing problem with time, state and capacity

    Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, Akira Miki, and Shinichirou Taguchi. Quantum annealing of vehicle routing problem with time, state and capacity. In Sebastian Feld and Claudia Linnhoff-Popien, editors,Quantum Technology and Optimization Problems, pages 145–156, Cham, 2019. Springer International Publishing

    work page 2019

  23. [23]

    Quantum annealing algorithm for vehicle scheduling

    Alan Crispin and Alex Syrichas. Quantum annealing algorithm for vehicle scheduling. In 2013 IEEE International Conference on Systems, Man, and Cybernetics, pages 3523–3528, 2013.doi: 10.1109/SMC.2013.601

    work page doi:10.1109/smc.2013.601 2013

  24. [24]

    Syrichas and A

    A. Syrichas and A. Crispin. Large-scale vehicle routing problems: Quantum annealing, tunings and results. Computers & Operations Research, 87:52–62, 2017.doi:10.1016/j.cor.2017.05.014

    work page doi:10.1016/j.cor.2017.05.014 2017

  25. [25]

    B., 1992, @doi [Statistical Science] 10.1214/ss/1177011136 , https://ui.adsabs.harvard.edu/abs/1992StaSc...7..457G 7, 457

    Dimitris Bertsimas and John Tsitsiklis. Simulated Annealing.Statistical Science, 8(1):10 – 15, 1993. doi:10.1214/ss/1177011077

    work page doi:10.1214/ss/1177011077 1993

  26. [26]

    New hybrid quantum annealing algorithms for solving vehicle routing problem

    Michał Borowski, Paweł Gora, Katarzyna Karnas, Mateusz Błajda, Krystian Król, Artur Matyjasek, Damian Burczyk, Miron Szewczyk, and Michał Kutwin. New hybrid quantum annealing algorithms for solving vehicle routing problem. In Valeria V. Krzhizhanovskaya, Gábor Závodszky, Michael H. Lees, Jack J. Dongarra, Peter M. A. Sloot, Sérgio Brissos, and João Teixei...

    work page 2020

  27. [27]

    Nguyen, James E

    Ramkumar Harikrishnakumar, Saideep Nannapaneni, Nam H. Nguyen, James E. Steck, and Eliza- beth C. Behrman. A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem, 2020. doi:10.48550/ARXIV.2005.12478

    work page doi:10.48550/arxiv.2005.12478 2020

  28. [28]

    Soundness Verification of Decision-Aware Process Models with Variable- to-Variable Conditions

    Sebastian Feld, Christoph Roch, Thomas Gabor, Christian Seidel, Florian Neukart, Isabella Galter, Wolfgang Mauerer, and Claudia Linnhoff-Popien. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer.Frontiers in ICT, 6, jun 2019. doi:10.3389/ fict.2019.00013

    work page arXiv 2019

  29. [29]

    An approach to the vehicle routing problem with balanced pick-up using ising machines

    Siya Bao, Masashi Tawada, Shu Tanaka, and Nozomu Togawa. An approach to the vehicle routing problem with balanced pick-up using ising machines. In2021 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), pages 1–4, 2021.doi:10.1109/VLSI-DAT52063.2021. 9427355

    work page doi:10.1109/vlsi-dat52063.2021 2021

  30. [30]

    Tambunan, Andriyan B

    Toufan D. Tambunan, Andriyan B. Suksmono, Ian J. M. Edward, and Rahmat Mulyawan. Quantum annealing for vehicle routing problem with weighted segment, 2022.doi:10.48550/ARXIV.2203. 13469

    work page doi:10.48550/arxiv.2203 2022

  31. [31]

    Quantum robustness verification: A hybrid quantum-classical neural network certification algorithm, 2022

    Nicola Franco, Tom Wollschlaeger, Nicholas Gao, Jeanette Miriam Lorenz, and Stephan Guen- nemann. Quantum robustness verification: A hybrid quantum-classical neural network certification algorithm, 2022. arXiv:2205.00900

    work page arXiv 2022

  32. [32]

    Efficient milp decomposition in quantum computing for relu network robustness, 2023

    Nicola Franco, Tom Wollschläger, Benedikt Poggel, Stephan Günnemann, and Jeanette Miriam Lorenz. Efficient milp decomposition in quantum computing for relu network robustness, 2023. arXiv:2305.00472. 18

    work page arXiv 2023

  33. [33]

    Optimization of a refinery scheduling process with column generation and a quantum annealer

    Joaquín Ossorio-Castillo and Fran Pena. Optimization of a refinery scheduling process with column generation and a quantum annealer. Optimization and Engineering, 23:1–18, 09 2022. doi:10. 1007/s11081-021-09662-8

    work page 2022

  34. [34]

    Efficient algorithm for binary quadratic problem by column generation and quantum annealing.Journal of the Physical Society of Japan, 92(11):113002, 2023

    Sota Hirama and Masayuki Ohzeki. Efficient algorithm for binary quadratic problem by column generation and quantum annealing.Journal of the Physical Society of Japan, 92(11):113002, 2023

    work page 2023

  35. [35]

    Quantum pricing-based column- generation framework for hard combinatorial problems.Physical Review A, 107(3), March 2023

    Wesley da Silva Coelho, Loïc Henriet, and Louis-Paul Henry. Quantum pricing-based column- generation framework for hard combinatorial problems.Physical Review A, 107(3), March 2023. doi:10.1103/physreva.107.032426

    work page doi:10.1103/physreva.107.032426 2023

  36. [36]

    Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs

    Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini, and Göran Johansson. Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs. Phys. Rev. Applied, 20(3):034062, 2023. doi:10.1103/PhysRevApplied.20. 034062

    work page doi:10.1103/physrevapplied.20 2023

  37. [37]

    Enhancing quantum algorithms for quadratic unconstrained binary optimization via integer programming, 2023.arXiv:2302.05493

    Friedrich Wagner, Jonas Nüßlein, and Frauke Liers. Enhancing quantum algorithms for quadratic unconstrained binary optimization via integer programming, 2023.arXiv:2302.05493

    work page arXiv 2023

  38. [38]

    Polyhedralanalysisand effectivealgorithmsforthecapacitatedvehiclerouting problem, 1999

    AnnElizabethBixby. Polyhedralanalysisand effectivealgorithmsforthecapacitatedvehiclerouting problem, 1999

    work page 1999

  39. [39]

    Ivănescu

    Peter L. Ivănescu. Some network flow problems solved with pseudo-boolean programming.Opera- tions Research, 13(3):388–399, 1965.doi:10.1287/opre.13.3.388

    work page doi:10.1287/opre.13.3.388 1965

  40. [40]

    A polynomial algorithm for the max-cut problem on graphs without long odd cycles.Mathematical Programming, 29(1):28 – 40, 1984

    Martin Grötschel and George Nemhauser. A polynomial algorithm for the max-cut problem on graphs without long odd cycles.Mathematical Programming, 29(1):28 – 40, 1984

    work page 1984

  41. [41]

    F. Hadlock. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing, 4(3):221–225, 1975.doi:10.1137/0204019

    work page doi:10.1137/0204019 1975

  42. [42]

    Pardella

    Frauke Liers and G. Pardella. Partitioning planar graphs: A fast combinatorial approach for max-cut. Computational Optimization and Applications, 51:323–344, 01 2012. doi:10.1007/ s10589-010-9335-5

    work page 2012

  43. [43]

    Springer Cham

    The Quadratic Unconstrained Binary Optimization Problem. Springer Cham. doi:10.1007/ 978-3-031-04520-2

    work page

  44. [44]

    Springer, 1997

    Michel Deza and Monique Laurent.Geometry of Cuts and Metrics. Springer, 1997

    work page 1997

  45. [45]

    Speeding up ip-based algorithms for constrained quadratic 0–1 optimization

    Christoph Buchheim, Frauke Liers, and Marcus Oswald. Speeding up ip-based algorithms for constrained quadratic 0–1 optimization. Mathematical Programming, 124(1):513–535, Jul 2010. doi:10.1007/s10107-010-0377-3

    work page doi:10.1007/s10107-010-0377-3 2010

  46. [46]

    Advantage processor overview

    Catherine McGeoch and Pau Farré. Advantage processor overview. Technical report, D-Wave Systems Inc., 2022

    work page 2022

  47. [47]

    URL:https://quantum-computing.ibm.com

    IBM Quantum, 2021. URL:https://quantum-computing.ibm.com

    work page 2021

  48. [48]

    Minor-embeddinginadiabaticquantumcomputation: I.theparametersetting problem

    VickySiu-NganChoi. Minor-embeddinginadiabaticquantumcomputation: I.theparametersetting problem. Quantum Information Processing, 7:193–209, 2008.doi:10.1007/s11128-008-0082-9

    work page doi:10.1007/s11128-008-0082-9 2008

  49. [49]

    Minor-embedding in adiabatic quantum computation: Ii

    Vicky Choi. Minor-embedding in adiabatic quantum computation: Ii. minor-universal graph design. Quantum Information Processing , 10(3):343–353, October 2010. doi:10.1007/ s11128-010-0200-3

    work page 2010

  50. [50]

    Lübbecke.Branch-Price-and-Cut Algorithms

    Jacques Desrosiers and Marco E. Lübbecke.Branch-Price-and-Cut Algorithms. John Wiley & Sons, Ltd, 2011. doi:10.1002/9780470400531.eorms0118

    work page doi:10.1002/9780470400531.eorms0118 2011

  51. [51]

    Lübbecke.A Primer in Column Generation, pages 1–32

    Jacques Desrosiers and Marco E. Lübbecke.A Primer in Column Generation, pages 1–32. Springer US, Boston, MA, 2005.doi:10.1007/0-387-25486-2_1

    work page doi:10.1007/0-387-25486-2_1 2005

  52. [52]

    Lübbecke and Jacques Desrosiers

    Marco E. Lübbecke and Jacques Desrosiers. Selected topics in column generation. Operations Research, 53(6):1007–1023, 2005.doi:10.1287/opre.1050.0234. 19

    work page doi:10.1287/opre.1050.0234 2005

  53. [53]

    CynthiaBarnhart, EllisL.Johnson, GeorgeL.Nemhauser, MartinW.P.Savelsbergh, andPamelaH. Vance. Branch-and-price: Column generation for solving huge integer programs.Operations Re- search, 46(3):316–329, 1998

    work page 1998

  54. [54]

    Hane, and Pamela H

    Cynthia Barnhart, Christopher A. Hane, and Pamela H. Vance. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems.Operations Research, 48(2):318–326, 2000

    work page 2000

  55. [55]

    The abacus system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization

    Michael Jünger and Stefan Thienel. The abacus system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization. Software: Practice and Experience , 30(11):1325–1352, 2000. doi:10.1002/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO; 2-T

    work page doi:10.1002/1097-024x(200009)30:11 2000

  56. [56]

    Branch-and-Cut Al- gorithms for Combinatorial Optimization and Their Implementation in ABACUS, pages 157–222

    Matthias Elf, Carsten Gutwenger, Michael Jünger, and Giovanni Rinaldi. Branch-and-Cut Al- gorithms for Combinatorial Optimization and Their Implementation in ABACUS, pages 157–222. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001.doi:10.1007/3-540-45586-8_5

    work page doi:10.1007/3-540-45586-8_5 2001

  57. [57]

    G. B. Dantzig and J. H. Ramser. The truck dispatching problem.Management Science, 6(1):80–91,

    work page

  58. [58]

    doi:10.1287/mnsc.6.1.80

    work page doi:10.1287/mnsc.6.1.80

  59. [59]

    Springer Berlin Heidelberg, Berlin, Heidelberg,

    Manfred Padberg.Primal-Dual Pairs, pages 87–120. Springer Berlin Heidelberg, Berlin, Heidelberg,

    work page

  60. [60]

    doi:10.1007/978-3-662-12273-0_6

    work page doi:10.1007/978-3-662-12273-0_6

  61. [61]

    Cvrpsep: A package of separation routines for the capacitated vehicle routing problem

    Jens Lysgaard. Cvrpsep: A package of separation routines for the capacitated vehicle routing problem. Working paper, 12 2003

    work page 2003

  62. [62]

    On the complexity of the separation problem for rounded capacity inequal- ities

    Ibrahima Diarrassouba. On the complexity of the separation problem for rounded capacity inequal- ities. Discrete Optimization, 25:86–104, 2017.doi:10.1016/j.disopt.2017.02.003

    work page doi:10.1016/j.disopt.2017.02.003 2017

  63. [63]

    The separation problem of rounded capacity inequalities: Some polynomial cases

    Ibrahima Diarrassouba. The separation problem of rounded capacity inequalities: Some polynomial cases. Discrete Optimization, 23:33–55, 2017.doi:10.1016/j.disopt.2016.11.005

    work page doi:10.1016/j.disopt.2016.11.005 2017

  64. [64]

    Kopman, William Pulleyblank, and L.E

    Ted Ralphs, L. Kopman, William Pulleyblank, and L.E. Trotter. On the capacitated vehicle routing problem. Mathematical Programming, 94:343–359, 01 2003.doi:10.1007/s10107-002-0323-0

    work page doi:10.1007/s10107-002-0323-0 2003

  65. [65]

    A neural separation algorithm for the rounded capacity inequalities, 2023.arXiv:2306.17283

    Hyeonah Kim, Jinkyoo Park, and Changhyun Kwon. A neural separation algorithm for the rounded capacity inequalities, 2023.arXiv:2306.17283

    work page arXiv 2023

  66. [66]

    Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem.Networks, 83(1):197–209,

    Konstantin Pavlikov, Niels Christian Petersen, and Jon Lilholt Sørensen. Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem.Networks, 83(1):197–209,

    work page

  67. [67]

    doi:10.1002/net.22183

    work page doi:10.1002/net.22183

  68. [68]

    Lucas, Frontiers in Physics2 (2014), 10.3389/fphy.2014.00005, arXiv:1302.5843

    Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics, 2, 2014. doi: 10.3389/fphy.2014.00005

    work page doi:10.3389/fphy.2014.00005 2014

  69. [69]

    URL:https://github.com/dwavesystems/dwave-ocean-sdk

    Dwave ocean sdk. URL:https://github.com/dwavesystems/dwave-ocean-sdk

    work page

  70. [70]

    Gurobi optimizer reference manual, 2023

    LLC Gurobi Optimization. Gurobi optimizer reference manual, 2023. URL:https://www.gurobi. com

    work page 2023

  71. [71]

    New benchmark instances for the capacitated vehicle routing problem.European Journal of Oper- ational Research, 257(3):845–858, 2017.doi:10.1016/j.ejor.2016.08.012

    Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem.European Journal of Oper- ational Research, 257(3):845–858, 2017.doi:10.1016/j.ejor.2016.08.012

    work page doi:10.1016/j.ejor.2016.08.012 2017

  72. [72]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009

    work page 2009

  73. [73]

    Domain wall encoding of discrete variables for quantum annealing and qaoa

    Nicholas Chancellor. Domain wall encoding of discrete variables for quantum annealing and qaoa. Quantum Science and Technology, 4(4):045004, August 2019.doi:10.1088/2058-9565/ab33c2

    work page doi:10.1088/2058-9565/ab33c2 2019

  74. [74]

    Performance of domain-wall encoding for quantum annealing

    Jie Chen, Tobias Stollenwerk, and Nicholas Chancellor. Performance of domain-wall encoding for quantum annealing. IEEE Transactions on Quantum Engineering, 2:1–14, 2021. doi:10.1109/ tqe.2021.3094280. 20

    work page arXiv 2021

  75. [75]

    Understanding domain-wall encoding the- oretically and experimentally

    Jesse Berwald, Nicholas Chancellor, and Raouf Dridi. Understanding domain-wall encoding the- oretically and experimentally. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 381(2241), December 2022.doi:10.1098/rsta.2021.0410. 21

    work page doi:10.1098/rsta.2021.0410 2022