arXiv cs.AI· Haoran Liu, Guanyi Wang, Yu Yang·· 13 小时前AI 评分24
SAG-Sep：用稀疏增强图与 Onion-Guided 搜索加速圆容量割分离
SAG-Sep: Sparse Augmented Graphs and Onion-Guided Search for Rounded Capacity Cut Separation
AI 导读
SAG-Sep 通过单次编码器前向传播为节点打分，识别圆容量割（RCC）诱导子集，避免 NeuralSEP 式迭代预测-粗化推理。在 N=1000 客户的 NeuralSEP 基准上，配合无需训练的 Onion-Sweep 解码器，平均根间隙较最强基线降低 17.7%，单次分离迭代速度提升约 30 倍。该工作已被 NeurIPS 2026 主会接收。
正文 · AI 翻译
摘要：圆容量割（RCC）是容量约束车辆路径松弛中最有效的割之一，但在大规模下精确分离在计算上代价过高。现有的启发式和神经分离器可以很快，但往往无法在实际分离预算内产生足够多的有效割。我们提出 SAG-Sep，该分离器在单次编码器前向传播中，从分数 LP 解为各车辆数层级上 RCC 诱导子集中的节点隶属度打分，避免了 NeuralSEP 风格分离器所使用的迭代预测-粗化推理。SAG-Sep 将 LP 解编码为稀疏增广图（SAG），添加流信息引导的多跳边，从而在不使注意力稠密化的情况下暴露长程路径结构。除 LP 感知的稀疏编码外，我们观察到高价值精确 RCC 通常是嵌套的，组织成洋葱状的子集族，而 SAG-Sep 的节点分数跟踪子集嵌套深度。这促成了 Onion-Sweep（OS），一种免训练解码器，它按分数对客户排序，在一次向量化遍历中评估排序每个前缀的 RCC 违反量，并输出每个副本最违反的前缀，以及跨副本的嵌套提案族，将独立节点分数转化为结构协调的 RCC 候选，无需调优阈值或探测带。在 N=1000 客户实例的 NeuralSEP 基准上，SAG-Sep 配合 OS 相对于最强的 NeuralSEP 基线将平均根间隙降低 17.7%，而单遍 SAG-Sep 分离器实现了约 30 倍的每迭代神经分离加速。我们的发现表明，LP 感知的稀疏编码和高价值割的嵌套结构是值得在更广泛的神经分离中利用的结构模式。
| 评论： | 42 页，4 幅图，26 张表。已被 NeurIPS 2026（主赛道）接收。代码：此 https URL |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；优化与控制（math.OC） |
| MSC 分类号： | 90C57（主），90C27，90B06，68T07（次） |
| ACM 分类号： | I.2.6；G.1.6 |
| 引用为： | arXiv:2610.37952 [cs.LG] |
| （或 arXiv:2610.37952v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.37952 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Haoran Liu [查看电子邮件]
[v1]
2026 年 10 月 27 日星期二 20:37:06 UTC（320 KB）
来源：arXiv cs.AI · arxiv.org