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

Problem
This paper addresses the critique that neural combinatorial optimization solvers are less energy-efficient than traditional CPU-based metaheuristics, particularly due to the high energy costs associated with GPU training. The authors argue that the inference drawn from “training is expensive” to “neural solvers are net-inefficient” is flawed. They propose a framework to evaluate the energy efficiency of neural solvers relative to heuristic methods, specifically under conditions of fixed deployment volume. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors introduce the Amortized Efficiency Threshold (AET), which quantifies the deployment volume at which a neural solver’s total energy consumption becomes comparable to that of a heuristic baseline, given a constraint on solution quality. The framework accounts for both training energy costs and operational energy costs, allowing for a fair comparison. The cumulative energy ratio between the two solvers is shown to converge to a constant below one when the neural network outperforms the heuristic on a per-instance basis. The study is instantiated using the Multi-Task Vehicle Routing Problem (MTVRP) with 20 customers across 19 problem variants and five training seeds, employing a heuristic greedy search (HGS) via PyVRP as the baseline. The authors provide an open instrumentation and measurement protocol to facilitate reproducibility.

Results
The empirical results indicate that the crossover point for the AET is approximately 158,000 deployed instances, suggesting that beyond this volume, the neural solver becomes more energy-efficient than the heuristic. The per-instance energy ratio is reported as 0.41, indicating that the neural solver consumes significantly less energy per instance when evaluated against the heuristic. This finding is particularly relevant for moderate-sized instances, as the authors note that the structural convergence of the energy ratio at larger problem sizes remains an area for future research.

Limitations
The authors acknowledge that their framework is contingent on the assumption of fixed deployment volume and solution quality constraints, which may not hold in all practical scenarios. Additionally, the study is limited to the specific problem domain of the Multi-Task VRP, and the results may not generalize to other combinatorial optimization problems or larger instance sizes. The authors also note that the structural convergence of the energy ratio at larger problem sizes is left for future empirical validation.

Why it matters
This work has significant implications for the evaluation of neural combinatorial optimization methods, particularly in contexts where energy efficiency is a critical concern. By establishing a framework for comparing neural and heuristic solvers based on deployment volume and energy consumption, the authors provide a pathway for future research to explore the trade-offs between training costs and operational efficiency. This could influence the design and deployment of neural solvers in real-world applications, particularly in resource-constrained environments.

Authors: Sohaib Afifi
Source: arXiv:2605.14624
URL: https://arxiv.org/abs/2605.14624v1