Pith. sign in

REVIEW 3 major objections 6 minor 60 references

Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem

T0 review · 3 major / 6 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A quantum-assisted branch-and-price algorithm solves about 98% of graph-coloring benchmarks to optimality, using far fewer quantum shots than prior hybrid methods.

desk verdict A serious engineering integration of QAA sampling into branch-and-price for vertex coloring, but the branching rule is not shown complete and the 98% optimality claim is an empirical hit rate, not a proof within the algorithm. read the letter →

arxiv 2508.18887 v1 pith:43VYN4MD submitted 2025-08-26 quant-ph

Chiara Vercellino , M. Yassine Naghmouchi , Wesley Coelho , Giacomo Vitali , Alberto Scionti , Paolo Viviani , Olivier Terzo , Bartolomeo Montrucchio This is my paper
classification quant-ph
keywords vertexcoloringbranch-and-pricecolumngenerationquantumadiabaticalgorithmmaximumweightindependentsetneutral-atomprocessorunit-diskgraphhybridquantum-classicaloptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that the Vertex Coloring problem can be solved more efficiently by embedding a quantum adiabatic sampler inside a classical branch-and-price framework. The sampler is used to solve the pricing subproblem—finding high-weight independent sets to add as columns—and the resulting maximal independent sets are used both to build feasible colorings and to create branches. On a 140-instance benchmark (graphs of 10–16 vertices), the authors report reaching optimal colorings on roughly 98% of instances, while using orders of magnitude fewer quantum shots than their earlier branch-and-bound approach. The practical significance, if the claim holds, is that current noisy neutral-atom hardware can serve as a useful column generator inside classical optimization, not as a standalone solver.

What carries the argument

The load-bearing piece is the pricing subproblem reformulated as a maximum-weight independent set (MWIS) problem on the dual variables of the restricted master problem. Rather than solving that MWIS exactly at every column-generation iteration, QCBP runs a quantum adiabatic algorithm (QAA) on a neutral-atom register, sampling many candidate independent sets in parallel. The sampled maximal independent sets are then used as branching decisions: each child node fixes one such set as a color and removes its vertices from the graph. A classical exact ILP solver is called only at the end of the column-generation loop to certify that no negative reduced-cost column remains.

What would settle it

Rerun the 140-instance benchmark with each quantum sample replaced by an exact MWIS solver; if the same three instances still fail, the failures come from the branching scheme, not the quantum sampler. Alternatively, find a small graph whose unique optimal coloring uses a color class not contained in any maximal independent set the sampler ever generates—then QCBP cannot reach that optimal solution by construction.

Watch

Extended reading notes

Core claim

The central claim is that the bottleneck of classical branch-and-price for vertex coloring—the pricing subproblem, an NP-hard maximum-weight independent set problem—can be delegated to a neutral-atom quantum processor using a quantum adiabatic algorithm. QCBP repeatedly samples independent sets from the QPU, adds the best ones to the restricted master problem, and uses the maximal sets to branch. With this design, the paper reports an optimality rate of about 98 percent on the benchmark set and a median number of explored branch-and-bound nodes of at most 3, compared with up to 9 for the authors' prior method. On non-unit-disk graphs, where the physical embedding distorts connectivity, QCBP

Load-bearing premise

The branch-and-bound tree is assumed to explore every possible coloring, but it actually only branches on the maximal independent sets that the column-generation phase samples; the paper gives no proof that an optimal coloring can always be assembled from those sampled sets.

Editorial extensions

If this is right

  • If the 98% optimality rate holds more broadly, QCBP offers a template for using quantum samplers inside exact optimization frameworks rather than as standalone solvers.
  • The reduction in quantum shots (from 10^4–10^5 to below 10^4) makes the approach more feasible on current hardware with slow sampling rates.
  • The robustness on non-unit-disk graphs suggests that approximate embeddings may be acceptable for solving the pricing subproblem.
  • The three failures out of 140 instances are consistent with the paper's own labeling of the method as a heuristic, so a completeness proof or a stronger sampling strategy would be needed to claim exactness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the branch-and-bound search is genuinely incomplete—a possibility the paper does not rule out—then the 98% figure is an empirical success rate on small graphs, not a guarantee; on larger or adversarial instances the gap could widen.
  • The same column-generation-plus-sampling pattern could be lifted to other set-partitioning ILPs, such as bin packing or scheduling, where the pricing problem is also an MWIS or similar NP-hard selection problem.
  • A testable extension: replace the quantum sampler with an exact MWIS solver within the same QCBP loop; if the optimality rate stays at 100% and shot counts are irrelevant, the quantum contribution is the speed of column discovery, not the search completeness.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper proposes QCBP, a hybrid quantum-classical algorithm for the Vertex Coloring problem. It embeds a column-generation (CG) master problem in a branch-and-bound tree; pricing subproblems (maximum-weight independent set) are sampled by a quantum adiabatic algorithm on a neutral-atom QPU, with an exact GLPK solve as a termination safeguard. Branching creates one child per sampled maximal independent set by fixing that set as a color, and a greedy primal heuristic constructs feasible colorings from the generated columns. Experiments on 140 emulated instances (n=10-16) report optimality on ~98% of cases and lower QPU shot counts than the authors' prior HCG and BBQ-mIS methods; tests on a real QPU (up to n=40) are presented as evidence of robustness and scalability.

Significance. If the claims were fully supported, the paper would provide a concrete demonstration that neutral-atom QPU sampling can be integrated into a column-generation framework for vertex coloring, with the useful property that the final LP lower bound is certified by an exact classical solve. The authors deserve credit for the clear formulation of the CG master problem, the exact GLPK safeguard, the extensive shot-count statistics, and real-hardware PSP experiments on graphs beyond classical emulation. However, the branch-and-bound search is not proved complete, the hardware evidence supports only the PSP sampler rather than end-to-end solution of larger instances, and the comparisons are limited to the authors' own baselines. The result is therefore best read as a promising heuristic hybrid pipeline; the exactness and scalability claims go beyond what is demonstrated.

major comments (3)
  1. [Section 5.3.1 / 5.6.3] Branching incompleteness: Section 5.3.1 creates a child only by fixing λ_S=1 for maximal independent sets sampled during HCG; there is no λ_S=0 branch and no proof that the sampled mIS family covers an optimal coloring. The exact GLPK safeguard in Section 5.1 certifies only LP optimality of the RMP, not coverage of optimal integer colorings; an mIS containing an optimal color class can have non-positive reduced cost at the dual optimum and never enter the pool. Section 5.6.3 even allows termination when "no further maximal independent sets remain available for branching," which can occur because the pool is exhausted. The 3/140 failures in Table 2 are consistent with this. Unless completeness is proved, the ~98% figure in the abstract and Table 2 must be presented as an empirical heuristic success rate, with optimality certificates only where UB=LB.
  2. [Section 6.3] Scalability claim: Section 6.3 and the abstract claim 'practical applicability and scalability to larger graph instances,' but the hardware experiments for n=20,30,40 report only PSP-level metrics (fraction of negative-reduced-cost samples and mIS frequency, Figs. 6-7), not end-to-end QCBP optimality or final VC solutions. The only complete optimality demonstration is a 10-vertex instance (Figs. 8-9). These results validate the quantum sampler for MWIS, not the full solver's scalability. Please reframe the claim or add end-to-end results on larger hardware instances.
  3. [Section 6.2 / Tables 2-4] Baseline and attribution: Tables 2-4 and Figs. 4-5 compare QCBP only with the authors' own HCG and BBQ-mIS. Because QCBP includes an exact GLPK MWIS safeguard at the end of every column generation (Section 5.1), and Table 4 shows a median of 1-21.5 ILP calls per instance, the reported optimality improvement could be due mainly to these classical exact solves rather than to the quantum sampler. A control experiment using the same BP framework with GLPK-only pricing (no QPU), or an external classical BP solver, is needed to attribute the gain to the quantum component. Without it, 'outperforms' is not established.
minor comments (6)
  1. [Table 1 / Section 1] Typo: 'Acronyme' should be 'Acronym'; 'refereed' should be 'referred'.
  2. [Section 7] QAA is called 'Quantum Approximate Algorithm' in the conclusion; it should be 'Quantum Adiabatic Algorithm'.
  3. [Figures 6-7] Axis labels appear as garbled '/uni...' glyphs; the figures must be regenerated with readable labels.
  4. [Table 2] Please report the cause of the three failures (maximum node limit, no mIS available, or UB>LB) and whether the solver terminated with an optimality certificate.
  5. [Section 5.3.4] The node selection score UBloc(G'') × |E''| is not motivated; since a lower local upper bound is better, the choice of exploring higher scores first should be justified.
  6. [Availability] There is no data/code availability statement; provide the benchmark instances and implementations to make the comparison reproducible.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the 98% optimality claim is anchored to an external exact solver (GLPK), and comparisons to prior self-cited methods are empirical, not by-construction.

full rationale

I walked the claimed derivation chain: the algorithm solves the VCPF set-partitioning relaxation by column generation, uses QAA to sample MWIS pricing columns with a GLPK exact-solver safeguard, and embeds this in a branch-and-bound over maximal independent sets. The paper's headline 'optimality on ≈98% of benchmark instances' is measured against GLPK as an external exact VC solver (Section 6.2.1), so the success rate is not defined circularly by the algorithm's own outputs. The internal GLPK calls solve the MWIS pricing subproblem, not the VC benchmark, so they do not make the optimality metric self-referential. Comparisons to HCG and BBQ-mIS are empirical comparisons to prior published work by the authors; the claimed improvements are measured by optimality gaps, shot counts, and BB nodes, not derived from the citations. The self-citations to [7] and [8] are to peer-reviewed publications and serve as baselines and components, not as an unverified uniqueness argument. The real theoretical weakness is that branching is performed only on mISs produced by the column-generation pool, with no proof that these cover all optimal color classes (Sections 5.3.1, 5.6.3; stopping condition 'No further maximal independent sets remain available for branching'), and the paper itself labels the column-generation scheme a heuristic in Section 5.1. That is a completeness/correctness risk, not a circularity: the 98% figure is an empirical hit rate, and the paper does not claim to derive it from the branching rule alone. No step was found where a prediction is equivalent to an input by construction, where a fitted parameter is renamed a prediction, or where a load-bearing claim reduces to an unverified self-citation.

Assumptions & free parameters 6 free parameters · 6 assumptions · 0 invented entities

The algorithm imports standard decomposition and column-generation theory plus a physical model of neutral atoms; the paper's own contributions add hand-set pulse parameters, a trained embedding network, and an unproven completeness assumption for the branching rule. No new particles, forces, or physical entities are introduced.

free parameters (6)
  • QAA shots per PSP iteration = 200 (used in the hardware example, Figure 8)
    Hand-chosen number of samples per pricing solve; directly affects measured shot counts and column diversity.
  • QAA total evolution time = 3 µs
    Fixed to stay within QPU coherence time; a hand-set hyperparameter in Section 5.2.2.
  • Detuning ramp endpoints = δ(t0) = −15, δ(tf) = +15 rad/µs
    Fixed independently of the graph instance (Section 5.2.2).
  • Rabi frequency cap = Ωmax = 4π rad/µs
    Hardware-specified limit used to set the pulse amplitude (Section 5.2.2).
  • DEN training epochs = 3000 per graph, batch size 1
    The embedding network is retrained per instance for 1-2 minutes per graph (Section 5.2.1); architecture and full ELF loss are not specified.
  • Node selection score = UBloc(G'') × |E''|
    Hand-specified priority rule for exploring branch-and-bound nodes (Section 5.3.4).
assumptions (6)
  • standard math Column generation duality: the pricing subproblem reduces to MWIS with dual weights, and negative reduced-cost columns improve the LP relaxation
    Invoked in Section 5.1 (Eqs. 13-16); standard LP duality and Dantzig-Wolfe pricing theory.
  • domain assumption Rydberg blockade on the embedded unit-disk graph enforces independent-set constraints, so quantum samples are independent sets
    Physical assumption about neutral-atom QPUs used in Sections 3.1 and 5.2.2.
  • domain assumption Approximate (non-UD) embeddings produce a hardware graph G' with the same vertices and extra edges, so every sampled independent set is feasible for G
    Stated in Section 5.2.2 ('if Rmin < rmax, the effective graph G' contains more edges than G'); no verification on the 62 non-UD instances is reported.
  • ad hoc to paper The maximal independent sets generated by the HCG loop at each node are rich enough that branching on λS~=1 covers an optimal coloring
    Implicit in Section 5.3.1; no completeness proof is provided and the 3/140 failed instances suggest incompleteness.
  • standard math Classical spectral lower bounds (Hoffman, Elphick-Wocjan, Edwards-Elphick) are valid lower bounds for the chromatic number of the subgraph
    Used in Section 5.3.2, Eq. 18; these are published theorems.
  • domain assumption The final exact GLPK solve of the MWIS pricing problem guarantees that column generation terminates with a valid LP lower bound
    Design claim in Section 5.1; relies on GLPK correctly solving the ILP, a standard software assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem." pith.science (2026). https://pith.science/paper/43VYN4MD

@misc{pith2026250818887,
  author       = {Pith},
  title        = {Pith review of: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/43VYN4MD}},
  note         = {Machine review of arXiv:2508.18887}
}
abstract

This paper introduces Quantum Classical Branch-and-Price (QCBP), a hybrid quantum-classical algorithm for the Vertex Coloring problem on neutral-atom Quantum Processing Units (QPUs). QCBP embeds quantum computation within the classical Branch-and-Price (BP) framework to address three bottlenecks in classical BP algorithms: the computational cost of Pricing Subproblems (PSPs), branching efficiency, and the quality of primal heuristics. It uses quantum-assisted Column Generation (CG) based on Quantum Adiabatic Algorithms (QAA) to sample high-quality maximum-weight independent sets (MWIS), reducing the need to repeatedly solve NP-hard PSPs. The adapted branching strategy leverages quantum-generated independent sets to explore fewer nodes, tighten lower bounds, and converge faster. A classical primal heuristic rapidly builds feasible solutions from quantum-generated sets, avoiding unnecessary quantum calls or additional Integer Linear Programming (ILP) solves. Compared with our prior Hybrid Column Generation (HCG) and Branch-and-Bound through maximal Independent Set (BBQ-mIS), QCBP improves both quantum-resource utilization and solution quality. Extensive experiments show QCBP significantly outperforms HCG and BBQ-mIS, reaching optimality on $\approx 98\%$ of benchmark instances. Preliminary validation on real neutral-atom hardware indicates robustness to quantum noise and hardware constraints, supporting practical applicability and scalability to larger graph instances. QCBP emerges as a viable hybrid method for combinatorial optimization with promising scalability on near-term quantum hardware.

Figures

Figures reproduced from arXiv: 2508.18887 by the authors.

Figure 1
Figure 1. Workflow of the hybrid classical-quantum column generation approach. First, a minimal sub-set [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Adiabatic pulse example for a graph with [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Hybrid Quantum-Classical Branch-and-Price Algorithm (QCBP). [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Quantum shot distributions by method and graph type. [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Branch-and-Bound node distributions grouped by graph size [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Percentage of new sets found through PSP solution via QPU, grouped by PSP size [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: Percentage of mISs found through PSP solutions via QPU, grouped by PSP size [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: Occurrences of each bitstring sampled by the QPU and corresponding reduced cost. [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: Final coloring of a 10-vertex VC instance solved with QCBP on Orion Alpha QPU. [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

60 extracted references · 50 canonical work pages

  1. [1]

    Quantum computing with neutral atoms,

    L. Henriet, L. Beguin, A. Signoles, T. Lahaye, A. Browaeys, G.-O. Reymond, and C. Jurczak, “Quantum computing with neutral atoms,” Quantum, vol. 4, p. 327, 2020

    2020

  2. [2]

    Ultracold rubidium atoms excited to rydberg levels,

    D. Ciampini, O. Morsch, and E. Arimondo, “Ultracold rubidium atoms excited to rydberg levels,” Journal of Atomic, Molecular , Condensed Matter and Nano Physics, vol. 2, no. 3, pp. 161–167, 2015

    work page 2015

  3. [3]

    Graph algorithms with neutral atom quantum processors,

    C. Dalyac, L. Leclerc, L. Vignoli, M. Djellabi, W. d. S. Coelho, B. Ximenez, A. Dareau, D. Dreon, V . E. Elfving, A. Signoles et al., “Graph algorithms with neutral atom quantum processors,” The European Physical Journal A , vol. 60, no. 9, pp. 1–15, 2024

    work page 2024

  4. [4]

    Unit disk graphs,

    B. N. Clark, C. J. Colbourn, and D. S. Johnson, “Unit disk graphs,” Discrete mathematics, vol. 86, no. 1-3, pp. 165–177, 1990

    1990

  5. [6]

    Mixed-integer linear programming solver using benders decomposition assisted by a neutral-atom quantum processor,

    M. Y . Naghmouchi and W. d. S. Coelho, “Mixed-integer linear programming solver using benders decomposition assisted by a neutral-atom quantum processor,” Physical Review A, vol. 110, no. 1, p. 012434, 2024

    work page 2024

  6. [7]

    Quantum pricing-based column-generation framework for hard combinatorial problems,

    W. da Silva Coelho, L. Henriet, and L.-P. Henry, “Quantum pricing-based column-generation framework for hard combinatorial problems,” Physical Review A, vol. 107, no. 3, p. 032426, 2023

    work page 2023

  7. [8]

    Bbq-mis: a parallel quantum algorithm for graph coloring problems,

    C. Vercellino, G. Vitali, P. Viviani, E. Giusto, A. Scionti, A. Scarabosio, O. Terzo, and B. Montrucchio, “Bbq-mis: a parallel quantum algorithm for graph coloring problems,” in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) , vol. 2. IEEE, 2023, pp. 141–147

    work page 2023

  8. [9]

    On some applications of the selective graph coloring problem,

    M. Demange, T. Ekim, B. Ries, and C. Tanasescu, “On some applications of the selective graph coloring problem,” European Journal of Operational Research, vol. 240, no. 2, pp. 307–314, 2015

    work page 2015

Show all 60 references
  1. [10]

    Applications of graph coloring in modern computer science,

    S. Ahmed, “Applications of graph coloring in modern computer science,” International Journal of Computer and Information Technology, vol. 3, no. 2, pp. 1–7, 2012

    2012

  2. [11]

    An application of iterated local search to graph coloring problem,

    M. Chiarandini, T. Stützleet al., “An application of iterated local search to graph coloring problem,” inProceedings of the computational symposium on graph coloring and its generalizations . Ithaca New York (USA), 2002, pp. 112–125

    2002

  3. [12]

    G. C. Lewandowski, Practical implementations and applications of graph coloring . The University of Wisconsin- Madison, 1994

    1994

  4. [13]

    A survey of graph coloring-its types, methods and applications,

    P. Formanowicz and K. Tana´s, “A survey of graph coloring-its types, methods and applications,”F oundations of Computing and Decision Sciences , vol. 37, no. 3, pp. 223–238, 2012

    2012

  5. [14]

    Register allocation & spilling via graph coloring,

    G. J. Chaitin, “Register allocation & spilling via graph coloring,” ACM Sigplan Notices, vol. 17, no. 6, pp. 98–101, 1982. 19 Vercellino et al.: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem

    1982

  6. [15]

    A graph coloring algorithm for large scheduling problems,

    F. T. Leighton, “A graph coloring algorithm for large scheduling problems,”Journal of research of the national bureau of standards, vol. 84, no. 6, p. 489, 1979

    1979

  7. [16]

    Frequency assignment: Theory and applications,

    W. K. Hale, “Frequency assignment: Theory and applications,” Proceedings of the IEEE , vol. 68, no. 12, pp. 1497–1514, 1980

    1980

  8. [17]

    Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results,

    P. Hansen, M. Labbé, and D. Schindl, “Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results,” Discrete Optimization, vol. 6, no. 2, pp. 135–147, 2009

    2009

  9. [18]

    An exact approach for the vertex coloring problem,

    E. Malaguti, M. Monaci, and P. Toth, “An exact approach for the vertex coloring problem,”Discrete Optimization, vol. 8, no. 2, pp. 174–190, 2011

    2011

  10. [19]

    A column generation approach for graph coloring,

    A. Mehrotra and M. A. Trick, “A column generation approach for graph coloring,”informs Journal on Computing , vol. 8, no. 4, pp. 344–354, 1996

    1996

  11. [20]

    A branch-and-cut algorithm for graph coloring,

    I. Méndez-Díaz and P. Zabala, “A branch-and-cut algorithm for graph coloring,”Discrete Applied Mathematics, vol. 154, no. 5, pp. 826–847, 2006

    2006

  12. [21]

    A wide branching strategy for the graph coloring problem,

    D. R. Morrison, J. J. Sauppe, E. C. Sewell, and S. H. Jacobson, “A wide branching strategy for the graph coloring problem,” INFORMS Journal on Computing , vol. 26, no. 4, pp. 704–717, 2014

    2014

  13. [22]

    A branch-and-price algorithm for the robust graph coloring problem,

    C. Archetti, N. Bianchessi, and A. Hertz, “A branch-and-price algorithm for the robust graph coloring problem,” Discrete Applied Mathematics, vol. 165, pp. 49–59, 2014

    2014

  14. [23]

    A tutorial on column generation and branch-and-price for vehicle routing problems,

    D. Feillet, “A tutorial on column generation and branch-and-price for vehicle routing problems,” 4or, vol. 8, no. 4, pp. 407–424, 2010

    2010

  15. [24]

    Send a job to fresnel,

    Pasqal, “Send a job to fresnel,” https://docs.pasqal.com/cloud/fresnel-job/, 2025, pasqal Documentation (Cloud documentation), Last updated: June 30, 2025. Retrieved August 14, 2025

    2025

  16. [25]

    Hybrid classical–quantum branch-and-bound algorithm for solving integer linear problems,

    C. Sanavio, E. Tignone, and E. Ercolessi, “Hybrid classical–quantum branch-and-bound algorithm for solving integer linear problems,” Entropy, vol. 26, no. 4, p. 345, 2024

    2024

  17. [26]

    A quantum approximate optimization algorithm,

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” arXiv preprint arXiv:1411.4028, 2014

    2014 arXiv

  18. [27]

    Bayesian optimization with skopt; scikit-optimize 0.8.1 documenta- tion — scikit-optimize.github.io,

    “Bayesian optimization with skopt; scikit-optimize 0.8.1 documenta- tion — scikit-optimize.github.io,” [Accessed 26-08-2024]. [Online]. Available: https://scikit-optimize.github.io/stable/auto_examples/bayesian-optimization.html

    2024

  19. [28]

    Partitioning procedures for solving mixed-variables programming problems,

    J. BnnoBRs, “Partitioning procedures for solving mixed-variables programming problems,” Numer . Math, vol. 4, no. 1, pp. 238–252, 1962

    1962

  20. [29]

    Hybrid quantum benders’ decomposition for mixed-integer linear programming,

    Z. Zhao, L. Fan, and Z. Han, “Hybrid quantum benders’ decomposition for mixed-integer linear programming,” in 2022 IEEE Wireless Communications and Networking Conference (WCNC) . IEEE, 2022, pp. 2536–2540

    2022

  21. [30]

    Hybrid quantum-classical general benders decom- position algorithm for unit commitment with multiple networked microgrids,

    F. Gao, D. Huang, Z. Zhao, W. Dai, M. Yang, and F. Shuang, “Hybrid quantum-classical general benders decom- position algorithm for unit commitment with multiple networked microgrids,” arXiv preprint arXiv:2210.06678, 2022

    2022 arXiv

  22. [31]

    On hybrid quantum and classical computing algorithms for mixed-integer programming,

    C.-Y . Chang, E. Jones, Y . Yao, P. Graf, and R. Jain, “On hybrid quantum and classical computing algorithms for mixed-integer programming,” arXiv preprint arXiv:2010.07852, 2020

    2010 arXiv

  23. [32]

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

    J. Ossorio-Castillo and F. Pena-Brage, “Optimization of a refinery scheduling process with column generation and a quantum annealer,” Optimization and Engineering, vol. 23, no. 3, pp. 1471–1488, 2022

    2022

  24. [33]

    A branch and price approach for routing and refueling station location model,

    B. Yıldız, O. Arslan, and O. E. Kara¸ san, “A branch and price approach for routing and refueling station location model,” European Journal of Operational Research, vol. 248, no. 3, pp. 815–826, 2016

    2016

  25. [34]

    A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection,

    M. Dell’Amico, G. Righini, and M. Salani, “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection,” Transportation science, vol. 40, no. 2, pp. 235–247, 2006

    2006

  26. [35]

    A branch-and-price algorithm for an integrated production and inventory routing problem,

    J. F. Bard and N. Nananukul, “A branch-and-price algorithm for an integrated production and inventory routing problem,” Computers & Operations Research, vol. 37, no. 12, pp. 2202–2217, 2010

    2010

  27. [36]

    Unit commitment in electric energy systems,

    M. F. Anjos, A. J. Conejo et al., “Unit commitment in electric energy systems,” F oundations and Trends® in Electric Energy Systems, vol. 1, no. 4, pp. 220–310, 2017

    2017

  28. [37]

    A branch-and-price method for a liquefied natural gas inventory routing problem,

    R. Grønhaug, M. Christiansen, G. Desaulniers, and J. Desrosiers, “A branch-and-price method for a liquefied natural gas inventory routing problem,” Transportation Science, vol. 44, no. 3, pp. 400–415, 2010

    2010

  29. [38]

    Optimization framework for distributed energy systems with integrated electrical grid constraints,

    B. Morvaj, R. Evins, and J. Carmeliet, “Optimization framework for distributed energy systems with integrated electrical grid constraints,” Applied energy, vol. 171, pp. 296–313, 2016. 20 Vercellino et al.: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Colori...

    2016

  30. [39]

    A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times,

    M. J. P. Lopes and J. V . de Carvalho, “A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times,” European journal of operational research, vol. 176, no. 3, pp. 1508–1527, 2007

    2007

  31. [40]

    Branch-and-price for energy optimization in multi-hop wireless sensor networks,

    L. Xu and S. Haddad Vanier, “Branch-and-price for energy optimization in multi-hop wireless sensor networks,” Networks, vol. 80, no. 1, pp. 123–148, 2022

    2022

  32. [41]

    Optimal admission control in damper- based networks: Branch-and-price algorithm,

    M. Y . Naghmouchi, S. Ren, P. Medagliani, S. Martin, and J. Leguay, “Optimal admission control in damper- based networks: Branch-and-price algorithm,” in 2023 9th International Conference on Control, Decision and Information Technologies (CoDIT). IEEE, 2023, pp. 488–493

    2023

  33. [42]

    A branch-and-price approach for integrating nurse and surgery scheduling,

    J. Beliën and E. Demeulemeester, “A branch-and-price approach for integrating nurse and surgery scheduling,” European journal of operational research, vol. 189, no. 3, pp. 652–668, 2008

    2008

  34. [43]

    A tutorial on quantum approximate optimization algorithm (qaoa): Fundamentals and applications,

    J. Choi and J. Kim, “A tutorial on quantum approximate optimization algorithm (qaoa): Fundamentals and applications,” in 2019 international conference on information and communication technology convergence (ICTC). IEEE, 2019, pp. 138–142

    2019

  35. [44]

    The variational quantum eigensolver: a review of methods and best practices,

    J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y . Li, E. Grant, L. Wossnig, I. Rungger, G. H. Boothet al., “The variational quantum eigensolver: a review of methods and best practices,” Physics Reports, vol. 986, pp. 1–128, 2022

    2022

  36. [45]

    Hybrid quantum-classical heuristic to solve large-scale integer linear programs,

    M. Svensson, M. Andersson, M. Grönkvist, P. Vikstål, D. Dubhashi, G. Ferrini, and G. Johansson, “Hybrid quantum-classical heuristic to solve large-scale integer linear programs,” Physical Review Applied, vol. 20, no. 3, p. 034062, 2023

    2023

  37. [46]

    A hybrid quantum- classical approach to solving scheduling problems,

    T. Tran, M. Do, E. Rieffel, J. Frank, Z. Wang, B. O’Gorman, D. Venturelli, and J. Beck, “A hybrid quantum- classical approach to solving scheduling problems,” in Proceedings of the International Symposium on Combina- torial Search, vol. 7, no. 1, 2016, pp. 98–106

    2016

  38. [47]

    Neural optimization for quantum architectures: graph embedding problems with distance encoder networks,

    C. Vercellino, G. Vitali, P. Viviani, A. Scionti, A. Scarabosio, O. Terzo, E. Giusto, and B. Montrucchio, “Neural optimization for quantum architectures: graph embedding problems with distance encoder networks,” in 2023 IEEE 47th Annual Computers, Software, and Applications Co...

    2023

  39. [48]

    Efficient protocol for solving combinatorial graph problems on neutral-atom quantum processors,

    W. da Silva Coelho, M. D’Arcangelo, and L.-P. Henry, “Efficient protocol for solving combinatorial graph problems on neutral-atom quantum processors,” arXiv preprint arXiv:2207.13030, 2022

    2022 arXiv

  40. [49]

    Neural- powered unit disk graph embedding: qubits connectivity for some qubo problems,

    C. Vercellino, P. Viviani, G. Vitali, A. Scionti, A. Scarabosio, O. Terzo, E. Giusto, and B. Montrucchio, “Neural- powered unit disk graph embedding: qubits connectivity for some qubo problems,” in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) ....

    2022

  41. [50]

    Using QAOA and QAA to solve a ud-mis problem,

    “Using QAOA and QAA to solve a ud-mis problem,”https://pulser.readthedocs.io/en/latest/tutorials/qaoa_mis.html, accessed: 2022-11-05

    2022

  42. [51]

    A branch-and-price algorithm for the generalized assignment problem,

    M. Savelsbergh, “A branch-and-price algorithm for the generalized assignment problem,”Operations research, vol. 45, no. 6, pp. 831–841, 1997

    1997

  43. [52]

    Branching in branch-and-price: a generic scheme,

    F. Vanderbeck, “Branching in branch-and-price: a generic scheme,”Mathematical Programming, vol. 130, pp. 249–294, 2011

    2011

  44. [53]

    Bin packing with conflicts: a generic branch-and-price algorithm,

    R. Sadykov and F. Vanderbeck, “Bin packing with conflicts: a generic branch-and-price algorithm,”INFORMS Journal on Computing, vol. 25, no. 2, pp. 244–255, 2013

    2013

  45. [54]

    Glpk - gnu linear programming kit,

    “Glpk - gnu linear programming kit,” https://www.gnu.org/software/glpk/, accessed: 2022-11-05

    2022

  46. [55]

    Unit disk graph recognition is np-hard,

    H. Breu and D. G. Kirkpatrick, “Unit disk graph recognition is np-hard,” Computational Geometry, vol. 9, no. 1-2, pp. 3–24, 1998

    1998

  47. [56]

    Adiabatic quantum computation,

    T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Reviews of Modern Physics , vol. 90, no. 1, p. 015002, 2018

    2018

  48. [57]

    Quantum optimization for maximum independent set using rydberg atom arrays,

    H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin, “Quantum optimization for maximum independent set using rydberg atom arrays,” 2018. [Online]. Available: https://arxiv.org/abs/1808.10816

    2018 arXiv

  49. [58]

    Controlling quantum many-body dynamics in driven rydberg atom arrays,

    D. Bluvstein, A. Omran, H. Levine, A. Keesling, G. Semeghini, S. Ebadi, T. T. Wang, A. A. Michailidis, N. Maskara, W. W. Ho, S. Choi, M. Serbyn, M. Greiner, V . Vuleti´c, and M. D. Lukin, “Controlling quantum many-body dynamics in driven rydberg atom arrays,” Science, vol. 371...

    2021 doi

  50. [59]

    On eigenvalues and colorings of graphs. ii,

    A. Hoffman and L. Howes, “On eigenvalues and colorings of graphs. ii,” Annals of the New York Academy of Sciences, vol. 175, pp. 238 – 242, 03 2007

    2007

  51. [60]

    An inertial lower bound for the chromatic number of a graph,

    C. Elphick and P. Wocjan, “An inertial lower bound for the chromatic number of a graph,” arXiv preprint arXiv:1605.01978, 2016. 21 Vercellino et al.: Hybrid Quantum-Classical Branch-and-Price Method for the Vertex Coloring Problem

    2016 arXiv

  52. [61]

    Lower bounds for the clique and the chromatic numbers of a graph,

    C. Edwards and C. Elphick, “Lower bounds for the clique and the chromatic numbers of a graph,”Discrete Applied Mathematics, vol. 5, no. 1, pp. 51–64, 1983. 22

    1983

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.