PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2609.04593v1cs.LG

TL;DR

CVRPTW coarsening must reduce large QUBOs while avoiding family-specific tuning and poor random-instance feasibility. The paper combines adaptive coefficient conditioning with a single-configuration GNN coarsener, improving raw feasibility and preserving smaller solvable QUBOs, while hardware tests reproduce the conditioning effect.

  • Problem

    Existing CVRPTW coarsening depends on family-specific tuning and deteriorates on random instances, while direct QUBO formulations grow rapidly.

  • Method

    The paper calibrates QUBO penalties by controlling coefficient range and replaces the hand-tuned merge score with a GNN evaluated using simulated annealing and Advantage2 hardware.

  • Results

    Across N=10–100, the GNN preserves feasibility more reliably than the tuned heuristic while shrinking the QUBO approximately 5–6×; conditioning raises hardware raw feasibility from 0.02% to 39%.

  • Takeaways & Limitations

    Coefficient conditioning and learned coarsening improve raw feasibility and tractability, but the pipeline matches rather than surpasses the classical reference bound after repair and local search.

  • Takeaways & Limitations

    Hardware experiments test conditioning at approximately N=10–20 rather than benchmarking an end-to-end routing solver, and hardware pre-repair feasibility is below simulated annealing on the same QUBOs.

Abstract

from arXiv · show

Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expanded to the original graph. For the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), existing coarsening heuristics require family-specific tuning and remain unreliable on random instances. We address these limitations on the Solomon benchmark using simulated annealing and a D-Wave Advantage2 processor. We first introduce adaptive penalty calibration. Uniform penalty scaling has little effect, whereas controlling the internal coefficient range substantially improves raw samples. Removing non-binding constraints, normalising binding ones, and scaling the remaining penalties reduces mean raw constraint violations from 33.0 to 0.06 at the same solver budget (p=3.7e-11, n=56). A variable-count-preserving control attributes this gain to conditioning rather than problem size. Second, we replace the hand-tuned merge score with a graph neural network (GNN) using one configuration across all families. At N=10, it achieves 100% feasibility across all Solomon families, including R-type (100% vs. 80% for the tuned heuristic). Across N=10,...,100, feasibility is 83% vs. 69%, with the GNN better or tied on 85/90 instance-size pairs. At N=80,100, the difference is significant (p=0.002; 25/25 pairs), while the QUBO remains approximately 5-6 times smaller. Finally, hardware experiments reproduce the conditioning effect at fixed logical variable count: feasible samples increase from 0.02% to 39% across 13 instances. Classical repair with local search remains a reference bound for end-to-end solution cost.

1 Introduction

The paper targets QUBO size and unreliable family-specific coarsening for CVRPTW, introducing adaptive penalty calibration and a tuning-free GNN coarsener evaluated on Solomon instances and quantum hardware.

  • Motivation: Direct VRP QUBO encodings grow rapidly, so only small instances fit current quantum-annealing hardware.Graph coarsening merges compatible customers, solves a reduced problem, and expands the solution.
  • Motivation: Family-specific coarsening tuning preserves clustered-instance feasibility but deteriorates on random instances.The paper targets this dependence on family-specific hyperparameters.
  • Contributions: Adaptive calibration reduces raw constraint violations from 33.0 to 0.06 at equal solver budget by controlling QUBO conditioning rather than uniformly scaling penalties.The contribution drops non-binding constraints, normalises binding ones, and scales remaining penalties.
  • Contributions: A single GraphSAGE-based configuration recovers 100% R-type feasibility at N=10 without per-family tuning.The learned merge scorer replaces the hand-tuned heuristic.
  • Contributions: Across N=10–100, learned coarsening preserves feasibility more reliably, remains significant at N=80 and 100, and shrinks the QUBO approximately 5–6×.The hardware validation compares conditioning at fixed logical-variable count.

2 Background and related work

The paper formulates CVRPTW as a constrained QUBO and situates coarsening, penalty selection, learned heuristics, and hardware embedding as responses to routing encodings that scale poorly on annealers.

  • Problem and QUBO background: CVRPTW seeks minimum-distance vehicle routes that visit each customer once while satisfying capacity and time-window constraints.Travel time is proportional to Euclidean distance, and early arrival permits waiting.
  • Problem and QUBO background: Penalty methods encode constrained routing by adding weighted squared-violation terms to the QUBO energy.The study uses simulated annealing to isolate algorithmic effects from hardware noise.
  • References and comparisons: OR-Tools provides the strong classical reference used for comparison.
  • References and comparisons: Position-based routing encodings grow quickly, while sparse qubit connectivity makes minor embedding expensive.Graph coarsening addresses this size and connectivity difficulty.
  • Coarsening: Prior CVRPTW coarsening supplies the procedure and encoding but retains per-family hyperparameter dependence.This paper aims to remove that dependence.
  • Penalty selection: Penalty weights must prevent profitable violations while avoiding unnecessary coefficient range that consumes finite annealer precision.The paper’s conditioning result concerns coefficient range, especially the capacity-slack block.
  • Learned heuristics: The merge scorer uses GraphSAGE and reward-driven expert iteration, extending learned combinatorial-optimization heuristics to coarsening.
  • Hardware embedding: Minor embedding maps logical QUBOs onto fixed processor connectivity, with higher-degree Advantage2 topology enabling shorter chains for comparable logical problems.

3 Method

The method combines spatio-temporal graph coarsening, position-based QUBO routing, adaptive penalty calibration, and a reward-trained GNN that scores feasible customer merges.

  • Pipeline: The pipeline replaces heuristic coarsening scores with a GNN and static penalties with adaptive calibration, while OR-Tools supplies the cost reference.
  • 3.1 Spatio-temporal coarsening: Coarsening ranks candidate edges, keeps time-feasible pairs, and repeatedly forms super-nodes until the target node fraction is reached.The permissiveness parameter controls the candidate fraction, while smaller P produces more aggressive merging.
  • 3.1 Spatio-temporal coarsening: A merged super-node sums demands, combines service time with internal travel, tightens the feasible time window, and later restores the original customer order.Including internal travel prevents it from being counted again after inflation.
  • 3.2 QUBO formulation: The position encoding uses binary variables x_i,j,k to indicate vehicle visits to customers at route steps, with FQS and APS differing in route-step allocation.The default APS radius r=1 coincides with the FQS prescription.
  • 3.2 QUBO formulation: The QUBO penalises visit uniqueness, capacity, self-loop, time-window, and continuity violations while minimising a lower-weight distance objective.Weights strictly prioritise stronger constraints over weaker ones.
  • 3.3 Adaptive penalty calibration: Capacity uses binary log-slack, whose squared penalty can create very large couplings.These slack-induced couplings motivate adaptive calibration.
  • 3.3 Adaptive penalty calibration: Adaptive penalties scale weights relative to an objective upper bound, drop non-binding capacity constraints, and normalise binding capacity terms.Normalisation returns the capacity block to the scale of the remaining penalties; scaling alone changes little.
  • 3.4 GNN merge scorer: The GNN uses GraphSAGE layers and a symmetric edge head to replace the heuristic score while retaining explicit feasibility checks.Training labels come from instance-specific downstream rewards across heuristic settings and model rollouts.

4 Experimental setup

Experiments use the Solomon CVRPTW benchmark, fixed solver budgets, and a held-out, family-stratified evaluation design. OR-Tools supplies a feasible-solution cost reference rather than a certified optimum, while statistical tests aggregate seeds at the instance level.

  • Benchmark: 56 Solomon instances span clustered, random, and mixed customer locations with narrow or wide scheduling horizons.Series 1 has narrower windows and lower vehicle capacity; Series 2 has wider windows and greater capacity.
  • Benchmark: The GNN uses a deterministic family-stratified split of 43 training and 13 held-out test instances, with test data excluded from training and model selection.
  • Baselines: OR-Tools provides a strong classical cost reference under a fixed time limit, but does not certify optimality.The paper reports feasible-run cost gaps relative to OR-Tools and avoids calling them optimality gaps.
  • Evaluation protocol: All compared conditions receive identical solver budgets, including backend, reads, sweeps, and seed, with at least three seeds per experiment.Penalty and coarsening studies use five to ten seeds, and bootstrap 95% confidence intervals are reported.
  • Benchmark visualization: Figure 4 shows the first 25 customers in representative Solomon instances, encoding window-open time ei by colour and the depot as a red star.The random R family is identified as the hard family throughout.
  • Evaluation protocol: Primary Wilcoxon tests median-aggregate runs across seeds per instance before forming pairs, while feasibility and cost-gap comparisons are analyzed separately.Experiments ran on a single workstation, with GPU use limited to GNN training.

5 Results

Results show that adaptive penalty conditioning improves raw QUBO samples, while GNN-guided coarsening preserves feasibility more reliably across instance families and sizes. Coarsening also reduces QUBO size, but final solution cost remains bounded by classical repair.

  • Baseline reproduction: Coarsening reduced QUBO size by approximately P 2, accelerated sampling by about 3.2×, and lowered route distance by 16–25% among feasible runs.
  • Adaptive penalty calibration: 33.0 to 0.06 mean pre-repair violations and 0.7% to 94.8% pre-repair feasibility followed adaptive penalty calibration at equal solver budget.The paired Wilcoxon test gave p=3.7 × 10−11 with n=56.
  • Adaptive penalty calibration: Objective scaling alone changed violations from 33.0 to 29.6, whereas dropping non-binding capacity constraints reduced them to 3.4 before binding-weight normalisation completed the improvement.
  • Adaptive penalty calibration: At 131 variables, cap-crush matched full adaptive with 0.06 pre-repair violations and 94.6% feasibility, isolating internal dynamic range rather than problem size as the key lever.Cap-crush used 30 more variables than smart-cap.
  • GNN-guided coarsening: At N=10, the GNN achieved 100% feasibility across families, including 100% for R-type versus 80% for the tuned heuristic, while attaining approximately 0.98 edge-ranking AUC.
  • Learned coarsening: Across N∈{10,20,40,50,60,80,100}, GNN feasibility was 83.3% versus 68.9%, better or tied on 85 of 90 pairs, using one configuration across families.The paired Wilcoxon comparison over size-instance pairs gave p=3.4 × 10−4.
  • Learned coarsening: At N=80,100, the tuned heuristic fell to 53.8–58.3% feasibility while the GNN remained at 74.4–75.0%, indicating poorer transfer of family-tuned parameters.
  • Tractability and scaling: Coarsening kept the QUBO approximately 5–6× smaller and solvable through N=100, although the coarsened formulation still grew with N.The uncoarsened QUBO grew from 156 variables at N=10 to 15,450 at N=100.

6 Evaluation on quantum hardware

Hardware experiments reproduce the conditioning effect at fixed logical variable count, while embedding remains limited to small instances. The relevant hardware quantity is Ising rescaling into device ranges, not the raw coefficient ratio.

  • At N=20, the uncoarsened formulation fails to embed, while both coarsened variants embed with maximum chains of length 11.
  • 39.4% feasible samples with cap-crush versus at most 0.2% with static penalties confirms the conditioning effect at matched logical variable count.Cap-crush also reduces mean pre-repair violations from 12.6 to 1.1 per sample.
  • The static and cap-crush comparison uses the same logical variable count, isolating coefficient conditioning from problem size.The controlled comparison averages 47.8 logical variables per instance.
  • The Ising rescaling factor, rather than the raw coefficient ratio, predicts hardware raw quality because compression pushes objective terms below coupler resolution.The rescaling factors are 2.7 × 10^10 for static and 1.7 × 10^5 for cap-crush.
  • The hardware result is a conditioning study at approximately N=10–20, not evidence that the annealer outperforms classical sampling or end-to-end routing.Simulated annealing reaches 79% pre-repair feasibility versus 43% on the processor at N=10.

7 Beyond the position encoding

Alternative encodings separate QUBO size from feasibility by changing where routing constraints are represented. Route activation reduces variables but remains incomplete, whereas set partitioning builds feasibility into a classical route pool and substantially improves raw samples.

  • Route activation reduces the N=20 QUBO from 420 to 59–75 variables but lowers feasibility with GNN coarsening from 66.7% to 55.6%.
  • Route activation is not a complete CVRPTW formulation because it omits cumulative travel time along routes.Individually admissible arcs can still form a sequence that violates a time window.
  • Set partitioning generates routes that already satisfy capacity and time-window constraints, leaving the QUBO to select a minimum-cost exact cover.
  • Exact-cover rates reach 97%, 97%, and 96% at N=10, 15, and 20, versus 79%, 45%, and 45% pre-repair feasibility for position encoding.The corresponding route pools contain only 56–90 variables.
  • The set-partitioning comparison suggests that the conditioning burden belongs to the position encoding rather than intrinsically to CVRPTW.

8 Discussion and limitations

The paper’s strongest transferable findings concern QUBO conditioning and coarsening that remains reliable across families and sizes. The conclusions are bounded by hardware scale, formulation scope, asymptotic growth, and the limited role of the learned merge score itself.

  • Fixed-variable controls show that conditioning, rather than a smaller search space, drives the improvement in raw sample quality.On Advantage2, raw feasibility rises from 0.02% to 39% without changing logical variable count.
  • Across N=10–100, the learned coarsener preserves feasibility more reliably than the tuned heuristic while keeping the QUBO solvable at N=100 and embeddable at N=20.
  • Hardware experiments benchmark conditioning at approximately N=10–20 rather than an end-to-end routing solver, and classical simulated annealing achieves higher pre-repair feasibility.
  • The claims concern raw sample quality, feasibility, and tractability rather than final solution cost, which remains bounded by classical repair followed by local search.
  • Coarsening reduces problem size by roughly five to six times but does not change the underlying encoding’s asymptotic growth.
  • The learned coarsener’s feasibility advantage comes from operating across families and sizes without retuning, not from its merge score in isolation.Its pooled pre-repair violation difference from a fixed-parameter heuristic is not significant (p=0.62).
  • Primary experiments use the Solomon benchmark and FQS/APS coincide under the studied configuration, limiting formulation and benchmark breadth.

9 Conclusion and future work

Adaptive calibration improves CVRPTW feasibility through coefficient conditioning, while learned coarsening improves feasibility and tractability across Solomon families. End-to-end solution cost nevertheless matches rather than surpasses the classical reference, and future work targets alternative encodings and hardware integration.

  • Conclusion: 39% raw feasibility is reached on hardware after conditioning, versus almost no feasible samples at the same logical variable count.The fixed-variable-count comparison attributes the improvement to conditioning rather than a smaller QUBO.
  • Conclusion: The learned coarsener preserves feasibility more often across N=10–100 with one configuration and reduces QUBO size by approximately five to six times.These reductions keep the formulation solvable at N=100 and embeddable at N=20.
  • Conclusion: After classical repair and local search, the pipeline matches but does not surpass the classical reference bound in end-to-end solution cost.The reported gains concern conditioning, feasibility, and tractability rather than final solution cost.
  • Future work: Set-partitioning is proposed as future work because it avoids the slack variables responsible for the conditioning burden and achieves 96–97% pre-repair feasibility.Hardware evaluation would require integrating route-pool generation into the optimization loop.
  • Reproducibility: All code, configurations, trained models, result files, and Solomon benchmark instances are available in the project repository.The materials are intended to reproduce every figure and table.
Loading 2609.04593v1…