跳到正文
arXiv cs.AI· Jinhyung Bae·· 10 小时前AI 评分20

神经路由求解器何时值得重新分配采样预算?实例级分配研究

When Does Reallocating a Sampling Budget Pay? Instance-wise Allocation for Neural Routing Solvers

AI 导读

针对 POMO、Attention Model 和 Sym-NCO 三个预训练神经路由求解器,在旅行商问题上非均匀分配采样预算在训练分布内最多只降低 2.5% 的总最优性差距,均匀分配已接近最优。

正文 · 原文

View PDF HTML (experimental)

Abstract:Neural routing solvers sample many solutions per instance and keep the best, with the same number of samples for every instance. We measure how much a non-uniform split of the same total budget is worth and which property of a workload decides it. Best-of-k curves estimated by averaging random orderings of stored samples overstate the gain, and deciding on one half of the samples while evaluating on the other understates it; we use exact best-of-k curves, a U-statistic over all orderings. For three pretrained solvers (POMO, the Attention Model and Sym-NCO) on the traveling salesman problem, reallocation reduces the total optimality gap by at most 2.5% on the training distribution, so uniform allocation is close to optimal there. On workloads that mix in out-of-distribution instances it reduces the gap by 11.8-13.3% (1.1-1.8% of tour length) for the two solvers that degrade under the shift, and almost nothing for the one that does not. Across two heterogeneity mechanisms, three solvers, two confirmation collections and budgets of 25 to 200 samples per instance, the gain is predicted by the spread of difficulty within a workload, not its average. Allocating on a power-law curve fitted to twenty charged probe samples per instance recovers 88-93% of the uncharged optimum; successive halving does worse. A 2-opt local search, however, removes most of the gap at negligible cost, after which reallocation adds a few hundredths of a percent of tour length.
Comments: v2: merged and corrected version; supersedes v1 of this paper and arXiv:2608.13087, re-analysed with exact best-of-k curves, with new baselines and a local-search comparison. 27 pages, 5 figures. Submitted to the Journal of Heuristics. Code and data: this https URL
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
Cite as: arXiv:2609.27917 [cs.LG]
  (or arXiv:2609.27917v2 [cs.LG] for this version)
  https://doi.org/10.48550/arXiv.2609.27917

arXiv-issued DOI via DataCite

Submission history

From: Jinhyung Bae [view email]
[v1] Fri, 21 Aug 2026 17:54:00 UTC (2,281 KB)
[v2] Wed, 18 Nov 2026 15:53:35 UTC (85 KB)

来源:arXiv cs.AI · arxiv.org