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

Haoran Liu; Guanyi Wang; Yu Yang

cs.LGOct 27, 2026

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

Authors: Haoran Liu, Guanyi Wang, Yu Yang

Organizations: Department of Industrial Systems Engineering, University of Florida, Florida, United States · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore

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.

Figures & tables

Figure 1: Pipeline overview of SAG-Sep for RCC separation. The current LP solution is encoded as a sparse augmented graph, replicated and evaluated in one batched forward pass, and converted into candidate subsets by thresholding or Onion-Sweep. Violated RCCs are added back to the LP relaxation in a separate–add–resolve loop.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Graph Transformer layer with edge-biased multi-head attention (pre-normalization). Edge embeddings are encoded once, shared by all layers, and enter each head only through the scalar attention bias

b_{ij}

Figure 3: Empirical marginal of $p_{i}(w)$ on $N=300$ root-relaxation LP states (approximately $6\times 10^{6}$ post-sigmoid predictions). Left: histogram is sharply bimodal at $0$ and $1$ with low mass near the threshold $\tau=0.5$ . Right: the CDF is shallow on the central region, giving $\Pr(|p_{i}(w)-\tau|\leq\varepsilon)\lesssim 0.6\,\varepsilon$ for $\varepsilon\leq 0.1$ and supporting $q(\varepsilon)=O(\varepsilon)$ .

Figure 4: Per-instance marginals of $p_{i}(w)$ on six randomly sampled $N=300$ root-relaxation LP states. The bimodal pattern, and the resulting low density near $\tau=0.5$ , is structural rather than instance-specific; isolated secondary modes (e.g. Graph $0$ near $p=0.45$ ) do not violate the linear anti-concentration rate read from the aggregate CDF.

Block	Item	Value
Backbone	type	transformer
	#layers ( $L$ )	6
	latent dimension ( $d$ )	256
Transformer	#heads	8
	dropout	0.1
	edge features	enabled

Appendix

Table 6: Model configuration for SAG-Sep training.

Component	Item	Value
Adam	learning rate	$1\times 10^{-3}$
	weight decay	0.0
	betas	(0.9, 0.999)
	eps	$1\times 10^{-8}$
CosineAnnealingWarmRestarts	$T_{0}$ (optimizer steps)	200
	$T_{\text{mult}}$	1

Appendix

Table 7: Optimizer and scheduler configuration.

Training data	$N=50$ – $100$	$N=200$ – $400$	$N=500$ – $1000$
XML20	8.79	14.03	21.91
XML30	7.25	12.75	21.26
XML40	6.83	10.65	18.76
XML50	6.05	10.06	18.10
XML100	5.88	9.43	17.35

Appendix

Table 8: Root-gap ablation by exact-labeled training instance size. Values are average root gaps (%, lower is better) on the random benchmark. Run at an earlier development stage; absolute gaps differ from Table 1 , and comparisons are within the table.

Setting	$N=50$	$N=100$	$N=200$	$N=300$	$N=400$
Sample loss	9.47	10.86	13.22	13.39	14.85
Mix	8.55	10.74	12.38	12.72	12.98
Instance loss	9.88	11.39	13.74	14.22	14.57
No positive weight	7.98	9.78	11.91	12.33	12.79

Appendix

Table 9: Ablation on positive-weight loss: mean optimality gap (%) by instance size (lower is better). Run at an earlier development stage; absolute gaps differ from Table 1 , and comparisons are within the table.

Size	Full batch, no shared edge	Microbatch 48	Shared edge
$N=500$	8/10	9/10	10/10
$N=750$	4/10	5/10	10/10
$N=1000$	3/10	6/10	10/10

Appendix

Table 10: Inference feasibility with and without shared-edge encoding on an L4 GPU. Entries report non-OOM instances out of 10 random benchmark instances.

Size	Profiled instance	No shared edge	Shared edge	Reduction
$N=500$	random-19-X-n500	2.50 GiB	0.34 GiB	7.4 $\times$
$N=750$	random-8-X-n750	6.46 GiB	0.66 GiB	9.8 $\times$
$N=1000$	random-19-X-n1000	15.68 GiB	1.20 GiB	13.1 $\times$

Appendix

Table 11: Peak allocated GPU memory for full-batch inference without shared edges versus shared-edge inference.

Setting	$\tau_{1}$	$\tau_{2}$	$N=50$ – $100$	$N=200$ – $400$	$N=500$ – $1000$
default	$10^{-6}$	0.50	5.88	9.43	17.35
$\tau_{1}=0.05$	0.05	0.50	5.91	9.42	17.58
$\tau_{1}=0.10$	0.10	0.50	6.01	9.42	17.84
$\tau_{2}=0.45$	$10^{-6}$	0.45	6.31	9.45	17.28
$\tau_{2}=0.55$	$10^{-6}$	0.55	6.23	9.48	17.93

Appendix

Table 12: Sensitivity to graph and subset thresholds. Each cell reports average root gap (%, lower is better). Run at an earlier development stage; absolute gaps differ from Table 1 , and comparisons are within the table.

Method	Final gap (%)	Runtime (s)	Instance wins
Exact separation	35.411	23051.54	5 / 10
SAG-Sep	35.414	26.48	5 / 10

Appendix

Table 14: Ten-iteration comparison between exact separation and SAG-Sep on ten

N=1000

instances (the final bound is the LP after nine rounds of cuts).

Round	Threshold	OS	$\pi$ -NeuralSEP 2 +GC	Exact
1	50.34	49.99	51.05	50.19
2	47.72	47.58	48.45	47.72
3	45.60	45.55	46.01	45.33
4	43.49	42.93	43.81	42.78
5	41.66	40.56	42.03	40.87
6	39.93	38.57	40.27	39.23

Appendix

Table 15: Mean root gap (%) after each separation round on the ten

N=1000

benchmark instances, from the same raw LP and independent of time. The exact column is the exact separator of Table 14 ; the threshold column is the SAG-Sep run of that table, whose final bound is round 9;

\pi

-NeuralSEP 2 +GC uses the re-run batch of Appendix D.6 .

Regime	$N$	OS	$\pi$ -NeuralSEP 2 +GC	CVRPSEP	OS vs. $\pi$ -NeuralSEP 2 +GC	OS vs. CVRPSEP
XML-A	500	8.37	8.85	11.54	10/0/0	10/0/0
XML-A	750	13.47	15.47	18.25	10/0/0	10/0/0
XML-A	1000	17.35	20.77	22.35	10/0/0	10/0/0
XML-B	500	8.86	11.78	16.53	10/0/0	10/0/0
XML-B	750	17.19	19.56	23.07	10/0/0	10/0/0
XML-B	1000	21.61	25.50	27.27	10/0/0	10/0/0

Appendix

Table 20: Generalization to two XML parameter settings at unseen sizes, 5–10

\times

the training size (ten instances per cell, 3600-second limit). Mean root gap (%); W/T/L counts the paired per-instance comparisons of OS against each baseline. XML-A: central depot, random customers, many small and few large demands, medium routes. XML-B: corner depot, random customers, small high-variance demands, medium routes.

Instance	OS	$\pi$ -NeuralSEP 2 +GC	CVRPSEP
X-n524-k153	19.40	19.04	23.49
X-n573-k30	3.36	5.14	5.81
X-n613-k62	11.42	13.57	16.36
X-n701-k44	12.54	16.24	19.49
X-n716-k35	16.94	19.65	20.75
X-n749-k98	19.14	20.49	26.00

Appendix

Table 21: Root gap (%) on ten CVRPLIB X instances drawn uniformly from

N\in[500,1001]

(3600-second limit).

$N$	CVRPSEP gap (%)	Engine gap (%)	CVRPSEP s/inst (CPU)	Engine s/inst (GPU)	Time ratio
50	1.969	1.968	0.09	0.16	1.86 $\times$
75	2.768	2.768	0.63	0.74	1.19 $\times$
100	4.539	4.538	2.93	2.20	0.75 $\times$
200	6.281	6.283	95.8	32.1	0.34 $\times$

Appendix

Table 22: Released C engine (full recipe) versus CVRPSEP, both run to closure in the same root loop (ten random instances per size, means). Gap is with respect to the optimal solution. The time ratio is engine time over CVRPSEP time, computed from unrounded means.

Phase	Cuts	Mean violation	Capacity-dominated (%)	Capacity part $>0$ (%)
Root, first 10% of rounds	2,032	7.88	86.1	96.9
Root, 10–50% of rounds	8,502	2.34	22.5	48.8
Root, last 50% of rounds	6,424	0.24	0.0	0.5
Tree nodes	8,453	0.13	0.0	0.2

Appendix

Table 24: Capacity and rounding parts of the violation of exact RCCs in complete branch-and-cut runs with exact separation (30 random benchmark instances,

N=50

75

100

; 25,411 cuts). A cut is capacity-dominated if its capacity part exceeds its rounding part; violations are in the units of

\bar{x}(\delta(S))

. Root round

r

of an instance’s

R

rounds falls in the first tenth if

r/R\leq 0.1

and in the first half if

r/R\leq 0.5

; none of the 6,424 late-root and 8,453 tree cuts is capacity-dominated.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 139 papers

RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
Oct 10, 2026Vladimir Kirill Bickov, Neil Yorke-SmithNeural Combinatorial Optimization Vehicle Routing
Delft University of Technology, The Netherlands
TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing
Oct 20, 2026Peiheng Jian, Zhenwei Wang, Tiehua Zhang +4Vehicle Routing Neural Combinatorial Optimization
School of Computer Science and Technology, Tongji University, Shanghai, 201804, China · School of Computer Science, University of Nottingham Ningbo China, Ningbo, 315100, China · Yixin Group Limited, Beijing, China +1
Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport
May 10, 2026Samuel J. K. Chin, Maximilian SchifferVehicle Routing Neural Combinatorial Optimization
MIT · TUM

Oct 10, 2026J/K move · Enter open · S save

RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

Vladimir Kirill Bickov, Neil Yorke-Smith

Delft University of Technology, The Netherlands

Neural Combinatorial Optimization Vehicle Routing

Open paper AskPDF arXiv

Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.

Abstract

Vehicle Routing

Explore similar work

RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem

TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing

Neural Cluster First, Route Second: Capacitated Vehicle Routing via Differentiable Optimal Transport