PaperlayerView exact revision on arXiv

Source-linked AI summary

SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation

Haoran Liu, Guanyi Wang, Yu Yang

arXiv:2610.37952v1cs.LGcs.AImath.OC

TL;DR

Exact RCC separation is computationally prohibitive at scale, while existing heuristic and neural separators can struggle to produce enough effective cuts within practical budgets. SAG-Sep uses a sparse augmented LP graph and a single-pass encoder, with Onion-Sweep generating violation-guided nested candidates. At N=1000, SAG-Sep reduces the gap to 22.03%, versus 25.82% for π-NeuralSEP2+GC and 28.72% for CVRPSEP.

  • Problem

    Exact RCC separation becomes computationally prohibitive as customer counts grow, while existing methods face limits in cut throughput or scalable long-range inference.

    Source: §1 · p. 2

  • Method

    SAG-Sep encodes the fractional LP solution as a sparse graph with flow-informed multi-hop edges and scores subset membership in one pass, while Onion-Sweep selects violated ranking prefixes and nested proposals.

    Source: §1 · p. 2, §3.2 · pp. 5–6

  • Results

    At N=1000, SAG-Sep reduces the gap to 22.03%, versus 25.82% for π-NeuralSEP2+GC and 28.72% for CVRPSEP.

    Source: §4.2 · p. 9

  • Takeaways & Limitations

    The results suggest reframing cut generation as structured prediction over solver states, with attention architectures taking over expensive separation subroutines at the root node.

    Source: §6 · p. 12

    The main evaluation uses the NeuralSEP benchmark distribution, and the effect on complete branch-and-cut or branch-price-and-cut solves is only preliminarily tested.

    Source: §5 · pp. 11–12

Abstract

from arXiv · show

Rounded capacity cuts (RCCs) are among the most effective cuts for capacitated vehicle-routing relaxations, but exact separation is computationally prohibitive at scale. Existing heuristic and neural separators can be fast, but often fail to produce sufficiently many effective cuts within practical separation budgets. We introduce SAG-Sep, a separator that scores node membership in RCC-inducing subsets across vehicle-count levels from a fractional LP solution in a single encoder forward pass, avoiding the iterative predict-and-coarsen inference used by NeuralSEP-style separators. SAG-Sep encodes the LP solution as a Sparse Augmented Graph (SAG), adding flow-informed multi-hop edges that expose long-range routing structure without densifying attention. Beyond LP-aware sparse encoding, we observe that high-value exact RCCs are typically nested, organizing into onion-like subset families, and SAG-Sep's node scores track subset nesting depth. This motivates Onion-Sweep (OS), a training-free decoder that ranks customers by their scores, evaluates the RCC violation of every prefix of the ranking in one vectorized pass, and emits the most violated prefix of each replica together with a cross-replica family of nested proposals, converting independent node scores into structurally coordinated RCC candidates without a tuned threshold or probing band. On the NeuralSEP benchmark with N=1000 customer instances, SAG-Sep with OS reduces the average root gap by 17.7% relative to the strongest NeuralSEP baseline, while the single-pass SAG-Sep separator achieves a roughly 30-fold per-iteration neural separation speedup. Our findings suggest that LP-aware sparse encoding and the nested structure of high-value cuts are structural patterns worth leveraging in neural separation more broadly.

1 Introduction

RCC separation is effective but difficult to scale, while existing neural approaches face limits in capturing long-range structure and efficient inference. SAG-Sep combines sparse LP-aware encoding with score-guided, nested cut proposals.

1 Introduction

  • Exact RCC separation becomes computationally prohibitive at scale, while CVRPSEP can generate few effective cuts on larger problems.NeuralSEP-style recursive coarsening also incurs training and inference overhead, synchronization, and reduced GPU parallelism.Source: §1 · p. 2

1.1 Contributions

  • SAG-Sep adds flow-informed multi-hop edges to a sparse LP-support graph and scores RCC-subset membership across vehicle-count levels in one encoder pass.This avoids NeuralSEP-style iterative predict-and-coarsen inference.Source: §1 · p. 2, §1.1 · p. 3
  • Onion-Sweep uses violation-guided ranking prefixes and cross-replica nested proposals, motivated by the observed onion-like structure of high-value exact cuts.The decoder removes dependence on a tuned threshold and probing band.Source: §1 · p. 2, §1.1 · p. 3

1.2 Related Work

  • Learning-based cut generation directly proposes valid inequalities, a less-studied direction than selecting cuts from existing candidate pools.SAG-Sep predicts RCC-defining subsets from fractional LP solutions, extending neural separation approaches [Kim et al., 2024].Source: §1.2 · pp. 3–4

2 Preliminaries

The preliminaries define the CVRP and its capacity inequalities, then describe exact RCC separation as a search for violated subsets that can be added to the LP relaxation.

2.1 The Capacitated Vehicle Routing Problem (CVRP)

  • The CVRP seeks minimum-cost depot-rooted routes that serve every customer exactly once, subject to customer demands and vehicle capacity.The formulation uses edge variables and degree constraints to ensure each customer has exactly two incident edges.Source: §2.1 · p. 4

2.2 Exact Separation of RCCs

  • Because RCCs form an exponential family, solvers repeatedly separate them and add violated inequalities until the relaxation is sufficiently tight or bound improvements become marginal.The exact formulation’s optimal subset yields a violated inequality when its crossing value is below the required right-hand side.Source: §2.1 · p. 4, §2.2 · p. 5
  • RCC separation seeks a customer subset whose LP cutset value is below twice the rounded demand-to-capacity bound, with maximum violation as the exact objective.The rounded bound uses the minimum number of vehicles implied by total subset demand; exact separation enumerates vehicle-count right-hand sides and searches for a demand-heavy subset with low crossing value.Source: §2.2 · pp. 4–5, §2.1 · p. 4

3 Algorithmic Design of SAG-Sep

SAG-Sep scores customers in replicated sparse augmented graphs from the current LP solution, then forms RCC candidates for the separate–add–resolve loop. Its Onion-Sweep decoder searches ranked prefixes within and across replicas.

3.1 Pipeline Overview

  • The pipeline replicates the augmented graph, evaluates the replicas in one encoder pass, constructs candidate subsets, and adds violated RCCs back to the LP for re-optimization.Candidates come from thresholding or Onion-Sweep, and the loop continues until no violated cut is identified or the time or iteration budget is exhausted.Source: §3.1 · p. 5, Figure 1 · p. 6

3.2 Augmented LP Support Graph

  • The augmented graph retains LP-support edges with nontrivial LP mass and adds flow-informed multi-hop connections for sparse attention over longer-range routing structure.The multi-hop score is the largest bottleneck value among shortest LP-support paths of at most K hops; a small hop radius controls edge growth.Source: §3.2 · pp. 5–7

3.3 Onion-Sweep Decoding

  • Within each replica, Onion-Sweep selects the most violated ranked prefix; across replicas, it forms nested proposals from a global priority ordering.The sweep evaluates prefix violations in one vectorized pass; the threshold subset is also a ranking prefix, and the decoder has no tuned threshold or probing band.Source: §3.3 · pp. 7–8
  • Onion-Sweep is motivated by the observation that high-value exact cuts often form nested onion families ordered by required vehicle count.Onion prefixes with violation below 10^-4 are discarded before the final filter.Source: §3.3 · p. 8

4 Experiments

The experiments compare SAG-Sep with exact, heuristic, and learned RCC separators at the root node, then examine graph augmentation and test-time decoding. They report stronger large-instance bounds and evaluate when Onion-Sweep improves separation.

4.1 Experimental Setup

  • The root-node evaluation uses the NeuralSEP benchmark and compares SAG-Sep with exact, CVRPSEP heuristic, and NeuralSEP separators.The main comparison uses the CVRP formulation and reports mean optimality gap and total root-node runtime.Source: §4.1 · p. 9, §4.2 · p. 9

4.2 Single-Pass Separation vs. Recursive Coarsening

  • At N=1000, SAG-Sep reaches a 22.03% gap versus 25.82% for π-NeuralSEP2+GC and 28.72% for CVRPSEP, with 0.65s per-round neural separation.From N=400 onward, SAG-Sep gives the best gaps; it also has the lowest runtime at N=400–500. Table 1 reports the root-node gap and runtime comparison.Source: §4.2 · p. 9, Table 1 · p. 10

4.3 Augmented LP Graphs for RCC Separation

  • Flow-based edge values (+Val) give the best results at all sizes, while zero-feature connectivity edges degrade performance at eight of nine sizes.Hop-type information (+Hop) consistently improves over the raw LP-support graph; Table 2 compares separately trained augmented variants with hop radius 3, not Table 1 results.Source: §4.3 · p. 10, Table 2 · p. 10

4.4 Test-Time Refinement

  • Aggressive conditioned sampling improves bounds at all sizes, but its extra replica encoding costs more on small instances and becomes marginal when the LP loop dominates.Onion-Sweep needs no extra forward pass, but its larger number of proposals per round can increase root runtime at N=300–500.Source: §4.4 · p. 11
  • Onion-Sweep improves mean root bounds at every size and on 85 of 90 instances, by 1.5–2.1 pp at N≤200 and 0.4–0.9 pp at N≥300.Compared with Onion-MBP, OS improves bounds by 0.2–0.9 pp at N≤400; at N≥500, the two are within 0.25 pp in either direction. At N=300–500, OS has higher root runtime than the threshold readout and cut-managed Onion-MBP.Source: §4.4 · p. 11, Table 3 · p. 11

5 Limitations

The paper establishes results for root-node separation in the two-index formulation, while broader solver settings and transfer to other cut families have boundaries. It also identifies limitations involving training labels, benchmark coverage, and implementation comparisons.

Scope

  • The evaluation focuses on the root node of the two-index formulation; effects on complete branch-and-cut or branch-price-and-cut solves are only preliminarily tested.At N≤300, CVRPSEP remains stronger; the reported lower root gaps apply to large-scale, LP-bound regimes within the same time limit.Source: §5 · p. 11

Transfer boundaries

  • The encoder and decoder transfer to relaxations exposing edge values when the host formulation supplies the valid inequality and violation check, but heterogeneous fleets remain open without a single capacity C.Linehaul–backhaul and pickup-and-delivery loads also need variant-specific inequalities.Source: §5 · pp. 11–12

Labels, benchmark, and implementation

  • Exact-separation labels are expensive at training scale, label dependence limits fast transfer to other cut families, and the main evaluation uses the NeuralSEP benchmark distribution.The main speed comparisons use the Python research implementation against baselines’ own code; Onion-Sweep remains hand-designed, with a learned decoder left for future work.Source: §5 · p. 12

6 Conclusion

SAG-Sep combines a sparse, flow-informed graph representation with single-pass neural separation. Onion-Sweep uses the nested structure of high-value RCCs, while the paper points to broader structured-prediction directions for cut generation.

6 Conclusion

  • SAG-Sep adds flow-informed long-range structure to the LP-support graph, enabling single-pass neural separation.Its Sparse Augmented Graph representation supports the encoder without densifying attention.Source: §6 · p. 12
  • High-value RCCs are often nested and onion-like, and SAG-Sep's scores reflect this structure.Onion-Sweep exploits the pattern as a training-free decoder that tightens root bounds without extra forward passes or threshold tuning.Source: §6 · p. 12
  • The paper suggests framing cut generation as structured prediction over solver states, with attention architectures taking over expensive root-node separation subroutines.Proposed directions include learned decoding for candidate diversity and relaxation improvement, or feedback methods that optimize cut sets.Source: §6 · p. 12

Appendices

The appendix specifies SAG-Sep's edge-biased sparse transformer and analyzes the attention module's Lipschitz stability. The analysis relies on bounded node features and links stability to feature magnitudes, weight norms, and the sparse attention pattern.

A.1 Transformer Layer

  • SAG-Sep uses a pre-normalization transformer block with multi-head attention followed by a row-wise feed-forward network and residual connections.Edge embeddings are shared auxiliary features, entering each attention head through a scalar bias; attention is restricted to augmented-graph neighbors.Source: §A.1 · pp. 16–18, Figure 2 · p. 17
  • Attention is asymmetric across directed node pairs, omits self-loop attention edges, and relies on residual connections to carry prior node representations.Every vertex has positive LP degree, and the depot is connected to every customer, so each attention neighborhood is nonempty.Source: §A.1 · p. 17

A.2 Lipschitz Continuity of the Attention Module

  • Under bounded input node features, the appendix derives a Lipschitz bound for a single attention head and extends it to multi-head attention.The bounded-input assumption is described as stabilized in practice by layer normalization and finite inference activations.Source: §A.2 · pp. 18–19
  • The attention module's stability depends quadratically on node-feature magnitude, multiplicatively on weight spectral norms, and on the sparse attention pattern.This module-level result supports the local stability assumption used for conditioned-probing analysis, but Onion-Sweep does not rely on it.Source: §A.2 · pp. 18–19

A.3 Aggressive Sampling via Conditioned Probing

Aggressive conditioned probing evaluates more replicas to find candidate cuts beyond the base grid, but it increases inference and LP re-optimization costs. A stability and anti-concentration analysis explains why dense probing eventually has diminishing returns.

A.3 Aggressive Sampling via Conditioned Probing

  • Aggressive sampling evaluates conditioned replicas on a denser grid, thresholds their predictions, and evaluates the induced RCCs under the current LP solution.The resulting cuts are deduplicated and ranked by violation; finding useful cuts this way increases inference workload and LP re-optimization cost.Source: §A.3 · p. 19
  • Under a local Lipschitz assumption, intervals whose safety margin exceeds L/R have stable thresholded subsets; other intervals may contain threshold crossings.The proposition bounds the expected measure of the unstable region using marginal anti-concentration.Source: §A.3 · pp. 19–20
  • Dense conditioning saturates rather than improving indefinitely because new thresholded subsets require nodes near the decision boundary.The bound concerns the measure of the unstable conditioning region, not missed cuts; Onion-Sweep instead selects ranking prefixes by violation.Source: §A.3 · pp. 19–20
  • On 442 random LP states from N = 300 root relaxations, the empirical marginal satisfies Pr(|pi(w) − τ| ≤ ε) ≲ 0.6 ε for ε ≤ 0.1.The predictions concentrate near 0 and 1, with low density near τ = 0.5; the observed bimodal pattern is consistent across instances.Source: §A.3 · p. 20

A.4 Proof of the Resolution Error Bound

The resolution-bound appendix connects threshold instability to probability mass near the decision boundary. Its empirical figures show low central density in pooled predictions and a similar pattern across sampled instances.

A.4 Proof of the Resolution Error Bound

  • The aggregate prediction histogram is sharply bimodal at 0 and 1, with low mass near τ = 0.5; its CDF supports Pr(|pi(w) − τ| ≤ ε) ≲ 0.6 ε for ε ≤ 0.1.The empirical marginal pools roughly 6 × 10^6 post-sigmoid predictions from N = 300 root-relaxation LP states.Source: Figure 3 · p. 21
  • Across six sampled N = 300 root-relaxation LP states, the per-instance marginals show the same bimodal pattern and low density near τ = 0.5.An isolated secondary mode, such as Graph 0 near p = 0.45, does not violate the linear anti-concentration rate read from the aggregate CDF.Source: Figure 4 · p. 21
  • The proof bounds unstable intervals by expressing instability as a union over nodes and applying the marginal anti-concentration assumption.The appendix then substitutes this bound into the expected unstable-region measure.Source: §A.4 · pp. 20, 22

A.5 Proof of Sparse Augmentation Complexity

This section compares exact RCC formulations and examines how demand banding affects cut diversity. The demand-banded variant improves final average gaps and runtime on the largest reported instances.

A.5 Proof of Sparse Augmentation Complexity

  • The sparse-augmentation proof counts simple paths of length at most K, uses path appearance probability ρ^t, and bounds intersections between path pairs.The supplied proof passage concludes that an empty product converges to one for each fixed path length.Source: §A.5 · pp. 22–23

B Exact RCC Separation Study and Onion Analysis

  • The exact-separation study compares three related formulations and uses an upper-bounded, demand-banded variant to generate diverse cuts and study nesting.The section defines RCC violation as 2⌈D(S)/C⌉ − x̄(δ(S)).Source: B Exact RCC Separation Study and Onion… · p. 23

B.1 Three Exact RCC Separation Formulations

  • The direct violation-maximization formulation retains the lower-bound demand constraint, but high-demand subsets can dominate its enumeration and undermine cut diversity.Unlike the demand-banded variant, the lower-bound formulations can admit a subset at multiple vehicle-count values.Source: §B.1 · p. 24, §B.2 · p. 25

B.2 Diversity and Repetition Properties

  • Demand banding makes each subset feasible for at most one vehicle-count value, preventing repeated subsets within a separation round.Both lower-bound formulations can return duplicated subsets across multiple m values.Source: §B.2 · p. 25

B.3 Empirical Comparison of Exact Formulations

  • At N = 750 and N = 1000, demand banding improves final average gaps from 41.00% to 40.59% and from 50.61% to 50.08%, respectively, while reducing runtime.The comparison is between the classical lower-bound Fukasawa formulation and the demand-banded variant.Source: Table 4 · p. 26, §B.3 · p. 26

B.4 Onion Structure in Exact Labels and Learned Scores

Exact RCC subsets are largely nested across demand bands, and SAG-Sep scores align with exact membership frequency. Onion-Sweep uses these rankings to form coordinated nested candidate cuts.

B.4 Onion Structure in Exact Labels and Learned Scores

  • Exact-label M-nesting is 0.836–0.868 on XML100 and 0.74–0.85 on random labels from N = 50 to N = 1000; containment is 0.88–0.95 across those random-label sizes.The reported results indicate largely nested onion layers, including at the largest evaluated sizes.Source: Table 5 · p. 27, §B.4 · p. 27
  • SAG-Sep’s cross-replica mean-score correlation with exact membership frequency is 0.84–0.89 through N = 750 and 0.81 at N = 1000; the best replica reaches 0.83–0.91.The comparison uses Spearman correlation.Source: §B.4 · p. 27
  • Onion-Sweep selects the most violated prefix of each replica’s score ranking and forms demand-triggered prefixes across replicas to produce nested RCC candidates without additional training.The decoder replaces independent hard thresholding with within-replica violation-guided selection and cross-replica proposals based on soft frequency scores.Source: §B.4 · p. 27

C.1 Training Procedure

The appendix reports training and inference choices alongside supplemental comparisons of SAG-Sep’s quality, runtime, memory use, and decoding variants. Across these tests, the strongest results include near-exact fixed-round bounds at much lower runtime and improved performance from Onion-Sweep on large instances.

C.1 Training Procedure

  • XML40/XML50 recover much of XML100 performance with cheaper exact-label generation, supporting smaller exact-labeled datasets as a practical supervised bootstrap.XML20 labels take a few seconds per instance, XML30 tens of seconds, and XML40/XML50 around a minute; XML100 labeling can approach a one-hour cap on difficult instances.Source: §C.1 · p. 28

C.2 Loss Functions

  • The final configuration uses unweighted BCE: positive-class weighting and alternative averaging variants did not improve downstream separation quality in these tests.The checkpoint is trained on exact RCC labels generated across vehicle-count levels at root LP states.Source: §C.1 · p. 28, §C.2 · p. 29

C.3 Shared Edge Encoding and Inference Memory

  • 7.4×–13.1× lower peak allocated memory: shared-edge inference reuses edge encodings across replicas and completes large-instance cases that otherwise run out of memory.On small instances (N ≤75), the plain batched forward pass is faster; bounds are identical either way.Source: §C.3 · p. 30, Table 11 · p. 31

D.1 NeuralSEP1 Reproduction and One-Shot Base Model

  • At N ≥500, NeuralSEP1’s recursive-coarsening variant remains far behind SAG-Sep, while coarsening improves large-instance robustness at added small-instance overhead.The NeuralSEP1 one-shot model produces essentially zero violated cuts at N = 750 and 1000.Source: §D.1 · p. 33, Table 13 · p. 33

D.2 Fixed-Round Comparisons at N=1000

  • 0.003 percentage-point gap difference, with about 870× lower mean end-to-end runtime: SAG-Sep essentially matches exact separation after ten iterations on ten N = 1000 instances.The comparison reports final mean gap and runtime; the final bound is the LP after nine rounds of cuts.Source: Table 14 · p. 34, §D.2 · p. 34
  • From round 5, OS overtakes the threshold readout; it adds about 150 cuts per round at N = 1000, while π-NeuralSEP2+GC is weakest at every round.OS improves on the threshold readout on 85 of 90 instances and on π-NeuralSEP2+GC on 77 of 90.Source: §D.2 · p. 34, Table 15 · p. 34, §D.6 · p. 36

D.4 Serial SAG-Sep + CVRPSEP Hybrid

  • The serial SAG-Sep + CVRPSEP hybrid tightens root bounds but adds costly LP and heuristic work at larger sizes; near-exact bounds make the tradeoff favorable when they matter.At N = 200 it is within 0.01 pp of CVRPSEP’s gap in about a third of the runtime; at N = 300 and 400 it reaches lower gaps in less time.Source: §D.4 · p. 35, Table 17 · p. 35

D.5 Detailed K-hop Ablation

  • K = 2 gives the best gap at every tested size from N = 100 onward; TF32 has no uniform bound–time benefit, so the main results use fp32.The wider K-hop radii are consistently weaker from N = 100, and TF32 can worsen the final gap when node scores cross the τ = 0.5 cutoff.Source: §D.5 · p. 35, §D.3 · p. 35, Table 16 · p. 35

D.7 Generalization Beyond the Benchmark

The appendix tests SAG-Sep+OS beyond the main benchmark, describes the released engine’s scope, and reports preliminary root and branch-and-cut evaluations. Results are favorable in the tested transfer settings, with an identified boundary for prefix decoding and limited-scope solver experiments.

D.7 Generalization Beyond the Benchmark

  • OS wins all 60 paired comparisons against π-NeuralSEP2+GC on unseen XML regimes and 9 of 10 CVRPLIB X instances, and has a lower gap than CVRPSEP on all 70 instances.The frozen checkpoint was trained at N = 100 and tested at N = 500, 750, and 1000, as well as on X instances with N between 524 and 979.Source: §D.7 · p. 36, Table 20 · p. 37, Table 21 · p. 37
  • The prefix decoder only partially covers many small, disjoint cuts when demand per customer is unusually high; test-time cut refinement compensates on X-n524-k153.On that instance, the reported gap is 17.04% with refinement, versus 19.40% for OS and 19.04% for π-NeuralSEP2+GC.Source: §D.7 · p. 37

E Code Release and Scope Beyond the Root Node

  • The released repository includes solver integrations beyond the paper’s claimed contributions; these components are evaluated only preliminarily, while the main paper focuses on the root node.The branch-and-cut and branch-price-and-cut examples are described as preliminary, with a forthcoming extended version planned to evaluate them in detail.Source: E Code Release and Scope Beyond the… · pp. 37–38

E.1 The Released Engine Run to Closure Against CVRPSEP

  • At root-loop closure, the released engine and CVRPSEP reach bounds within 0.002 gap points at every size; the GPU engine is slower at N = 50 and 75, faster from N = 100.This is a systems comparison, not a like-for-like separator-speed comparison; the engine is three times faster at N = 200, while the CPU-only crossover moves to N = 200.Source: §E.1 · p. 38, Table 22 · p. 38

E.2 Preliminary Complete Branch-and-Cut

  • In five complete branch-and-cut runs, root bounds agree within 0.06 percentage points, so observed time and tree-size differences mainly reflect tree search rather than root-bound quality.The test set includes only N = 75 and 100 instances that CVRPSEP solves within the two-hour limit, so it compares solve times, not solve rates.Source: §E.2 · p. 38, Table 23 · p. 39

E.3 Capacity and Rounding Parts of Exact RCC Violations

  • Across 25,411 exact cuts, violations shift from capacity-dominated early root cuts to small, rounding-driven cuts later in the root loop and at tree nodes.The transition occurs within the root loop through repeated separation; branching adds nothing qualitatively new.Source: §E.3 · p. 39, Table 24 · p. 39

E.4 Transfer Across Problem Classes: The Released Examples

Released examples test the engine on VRP variants and the capacitated minimum spanning tree problem without retraining for those settings. The results vary by problem and instance, and the authors characterize these runs as preliminary rather than as a benchmark.

E.4 Transfer Across Problem Classes: The Released Examples

  • On capacitated, asymmetric, and time-windowed VRP instances, SAG-Sep and CVRPSEP reach identical root bounds and both solve all 30; on rc101_100, SAG-Sep finishes in 478 seconds versus 1785.On open VRP, root bounds agree on three of seven instances and differ by at most 0.004 gap points on the other four.Source: §E.4 · pp. 39–40, Table 25 · p. 41
  • On CMST, without CMST training, root bounds differ on 19 of 20 instances; SAG-Sep’s bound is higher on 13, by up to 5.8 gap points at tight capacity.It solves three instances versus one for CVRPSEP within the limit, with the count depending on the driver’s tree-commitment setting.Source: §E.4 · p. 40, Table 26 · p. 42
  • These are released-example runs, not a benchmark: they use one seed, small instance sets, and timings from shared cluster nodes.The engine can reach VRP root bounds with 50–76% of the root cuts CVRPSEP adds, but its CPU root loop is slower.Source: §E.4 · p. 40, Table 25 · p. 41, Table 26 · p. 42

Related papers

Loading 2610.37952v1…