GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer
Youssef Kamel Rezk, Paweł Gora
cs.LG
Quick verdict
Improves annealer CVRPTW feasibility via GNN coarsening + adaptive QUBO penalties; rigorous, honest study, but classical baselines still dominate end-to-end.
Summary
This paper targets two bottlenecks in solving the CVRPTW via QUBO formulations on quantum annealers: poor constraint conditioning and family-tuned graph coarsening. First, the authors show that uniformly scaling penalty weights barely changes simulated-annealing behavior, whereas controlling the QUBO's internal coefficient dynamic range matters greatly: dropping non-binding capacity constraints, normalizing binding ones, and rescaling the rest cuts mean pre-repair violations from 33.0 to 0.06 at N=10 under an equal budget (paired Wilcoxon p=3.7e-11, n=56). A cap-crush control preserving the variable count (131) matches full adaptation, isolating conditioning from problem size. Second, a GraphSAGE merge scorer trained by expert iteration replaces the hand-tuned coarsening score with one configuration across all Solomon families, reaching 100% feasibility at N=10 (including R-type: 100% vs 80% for the tuned heuristic) and 83.3% vs 68.9% across N=10–100 (better/tied on 85/90 pairs; significant at N=80/100, p=0.002) while shrinking the QUBO 5–6×. On a D-Wave Advantage2 processor at N=10, the conditioned formulation lifts pre-repair feasibility from 0.02% to 39.4% at an identical 48-variable count. The authors are candid: classical repair plus local search still beats every QUBO pipeline variant end-to-end, the annealer trails simulated annealing (79% vs 43%), and the instance-level test across sizes is marginal (p=0.055). Limitations: Solomon-only evaluation, a small hardware study, and a GNN advantage partly attributable to a heuristic baseline whose N=10 tuning transfers poorly.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Adaptive penalty calibration (drop non-binding capacity constraints, normalize binding ones, scale the rest) reduces mean pre-repair constraint violations from 33.0 to 0.06 at N=10 under an equal solver budget (paired Wilcoxon p=3.7e-11, n=56).
- The calibration gain is attributable to QUBO coefficient conditioning rather than problem-size reduction, because the variable-count-preserving cap-crush control (131 variables) matches full adaptation.
- A single-configuration GNN (GraphSAGE) merge scorer trained by expert iteration is better or tied on 85/90 instance-size pairs across N=10–100 (83.3% vs 68.9% coarsened feasibility), significant at N=80/100 (p=0.002), while keeping the QUBO 5–6× smaller.
- On a D-Wave Advantage2 processor at N=10, the conditioned formulation raises pre-repair feasibility from 0.02% to 39.4% at an identical 48-variable count, and the Ising rescaling factor (not the raw coefficient ratio) is the physically relevant conditioning proxy.
- The pipeline matches but does not surpass classical repair with local search on end-to-end cost, so the contribution is confined to QUBO conditioning, feasibility, and tractability.
Strengths
Causally clean conditioning control
The cap-crush control keeps the static 131-variable QUBO and changes only the dynamic range, yet matches full adaptive calibration exactly (0.06 pre-repair violations, ~95% feasibility; Section 5.2, Fig. 7), cleanly separating conditioning from problem-size reduction. Scale-only (33.0→29.6, p=0.03) rules out magnitude as the lever.
Unusual honesty about negative results
Table 2 shows classical repair-only+local search (4.7–18.5% gap) beating every QUBO variant; SA beats the annealer (79% vs 43% pre-repair feasibility, Section 6.3); the instance-level test across sizes is disclosed as p=0.055 (Section 5.4); the abstract explicitly bounds claims to conditioning, feasibility, and tractability.
Statistical hygiene above field norm
Mechanism localization across encodings
Reproducibility posture
Weaknesses
No end-to-end practical advantage
GNN advantage partly a baseline-transfer artifact
Feasibility still degrades and the proposed fix fails
Minimal hardware evidence
Single benchmark and degenerate FQS/APS configuration
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper targets QUBO-based solution of the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) on quantum annealers, building directly on the coarsening approach of Özyılmaz (arXiv:2510.22329) and the FQS/APS position encoding of Borowski et al. Two method claims plus one hardware claim are central. **(1) Adaptive penalty calibration (§5.2):** absolute penalty scale is nearly inert for simulated annealing; the QUBO's internal coefficient dynamic range — dominated by the squared binary log-slack couplings of the capacity constraint, of order (2^m)²·Pcap (≈10¹² for Q=1000) — is the effective lever. Removing non-binding capacity constraints, normalizing binding ones (Eq. 5), and rescaling the rest cuts mean pre-repair violations from 33.0 to 0.06 at N=10 under equal budget (paired Wilcoxon, p=3.7e-11, n=56). A variable-count-preserving control (cap-crush, 131 variables) matches full adaptive (0.06 violations, 94.6% vs 94.8% feasibility), attributing the gain to conditioning rather than size. **(2) GNN-guided coarsening (§5.3–5.4):** a GraphSAGE merge scorer trained by expert iteration replaces the hand-tuned merge score with one configuration across all Solomon families — 100% feasibility at N=10 (R-type 100% vs 80%), 83.3% vs 68.9% across N=10–100 (better/tied on 85/90 pairs; significant at N=80/100, p=0.002), QUBO ~5–6× smaller. **(3) Hardware (§6):** on Advantage2 at N=10, pre-repair feasibility rises 0.02%→39.4% at a fixed 48-variable count. The authors explicitly bound all claims to conditioning, feasibility, and tractability — not end-to-end cost.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Does this paper show quantum computers beating classical solvers for vehicle routing?
No. The authors explicitly state the pipeline matches but does not surpass classical baselines: repair-only plus local search achieves 4.7–18.5% cost gaps versus 35.8–64.9% for the GNN QUBO pipeline (Table 2), and simulated annealing reaches 79% pre-repair feasibility versus 43% on the D-Wave Advantage2 processor. The claimed contribution is to QUBO conditioning, feasibility, and tractability, not end-to-end routing performance.
What are the two main innovations of the paper?
First, adaptive QUBO penalty calibration: showing that the internal coefficient dynamic range (dominated by squared binary log-slack couplings of the capacity constraint), not absolute penalty scale, drives raw solution quality — proven with a control that keeps variable count fixed while collapsing the range. Second, a GraphSAGE-based merge scorer trained by expert iteration that replaces family-specific coarsening hyperparameter tuning with one configuration across all Solomon benchmark families.
What problem sizes can actually be solved with this approach?
With coarsening, simulated annealing solves the reduced QUBO up to N=100 customers (2,577 variables vs 15,450 uncoarsened). However, hardware embeddability on D-Wave Advantage2 is limited to roughly N=10–20 customers; at N=40 no variant could be embedded, and the hardware experiments were run only at N=10.
Is the code and data available?
Yes. The paper states that all code, configurations, trained models, and result files needed to reproduce every figure and table are publicly available on GitHub (cvrptw-qubo-coarsening repository), including the Solomon benchmark instances. The main experiments use a seed-reproducible simulated-annealing backend; only the quantum hardware comparison requires QPU access.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figure-internal data points are accessible only through captions and in-text numbers (standard PDF-extraction limit); all quantitative claims cited in this review come from body text, tables, or caption annotations, all of which were present.
- The paper text appears complete (ends with the full reference list and acknowledgements); no truncation was detected.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.