FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization
Authors: Shengyu Feng
Weiwei Sun
Shanda Li
Ameet Talwalkar
Yiming Yang
Venue: ICLR 2026 Poster (2026)
Keywords: Combinatorial Optimization
Graph Neural Networks
Large Language Models
Primary area: datasets and benchmarks
TL;DR: We evaluate 16 recent machine learning-based combinatorial optimization solver on challenging real-world instances from problems, results revealing the significant limitations of existing methods.

Abstract: Machine learning (ML) has shown promise for tackling combinatorial optimization (CO), but much of the reported progress relies on small-scale, synthetic benchmarks that fail to capture real-world structure and scale. A core limitation is that ML methods are typically trained and evaluated on synthetic instance generators, leaving open how they perform on irregular, competition-grade, or industrial datasets. We present FrontierCO, a benchmark for evaluating ML-based CO solvers under real-world structure and extreme scale. FrontierCO spans eight CO problems, including routing, scheduling, facility location, and graph problems, with instances drawn from competitions and public repositories (e.g., DIMACS, TSPLib). Each task provides both easy sets (historically challenging but now solvable) and hard sets (open or computationally intensive), alongside standardized training/validation resources. Using FrontierCO, we evaluate 16 representative ML solvers---graph neural approaches, hybrid neural–symbolic methods, and LLM-based agents---against state-of-the-art classical solvers. We find a persistent performance gap that widens under structurally challenging and large instance sizes (e.g., TSP up to 10M nodes; MIS up to 8M), while also identifying cases where ML methods outperform classical solvers. By centering evaluation on real-world structure and orders-of-magnitude larger instances, FrontierCO provides a rigorous basis for advancing ML for CO. Our benchmark is available at https://huggingface.co/datasets/CO-Bench/FrontierCO.

Published as a conference paper at ICLR 2026
FRONTIERCO: REAL- WOOLD AND LARGE-SCALE EVALUATION OF MACHINE LEARNING SOLVERS FOR
COMBINATORIAL OPTIMIZATION
Shengyu Feng' Weiwei Sun" Shanda Li Ameet Talwalker Yiming Yang
School of Computer Science, Carnegie Mellon University {shengyuf, weiwes, shandal, atalwalk, yiming} cmu.edu
ABSTRACT
Machine learning (ML) has shown promise for tackling combinatorial optimization (CO), but much of the reported progress relies small-scale, synthetic bench- marks that fail to capture real-world structure and scale. A core limitation is that ML methods are typically trained and evaluated on synthetic instance genera- tors, leaving open how they perform on irregular, datasets. We present FRONTIERCO, benchmark for evaluating ML-based CO solvers under real-world structure and extreme scale. FRONTIER CO spans eight CO problems, including routing, scheduling, facility location, and graph problems, with instances drawn from competitions and public repositories (c.g., DIMACS, TSPLib). Each task provides both easy sets (historically challenging but now solvable) and hard sets (open or computationally intensive), alongside standardized training/validationn resources. Using FRONTIERCO, we evaluate representative ML solvers graph neural approaches, hybrid neural symbolc methods, and IL.M-based agents-agains state-of-the-ard elassical solvers. We find a persistent performance gap that widens under structurally challenging and large instance sizes (c.g.. TSP up to 10M nodes; MIS up to 8M), while also identifying cases where ML methods outperform classical solvers. By centering evaluation on real-world structure and cndees-offmaaninee vides rigorous basis for advancing ML for CO. Our benchmark is available bttps://hugginge
ioppetition-grade or industrial
larger instances, FRONTIER CO pro-
co/ hat/aatasesss..m httpss//cooeeeeeeeeeeeeeeeee
INTRODUCTION
Combinatorial optimization (CO) lies at the heart of computer science, operations research, and applied mathematics, with applications in routing, allocation, planning, and scheduling (Korte & Vygen 2012). Most CO problems are intractable or NP-hard, and decades of research have relied on carefully engineered heuristics and exact solvers to make progress. Recently, machine learning (ML) has been proposed as a way to automate algorithm design, raising the exciting possibility that data-driven solvers could eventually rival complement human-crafted methods.
Two main paradigms have emerged. Neural solvers use graph neural networks, reinforcement learning, or diffusion models to directly generate or guide solutions (Cappart al. 2023; Bengio et al. 2020). Symbolic solvers, by contrast, leverage large language models (LLMs) to synthesize executable algorithms, often refining them through self-feedback or iterative search (Romera- Paredess al. 2023: Liu et al. 2024 Ye et al. 2024 Novikov et al. 2025). Both paradigms have produced intriguing successes on benchmark datasets, sparking optimism about ML's role in CO.
Yet central question remains unanswered: can ML-based solvers match surpass state-of- the-art (SOTA) human-designed algorithms on real-world CO problems? Existing benchmarks do not allow to answer this rigorously. They suffer from three limitations: (i) scale: most focus on toy instances orders of magnitude smaller than real applications (Kool et al. 2019 Luo
al.] ) (ii) realism: synthetic datasets often fail capture struetural diversity; and (ii) data realism and coverage, i.e., most ML evaluations rely on synthetic generators, which limits insight
"Equal contributors.

---

Published as a conference paper at ICLR 2026
into performance irregular, -un-Euulidean, competition grade instances that classical solvers routinely tackle. As a result, ML methods are often assessed at modest scales and on structurally simplified distributions.
To address these limitations, we present FRON- TIERCO, benchmark that evaluates ML-based solvers under real-world structure and extreme in- stance sizes across eight CO problems from five egories (Figure D. Unlike evaluations based solely on synthetic data, FRONTIERCO integrates instances from TSPLib, Rebbelti 1191), DIMACS challenges (Johnson & McGeoch) 1993), CFLP testbeds (Avella et al., 2009), and other competition or repository sources, and complements them with standardized training/validation resources. For each problem we provide two test sets: easy (once challenging, now solvable by SOTA classical methods) and hard (open or computationally intensive). We intentionally in- clude structurally challenging cases (e.g., PUC hy- percubes (Rosseti et al., (201);; SAT-induced MIS (Xu al. 2007)) and push scale by orders of mag- nitude to reflect real-world difficulty. Concretely, FRONTIERCO scales to TSP with 10M nodes and MIS with 8.M nodes. Prior larger-scale scale ML evalua- tions (e.g.. DIMES) scaled TSP graphs with 10K nodes, while early neural TSP studies commonly used < 100 nodes (Kool et al. 2019).
Routing
Graph
Havwiing
Gonscatin (wos)
Prossein
Claa Caaaraadd
FrontierCO
Tree
CADarroturd
Location
Problens
Scheerding
shop
(CMN))
Scheduling
Figure Overview FRONTIERCO.
Using this benchmark, we conduct a systematic, cross-paradigm evaluation of MI.-based CO solvers. Our study covers 16 representative approaches, including end-to-end neural solvers, neural-enhanced heuristics (Bengio et al. 2020 Cappart et al.) 2023), and LLM- agentic methods (Sun et al.) 2025), and compares them directly against the best human-designed solvers. This unified evaluation reveals several key insights: (i) ML methods still lag significantly behind SOTA human solvers, especially hard instances; (ii) neural solvers demonstrate the potential to enhance simple human heuristics, but in general struggle with scalability, non-local structure, and distribution shift; (iii) LLM-based solvers sometimes may outperform the SOTA classical solvers but display high variance due to their incapability in understanding the effectiveness different algorithms they are trained on.
Our contributions threefold.
1. Benchmark under real-world structure and extreme scale, A unified evaluation suite across eight problems that pairs competition/rell-woti instances with hard, structurally irregular cases and orders-of-maaee -faagnnu-e larger sizes than prior ML evaluations (e.g., TSP: 10M vs. 10k; MIS: 8M vs. 1 1kk (Qiu et al. 2022
2. Unified evaluation. We conduct rigorous comparison of 16 ML-based solvers against state-of-ther the-art classical baselines, under standardized protocols.
3. Empirical insights. We identify fundamental limitations current MI. approaches, while also highlighting the potential and future research directions for ML-based solvers.
FRONTIERCO: THE PROPOSED BENCHMARK
2.1 FORMAL OBJECTIVE AND EVALUATION METRICS
We follow Papadimitriou & Steiglitz 1982 denoting combinatorial optimization (CO) problem instance as a solution as x E X,, and defining the objective as
min c. (x) = cost(I;; s) valid zEX.
(I)
where cost(z;;) s) is a problem-specife objective (e.g., the tour length in routing problems), and valid(z;;) s) penalizes constraint violations-takinn taking value co if a is infeasible, and 0 otherwise. Note
2

---

Published as a conference paper at ICLR 2026
that any maximization problem can be tumned into minimization one by negating the objective sign, and we treat all problems in its minimization version for unified evaluation in this work.
To accommodate the varying scales of different problem instances, we define the primal gap as: if x is infeasible cost(2;; s) c² < 0,
(g(2; s) =
[cost(2;; 8) - c*1
otherwise,
max cost(x;; s)l, [3=
where c* the (precomputed) optimal or best-known cost for instance s. This metric has been popularly used in classical solvers (Berthold, [006] [013] AAcherberg et al. 2012), the DIMACS challenge (DIM 2013-2014), and recent neural solvers (Nair et al.] [Chiiela et al. 2021 Huang et al. 2023). By definition, our primal gap is strictly bounded within the range [0, (i.e., 0% to 100% where is optimal and is the worst possible score. Any feasible solution will result in a gap strictly less than 1. We set the primal gap for infeasible solutions to to flag them as failures, aligning with the intuition that infeasible solutions are never better than feasible ones.
2.2 DOMAIN COVERAGE
This study focuses eight types of CO problems that have gained increasing attention in recent machine learning research. These problems are:
MIS (Maximum Independent Set): Find the largest subset of non-adjacent vertices in graph, whose minimization version (corresponding to Equation D is to minimize the negative set size.
MDS (Minimum Dominating Set): Find the smallest subset of vertices such that every vertex in the graph is either in the subset or adjacent to a vertex in the subset.
TSP (Traveling Salesman Problem): Find the shortest possible tour that visits each city exactly once and returns to the starting point. We focus on the 2D Euclidean space in this work.
CVRP (Capacitated Vehicle Routing Problem): Determine the optimal set of delivery routes for a fleet of vehicles with limited capacity to serve set of customers.
CFLP (Capacitated Facility Location Problem): Choose facility locations and assign clients to them to minimize the total cost, subject to facility capacity constraints.
CPMP (Capacitated p-Median Problem): Select facility locations and assign clients to them to minimize the total distance, while ensuring that no facility exceeds its capacity.
FJSP (Flexible Job-Shop Scheduling Problem): Schedule a set of jobs on machines where each operation be processed by multiple machines, aiming minimize the makespan while respecting job precedence and machine constraints.
STP (Steiner Tree Problem): Find a minimum-com tree that spans a given subset of terminals in a graph, possibly including additional intermediate nodes.
The dataset statisties are summarized in Table with additional details provided in the Appendix B Note that only test data are collected from the listed sources; training and validation data gen- erated from the same synthetic generator to ensure they are from the same distribution (but may at different scales and set size dependent on the model efficiency/scllabiltt)).. in order to ensure the fair comparison among neural and LLM solvers (see Section 2.5
Graph-based problems (MIS and MDS) and routing problems (TSP and CVRP) have been widely used to evaluate end-to-end neural solvers (Qiu et al. 2022 Zhang et al. 2023 Sun & Yang 2023 Sanokowski et al., 2025), as these tasks often admit relatively straightforward decoding strategies to transform probabilistic model output into feasible solutions. In contrast, facility location and scheduling problems (such as CFLP. CPMP, and FJSP) involve more complex and interdependent constraints, making them better suited to hybrid approaches that combine neural networks with traditional solvers (Gasse al. 2019 Scavuzzo et al., 2022 |eng & Yang. 2025b). Tree-based problems have received comparatively less attention in neural CO, yet we include a representative case (e.g., STP) due their fundamental importance in the broader CO landscape. All of the above problems can also be directly handled by symbolic solvers, enabling comprehensive and comparable
evaluations across solver paradigms Coomera-Pareded et al. 2023 Liu et al. 2024 Ye et al. 2024).
Note that this gap definition is different from the one widely used in routing literature Kool et al.
2019
Sun & Yang 2023 Tuo et al. 2023,, which can be larger than 100%.
3

---

Published as a conference paper at ICLR 2026
Table 1: Summary of collected problem instances.
Problem
Test Set Sources
Attributes
Easy Set
Hard Set
2nd DIMACS Challenge BHOSLib
Instances Nodes
36
16
MIS
1,404-7,995,664
1.150-4.000
Instances
20
20
MDS
PACE Challenge 2025
Nodes
2,671-675,952
1.033,88--2298,062
TSPLib
Instances Cities
29
19
TSP
8th DIMACS Challenge
1,002-18,512
10,000-10,000,0000
Golden al.
1998
Instances Cities
20
10
CVRP
Arnold
2019
200-483
3,000-30,000
Instances
20
30
Avella & Boccia 2009
CFLP
Facilities
1,000
2,000
Avella et al.
2009
Customers 1,000
2,000
Lorena & Senne
2000
Instances Facilities
12
CPMP
Stetanello ct all
2015
100-4,461
10,510-498,378
Gnägi & Baumann 2021
Medians
10-1,000
100-2,000
Instances
60
20
Behnke & Geiger 2012)
FISP
Jobs
10 10-100
10-100
Naden & Roshanacl
2021
Machines
10-20
20 60
Leitner et al.
2014)
Instances Nodes
23
50
STP
Rosseti
2001
7,565-71,184
64 4,096
2.3
PROBLEM INSTANCES
For each CO problem type, we collect diverse pool of problem instances from problem-specific and comprehensive CO libraries (Reinelt 1991 Xu et al. 2007). major CO competitions (Johnson & McGeoch, 1993 PACE, 2025), and evaluation sets reported in recent research papers.
Due to rapid progress in CO, many instances from earlier archives can now effectively solved by SOTA problem-specife solvers, often achieving optimality gap below 1% within 1-hour time budget. We select a representative subset such instances as our easy set, which serves to validate the baseline effectiveness of ML-based solvers.
With a high-level goal to advance the CO solvers on open challenges, we also construct hard set comprising open benchmark instances widely used to assess cutting-edge edge -uman-designed algorithms. Many these instances lack known optimal solutions and remain beyond the reach of existing heuristics. As result, they less susceptible heuristic hacking, where neural solvers LLM- based agents rely on handcrafted decoding strategies or memorize prior solutions, rather than learning solve the problem from first principles. Importantly, our hard set size. Instead, we emphasize structurally complex cases, such as hypercube graphs in STP (Rosseti al. 2001) or SAT-induced MIS (Xu al. 2007), which require models understand and reason about intricate problem structures.
defined merely by instance
2.4 SOTA SOLVERS AND BEST KNOWN SOLUTIONS (BKS)
We identify the SOTA solver for each CO problem type based on published research papers and competition leaderboards. The selected solvers include: KaMIS (Lamm et al. (207)) for MIS, 1.H-3 (Helsgaun 2017) for TSP, HGS (Vidal et al. 2012) for CVRP, GB21-MH (Gnägi & Baumann, 2021] hybrid metaheuristie. for CPMP, and SCIP-Jack (Rehfeldt et al.) 2021 for STP. For problems where no dominant problem-specific solver is available (c.g.. MDS, CFLP. FJSP), we rely on general- purpose commercial solvers, such as Gurobi (Gurobi Optimization, LLC 2024 for MDS and CFLP (Mixed Integer Programming). and CPLEX (Cplex 2009) for FISP (Constraint Programming). Among them, Gurobi, CPLEX and JCck-Jack exact solvers; the rest heuristic-based
Prior evaluations of ML-based CO solvers often relied on self-generated synthetic test instances, leading difficulties in fair comparison across papers. These instances are sensitive to imple-
4

---

Published as a conference paper at ICLR 2026
mentation details such random seeds and Python versions, introducing undesirable variability and inconsistency. To address this, we provide standardized BKS for all test-set instances in our benchmark. These BKS are collected from published literature and competition leaderboards, and are further validated using the corresponding SOTA solvers executed on our servers. For instances lacking known BKS, such the MDS instances from the PACE Challenge 2025 (PACE, 2025), or for benchmarks with outdated references, such as those in the CFLP literature, we run the designated SOTA solver for up two hours obtain high-quality reference solutions.
2.5 STANDARDIZED TRAINING/VALIDATTOO DATA
Similar to BKS, inconsistencies in self-generated training and validation data can also contribute to difficulties in cross-paper comparisons. To address this, FRONTIERCO provides standardized training sets for neural solvers and development sets for LLM agents, generated using variety of problem-specific instance generators (details in Appendix B
We also release complete toolkit that includes data loader, evaluation function, and abstract solving template tailored for LLM-- agents. The data loader and evaluation function are hidden from the agents prevent data leakage. The solving template provides natural language problem description along with Python starter code specifying the expected input and output formats. An example prompt provided Appendix C.3
EVALUATION DESIGN
3.1 IMPLEMENTATION SETTINGS
In light of the difficulty and scale of our problem instances, we allow a maximum solving time of one hour per problem instance, as most solvers, including both classical and ML-based solvers, may require such time to obtain a single feasible solution (see efficiency analysis in Appendix E
For fair comparison, each solver is executed on a single CPU core of a dual AMD EPYC 7313 16-Core processor, and neural solvers are run a single NVIDIA RTX A6000 GPU. Since the solving time is influenced by factors such as compute hardware (CPU vs. GPU), solver type (exact vs. heuristic), and implementation language (C++ vs. Python), we use the primal gap (Equation 2 as the primary evaluation metric, and solving time is reported for reference only. For any infeasible solution, we assign primal gap of 1 and solving time of 3600 seconds. The arithmetic mean of the primal gaps and geometric mean of solving time are reported across our experiments.
3.2 REPRESENTATIVE NEURAL SOLVERS FOR COMPARATIVE EVALUATION
In addition to the SOTA human-designed solvers described in Section 2.4 we include a curated set of machine learning- based CO solvers from recent literature. The neural sol vers are tailored to specific problem categories they are developed for:
DiffUCO (Sanokowski al. 2024): An unsupervised diffusion- based neural solver for MIS and MDS that learns from the Lagrangian relaxation objective.
SDDS (Sanokowski et al. 2025 A more scalable version of DiffUCO for MIS and MDS, with
efficient training process.
RLNN (Feng & Yang 2025a): A neural sampling framework that enhances exploration in CO by enforcing expected distances between sampled and current solutions.
LEHD (Luo et al.) 2023): A hybrid encoder-decoder model for TSP and CVRP, with strong
generalization to real-world instances.
DIFUSCO (Sun & Yang 2023): A diffusion-based approach for TSP that achieves strong scalability, solving instances with up to 10,000 cities.
SIL (Luo et al. 2023): A linear-complexity transformer solver that achieves extreme scalability, handling routing instances with up to 100,000 cities.
DeepACO (Ye et al. 2023): A neural solver that adapts Ant Colony Optimization (ACO) principles to learn metaheuristic strategies.
5

---

Published as a conference paper at ICLR 2026
tMDP (Scavuzzo et al.
2022 A reinforcement learning framework that models the branching process in Mixed Integer Program (MIP) solver as a tree-structured Markov Decision Process.
SORREL Feng Yang 2025b): A reinforcement learning method that leverages suboptimal
demonstrations and self imitation learning train branching policies in MIP solvers.
2019 A graph convolutional network CONN))guided solver for MIPs, which learns to guide branching decisions within branch-and- hannchandd-bund bound framework.
GCNN Gasse et al.
IL-LNS (Sonnerat al.
2021): A neural large neighborhood search method for Integer Linear Programs (II.P) that is trained to predict the locally optimal neighborhood choice.
2023): A contrastive learning- based large neighborhood search approach for ILPs which advances the imitation learning strategy in IL-LNS.
CL-LNS (Huang et al.
2022): A reinforcement learning-based approach for FJSP that employs multi-pointer graph networks to capture complex dependencies and generate efficient schedules.
MPGN (Lei al.
2025a A Sarning-guided rolling horizon optimization method that integrates machine learning predictions into the rolling horizon framework.
I-RHO (Li et al.
Since STP not well studied by existing neural methods, we consider both reinforcement learning (RL) and supervised learning (SL) baselines, predicting the Steiner points. The Taka- hashi-Matsuyama algorithm (Takahashi & Matsuyama 1980) is then applied for decoding.
3.3 REPRESENTATIVE LLM -BASE AGENTS FOR COMPARATIVE EVALUATION
Our LLM-based solvers are selected based on the CO-Bench evaluation protocol (Sun al. 2025). including both general-purpos prompting approaches and CO-specific iterative strategies:
FunSearch (Romera- Paaeer--arreee al., 2023): An evolutionary search framework that iteratively explores the solution space and refines candidates through backtracking and pruning.
Self-Refine (Madaan et 2023 Shinn al.) 2023): feedback-drive refinement method in which the I.IM improves its own output via iterative self-refinement.
ReEvo Ye et al. 2024): A self-evolving agent that leverages past trajectories- botth successful and failed to refine its future decisions through reflective reasoning.
All LLM-based solvers are evaluated across the full set eight CO problem types in our benchmark.
4 RESULTS
We summarize the comparative results in Figure 2 and Table See detailed results in Appendix D Note that the primal gap is computed relative to the best known solution (BKS), its absolute value does not directly reflect the inherent difficulty of the restance-especie in cases where no known optimum exists.
We draw several key observations from our results. First, there is a substantial performance gap between human-designed state-of-the-art (SOTA) solvers and ML-based solvers across all problem types and difficulty levels. Strikingly, this gap is more pronounced in our benchmark than in previously published results. For instance, LEHD reports only 0.72% gap on a standard TSP benchmark (Kool et al. 2019), whereas on our new benchmark the gap widens to 10% on easy TSP instances and an alarming 77% on hard instances. major factor behind this discrepancy lies in the training and evaluation protocols. Prior studies typically trained neural solvers on synthetic graphs of a fixed size (e.g.. 1000 nodes) and evaluated them on test instances of the same size, ensuring aligned conditions. In contrast, our datasets incorporate substantial variability in both graph size and structure across training and test sets. This setup better reflects real-world deployment scenarios but also introduces significant distribution shifts, under which LEHD and many other ML-based methods experience severe performance degradation in FRONTIERCO.
Second, neural solvers face serious scalability challenges. Although they used to be treated as efficient heuristics on scage-scale, difficult instances, we find that in practice this is often not the case. Neural networks typically address the non-convexity of CO problems through veerpparameterization

---

Published as a conference paper at ICLR 2026
Easy Set
MIS
Hard Set
Easy Set
MDS
Hard Set
KaHES
penico
crass
RUAA
Fandeencce
See-Rtrfive
FedEv
penico
crass
RLAN
Fardeercc
Seef-hifive
FedEvo
Gambii
DIPACO
Fundlarch
Reff-
Retbo
Gumbi
DIRCEO
Scers
Fandleart
SelfRelite
Easy Set
TSP
Hard Set
Easy
CVRP
Hard Set
LK303
LEND
DIPUICO
FurSearcd
Sit
Sen-ftrtie
AetEve
uee-3
LEND
Furteerccp
Sett-triie
HOS
LEHO
Derpico
Funtlearci
Self Raftie
AmE
Mot
Levo
Finslears
Sent Ruffine
Set
CFLP
Hard Set
CPMP
Hard
Gurens
OCMN
FuntSarch
Seifftrtie
Rerfue
Gurats
SORNEL
OCMN
Funtearch
Set-ftrtie
Rerliv
0822 Mi
C2,486 R-LN5
FunSkarch
Seff-Reine
Aetiv
G82 MRi
R-LAS
2,408
FunsRant
Self-Rrind Rarine
PerEve
FJSP
Cap
ORLER
MM1S4
LABS
Punteannt
Refiv
CPLER
Rundeanch
Self-ette
Jack
Fundkarch
st
Seaf Reffow
SCP jack
FunSeerch
St
Sett-ettee
Figure 2: Primal gap (%) across eight CO problems on easy and hard sets (lower is better). Classical
(blue), neural (green), and L.MM-baed agents (red). Bars marked with indicate least one infeasible run on that test set; in such cases we assign gap 1 and time 3600 seconds (see Section
(Allen-Zhu et al. 2019), which inflates single-value variables into high-dimensional representations
and leads frequent out-of-memory failures (observed in of problems; see Appendix D) Inference efficiency is an additional bottleneck. For example, the auto-regressive solver LEHD (Luo)
al. 2023) requires running transformer model (Vaswani al., 2017 for 10M steps to produce single solution our largest TSP instance, failing to return any solution within the 1-hour time limit. Similar inefficiencies exist even on easier instances under shorter time budgets (Appendix E Addressing these issues through integration of reduction techniques (Andersen & Andersen 1995) and the design of more compact neural architectures is thus important direction for future research.
Third, LLM-based agents show the potential to outperform prior human-designed SOTA solvers. For example, Self-Refine surpasses KaMIS on the easy MIS set, and FunSearch outperforms HGS on the hard CVRP set. A closer inspection of these methods reveals their algorithmic sophistication: Self- Refine applies kernelization to simplify MIS instances, solves small kernels exactly using a Tomita- style max-clique algorithm, and employs ARW-style heuristics with solution pools, crossover, and path-relinking for larger instances. Similarly, FunSearch builds an Iterated Local Search framework for CVRP, enhanced with regret insertion and Variable Neighborhood Descent. These results highlight

---

Published as a conference paper at ICLR 2026
the promise of LLM-based approaches in automatically developing competitive, and in some cases superior, solvers for CO.
Fourth, despite their promise, LLM-based agents exhibit substantial performance variability. For example, while they perform comparably to the SOTA solver HGS on the hard CVRP set, they fall dramatically short on TSP- even though both are routing problems. We hypothesize that this stems from the nature of LLM training: while models are exposed to diverse dumanndesigned heuristics and can combine them in novel ways, they generally lack the ability to reliably assess the effectiveness of the generated algorithms. As a result, each sampling run may randomly yield different, not necessarily effective, strategy. This absence of internal reasoning abilities largely restricts the applicability of LLM agents to hard-to- generate resource- inteensve algorithms for large instances (e.g., frequent aut-of-memory issues on CPMP during evolving). Current agentic frameworks tend to focus on problems that are challenging yet easy to verify, strongly relying on external feedback. contrast, FRONTIERCO provides hard-to-verify benchmark (but still verifiable for evaluation purposes) that highlights the reasoning capabilities of the LLM themselves.
tasks and raises safety concerns when they
Table 2:
The average primal gap achieved by L.M agentic solvers over eight CO problems.
Table 3: Ablation study on the effective- ness of the neural module.
Avg. Gap (All)
Avg. Gap 4 (Easy)
Avg. Gap (Hard)
TSP-Easy
CFLP-Easy
Method
Method
Gap |
Method
Gap
FunSearch
20.35%
10.05%
30.65%
LKH-3
0.03 %
Gurobi
0.00%
Self-Refine
15.11%
8.18%
22.03%
2-OPT
20.09%
SCIP
6.50%
ReEvo
13.25%
7.25%
19.25%
DIFUSCO
4.19%
GCNN
3.22%
DISCUSSIONS
5.1 DOES THE NEURAL MODULE HELP?
Considering the performance gap between neural solvers and SOTA solvers, natural question arises: does the neural module actually contribute to improved performance? To explore this, we conduct an ablation study by removing the neural component from the underlying algorithm of each neural solver. We evaluate two representative pairs: DIFUSCO (Sun & Yangl 2023) vs. 2-OPT, and GCNN (Gasse et al. 2019) vs. SCIP (Achterberg. 2009). The results are summarized in Table 3
The results show that both DIFUSCO and GCNN significantly improve upon their respective heuristic baselines, indicating a meaningful contribution from the neural module. However, such improvement is still far from being comparable to the SOTA classical solvers. Overall, our findings suggest that neural components can enhance human-designed heuristics, but such improvement is typically realized when built on relatively weak base algorithms. Whether similar gains can be achieved when enhancing already strong heuristics remains unclear.
5.2 Do NEURAL SOLVERS CAPTURE GLOBAL STRUCTURE?
Most neural solvers are based on graph neural networks (GNNs which rely on local message passing. While they have demonstrated strong performance on routing problems such as TSP and CVRP-which involve complex global constraints-the majority of existing evaluations are limited to 2D Euclidean instances. Compared general graph problems, Fuclidean instances-suce as those in metric TSP-often exhibit favorable local structures (e.g., triangle incquality). which can be explicitly exploited by certain algorithms achieve improved performance (Karlin al. 202T). In contrast, general graph problems such as MIS lack such spatial regularities, and neural solvers often perform poorly on them (Angelini Ricei-Tersenghh 2022) Böther al. 2002)).
To explicitly evaluate the ability of neural solvers in capturing global structure, we leverage the rich source of STP instances, which includes both Fuclidean and non- Eu-Fuuliddan graphs (see Appendix B.8
By GNN, we refer to general message passing frameworks including attention-based neural architectures.
8

---

Published as a conference paper at ICLR 2026
for details). We train two separate GNNs to predict Steiner nodes, using ground truth labels generated by SCIP-Jack (Rehfeldt et al., 2021). One model is trained on Euclidean instances, and the other on non-Euclidean instances. The training dynamics are shown in Figure
The results reveal a clear contrast: while the GNN quickly achieves a high F1 score in predicting Steiner points on Euclidean graphs, it fails to make any progress non-Euclidean ones. This suggests that existing GNNs implicitly rely on locality and cannot really capture the global structure. These findings underscore fundamental limitation in the expressive power of current neural solvers. In Appendix
we also extend the discussion to the non-Euclidean (non-metric) TSP instances.
Supervised Learning on STP
Validation F1 Score
0.9
0.0
lling
Path
Iterated
Wpprest
critical
Br
Bridge
Largg
Initialization Lin
ge
Relinkin
iotiive
Diversite
Gre
edy
Tabu
perneiszatin
0.6
0.7
Euclidean Instances
Annnnne
opt
style
Sher
Seea
cast
regaun
r
Doubi
terne
Addapt
Adaatidii
0.5
0.4
Non-Euclidean Instances
lasplors
Ne1ghe
Algor
ghborhoo
thm
simü
Simblated
Method
lated
Procedure
Sweep
Clsserring
0.3
Constraint
Variable
Programmung
0.2
Heuristic Mode Randomazed
Loca
80
Iterations
Figure 3: Training dynamics of neural solvers on Euclidean and non-Euclidean STP instances.
Figure 4: Word cloud of the algorithms gener-
ated by LLM-based solvers.
5.3 WHAT KINDS OF ALGORITTMS Do LLM-BASED BASED SOLVERS DISCOVER?
To better understand the algorithmic strategies developed by LLM-based solvers, we visualize the key words corresponding to their generated algorithms using the word cloud in Figure 4 where the size of each word reflects its frequency of appearance across algorithms.
clear pattern emerges; classical petahheuissies-ppatilllaaal particularly simulated annealing (SA) and large neighborhood search (LNS)-conistentte appear across diverse set of problems and often form the foundation of I.I.M generated algorithms. This highlights shared reliance on well-established CO algorithms that effectively balance exploration and exploitation. While current L.MMs still fall short of demonstrating novel algorithmic reasoning (algorithms that cannot be mapped existing ones) in CO, their strategies tend to replicate known metaheuristies and problem-specific techniques from the literature. Interestingly, we observe that their performance does not critically depend on integrating existing solvers, suggesting that LLMs autonomously construct plausible and often effective algorithms. This adaptability is particularly promising for rapidly tackling new problem variants classical problems with additional constraints, indicating strong potential for LLMs in zero-shot or few-shot algorithm design scenarios.
RELATED WORK
Current machine-learning approaches CO fall into two broad categories: neural and symbolic solvers. Neural solvers primarily train a graph neural network (GNN) model with standard machine
learning objectives (Bengio et al. 2020 Cappart al., 2023). The trained GNN is then used either to
predict complete solutions (Luo et al. 2023 Sun & Yangl 2023 Sanokowski et al. 2024 2025) or to guide classical heuristics such as branch-and-
(Gasse et al. 2019 Scavuzzo et al. 2022 Feng [
& 2025) and large neighborhood search (Sonnerat et al. [021 Huang et al.) 2023 Feng et al.
2025b)
2025). Symbolic solvers instead attempt to generate executable programs that solve the problem, exploring the space of algorithmic primitives with reinforcement learning (Kuang et al. 2024a
leveraging LLM agents for code generation (Romera- Parenas et al.) 2023 Ye et al. 2024 Liu et al.
2024 Novikov et al. 2025).
Despite these advances, empirical studies have mostly focused on synthetic benchmarks (Kool et al.
2019 Zhang al. 2023 Berto et al. 2025 Bonnet et al. 2024 Ma et al. 2025), falling short in

---

Published as a conference paper at ICLR 2026
scalability and diversity, restricted to single type of CO problems Thyssens et al. 2023 Li et al. 2025b). Besides, the lack of training instances in existing LLM agentic benchmarks (Fan et al. 2024 Tang et al., 2025 Sun et al. 2025) also hinders the further development. To bridge these gaps, introduce a comprehensive benchmark with both realistic evaluation instances and diverse training data sources.
7 CONCLUSION
We present FRONTIERCO, benchmark designed to rigorously evaluate ML-baaed CO solvers under realistic, large-scale, and diverse problem settings. Through a unified empirical study, we reveal that while current ML methods-iinllddng both neural and LLM-based solvers- still lag behind state-of- scalability. However, our findings also uncover promising avenues: neural solvers excel on structured problems, and LLM agents demonstrate novel strategy discovery on hard instances. We hope FRONTIERCO CO will serve as foundation for advancing the design and evaluation of next-generation ML-based CO solvers.
potential, they juuann-dsigne algorithms in terms of efficiency, generalization, and
Boarder Impact FRONTIERCO offers standardized, challenging benchmark advance ML for combinatorial optimization. It enables rigorous, reproducible evaluation, encourages scalable and generalizable solver development, and highlights current limitations to guide more robust and impactful AI solutions in real-world decision vecision-making.
REPRODUCIBILITY STATEMENT
Details of data collection are provided in Appendix B The implementations of neural solvers are taken from the official public repositories of each method, referenced in Section 3.2 All remaining code, including that for classical solvers, BKS computation, and L.L agent solvers, is available at httpss///qa thu.. com/ sunnwel / Font ierco
REFERENCES
11th DIMACS Implementation Challenge: Steiner Tree Problems. Website, 2013-2014, URL https //dimacsl1- 2ib. de/
Co-organized by DIMACS and ICERM. Available at https://
dimacsil. 2ib.de//
Tobias Achterberg, Scip: solving constraint integer programs. Mathematical Programming Computa- tion, 1:1-41, 2009.
Tobias Achterberg, Timo Berthold, and Gregor Hendel. Rounding and propagation heuristics for mixed integer programming. In Operations Research Proceedings 2011: Selected Papers of the International Conference on Operations Research (OR 201 I), August 30-September 201 Zurich, Switzerland, pp. 71 71-76. Springer, 2012.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL lattps: wtw.:eeeeddinnn...uuusseee www.eers....paapaapaeeeeee files/papal files//aper/2019/ File/ F1le/62dadb2223452222222 2ttpe//acce22222233322222222bbb.
pdf
Guilherme Almeida, Elisangela Martins de Sá. Sérgio Souza, and Marcone Souza. A hybrid iterated local search matheuristic for large-scale single source capacitated facility location problems. Journal of Heuristics, 10:1-28,11 12 2023. doi:
Erling Andersen and Knud Andersen. Presolving linear programming. Math. Program., 71: 221 221-245, 12 1995. doi: 10. 00.007//F01588000.
10

---

Published as a conference paper at ICLR 2026
Maria Chiara Angelini and Federico Ricci- Tersenghi. Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum indepen- dent set. Nature Machine ((1))) Decembeerrr 2022. ISSN 2522-5839, doi: 10.1038/ URL.ttt / doi org/10 1038/ s4 00153/8/222255222-2-00000000 -22-00099-99
5422566-022-05889-y
Florian Arnold, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-scale routing problems. Comput. Oper. Res., 107(C):32-42, 2019. ISSN 0305-0548. doi: 10.1016/j.cor 2019.03.006.
www.:oorrr211... 006
Pasquale Avella and Maurizio Boccia. A cutting plane algorithm for the capacitated facility location problem. Computational Optimization and Applications, 43(1):39-65 May 2009. doi: 10.10007/110899000--99222 v=33200911p39-65.hcmm html
URLpttts:://iee. http:///ddaaa.rppp....eeee
Pasquale Avella, Maurizio Boccia, Antonio Sforza, and Igor Vasilyev. An effective heuristic for large-scale capacitated facility location problems. Journal of Heuristics, 15:597-615, 12 2009.
Vahid Roshanaei Bahman Naderi, Rubén Ruiz. Repository for mixed -nttger programming versus constraint programming for shop scheduling problems: New results and outlook. 2023. doi:
71.5281//emod6.754122.
com. TNF ITTO///FOOOOMM2222222222 0326
Albert-Lászió Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286
(5439):509-512, 1999, doi: 10. 21t.://ceencce26655555577 5509,
org/doi/abs http://bb.....1122/ccieeeeeeeeee 5439.503
D. Behnke and Martin Josef Geiger. Test instances for the flexible job shop scheduling prob- lem with work centers. 2012. URL setp:::://pp..emmmnnccccc.ccoooo wtt.://oo.....ooooooouou....
54531116
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' horrizzo, 2020.
Timo Berthold. Primal heuristics for mixed integer programs. PhD thesis, Zuse Institute Berlin (ZIB), 2006.
Timo Berthold. Mcasuring the impact of primal heuristics. Operations Research Letters, 41(6): 611-614, 2013.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda. André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song, Changhyun Kwon, Lin Xie, and Jinkyoo Park. RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025. URL /RL.atts:://gtttattt httptttthhubb..oo wttp://cc//...eee/e/eooo
Clément Bonnet, Daniel Luo, Donal John Bymee Shikha Surana, Sasha Abramowitz, Paul Duckworth, Vincent Coyette, Laurence Illing Midgley, Elshadai Tegegn, Tristan Kalloniatis, Omayma Mahjoub, Matthew Macfarlane, Andries Petrus Smit, Nathan Grinsztajn, Raphael Boige, Cemlyn Neil Waters, Mohamed Ali Ali Mimouni. Ulrich Armel Mbou Sob, Ruan John de Kock, Siddarth Singh, Daniel Furelos- Prrelos-Blanco. Victor Le, Amn Pretorius, and Alexandre Laterre. Jumanji: diverse suite of scalable reinforcement learning environments in JAX. In The Twelfth International Conference on Learning Representations, 2024. URL 1d=C4CxQmp9wc
net/ forum?
Maximilian Böther, Otto KiBig, Martin Taraz, Sarel Cohen, Karen Seidel, and Tobias Friedrich. What's wrong with deep learning in tree search for combinatorial optimization. In International Conference on Learning Representations, 2022. URL htttts:::/ppeeeeeeeeee wwwpeeewwwwwwwweeeeeeeeeeeeeeeee forum?
ld ZHzddyH24
Quentin Cappart, Didier Chételat. Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023.

---

Published as a conference paper at ICLR 2026
Marco Caserta and Stefan VoB. A general corridor method-basee approach for capacitated fa- cility location. International Journal of Production Research, 58(13):3855 3880, 2020. doi: 10. 10.100000207544.20991666663
1636320
Antonia Chmicla, Elias Boutros Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch and bound. In A. Beygelzimer, Y. Dauphin. P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL htttps://openreiiie net/ forum? did= d= IEImgF xKU63
G. Comuejols, R. Sridharan, and J.M. Thizy. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50(3):280- 297. 1991. ISSN 0377-2217. doi:
URL https
/wwww.scientt. wwwteeewwedddeeeeeeeeee.eeeeeeee com http://........c.eeeeee//e/oaaaa
IBM ILOG Cplex. V12. 1: User's manual for cplex. International Business Machines Corporation, (445)):157,0009
Stéphane Dauzère-Pérès, Junwen Ding, Liji Shen, and Karim Tamssaouet. The flexible job shop scheduling problem: A review. European Journal of Operational Research, 314(2):409-435 2024. ISSN 0377-2217. doi: https://bb..agg///000/////.o.2..
URL htt.h:ttp//// //www www
Juan Diaz and Elena Fernandez. Hybrid scatter search and path relinking for the capacitated p-median problem. European Journal of Operational Research, 169:570-585, 02 2006. doi:
(0.10166..coo.2204488...
Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, and Yongfeng Zhang. NPHardEval: Dynamic benchmark on reasoning ability of large language models via complexity classes. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 4092 4114 Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18633/v/2024. acl-long.22 225.
Shengyu Feng and Yiming Yang. Regularized langevin dynamies for combinatorial optimization. In International conference machine learning. PMLR, 2025a.
Shengyu Feng and Yiming Yang. Sorrel: Subopiimal-demoonstatioon gaaiiongsttratt--ggiideddddd reinforcement learning for learning to branch. In The 39th Annual AAAI Conference on Artificial Inielligence, 2025b.
Shengyu Feng, Zhiqing Sun, and Yiming Yang. Spl-Ins: Sampling-enhanced large neighborhood search for solving integer linear programs, 2025. URL
16171
Zhang-Hus Hua Fu, Sipeng Sun, Jintong Ren, Tianshu Yu, Haoyu Zhang, Yuanyuan Liu, Lingxiao Huang, Xiang Yan, and Pinyan Lu. A hierarchical destroy and repair approach for solving very large-scale travelling salesman problem, 2023. URL htt.t:tps////m arxiv http::://wwwwww..../a/.. abs /taaab//3000 2308. 04639
Sune Gadegaard, A. Klose, and Lars Nielsen. An improved cut-and-solve algorithm for the single- source capacitated facility location problem. EURO Journal on Computational Optimization, 6, 04 2017. doi: 10.1007//113655-0777
16775-117-008444
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, 2019.
Mario Gnägi and Philipp Baumann. A matheuristic for large-scale capacitated clustering. Computers & Operations Research, pp. 105304, 2021.
Bruce L. Golden, Edward A. Wasil, James P. Kelly, and I-Ming Chao. The impact of metaheuristics on solving the vehicle routing problem: Algorithms, problem sets, and computational results. 1998. URLhttte //api semant ischoll wttp:oog///ooeee 757468
12

---

Published as a conference paper at ICLR 2026
Gianfranco Guastaroba and M.Grazia Speranza. Kernel search for the capacitated facility location problem. Journal of Heuristics, 18:1-41, 12 2012. doi: 10.1007/s10732-012299111
Gurobi Optimization, LLC.. Gurobi Optimizer Reference Manual, 2024. URL https: www
gurobi comm
Keld Helsgaun. An extension of the lin-kernighan-helgaan tsp solver for constrained traveling salesman and vehicle routing problems, 12 2017.
Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning In International conference on machine learning. PMLR, 2023.
David Johnson and Michael A. Trick. Cliques, Coloring, and Satisfiabillit: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, USA, 1996. ISBN 0821866095.
David S. Johnson and Catherine C. McGeoch. Network Flows and Matching: First DIMACS Implementation Challenge. American Mathematical Society, USA, 1993. ISBN 0821865986.
Jordan Srour and Steef van de Velde. Are stacker crane problems easy? a statistical study. Computers & Operations Research, 40()):674660, 2013. ISSN 0305-0548. doi: https://
wttpttts::///// http::/wwwwwwwwwcee//eeeeeeeee/e rect. com/ com/sciincee arricle/s1//300056111111111
Transport Scheduling.
Daniel Juhl, David Warme, Pawel Winter, and Martin Zachariasen. The geosteiner software pack- age for computing steiner trees in the plane: an updated computational study, Mathematical Programming Computation, 10, 02 2018. doi: 1..1007/115322-11--013333
Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. A (slightly) improved approximation algorithm for metric tsp. In Proceedings of the 53rd Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2021, pp. 32-45, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450380539. doi: 2..144533406325.4551000 URL https
//doi.org/// 11w./1111133331 3451009
Yasuhito Kawano. A reduction from an Iwe problem maximum independent set problems. Scientific Reports, 13, 05 2023. doi: 10. 01008//41988002334433
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019. URL /ttppss
Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms. Springer Publishing Company, Incorporated, 5th edition, 2012. ISBN 3642244874.
Yufei Kuang, Jie Wang, Haoyang Liu, Fangzhou Zhu, Xijun Li, Jia Zeng, Jianye HAO, Bin Li, and Feng Wu. Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework. In The Twelfth International Conference Learning Representations, 2024a.
Yufci Kuang, Jie Wang. Yuyan Zhou, Xijun Li, Fangzhou Zhu, Jianye Hao, and Feng Wu. Towards general algorithm discovery for combinatorial optimization: Learning symbolic branching policy from bipartite graph. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 25623-25641. PMLR, 21-27 Jul 2024b.
Sebastian Lamm. Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. Finding near-optimal independent sets at scale. J. Heuristics, 23(4):277-229 2017. doi: 10.1007/ s10732-017-9337-x URL / http:///ooooooo/.//// 1007 00000///111100011000000000000000
13

---

Published as a conference paper at ICLR 2026
Kun Lei, Peng Guo, Wenchao Zhao, Yi Wang. Linmao Qian, Xiangyin Meng, and Liansheng Tang. A multi-action deep reinforcement learning framework for flexible job-shop scheduling
problem. Expert Systems with Applications, 205:117796, 2022. ISSN 0957-4174. doi: https://doi.
htgp:0..0rojiess.2222111119 URL htt..htttt://///t.m www.ww.cccii......... scw.ecedieeeeeeeo encedi rect wtt.scccccss/oeeee.ee science/ ant.ccle//11/0955477722000
Markus Leitner, Ivana Ljubic, Martin Luipersbeck, Markus Prossegger, and Max Resch. New real-world instances for the steiner tree problem graphs, 01 2014.
Jure Leskovec and Andrej Krevi. SNAP Datasets: Stanford large network dataset collection. http /sw.pp edu data, June 2014.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference Knowledge Discovery in Data Mining, KDD '05, pp. 177-187, New York, NY, USA, 2005. Association for Computing Machinery, ISBN 159593135X. URL /ttp:s:/ddollorg/101111336
doi: 00.1145/101187001000
10818988899
Sirui Li, Wenbin Ouyang. Yining Ma, and Cathy Wu, Learning-guided rolling horizon optimization for long-horizon flexible job-shop scheduling. In The Thirteenth International Conference on Learning Representations, 2025a. URL htttps::/opeereeieeet net forum? 1
Yang Li, Jiale Ma, Wenzheng Pan, Runzhong Wang. Haoyu Geng, Nianzu Yang, and Junchi Yan. ML4TSPBench: Drawing methodological principles for TSP and beyond from streamlined de- sign space of learning and search. In The Thirteenth International Conference on Learning Representations, 2025b. URL httphhttttpseeeeeeeeeeeee
net. fertt/foumm?? htta://fforuumnoggUUUVVEEEEE G=
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang, Evolution of heuristies: Towards efficient automatic algorithm design using large language model. In ICML, 2024.
Luiz A.N. Lorena and Edson L.F. Senne. Local search heuristies for capacitated p-median problems. 08 2000.
Luiz A.N. Lorena and Edson L.F. Senne. A column generation approach to capacitated p-median problems. Computers & Operations Research, (66 876, 2004. ISSN 0305-0548. doi: https: Wibiiooghoo.0000000000s006400009
URL htttps://www:s htt.:::/www..cceeed.rreee. com/
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirty Conference on Neural Information Processing Systems, 2023. URL
net hwt.:netetoonnooe. formmmormmmmm did
RBI RRAbd
Jiale Ma, Wenzheng Pan, Yang Li, and Junchi Yan. ALACO-bench-101: Benchmark machine learning for classic combinatorial problems on graphs. In The Thirty-ninth Anmual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2025.
//openreview. net. wwwpreevwww..eee//rmu.......o formm::d=yyenttBkk.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. ArXiv, abs/2303. 17651, 2023.
Bahman Naderi and Vahid Roshanaei. Critical-pate paii--ppthhhaaaaee search logic-based benders decomposition approaches for flexible job shop scheduling. INFORMS Journal on Optimization, 4, 08 2021. doi: 10.1287/ijo..0211 10056.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:20/2.13349) 2020.
14

---

Published as a conference paper at ICLR 2026
Alexander Novikov, Ngån Vü, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wag- ner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Push- meet Kohli, and Matej Balog. Alphaevolve: coding agent for scientific and algorithmic discovery, 2025. URL http::ttt:///trtt
www. /250 13131
Ibrahim Osman. Capacitated clustering problems by hybrid simulated annealing and tabu search, international transactions in operational research, 317-336. International Transactions in Operational Research, 1:317-336, 07 1994. doi: 10.
PACE, 2025, Pace 2025 Challenge:
Dominating Set. Website, 2025. URL https: /
pacechallenge 2trg/2025/// /ds Parameterized Algorithms and Computational Experi- ments Challenge. Available at https: /ptp//eccaalleengeeore/22233333
Christos Papadimitriou and Kenneth Steiglitz. Combinatorial Optimization: Algorithmss and Com- plexity, volume 32. 01 1982. ISBN 0-13-152462-3, doi: 1..1009/AASP.11944 164450.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Daniel Rehfeldt, Yuji Shinano, and Thorsten Koch. Seip-jack: An exact high performance solver for steiner tree problems graphs and related problems. In Hans Georg Bock, Willi Jäger, Ekaterina Kostina, and Hoang Xuan Phu (eds.), Modellngg Simulation and Optimization of Complex Processes HPSC 2018, pp. 201-223, Cham, 2021. Springer International Publishing. ISBN 978-3-030-55240- 4.
Gerhard Reinelt. Tsplib a traveling salesman problem library. INFORMS J. 3(4)3376 384, 1991. html #Reinelt91
trrierriiee. de/ http:///////oooaaaaa/a//o///////
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg. Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi, Josh Grochow, Andrea Lodi, Jean-Baptiste Mouret, Talia Ringer, and Tao Yu. Mathematical discoveries from program search with large language models. Nature, 625:468 475. 2023.
Isabel Rosseti, Marcus Poggi, Celso Ribeiro, Eduardo Uchoa, and Renato Werneck. New benchmark instances for the steiner problem in graphs. 08 2001. doi: 10. 1007/978-1-4757-41333
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. In ICML, 2024.
net/foormmi d= KX
Sebastian Sanokowski, Wilhelm Franz Berghammer, Haoyu Peter Wang, Martin Ennemoser, Sepp Hochreiter, and Sebastian Lehner. Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics. In The Thirteenth International Conference Learning Representations, 2025.
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022.
URL
net forum? ? 1ine201ddM41100 111071111110000 0mJ
Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: language agents with verbal reinforcement learning. In Neural Information Processing Systems, 2023.
Jiwoo Son, Zhikai Zhao, Federico Berto, Chuanbo Hua, Changhyun Kwon, and Jinkyoo Park. Neural combinatorial optimization for real-world routing, 2025. URL https: www.i.iiivvoooio org/bbs/ 25033 1 16159
15

---

Published as a conference paper at ICLR 2026
Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning large
neighborhood search algorithm for mixed integer programs. ArXiv, abs/2107. 2021. URL otg/CorpusID 236154745
2021.
https://api. www.stttschtnoooootoocccecccmc
Statistisches Bundesamt. Gemeinden in deutschland nach fläche, bevölkerung und postleitzahl am 2017. URL 31.03.2017 http:p/ww...n...aaaar//////aaaaa
Accessed: 20 September 2017.
Fernando Stefanello, Olinto C. B. de Araújo, and Felipe M. Müller. Matheuristics for the capacitated
p-median problem. International Transactions in Operational Research,, 1677 doi: https://doi.org//10 1/torr.../.....0. /
abbs/1..111/
12103
Mike Steglich. hybrid heuristic based on self-organising maps and binary linear programming techniques for the capacitated p-median problem. 06 2019. doi: 10.71482019-0267.
Weiwei Sun, Shengyu Feng, Shanda Li, and Yiming Yang. Co-bench: Benchmarking language model agents in algorithm search for combinatorial optimization, 2025. URL httptttts///xxi...to
abss2500 04310
Zhiqing Sun and Yiming Yang. DIFUSCO: traph-based diffusion solvers for combinatorial opti-
mization. Thirty-seventh Conference on Neurul Information Processing Systems, 2023. URL
https: //tp:ssv//ppeervveeww net (oooorrmddevvSe
gVV
Éric D. Taillard and Keld Helsgaun. Popmusic for the travelling salesman problem. Eur. J. Oper. Res., 272:420 429, 2019. URL https://app. http:pppp.eeantttmmm www.eemmaiiiomm www.nticchholar.....mo www.ooaarr.rggCoouuuDDDD. 52900855
Hiromitsu Takahashi and Akira Matsuyama. An approximate solution for the steiner problem in graphs. Mathematica Japonica, 24(6):573-577, 1980.
Jianheng Tang, Qifan Zhang. Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and im- proving large language models on graph computation. In International Conference on Learning Representations, 2025.
Daniela Thyssens, Tim Demeddde, Jonas K. Falkner, and Lars Schmidt-Thieme. Routing arena: A benchmark suite for neural routing solvers, 2023, URL
04140
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL 2tleeffffe2222244666000001111112
www.wne. co/paper http://ppp...e///pppppeaaaaaaeaa files//paerr20117
pdf
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611-624, 2012. doi: 10.1287/ 120.1048. URL httttp:://aoi..og/10..111. opre. 1120.1120
Ke Xu and Wei Li. Exact phase transitions in random constraint satisfaction problems. J. Artif. Int. Res., 12(1):93-103, March 2000. ISSN 1076-9757.
Ke Xu, Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Random constraint sat- isfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 171(8):514- 534, 2007. ISSN 0004-3702. doi: https///oiioorr//...06.....mmmmm .04.001..... URL https
www. www.scieeeeiiiieo rect com/ ott.a///c.......e....e.oaoaeaeaa
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. In Advances Neural Information Processing Systems, 2023.
16

---

Published as a conference paper at ICLR 2026
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper- heprrsheuuissics with reflective evolution. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with GFlownets. In Thirtyseventh Conference on Neural Information Processing Systems, 2023. URL httphtttt///peeeeee dd W3JHs2V
A THE USE LARGE LANGUAGE MODELS
Large Language Models (LLMs) were used exclusively for supportive purposes, such adapting baseline implementations, processing data, generating plots, and refining the manuscript text. Impor- tantly, LLMs were not involved in data collection/yythheis,, experimental design and result analysis, and therefore did not influence the scientific contributions of this work.
B DATA COLLECTION DETAILS
This section outlines the data collection process for all problems, covering both test and training/vali- dation instances. Since the training instance generation for neural solvers varies significantly across methods, omit low-level details such as the number of instances and parameter settings. Instead, we focus on describing the generation of the validation set (test cases used to provide feedback for iterative agent refinement) used for LLM-based solvers.
B. MAXIMUM INDEPENDENT SET
To construct suitable test instances, we conduct comprehensive re-evaluation of the datasets collected by Böther et al. (2022). We find that some large real-world graphs (Leskovec & Krevi 2014), such as ai-caida (Leskovec al. 2005) with up 26,475 nodes, are not particularly challenging for SOTA classical solvers like KaMIS (Lamm et al. 2017). which can solve them within seconds. Therefore, we select two moderately sized but more challenging datasets.
The easy test set comprises complementary graphs of the maximum clique instances from the 2nd DIMACS Challenge (Johnson & Trick 1996). while the hard test set consists of the largest 16 instances (each with over 1,000 nodes) from the BHOSLib benchmark (Xu et al. 2007), derived from SAT reductions. Since the original links have expired, we obtain these instances and their BKS from curated mirro For those interested in additional sources of high-quality MIS instances, we also highlight vertex cover instances from the 2019 PACE Challenge) reductions from coding theory and recent constructions derived from lcarning-witt with-errors (LWE) Kawano 2023), which provide promising strategy for generating challenging MIS instances.
Training instances generated using the RB model (Xu & Li 2000). widely adopted in recent
neural MIS solvers (Zhang et al.] (2023] Sanokowski et al. 2024 with 800-1,200 nodes for LLM validation set.
2025). We synthesize 20 instances
B.2 MINIMUM DOMINATING SET
Despite the popularity of MDS in evaluating neural solvers (Zhang et al. 2023 Sanokowski et al.) 2024; 2025) we find a lack of high-quality publicly available benchmarks. We therefore rely on the PACE Challenge 2025 using the exact track instances our easy and the heuristic track instances as the hard set. From each, we selected the 20 instances with the highest primal-dual gaps after a one-hour run with Gurobi. Reference BKS are obtained by extending the solving time two hours.
htteet//aacehallensecc///223
htteas//eela.ong//466333//22 htm
httss//pocechalleeg.oog///2222
17

---

Published as a conference paper at ICLR 2026
Training instances Barabási-Albes graphs (Barabási & Albert 1999) with 800-
100-1,200 nodes,
consistent with previous literature (Zhang et al. 2023 Sanokowski et al. 2024 2025) We generate
20 such instances for the LLM validation set.
B.3 TRAVELING SALESMAN PROBLEM
We source TSP instances from the 8th DIMACS Challenge and TSPLit The easy test set includes symmetric 2D Euclidean TSP instances (distance type EUC_2D, rounding applied) from TSPLib with over 1,000 cities, all with known optimal solutions. This aligns with settings used in prior neural TSP solvers (Karlin al. 2021).
The hard test set consists of synthetic instances from the DIMACS Challenge with at least 10,000 cities (Fu al. 2023). We obtain BKS from the LKH website ?
Training instances follow the standard practice of uniformly sampling points in unit square Kool al. (2019). For simplicity, we reuse DIMACS instances with 1,000 nodes as our LLM validation set, since they are drawn from the same distribution, except scaling the coordinates by constant.
B.4 CAPACITATED VEHICLE ROUTING PROBLEM
We collect CVRP instances from the 12th DIMACS Challenge 10 and CVRPLit which have significant overlap. From these, we select the Golden (Golden et al. (9988) and Belgium (collected by Arnold et al. (Amold et al. 2019)) instances as our easy and hard sets, respectively. We discard the route length constraints in the first eight Golden instances in experiments, All BKS retrieved from the CVRPLib website.
Training data generation follows the method used in DeepACO Yee al. includes up to 500 cities, with demands in [1, 9] and capacity fixed at 50. validation instances for LLMs, with 5 each for 20, 100, and 500 cities.
2023 Each instance
We generate 15 total
B.5 CAPACITATED FACILITY LOCATION PROBLEM
Following the benchmark setup in previous works (Guastaroba & Speranza 2012 Caserta & VoB 2020), select instances from Test Bed 1 (Avella & Boccia 2009) and Test Bed B (Avella et al. 2009) as our easy and hard test sets, respectively. The easy set includes the 20 largest instances from Test Bed 1, each with 1,000 facilities and 1,000 customers. The hard consists of the 30 largest instances from Test Bed B, each with 2,000 facilities and 2,000 customers. All instances are downloaded from the OR-Brescia website
Notably, our easy instances are already significantly larger than the most challenging instances typically used neural solver evaluations (Gasse al,, 2019, SSavuzzoo et al.) 2022] Feng & Yang 2025b), which contain at most 100 facilities and 400 customers. All easy instances can be solved exactly by Gurobi. For the hard instances, as all available BKS identified in the literature (Caserta & Voß 2020) inferior to those obtained by Gurobi, rerun Gurobi for two hours to obtain improved reference solutions.
Overall, find that Gurobi already demonstrates strong performance standard CFLP variants, in which each customer may be served by multiple facilities. Consequently, the single-source CFLP variant-where each customer must be assigned exactly one facility- has become more compelling and actively studied problem in recent CO literature (Gadegaard et al. 2017 Caserta VoB 2020 Almeida al. 2023). Several corresponding benchmarks also available on the OR-Brescia website.
For training data, we adopt the synthetic generation method from Cornuejols al. (Cornueools ct al. 1991), producing 20 instances with 100 facilities and 100 customers for LLM validation. This
httpe///hiaennnnuoorrrroos/ggggn results html
http:///r-brecca.uulll
18

---

Published as a conference paper at ICLR 2026
generation method is widely used in existing neural branching works (Gasse et al. 2019: Scavuzzo
et al. 2022; Feng & Yang 2025b), and forms part of the construction for Test Bed Avella & Boccia
2009
B.6 CAPACITATED P-MEDIAN PROBLEM
We follow the evaluation setup in recent works on CRMP (Stefanello al., 2015 Gnägi & Baumann
2021). Instances with fewer than 10,000 facilities are assigned to the easy set: larger ones go to the
hard set. Easy instances include 6 real-world São José dos Campos instances (Lorena & Senne 2004) and 25 adapted TSPLib instances (Lorena & Senne 2000 Stefanello et al. 2015).. These sourced
from INPE and SomAla websites. Hard instances are large-scale problems introduced by Gnägi
and Baumann (Gnägi & Baumann 2021), downloaded from their GitHut [ BKS are derived by
combining the best GB21-MH results and values reported (Stefanello et al. Gnägi & Baumann 2021).
2015 Steglich 2019
In total, we collect 31 easy and 12 hard instances, all using Euclidean distances. Additional alterna- tives include -pherical-distance instances (Diaz & Fernandez, 2006; Statistisches Bundesamt 2017)
and high-dimensional instances (Gnägi & Baumann 2021).
We synthesize training data with Osman's method (Osman 1994). The validation for LLMs
generated by fixing the number of facilities at 500 and varying medians p in {5, 10, 20, 50). Each setting includes 5 instances.
B.7 FLEXIBLE JOB-SHOP SCHEDULING PROBLEM
We collect FISP instances from two recent benchmark sets commonly used in the evaluation of classi- cal FISP solvers. The easy test set consists of instances introduced by Behnke and Geiger (Behnke &
Geiger 2012). available via GitHub mirro 16 The hard test set includes 24 of the largest instances
(with 100 jobs) from benchmark proposed by Naderi and Roshanaei (Naderi & Roshanaei (002]).
which we obtain from the official repository 17 These two datasets are selected based on recent
comparative studies in the literature (Bahman Naderi 2023 Dauzére-Pérés et al. 2024).
Based on our literature review, the strongest results have been reported by the CP-based Benders decomposition method (Naderi & Roshanaei 202I); however, the source code is not publicly available. As result, we adopt a constraint programming approach using CPLEX, which has demonstrated consistently strong performance relative other commercial solvers and heuristic methods (Bahman Naderi 2023).
Training data is generated following the same protocol used in Li al. (Li et al. 2025a). Specifically, we synthesize 20 instances, each with 20 machines and 10 jobs, to form the LLM validation set.
B.8 STEINER TREE PROBLEM
We collect STP instances from Stein and the 11th DIMACS Challenge The easy set includes Vienna-GEO instances (Leitner et al. 2014), which-despite having tens of thousands of nodes are solvable within minutes by SCIP-Jack. The hard set comprises PUC instances (Rosseti et al. 2001 most of which cannot be solved within one hour by SCIP-Jack and even lack known optima. BKS are determined by taking the best value between SCIP-Jack's 's one-hour primal bound and published solutions from SteinLib or Vienna-GHo (Leitner et al.) (014)). We also highlight the 2018 PACE Challenge as a useful benchmark with varied difficulty levels.
httt:///ww..ee.uppeae//////////t html
http://asegee..nt//mmmmm///.....
itaa:///imeel11.....000a0aa1 html
1tt--200181---ncceeeee hstances
19

---

Published as a conference paper at ICLR 2026
Training data includes two generation strategies. The first generator corresponds to the hardest instances in PUC (Rosseti et al. 2001), which constructs graphs from hypercubes with randomly sampled (perturbed) edge weights. We generate 100 training instances for neural solvers and 10 validation instances for LLMss across dimensions 6-10. The second, based on GeoSteiner (Juhl et al. 2018), samples 25,000-node graphs from unit square. We include 15 such instances (10 for neural solvers, 5 for LLMs 21 and add 45 adapted TSPLib instances (Juhl et al. 2018) to the neural training set. The LLM training set also serves the validation set for neural solvers.
C IMPLEMENTATION DETAILS
C.I NEURAL SOLVERS
DiffUCO, SDDS. The DiffUCO/SDDS checkpoints used in our evaluation are taken directly from the official repository and correspond to the models trained the RB-Large dataset. For MIS (easy and hard), we increase the number of inference steps to 50, while for MDS-easy we revert to the default of steps. Both models encounter out-of-memory issues on the MDS-hard set.
RLNN. We use the official checkpoint trained on RB-(800-1200) for all evaluations. All inference hyperparameters follow the original paper, except that we increase the number of inference steps to 100,000 on both MIS-easy and MIS-hard to fully utilize the 1-hour time budget.
DIFUSCO. We use the official checkpoint trained on TSP-10000 Decoding uses the greedy + 2-OPT heuristic, and all other inference parameters follow the configuration used in the original paper on TSP-10000.
LEHD.
We use the optimal TSP and CVRP checkpoints from the official repository Decoding employs the Parallel Local Reconstruction (PRC) heuristic. Instead of fixing the number of PRC iterations, we continue iterating until the 3600-second time budget is exhausted.
DeepACO. For CVRP, we evaluate the official CVRP500 checkpoint 26 tion phase, we follow the standard protocol and continue decoding using HGS until the time limit is reached.
After the neural construc-
SIL. We use the default checkpoints from the official repository for TSPLib (trained on TSP-1000) and CVRPLib (trained on CVRP-1000) 27 Similar to LEHD, decoding uses PRC and is iterated until the solving time budget exhausted.
tMDP SORREL.
We use the official checkpoints for the CFLP task from the tMDF 28 and SOR- RED repositories. For tMDP, we follow the DFS-based variant.
GCNN. For CFLP, GCNN is trained 100,000 -trong-branching samples collected from 10,000 instances. For CPMP, it is trained on 50,000 samples collected from 1,000 instances. Both training procedures follow the methodology of Gasse et al. (2019).
IL-LNS, CL-LNS. Training data is constructed from Docal-branchin trajectories on 200 instances. We follow the default protocol, using 20% of variables to define the large neighborhood, and keep all remaining hyperparameters identical to those in the official implementation
20

---

Published as a conference paper at ICLR 2026
Since the FJSP instances used in experiments already compatible with those evaluated by MPGN_ and L-RHO we adopt their exact hyperparameter settings, including the 450 training instances generated by Li al. (2025a).
MPGN, L-RHO.
C.2 LLM SOLVERS
Self-Refine In our implementation, we 64 iterations. In each iteration, the LLM receives the previous best-performing code and its dev-set evaluation results, then generates the next code. We use 04-mini with a medium reasoning budget and default sampling parameters. The dev evaluation timeout is 300s, although the LLM is prompted to write algorithms for a 3600s timeout. After 64 iterations, we evaluate the best dev-set code on the test set with a 3600s timeout.
FunSearch We follow the official FunSearch implementation and modify the prompt to fit our tasks. We set the number of islands to 10, functions per prompt 2, the reset period to 2 hours, and run 64 iterations with a 300s dev evaluation timeout. After 64 iterations, we evaluate the best dev-set code on the test set with 3600s timeout.
ReEvo We follow the official ReEvo implementation and modify the prompt fit our tasks. We set the population size to 10, initial population size to 4, mutation rate to 0.5, and run 64 iterations with a 300s dev evaluation timeout. After 64 iterations, evaluate the best dev-set code on the test set with 3600s timeout.
C.3 EXAMPLE PROMPT
Our query prompts basically consist of two parts: the description of the problem background and the starter code for L.M fill The following an example prompt on TSP.
The evaluation example
Problem Description
The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem where, given set of cities with known pairwise distances, the objective is to find the shortest possible tour that visits each city exactly once and returns to the starting city. More formally, given complete graph G (V, E) with vertices representing cities and edges E with weights representing distances, we seek to find a Hamiltonian cycle (a closed path visiting each vertex exactly once) of minimum total weight.
Starter Code
def velve (**kwargs)
Solve TSP instance.
Args:
nodes (list): List of (x, coordinates representing cities in the TSP problem
Format: [x11, yl), (x2, y2), (xn, yn)
Returns:
dict: Solution information with: "tour" (list): List node indices representing the solution path
Format: 10, 3, 1, ...J where numbers are indices into the nodes list
Your function must yield multiple solutions over time, not just return one solution
"httee://tthhbb.coo//r/r/e/////s http:://ggfthbbb.comm/ttttt
21

---

Published as a conference paper at ICLR 2026
Use Python's s yieid keywora repeatedly produce a stream solution
Each yielded solution should be better than the previcus one while True:
yield {
'tour': [],
D DETAILED RESULTS
Table present the detailed results for the evaluated methods in Section 4 A result marked with the method suffers from the out-of-memory timeout issue before obtaining feasible solution (assigned a primal gap and runtime 3600 seconds) on any instance in this benchmark. Note that the geometric mean and standard deviation is reported for the solving time.
Table 4: Comparative Results on MIS.
MIS
Easy
Hard
Method
Gap 1.51 0.43 %
Time J
Gap
Time |
KaMIS
223 + 5.62
2.65 0.81 %
274 + 1.29s
DiffUCO
9.54 9.82 %
154 +x 1.18s
6.45 1.43 %
19 +x 1.29 s
SDDS
11.85 + 12.47 %
223 +x 1.14s
5.24 1.12 %
27 +x 1.22
RLNN
6.29 + 8.81 %
532 +x 3.24s
6.31 + 2.76 %
1064 +x 1.65
FunSearch
1.87 + 3.63 %
3600 +x 1.00s
4.97 + 0.92 %
3600 +x 1.00s
Self-Refine
1.30 3.89 %
3600 + 1.00s
4.02 0.97 %
3600 1x 1.00s
ReEvo
1.44 + 4.05 %
3600 +x 1.00s
4.81 + 0.95 %
3600 +x 1.00s
Table 5: Comparative Results MDS.
MDS
Easy
Hard
Method
Gap
Time 4
Gap 4
Time
Gurobi
0.00 0.00 %
3600 +x 1.00
0.63% = 2.74 %
3600 =x 1.00
DiffUCO
71.86 = 21.56
54 + 26.86
*100.00 = 0.00 %
*3600 = 1.00s
SDDS
66.21 = 12.80 %
54 + 27.01s
*100.00 0.00 %
3300 =x 1.00s
FunSearch Relf-Refine
41.83 + 48.67 %
3600 +x 1.00s
95.21
11.43 %
3600 +x 1.00s
6.19 + 4.42 %
3600 + 1.00s
5.71 = 3.49%
3600 +x 1.00s
ReEvo
7.52 + 4.50 %
3600 +x 1.00s
5.81 5.24%
3600 +x 1.00s
22

---

Published as a conference paper at ICLR 2026
Table 6: Comparative Results on TSP.
TSP
Easy
Hard
Method
Gap +
Time +
Gap 4
Time
LKH-3
0.03 = 0.05 %
= 8.90
2.89 1.58 %
21 +x 6.69
LEHD
10.23 + 9.37 %
487 +x 4.20
*76.84
34.23
*1347 +x 1.63s
DIFUSCO
4.19 + 1.20 %
555 +x 2.45
*69.04 + 45.57 %
*2850 + 1.66s
SIL
2.51 + 1.56 %
3600 +x 1.00s
21.34 + 34.23 %
3600 + 1.00s
FunSearch Self-Refine
6.79 + 5.80 %
3600 +x 1.00s
35.82 + 25.62 %
3600 + 1.00s
6.29 + 5.35 %
3600 +x 1.00s
32.00 + 17.44
3600 +x 1.00s
ReEvo
5.65 + 6.16%
3600 +x 1.00s
37.77 + 38.57 %
3600 +x 1.00s
Table 7: Comparative Results on CVRP.
CVRP
Easy
Hard
Method
Gap
Time 4
Gap 4
Time
HGS
0.11 = 0.18% %
3600 +x s.00
6.74 2.50 %
*300 = 1.00
LEHD
1.97 + 0.92 %
893 + 1.74s
*100.00
0.00%
*3600 +, 1.00s
DeepACO
4.42 = 1.56 %
50 + 1.64s
*27.69 = 36.18 %
*3333 +x 1.12s
SIL
10.90 = 8.17 %
3600 +x 1.00s
11.35 = 4.4.6%%
3600 +x 1.00s
FunSearch
5.27 3.70 %
3600 + 1.00s
6.52 = 2.67%
3600 = 1.00s
Self-Refine
3.86 + 1.63 %
3600 +x 1.00s
27.50 = 6.19%
3600 + 1.00s
ReEvo
7.16 = 3.42 %
3600 =x 1.00s
10.01 = 2.83 %
3600 = 1.00s
Table 8: Comparative Results on CFLP.
CFLP
Easy
Hard
Method
Gap +
Time 4
Gap
Time 4
Gurobi
0.00 + 0.00 %
308 +x 1.93
0.01 + 0.02 %
3136 +x 1.34s
(MDP
3.54 + 3.14 %
3581 =x 1.00
55.35 +:2 21.7 %
3600 + 1.00s
SORREL
3.46 2.51%
3600 = 1.00
55.35 + 21.7 %
3600 +x 1.00s
GCNN
3.22 = 3.10%
3551 = 1.07s
55.35 + 21.7%
3600 = 1.00s
FunSearch
7.31 0.75 %
3600 1.00s
7.41 +:2 3.26 %
3600 =x 1.00s
Self-Refine
27.08 + 10.79 %
3600 +x 1.00
24.93 + 21.56 %
3600 + 1.00s
ReEvo
12.89 1.70%
3600 =x 1.00
12.79 + 6.40
3600 = 1.00s
Table Comparative Results on CPMP.
CPMP
Easy
Hard
Method
Gap
Time
Gap 1
Time
GB21-MH
0.53 + 0.49 %
541 +x 8.49
0.32 0.37 %
3600 + 1.00
IL-LNS
*80.57 + 36.75 %
*2636 + 1.92
*100.00 + 0.00 %
*3600 +x 1.00s
CL-LNS
*81.45 + 36.21 %
*2649 + 1.92
*100.00 + 0.00 %
*360 +x 1.00
GCNN
*42.91 + 28.66 %
*2143 +x 3.68 s
*100.00 = 0.00 %
3600 =x 1.00s
FunSearch
3.96 + 3.77 %
3600 +x 1.00
*77.32 + 41.06 %
*300 +x 1.00s
Self-Refine
2.84 + 2.57 %
3600 = 1.00
*74.05 = 39.50
*360 =x 1.00s
ReEvo
3.40 + 3.14%
3600 +x 1.00
*70.64 + 43.61% %
*3600 =x 1.00s
23

---

Published as a conference paper at ICLR 2026
Table 10: Comparative Results on FJSP.
FJSP
Easy
Hard
Method
Gap +
Time 4
Gap
Time +
CPLEX
0.00 0.00% %
702 = 17.01
0.01 + 0.04 %
3600 =x 1.00
MPGN
12.78
4.04 %
9 + 4.26
1.50 + 0.85 %
69 +x 1.90s
L-RHO
27.20 12.97 %
21 =x 1.87s
1.03 + 0.86 %
58 = 2.49
FunSearch
5.05 3.57 %
3600 =x 1.00s
12.10
2.90 %
3600 =x 1.00s
Self-Refine
6.66 + 2.48 %
3600 = 1.00s
1.14 + 1.27 %
3600 = 1.00s
ReEvo
5.61 2.78% %
3600 =x 1.00
2.16 + 1.72% %
3600 +x 1.00s
Table 11: Comparative Results on STP.
STP
Easy
Hard
Method
Gap J
Time 4
Gap
Time +
SCIP-Jack
0.00 + 0.00 %
22 + 5.43
0.50 + 0.62 %
717 +x 26.70s
RL
14.00 + 3.31 %
31 = 8.40
13.10 + 6.52 %
+ 4.44s
SL
14.00 3.31 %
31 = 8.40
13.10 + 6.52
+ 4.44s
FunSearch Self-Refine
8.29 + 5.44 %
3600 +x 1.00s
5.82 + 4.86%
3600 + 1.00s
11.23 6.04 %
3600
1.00s
6.93 + 3.96%
3600 = 1.00s
ReEvo
14.36 + 3.53% %
3600 =x 1.00s
10.03 + 6.43
3600 + 1.00s
E EFFICIENCY ANALYSIS OF NEURAL SOLVERS
Neural solvers are typically motivated fast heuristics that avoid the heavy computation of exact classical solvers. However, existing evaluations often overlook that many classical solvers can also operate fast heuristics when given restricted time budgets. To illustrate this point, take TSP as an example and compare commonly used fast-mode configurations of both classical and neural methods. Specifically, we include LKH-3 under the POPMUS IC setting (Taillard & Helsgaun) 2019) with 1,000 trials, DIFUSCO with 50 inference steps and greedy decoding, LEHD with greedy decoding, and SIL with 10 Parallel Local Reconstruction (PRC) steps. The comparative results on several TSPLib instances across different scales are shown in Table 12
Table 12:
Comparison between the fast version of classical and neural solvers on TSPLib instances across different scales.
TSP-easy Instances
LKH-3
LEHD
DIFUSCO
SIL
Gap 1
Time
Gap
Time
Gap
Time
Gap
Time
pr1002
0.70%
0.2s
17.02%
6s
4.25%
3s
0.82%
27s
111400
0.40%
0.3s
10.52%
6s
28.37%
8s
5.53%
31s
pr2392
0.68%
0.4s
10.97%
18s
14.80%
15s
3.46%
38s
pcb3038
0.68%
Is
14.70%
20s
11.85%
31s
3.27%
28s
fnl4461
0.76%
1s
16.00%
81s
3.50%
34s
2.64%
39s
r15915 5
1.43%
2s
9,42%
169s
3.31%
52s
5,41%
39s
rll 1894
2.25%
4s
27.56%
1204
31.47%
130s
6.41%
37s
1.53%
4s
41.75%
1765s
33.14%
164s
11.33%
42s
brd14051
1.39%
4s
29.19%
1981s
30.37%
167s
6.14%
39s
d15112
0.12%
5s
26.49%
2464s
3.20%
278s
5.21%
40s
d18512
1.22%
5s
29.64%
4767s
30.67%
266s
5.56%
41s
The results indicate that neural solvers remain substantially less effective than LKH-3 when all methods are run in their fast configurations. As the instance size grows from 1,002 to 18,512 nodes, I.H--3 requires only five additional seconds while still delivering near-optimal solutions. In contrast,
24

---

Published as a conference paper at ICLR 2026
DIFUSCO needs extra six minutes, and LEHD requires feasible tour. SIL is notably more scalable than both LEHD and DIFUSCO its runtime increases much more modestly, reflecting meaningful progress in ML-based solvers. However, its optimality gap remains large and does not show a clear advantage over LKH-3 in runtime or solution quality.
hour, merely to obtain a single
F ADDITIONAL ANALYSES ON NON-EUCLIDEAN CHALLENGES IN TSP
To further highlight the difficulty posed by non-Euclidean CO instances a challenge largely over- looked in current ML4CO evaluations- incorporate additional Asymmetric TSP (ATSP) benchmark composed of non-Euclidean (non-metric) instances. These instances originate from real- world datasets (Jordan Srour van de Velde 2013) that span stacker-crane operations, transportation and routing tasks, robotic motion planning, and data- compression problems. Dataset statistics and evaluation results are reported Table [3] and Table [4] respectively. RRNCO (Son et al. 2025), recent neural solver designed for real-world ATSP instances, is used for evaluation.
Table 13: Summary of ATSP instances.
Problem
Test Set Sources
Attributes
Easy Set
Hard Set
Instances
31
33
ATSP
Jordan Srour & van de Velde (2013)
Cities
131
323-932
Table 14: Comparative Results on ATSP.
ATSP
Easy
Hard
Method
Gap J
Time
Gap |
Time $
LKH-3
0.00 + 0.00 %
1927 +x 1.31
0.08 + 0.09 %
705 +x 2.52
RRNCO
1.42 = 0.69 %
3600 = s.00
15.46 + 7.88 %
3600 +x 1.00
FunSearch
0.00 + 0.00 %
3600 = 1.00s
3.52
5.26 %
3600 =x 1.00
Self-Refine
0.50 + 0.81 %
3600 +x 1.00
10.94 + 11.16 %
3600 +x 1.00
can be seen that although the largest ATSP instance, which is from the hard set, only contains 932 nodes, it is way challenging than the easy (metric) TSP instances at the small scale (~ 1000 nodes). where the former could not be solved to optimum within hour while the latter could be solved to optimum in seconds.
G DISCUSSIONS IN SOLVER DEPLOYMENT
Beyond solution quality and solving time, we observe substantial variation in deployment cost across solver families. In general, neural solvers rely heavily on GPUs and require significantly more memory than classical solvers, making them more expensive to deploy in practice. LLM-based solvers, while consuming considerable API credits or training resources during the evolutionary development phase, incur relatively low deployment cost during inference once the solver is finalized.
25


Reviews:
[{"review_id": "qzOXYSxza6", "reviewer": "Reviewer_uR1C", "summary": "The paper introduces FRONTIERCO, a benchmark for evaluating ML-based combinatorial optimization (CO) solvers under real-world structure and extreme scale. It targets three long-standing limitations in prior NCO evaluations: small “toy” instances, synthetic data that miss structural diversity, and inconsistent baselines/splits. The benchmark spans eight CO problems across routing, facility location, scheduling, graphs, and Steiner trees, drawing test instances from competitions and public repositories (e.g., TSPLib, DIMACS). For training/validation, the authors provide standardized synthetic generators for neural solvers and separate dev sets for LLM agents to avoid leakage; test evaluation is strictly on real-world instances. A unified protocol enforces a one-hour evaluation cap and a scale-invariant primal-gap metric with an explicit infeasibility policy.", "questions": "[Clarify and exemplify the metric]  \nProvide a boxed, self-contained definition of the primal-gap for both minimization and maximization tasks, with fully worked examples that cover negative and zero objective values as well as an infeasible output (e.g., explicitly show a case yielding gap = 1 with time = 3600s). Accompany this with a concise table mapping each task to its objective definition and sign convention so readers cannot misinterpret gap magnitudes across problems with differing scales or signs.  \n  \n[Make evaluation and training budgets fully transparent]  \nEnumerate complete training and sampling budgets so cost–performance trade-offs are clear and reproducible. For neural methods, report dataset sources and sizes, epochs/steps, batch sizes, learning-rate schedules, regularizers, number of seeds, total GPU hours, and peak memory. For LLM agents, disclose prompts/templates, sampling parameters (temperature, top-p), number of samples/iterations, wall-clock per sample, and aggregate CPU/GPU hours; include fair wall-clock comparisons to classical solvers under the same evaluation limits.  \n  \n[Strengthen statistical reporting and robustness]  \nReport mean ± standard deviation (or confidence intervals) per test set and run paired statistical tests (e.g., Wilcoxon) on shared instances to substantiate improvements. Release raw per-instance outcomes and add scatter plots (gap versus time), clearly marking infeasible or failed runs. Include sensitivity analyses: for neural models, vary model size and any reduction techniques; for LLM agents, vary the number of samples/iterations and compare tool-use versus no-tool settings.  \n  \n[Probe integration with strong classical components]  \nMove beyond “neural versus weak heuristic” and evaluate “neural + strong heuristic,” for example by plugging neural move-selection into LKH-3 or HGS variants. Measure whether such hybrids consistently lift near-SOTA classical solvers across tasks and scales, thereby clarifying the realistic contribution of learned components.  \n  \n[Expand structure-shift diagnostics]  \nGeneralize the Euclidean/non-Euclidean analysis beyond STP to graph problems such as MIS/MDS (e.g., SAT-induced versus random graphs) and to routing (metric versus non-metric variants). Report performance deltas, learning-curve contrasts, and any systematic failure modes to better characterize how models cope with structural distribution shifts.  \n  \n[Improve reproducibility aids]  \nRelease concise pseudocode for each evaluation harness (neural and LLM), including the hidden evaluation API signature to eliminate ambiguity in adapter interfaces. Publish all seeds, configuration files, and scripts required to regenerate figures and tables from raw outputs. Add a short “gotchas” section documenting environment pitfalls (e.g., Python/BLAS/MKL versions) that can materially affect results.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "[Problem motivation & clarity]  \nThe introduction tightly argues why synthetic, small-scale evaluations have over-estimated ML performance and motivates a real-world, frontier-scale benchmark. The easy/hard split, data provenance, and scale claims are clearly articulated, making the problem and goals unambiguous.  \n  \n[Benchmark design & practicality]  \nThe benchmark aggregates eight diverse CO tasks with real-world test instances and provides standardized BKS and synthetic training/dev resources. The one-hour cap and hardware normalization (single CPU core for all, single A6000 for neural solvers) produce a pragmatic, comparable setting. The scale-invariant primal-gap definition (including the infeasibility policy) is a strong choice for cross-task fairness.  \n  \n[Breadth and diagnostic depth of evaluation]  \nSixteen ML solvers spanning neural, hybrid, and LLM agents are compared to top classical solvers. Beyond averages, the paper probes why gaps occur: distribution shift from synthetic training to structurally diverse test sets; neural OOM/latency; and LLM variability/safety issues. The STP Euclidean vs. non-Euclidean experiment is a crisp test of “global structure” capture.\n  \n[Insightful, constructive negative results]  \nThe study shows that neural modules can improve weak baselines (e.g., DIFUSCO vs. 2-OPT; GCNN vs. SCIP) yet still trail strong classical SOTA, and it identifies promising pockets where LLM agents surpass classical SOTA (e.g., MIS-easy, CVRP-hard) while cautioning about instability. These balanced findings are valuable for the community.", "weaknesses": "1. The paper’s treatment of metric edge cases lacks technical clarity. While the primal-gap policy is defined—including handling of negative or zero costs and infeasible outputs—there are few concrete examples that cover both minimization and maximization settings. This matters because tasks can differ in objective sign and scale, and without worked examples readers may interpret the same numeric gap differently across problems. The gap definition section would benefit from illustrative cases; as is, reproduction and extension to new tasks or cost conventions can be confusing.\n\n2. Reporting granularity is limited, creating questions about numerical consistency. The main text emphasizes aggregate gaps, but offers few per-instance distributions, confidence intervals, or paired significance tests. This makes it difficult to assess the reliability of observed improvements or claimed LLM “wins.” In the results tables and figures, richer dispersion statistics and paired comparisons on shared instances would substantiate robustness and provide clearer selection guidance for practitioners.\n\n3. Transparency around compute and training budgets is insufficient. Although the evaluation setup standardizes a one-hour cap and hardware, the paper provides only limited per-method training details for neural baselines (e.g., epochs, steps, seeds, hyperparameters) and sparse accounting of sampling budgets for LLM agents. This obscures fairness and cost-effectiveness comparisons across approaches. The evaluation and appendices should enumerate these budgets; without them, reproducibility and cost–benefit assessment are hindered.\n\n4. The scope and novelty of LLM-based algorithms are not framed sharply enough. Word-clouds and qualitative analysis suggest that the agents largely recompose known metaheuristics such as simulated annealing and large-neighborhood search. What is missing is an explicit separation between retrieval/recombination and genuinely novel algorithmic invention. In the Discussion (§5.3), clarifying this boundary would calibrate expectations for future “agentic” progress and reduce the risk of overstating algorithmic novelty.\n\n5. Finally, statistical robustness and safety considerations are underdeveloped. The LLM agents exhibit high variance across runs—sometimes generating very different strategies—and can trigger OOM or other resource issues during iterative “evolving.” The paper does not provide a systematic variance/seed study or a resource-safety protocol (e.g., per-sample CPU/GPU caps). These gaps, noted across the results and discussion, leave practical adoption uncertain without clearer guardrails on reliability and operational cost.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T489MOoXoF", "reviewer": "Reviewer_VRL2", "summary": "This paper presents a standardized benchmark for the evaluation of machine learning–based solvers for eight combinatorial optimization problems. It provides a comparison of 16 ML-based solvers against state-of-the-art classical methods. The study offers some insights, revealing both the current limitations and the future potential of ML-based solvers in this domain.", "questions": "In addition to my remarks in the weaknesses section, I have the following questions:\n\n1. I did not fully understand your procedure for generating training instances. Let’s take the descriptions of the TSP and VRP training datasets as examples. You first mention that instances are uniformly sampled from a unit square. However, you later state that DIMACS instances with 1,000 nodes are used for the LLM dataset. Does this mean you created two separate datasets - one for “classic” NCO solvers and another for LLM-based methods?\n\n2. Additionally, you mention that 15 validation VRP instances are used “for LLMs,” but there is no information about how many training instances were generated, nor any details about the validation dataset for TSP. Why do TSP instances have 1,000 nodes, while CVRP instances go only up to 500 nodes? Do you consider 15 validation instances sufficient for a reliable evaluation?\n\nI would appreciate further clarification on these points, as well as on the training datasets for the other problems.\n\nAdditionally, I do not fully understand your claim that you provide regenerated training and validation datasets to eliminate inconsistencies found in previous works, and the limitation that existing models are trained on synthetic instances. Your TSP and CVRP datasets appear to be identical to those used in prior works - synthetic instances with node coordinates sampled from the unit square, demands drawn from [1, 9], and capacity set to 50. \n\n3. You mention that an asterisk (*) indicates that the method encountered out-of-memory or timeout issues. In that case, how was the optimality gap computed for those models if they did not produce any solution?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The methodology of the paper is good and well presented.\n\n2. Developing standardized benchmarks for evaluating ML-based CO solvers is necessary for progress in this field.\n\n3. Proposed benchmark cover routing, graph, location, set, and scheduling CO problems.  However, another scheduling problem would be welcome.", "weaknesses": "I believe that some of the claims in this paper are too strong and not supported by the current state of research in this domain.  \n\nIt is true, in general, that many neural solvers rely on attention mechanisms and suffer from well-known attention bottlenecks, and this paper points out that addressing these limitations is an important direction for future research. However, many works have already explored ways to mitigate these bottlenecks, which are entirely overlooked in this work. Some relevant works are listed below.\n\n1. The work by Luo et al. [1] specifically addresses the attention bottleneck problem in routing tasks. It directly challenges the claim in Section 5.1 that neural solvers are still far from being comparable to state-of-the-art classical solvers. In fact, their approach outperforms both LKH3 and HGS on large-scale CVRP instances.\n\n2. The scalability analysis in this work considers only a few (computationally expensive) models and concludes that NCO solvers have problems with scalability. An example in this work is LEHD, and it, as its name implies, relies on a Heavy Decoder architecture, which is very costly. However, there are significantly faster alternatives, for example, the method proposed in [2], and their experiments show that it is over 200× faster than LKH3, with only a minor drop in performance.\n\n3. The claim that most neural solvers are based on GNNs is not entirely accurate. Current SOTA neural solvers primarily employ attention mechanisms rather than GNNs - including the majority of models you evaluate in this work. \n\n4. The discussion and claims about capturing global structure using Euclidean and non-Euclidean problems are based on a single problem -  STP. I am not sure that is enough to conclude the ability of neural solvers to capture the global graph structure.\n\n5. I fully support the claim that most existing evaluations are limited to 2D Euclidean instances. However, unfortunately, this work did not take any steps to address this limitation - the benchmarks still exclude non-Euclidean instances for TSP and CVRP, despite the growing number of recent works focusing on this aspect. Including such instances would significantly strengthen the arguments and make the evaluation more comprehensive, especially given the stated goal of building a “real-world evaluation of NCO.” In practice, all real-world routing problems involve non-Euclidean distances. I therefore suggest adding the instances from [2], or any other real-world datasets, to your benchmark set.\n\n[1] Luo et al. Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems, ICLR 2024\n\n[2] Son et al. Neural Combinatorial Optimization for Real-World Routing, arXiv:2503.16159", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9rWTSzxwtL", "reviewer": "Reviewer_zcmM", "summary": "This paper proposed a systematic, large scale benchmark for machine learning for combinatorial optimization field. The benchmark collected a wide range of datasets, and standardized training pipelines, and exhibited insightful findings of current ML4CO methods compared to standard solvers.", "questions": "- In equation 2, why is the primal gap set to 1 when $cost \\cdot c* < 0$?\n- There also exists other CO benchmarks, e.g., https://github.com/Thinklab-SJTU/ML4CO-Bench-101, so what is your core competitive strength as another CO benchmark paper?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A large scale and wide benchmark makes a lot of sense for ML4CO field. The selection of problems are reasonable. The best known solution is a good guidance for CO practitionerrs. And the findings about current ML vs solvers are important guidelines for future research.", "weaknesses": "First of all, there is no clear weakness of the paper. There are some small concerns that I have:\n- The problem instances in table 1 are all collected from previous literature or competitions, which might limit the originality of the benchmark. \n- The standardized training and validation makes sense to some extent, but it may not be fair comparison. e.g., some methods may subsume scaling law and performs better with more training data, while other methods might be suitable for data scarcity but stagnant with more training data. Also, baselines such as GNNs seem incomparable to LLMs, as the modality is totally different. So it is not convincing to me if there exists a standardized training pipeline. \n- I think the deployment difficulty of various methods should also be considered, such as GPU hours, for real world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)