arXiv:2605.14624cs.LGcs.AI2026-05

提出神经求解器与启发式算法能效比较的新标准,量化其实际应用的临界部署量。

An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization

论文配图:An Amortized Efficiency Threshold for Comparing Neural and Heuristic Solvers in Combinatorial Optimization
图 1 · 摘自论文原文
  • 定义累计能耗平衡点(AET),以部署规模为基准比较神经与启发式算法效率
  • 在50个客户车辆路径问题中,神经求解器需部署约4560次才胜过启发式算法
  • 提供开源工具链,支持可复现的端到端能效对比实验

神经组合优化求解器常被批评为比CPU启发式算法能耗更高,因其训练需消耗大量GPU算力。本文指出,将‘训练成本高’直接等同于‘整体低效’是逻辑错误:训练为一次性固定开销,而启发式需在每次部署时持续消耗少量CPU能量。我们定义了‘摊销能效阈值’(AET),即在保证解质量的前提下,神经求解器总能耗或碳排放低于启发式算法所需的最小部署量。结果表明,只要单次求解性能更优,累积能耗比将趋于一个严格小于1的常数,且不依赖训练成本的度量方式。硬件制造碳足迹对双方对称分摊。我们在50客户容量的车辆路径问题(CVRP)环境中,采用Kool等人(2019)基于注意力的自回归模型,在20,000个实例上训练100轮、五组随机种子,并以PyVRP中的HGS为基线。实测操作交叉点约为4.56×10³次部署,单次能耗比为2.29×10⁻³。贡献在于提出框架、开放仪器及端到端测量协议。代码与基准流程见https://github.com/sohaibafifi/aet。

原文摘要 · Abstract (English)

A common critique of neural combinatorial-optimization solvers is that they are less energy-efficient than CPU metaheuristics, given the operational energy cost of training them on GPUs. This paper examines the inferential step from "training is expensive" to "neural solvers are net-inefficient", which is where the critique actually goes wrong. Training the network costs a large fixed amount of GPU energy; running the metaheuristic costs a small amount of CPU energy on every instance, repeated as long as the solver is deployed. The two are not commensurable until a deployment volume is fixed. We define the Amortized Efficiency Threshold (AET) as the deployment volume above which a neural solver breaks even with a heuristic baseline in total energy or carbon, under an explicit constraint on solution quality. We show that the cumulative-energy ratio between the two solvers tends to a constant strictly below one whenever the network wins per instance, and that this limit does not depend on how the training cost was measured. An embodied-carbon term amortizes hardware fabrication symmetrically on both sides. We instantiate the framework on the CVRP environment at n=50 customers with the attention-based autoregressive solver of Kool et al. (2019), trained for 100 epochs on 20,000 instances over five random seeds, and HGS via PyVRP as the heuristic baseline. The measured operational crossover sits near 4.56e3 deployed instances at the median of a six-point baseline-budget sweep; the per-instance neural-to-heuristic ratio is 2.29e-3. The contribution is the framework, the open instrumentation, and the end-to-end measurement protocol. Code and benchmark pipeline are available at https://github.com/sohaibafifi/aet.

组合优化能效评估神经求解器碳足迹

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。