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

AI summary

Overview

Research area: Machine learning for combinatorial optimization, specifically learned cutting-plane generation for the capacitated vehicle routing problem (CVRP).

Technical level: Advanced. The paper assumes familiarity with linear programming relaxations, branch-and-cut, cutting planes, and graph neural networks.

Scope: The paper introduces SAG-Sep, a single-pass neural separator that proposes rounded capacity cuts (RCCs) from a fractional LP solution, together with Onion-Sweep, a training-free decoder that turns the model's node scores into structurally coordinated cut candidates.

What This Paper Is About

Exact separation of rounded capacity cuts is NP-hard, and the standard heuristic (CVRPSEP) produces few effective cuts on large instances, so LP relaxations at the root node stay loose. Recent neural separators such as NeuralSEP can be fast, but they rely on recursive graph coarsening that requires repeated predict-and-coarsen stages and CPU–GPU synchronization, which limits throughput. The paper's goal is a separator that captures long-range routing structure in a single encoder pass and converts its scores into many effective cuts without threshold tuning.

Key Contributions

1. A Sparse Augmented Graph (SAG) encoding. Starting from the LP-support graph (edges with $\bar{x}_{ij} \geq \tau_1$), the method adds a small set of flow-informed multi-hop edges, so the model sees long-range routing structure without dense attention or iterative coarsening.

2. A one-shot separator architecture. SAG-Sep scores each customer's membership in an RCC-inducing subset across all vehicle-count levels $m \in {0, \dots, M-1}$, where $M = \lceil d(V^{+})/C \rceil$, in one batched encoder forward pass.

3. Onion-Sweep (OS), a training-free decoder. Instead of hard thresholding, OS sorts customers by score, evaluates the RCC violation of every prefix of the ranking in one vectorized pass, emits the most violated prefix per replica, and adds a cross-replica family of nested ("onion") proposals at each new vehicle-count level.

4. Evidence that high-value exact RCCs are nested. The authors analyze exact separation labels and find that valuable cuts form onion-like subset families, and that the encoder's node scores track this nesting depth — the structural observation that motivates OS.

Main Findings

• Large-instance gap reduction: On the NeuralSEP benchmark at $N = 1000$ customers, SAG-Sep with OS reduces the average root gap by 17.7% relative to the strongest NeuralSEP baseline. In absolute terms the gap at $N = 1000$ falls to 22.03%, versus 25.82% for $\pi$-NeuralSEP 2 +GC and 28.72% for CVRPSEP.

• Roughly 30-fold neural separation speedup: The single-pass SAG-Sep separator achieves about a 30-fold per-iteration neural separation speedup. At $N = 1000$ the per-round neural separation time is 0.65 s, versus 16–19 s for the NeuralSEP pipelines.

• Crossover with recursive pipelines: At $N = 200$, NeuralSEP 2 improves the gap by 0.79 percentage points over SAG-Sep but is about 7.9 times slower, and the GC variant improves by 1.41 pp but is about 12.3 times slower. At $N = 300$, SAG-Sep is faster than both recursive neural pipelines and tighter than NeuralSEP 2. From $N = 400$ onward it gives the best gaps in the main table, and at $N = 400$–500 it also has the lowest runtime. At $N \geq 750$ every method hits the time limit.

• CVRPSEP still wins on small instances: At $N \leq 300$, CVRPSEP remains stronger. The paper explicitly frames SAG-Sep as complementary rather than a replacement for CVRPSEP's engineered small-instance heuristics.

• Connectivity alone hurts; structure helps: In the graph ablation, adding zero-feature synthetic edges (+Conn) degrades performance relative to the raw LP-support graph at eight of nine sizes. Adding hop-type information (+Hop) consistently improves, and adding flow-based edge values (+Val) gives the best results at all sizes — "how" connectivity is added matters more than "how much."

• Onion-Sweep improves bounds almost everywhere: Replacing the threshold readout with OS improves the mean root bound at every size and on 85 of the 90 benchmark instances: by 1.5–2.1 pp at $N \leq 200$ at equal or lower runtime, and by 0.4–0.9 pp at $N \geq 300$. Against the earlier Onion-MBP decoder, OS improves the bound by 0.2–0.9 pp at $N \leq 400$ (71 of 90 paired wins overall).

• Theoretical control on graph growth: Proposition 3.1 shows that for an Erdős–Rényi LP-support graph with $\lambda_N = \rho(N-1)$, the expected edge ratio of the $K$-hop closure is $(1+o(1))\sum_{k=0}^{K-1}\lambda_N^k$; a hop radius of two keeps expected $|\tilde{E}|$ within a factor of about $1+\lambda$ of $|E_{\mathrm{LP}}|$. Shared edge encoding cuts edge-side memory from $O(M|\tilde{E}|D)$ to $O(|\tilde{E}|D)$.

• Zero-shot transfer in branch-and-cut: On 30 capacitated, asymmetric and time-windowed instances the released engine reaches exactly CVRPSEP's root bounds and both solve all 30. On the open VRP the bounds agree within 0.004 points of gap. On the capacitated minimum spanning tree problem (no CMST training, capacity cut as the only family), its root bound is higher on 13 of 20 instances — by up to 5.8 points at tight capacity — and lower on 6, by at most 0.44.

• Scope limitation beyond the root node: In exact-separation branch-and-cut runs on $N = 50$–100 instances, 86% of cuts found in the first tenth of the root rounds are capacity-dominated, none in the second half of the root loop or at tree nodes, and mean violation falls from 7.9 to 0.13.

Methodology in Plain English

The separator runs inside a standard separate–add–resolve loop. Given the current fractional LP solution, it first keeps only edges carrying nontrivial LP mass, producing a sparse support graph. It then augments this graph with a few extra edges linking customers reachable within a short number of hops, and labels each such edge with a "widest-path" style flow score (the largest bottleneck value over shortest LP-support paths) plus the hop distance. The idea is to let the model see who is indirectly connected to whom without paying for a dense graph.

The graph is then replicated once per possible vehicle-count level, since the right-hand side of an RCC depends on how many vehicles a subset requires. All replicas are processed in one batched forward pass by a six-layer transformer using masked self-attention, with edge features encoded once and shared across replicas to save memory. The output is a probability per customer per replica.

The decoding step is the paper's second idea. Rather than cutting the probabilities at some threshold, the decoder sorts customers by score and, using an incremental update of the cut value and the accumulated demand, evaluates the violation of every prefix of that ranking in one vectorized pass. It keeps the most violated prefix per replica, then builds a second family of proposals from the average score across replicas, adding nested prefixes each time the required vehicle count increases. Duplicates, already-present cuts, and non-violated subsets are filtered out. The tolerance is fixed at $\varepsilon = 10^{-6}$ with a minimum subset size of two, and cross-replica onion prefixes with violation below $10^{-4}$ are discarded, so no threshold, band width, or sampling is tuned.

Experiments compare against the exact separator of Fukasawa et al. (2006), CVRPSEP with only its RCC routines enabled, NeuralSEP 1, and NeuralSEP 2 with its $\pi$ and GraphChip variants. All runs are at the root node, with one AMD EPYC 9655P CPU thread for LP solving, one NVIDIA L4 GPU for inference, and a 3600-second root-relaxation time limit checked between separation rounds. The reported metric is the mean optimality gap $100(U-L)/U$ of the final root bound $L$ to the best-known solution value $U$.

Why This Matters

Impact on research: The paper argues that cut generation can be reframed as structured prediction over solver states, with attention architectures taking over an NP-hard separation subroutine while preserving the validity of the cuts added. It also offers a reusable structural insight — that high-value RCCs are nested — which is a property of the cut family, not of the particular network, and could inform other neural separators.

Real-world applications:

• Last-mile and parcel delivery routing, where CVRP relaxations must be tightened at scale.
• Fleet dispatch and logistics planning for large service territories.
• Capacity-constrained network design, such as the capacitated minimum spanning tree setting the authors test zero-shot.
• Any solver pipeline that needs fast dual bounds rather than fully optimal routes, e.g., pricing or quotation tools.

Industry relevance: The headline practical claim is throughput: a 0.65 s per-round neural separation time at $N = 1000$ versus 16–19 s for recursive pipelines, at a better root gap than both CVRPSEP and the strongest neural baseline. Since the separator consumes only the LP support graph, demands, and capacity, it plugs into existing branch-and-cut or branch-price-and-cut frameworks without architectural change. The authors release code, a trained checkpoint, and the benchmark instances.

Future Directions

• A learned decoder. The authors note that Onion-Sweep remains a hand-designed decoder and identify a learned decoder that reasons over candidate diversity and relaxation improvement as future work.

• Optimizing whole cut sets rather than single labels. They suggest reinforcement learning or online feedback could optimize entire cut sets instead of individual supervised subsets.

• Beyond the root node. Small, rounding-driven violations at tree nodes need an additional search layer; the authors release but do not claim results for that regime.

• Broader transfer and fleet settings. Fast transfer to other cut families is limited by dependence on expensive exact-separation labels, and heterogeneous fleets remain open because vehicle-count conditioning requires a single capacity $C$. Linehaul–backhaul and pickup-and-delivery loads need variant-specific inequalities.

Target Audience

Researchers and practitioners working at the intersection of machine learning and combinatorial optimization, especially those building learning-based components for exact solvers (cutting planes, branching, column generation). It is also relevant to operations research engineers who need faster root-node bounds for large-scale vehicle routing, and to ML researchers interested in graph representation design under sparsity constraints. Readers without background in LP relaxations and cutting planes will find the methodology section demanding.

Authors’ abstract

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.