SAG-Sep: 稀疏增强图与洋葱引导搜索用于圆容量割分离
SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation
Haoran Liu · Guanyi Wang · Yu Yang
中文摘要
圆容量割（RCC）是容量约束车辆路径松弛中最有效的割之一，但精确分离在大规模下计算代价过高。现有启发式与神经分离器速度较快，却常在实际分离预算内无法产生足够多的有效割。SAG-Sep 在单次编码器前向传播中，从分数 LP 解按车辆数层级为节点在 RCC 诱导子集中的隶属度打分，避免 NeuralSEP 式分离器的迭代预测-粗化推理。该方法将 LP 解编码为稀疏增强图（SAG），加入流量感知的多跳边以暴露长程路径结构而不使注意力稠密化。除 LP 感知稀疏编码外，高价值精确 RCC 通常呈嵌套结构，组织为洋葱状子集族，而 SAG-Sep 的节点分数跟踪子集嵌套深度。这引出 Onion-Sweep（OS），一种免训练解码器：按分数对客户排序，在一次向量化过程中评估排序每个前缀的 RCC 违反量，并输出每个副本最违反的前缀及跨副本的嵌套提议族，无需调参阈值或探测带即可将独立节点分数转为结构协调的 RCC 候选。在 N=1000 客户实例的 NeuralSEP 基准上，SAG-Sep 配合 OS 相对最强 NeuralSEP 基线将平均根间隙降低 17.7%，单次 SAG-Sep 分离器实现约 30 倍每迭代神经分离加速。
关键要点
- 01精确分离 RCC 在大规模下计算代价过高，现有神经分离器在预算内有效割不足
- 02SAG-Sep 单次前向为节点打分，避免 NeuralSEP 式迭代预测-粗化推理
- 03稀疏增强图加入流量感知多跳边，暴露长程路由结构而不稠密化注意力
- 04高价值 RCC 呈洋葱状嵌套，Onion-Sweep 免训练解码器将节点分数转为嵌套候选
- 05N=1000 实例上根间隙降 17.7%，单次分离约 30 倍加速
解读
尚无解读。
原始英文摘要
arXiv:2610.37952v1 Announce Type: cross 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.