Large Language Models as End-to-end Combinatorial Optimization Solvers
Authors: Xia Jiang
Yaoxin Wu
Minshuo Li
Zhiguang Cao
Yingqian Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Model; Combinatorial Optimization; Reinforcement Learning
Primary area: deep_learning

Abstract: Combinatorial optimization (CO) problems, central to decision-making scenarios like logistics and manufacturing, are traditionally solved using problem-specific algorithms requiring significant domain expertise. While large language models (LLMs) have shown promise in automating CO problem solving, existing approaches rely on intermediate steps such as code generation or solver invocation, limiting their generality and accessibility. This paper introduces a novel framework that empowers LLMs to serve as end-to-end CO solvers by directly mapping natural language problem descriptions to solutions. We propose a two-stage training strategy: supervised fine-tuning (SFT) imparts LLMs with solution construction patterns from domain-specific solvers, while a feasibility-and-optimality-aware reinforcement learning (FOARL) process explicitly mitigates constraint violations and refines solution quality. Evaluation across seven NP-hard CO problems shows that our method achieves a high feasibility rate and reduces the average optimality gap to 1.03–8.20% by tuning a 7B-parameter LLM, surpassing both general-purpose LLMs (e.g., GPT-4o), reasoning models (e.g., DeepSeek-R1), and domain-specific heuristics. Our method establishes a unified language-based pipeline for CO without extensive code execution or manual architectural adjustments for different problems, offering a general and language-driven alternative to traditional solver design while maintaining relative feasibility guarantees.

Large Language Models as End-to-end Combinatorial Optimization Solvers
Xia Jiang
Yaoxin Wu' Eindhoven University of Technology y. wu20tue.n.
Eindhoven University of Technology x. jiangg@tue.... .n1
Minshuo Li
Zhiguang Cao
Eindhoven University of Technology m. 1..178tue.nl. nl
Singapore Management University zgcao@smu. edu.sg
Yingqian Zhang
Eindhoven University of Technology YQZhang@tue... nl
Abstract
Combinatorial optimization (CO) problems, central to decision-making scenarios like logistics and manufacturing, traditionally solved using problem-specific algorithms requiring significant domain expertise. While large language models (LLMs) have shown promise in automating CO problem solving, existing ap- proaches rely on intermediate steps such as code generation or solver invocation, limiting their generality and accessibility. This paper introduces novel framework that empowers LLMs to serve as end-to-end CO solvers by directly mapping natu- ral language problem descriptions solutions. We propose two-stage training strategy: supervised fine-tuning (SFT) imparts LLMs with solution generation patterns from domain-spp -omaii--pecific solvers, while feasibility deasibility-and-optime and-oppimallty- -ware reinforcement learning (FOARL) process explicitly mitigates constraint viola- tions and refines solution quality. Evaluation across seven NP-hard CO problems shows that our method achieves a high feasibility rate and reduces the average optimality gap 1.03-8.20% by tuning a 7B-parameter LLM, surpassing both general-purpose L.MMs (e.g., GPT-4o), reasoning models (e.g., DeepSeek-RP 1), and domain-speciff heuristics. Our method establishes unified language- based pipeline for CO without extensive code execution manual architectural adjust- ments for different problems, offering a general and language-driven alternative to traditional solver design while maintaining relative feasibility guarantees.
Introduction
Large language models (LLMs) have emerged as powerful tools with the potential revolutionize not only traditional natural language processing (NLP) problems, but also a broad range of decision- making tasks, such time series prediction I 2 medical diagnostics 3 4 and computational optimization [5 6. As LLMs are increasingly recognized as general-pune -prrpose assistants for decision- making, there is growing interest their potential tackle NP-hard combinatorial optimization (CO) problems, which are central to many common real-world application scenarios. Specifically, CO arises in various domains such as transportation manufacturing [ and healthcare 9. often
*Correspnniing author
39th Conference on Neural Information Processing Systems (NcurIPS 2025)

---

requiring the design of complex heuristics to balance optimality and computational efficiency. LLMs facilitate CO by automating the problem-solving process, thereby reducing reliance on domain- specific modeling experts [5] Ideally. an LLM can interpret user requests and generate corresponding solutions entirely through natural language. Thus, reduces or eliminates the need for coding or formal modeling and making CO accessible to scenarios involving non-experts.
Existing research primarily leverages LLMs solve CO problems by generating executable code to discover heuristics [6]
To M or by interacting with optimization solvers 02 13. However,
these methods still require substantial domain -omain-specific expertise, as users must define problem- specific algorithmic templates (to evolve and discover heuristics) or proficiently use the existing optimizers (to execute the generated solver-calling programs). In contrast, end-to-end solvers model CO using natural language and offer more appealing alternative by directly generating solutions, thus mitigating reliance on domain knowledge and offering a unified solving process [14]
While L.MSs can reason out simple mathematical problems [6), their end-to-end capability for CO remains highly limited [8]. NP-hard CO problems often involve multiple constraints, making it challenging for LLMs to reason and identify even feasible solutions-let alone generate optimal ones. For example, GPT-3.5-turbo achieves an average optimality gap of 133% on the traveling salesman problem (TSP) with 50 nodes [9). Even state-of-the-art models, such as GPT-4o and Claude-3.5 Sonneet,,, achieve only around a 50% feasibility rate on CO problems with fewer than 30 nodes-a limitation that persists even with the application of instruction tuning [20]. These persistent shortcomings in both optimality and feasibility have raised significant concerns regarding the potential of LLMss for solving CO problems [21]. Thus, it remains an open question on how to enable L.MSs to effectively map natural dessriee CO problems to high-quality solutions.
In this paper, we aim to empower LLMs to serve as end-to-end solvers for general CO problems via a two-stage fine-tuning approach. In the first stage, we use the supervised fine-tuning (SFT) paradigm to teach LLMs solution generation patterns by learning from domain-specific CO solvers. Our empirical results reveal that SFT alone leads to over-greedy behavior for some problems, where LLMs violate constraints in pursuit of improved objectives. To address this issue, we propose a ann-liiy-and-ooimmaliiii awware reinforcement learning (FOARL) method in the second stage, explicitly mitigating constraint violations while promoting better optimization outcomes. By training only lightweight Low-Rank Adaptation (LoRA) modules, our approach enables a 7B 7B-parameter L.M to not only outperform the most advanced reasoning models, such as Deepseek-R1 [22 and OpenAl GPT-ol, but also surpass commonly used heuristics across seven CO problems.
Our contributions are outlined as follows. 1) Unlike recent approaches that rely on intermediate steps such as heuristic guidance solver invocation, we model CO as a language generation task and develop an SFT strategy that fine-tunes LLMs to function as end-to-end solvers. This reduces dependence on comain--specffe knowledge and simplifies the goblemm-slvinng pipeline. 2) Given that the SFT alone leads to over-greedy policies that violate cobblem-specffic constraints, we introduce the FOARL algorithm, which refines the LLM policy using reinforcement learning (RL) to improve solution quality. 3) We evaluate the effectiveness of our method on seven different problems without manual architectural customization for the policy model, making a significant step towards creating a unified solver for CO based on language generation. Experimental results show that our fine-tuned 7B- 1B-parameter LLM can outperform various larger LLMSs and problem-speciffe algorithms.
2 Related Work
Combinatorial Optimization. CO problems represent an important branch of optimization prob- lems that aims to find the optimal solution from a finite set of candidates. Due to the NP-hard nature, exact solutions to CO are often computationally intractable, prompting the development of approximation and heuristic algorithms [3]. Given varying characteristics (c.g., objectives and constraints) of different CO problems, heuristic designs are typically -specefipecc such as the insertion algorithm for the TSP 24 and the savings algorithm for the vehicle routing problem (VRP) (25). However, the design of these algorithms is typically a labor-intensive process that requires deep domain expertise 226. Thus, there has been growing interest in automating the heuristic de- sign process to reduce dependence on domain-specific knowledge. Recent advances have explored leveraging neural networks for CO, known as neural combinatorial optimization (NCO), which has shown promising performance various problems [27-31]. In contrast, LLMs offer a more
2

---

user-friendly, natural language- taguage-bbsed approach to interactive problem-solving, benefiting from the extensive knowledge learned during pre-training thus opening up new opportunities for CO [4]
LLMs for Optimization. LLMs can function as either program generatons or end-to-end optimizers for CO. Recent advances demonstrate that LLMs are capable of generating Python programs to iteratively discover heuristics or refine metahcuristics through evolutionary operations [6 I0 [2], In addition, the LLM-based mooel--henn-solve methods produce executable code that interfaces with CO solvers, such as Gurobi and OR- TooTools, to solve problems described in natural language [S] 12 33 However, these approaches typically depend complex prompt engineering and require users to be proficient in running and debugging the generated code. In contrast, treating LLMs as end-to-end optimization solvers offers a more automated and user-friendly alternative, which aims directly map language-bass based inputs to solutions by: 1) zero-shot or few-shot generation [88 20 2) iterative refinement of initial solutions [19 34] 3) step-by-step solution construction 35 Nonetheless,
these methods are generally limited to small-scale CO problems (e.g. TSP with fewer than 30 nodes)
and suffer from significant performance degradation as problem size increases [9 Moreover, their target CO problems often lack complex constraints, such as the capacity constraint in VRP, which LLMs can easily violate due hallucination. These limitations highlight the challenges in scaling end-to-end LLM solvers to more realistic and constrained optimization settings.
LLMs for Mathematical Reasoning. More generally, mathematical problems (e.g., those in algebra and optimization tasks) are essential benchmarks for evaluating LLMS' reasoning capabilities
36
LLMs have been evaluated on math-related tasks, ranging from middle school-level arithmetic
37..
Olympiad-level problems 38 and mathematical proof' [39] to combinatorial and graph
optimization challenges 20
35
40 Recent advances in LLM-based mathematical reasoning have
been driven by structured prompting techniques, such as chain of thought (CoT)) [4T, tree of thought
42], and graph of thought [43]. These methods emphasize stepwise reasoning, in which natural language and logical operations are intertwined to explicitly generate interpretable chains of thought [1]. However, step-by-step reasoning becomes impractical for CO problems, particularly large-scall ones. Due to their NP-hard nature, maintaining feasible and high-quality solutions throughout a long reasoning trajectory is extremely challenging, resulting in substantial complexity and inefficiency when scaling to larger instances. In this paper, we propose an alternative paradigm that enables L.MSs to directly learn end-to-end solution generation by imitating domain-specifie solvers. Additionally, we incorporate heuristic information into the prompt to facilitate latent solution-space exploration, allowing LLMs generate effective solutions without relying on explicit and verbose reasoning.
3 Problem Statement
We investigate how to apply LLMs to solve CO problems without relying on traditional algorithm design. Let P represent a specific CO problem (e.g.. the TSP), with each instance p E P defined as a tuple (Xp, p. fp. Cp), where Xp is the set of all possible solutions (i.e., solution space); fp X, - IR denotes the objective function be minimized (or maximized); C, = (Cp.1.Cp.2.-.. Cp.2..... Cp.m, } is set of constraints, and each Cp.s : Xp - {0. 1) indicates whether a solution satisfies the corresponding constraint or not. A feasible solution to a CO problem must satisfy all the involved constraints. For a given instance p. the goal is to find solution 2;. E Xp such that 1) 2 satisfies all constraints in Cp.
i.e. Vep. E Cp.. (x)) = 1, 2) for minimization problems, fp(xt) S fp(()) holds for all x E Xc,, where Xc, {x E Xpp VVp. E Cp. (x.(xr)) 1} the set of all feasible solutions.
Te T T be an LLM, where T is the space of text sequences. We define two mapping functions: 6: P + T, which maps CO problem instance to its textual description, and tip T + Xp. which maps text to a solution in the original solution space for (In practice, 1pp can be implemented using regular expressions or other parsing methods to extract solutions from the generated text). The end-to-end solution for a natural language-describe CO problem is formulated as:
4p (T)((()))))
where â is the LLM-ggnnrated solution to problem instance p. We evaluate the effectiveness of the end-to-end solution generation on a set of instances P. using the average optimality gap 1 (,(āp)-fala) and feasibility rate MP.).) = (epEP.//e...CC............. [5,())]
Mo.P.) = P.. Epep,
PP.
3

---

1. Data Generation
2. Supervised Fine-tuning
Reinforcement Learning
CO instances
Solution sampling
Domain- specifie solvers
Lurge Language Model (LLM)
LoRA adapters
Problem- Specific reward fx
Roste: [6, 10, 1, 7,
Roste: [0,
LoRA adapters
Roure: (0) 2, 10, 1,4,3,
Group relative policy optimization
Problem- solution pairs
Text-altribuied instance
Inference
Route 1, cos--108
Onesteering given leities... "output": Rouse: 60,6, 4,4, 71, Objective: 120.
"Instraction"
Rouse cost-75
Best-of-N strategy
J
I2
Route N. cost 122
Figure The framework of the proposed method.
In this paper, we consider CO problems, including TSP, orienteering problem (OP), capacitated VRP (CVRP), maximal independent set (MIS), minimum vertex cover (MVC), permutation flow shop scheduling problem (PFSP), and job-shop scheduling problem (JSSP). Notably, unlike traditional algorithm designs, which typically require customization in problem-specific heuristics or neural network architectures [44], our approach is generalizable and capable of solving other arbitrary (natural language-descring described) CO problems without extensive manual crafting or customization.
4
Methodology
4.1
Data Generation
The framework of the proposed method is illustrated Figure 1 LLMs need to learn solution generation patterns from problem solutions, the first step generating high-quality data, i.c., problem-solution pairs. To this end, the solutions to different CO problems are produced by special- ized solvers, e.g., the Lin- Lin-Kernighan-Heleeee iterated greedy (QIG) method [46] for Since it is intractable unify the heterogeneous solving processes of these solvers by learning their byzantine internal logic, we use the solvers to generate mear))optmmal solutions and train the LLM to directly learn from the solution representations, bypassing the need to replicate solver internals.
(LKH) solver 45 for TSP and the Q-learning-bane incorporating distinct internal programmatic logic.
We generate numerical instances and solve them using domain-specific CO solvers. Each numerical instance is then transformed into natural language by mapping function Φ, which is adapted from the text-attributed instance (TAI) framework in [14]. TAI consists of two components: (I) Instruction: problem description that outlines the optimization objective and relevant constraints, and (2) Input: instance-specific details that describe the attributes of individual nodes, for example, the city coordinates in TSP instance. The outputs generated by the solvers, which taken the labels for SFT, are also converted into natural language by listing the solution and its corresponding objective. For example, the textual solution for TSP instance is formatted as: "Routes: [0, 3, 4, 1, 2, 6, 0), Objective: 5797.33". Instead of explicitly specifying the solution exploration through COT, facilitate latent solution-space exploration by providing the general heuristic features in the input prompt, which biases the model toward more promising regions of CO problems. Taking TSP example, this includes the top-k (k 2) neighbors for each node along with their respective distances. During training, the LLMs can learn to explore the latent space through informative and low-cost guidance of the heuristic features. Specifically, the problem definition, instance generation, utilized solver, and the example of TAI for the studied problems are provided in Appendix
4.2 Supervised Fine-tuning
In most NLP domains, fine-tuning LLMs relies on annottted data detailed CoT reasoning trajectories, which are often costly and difficult to obtain [47. Our SFT process for CO benefits from more convenient data generation pipeline by leveraging existing specialized solvers. In this regard, we collect the datasets of problem-solutee pairs without much manual effort, while enabling L.MSs to effectively learn high-quality solution generation. We adopt the instruction tuning paradigm, which

---

24%
Mean: 2.80%
38%
Mean: 5.15%
Mean: 2.64 edges
Progurtin
25%
17%
2%
13%
0%
0%
0%
10
2
Distance Limir Violation OP (%)
Capacity Violation CVRP (%)
Number of Violating Edges MIS
Figure 2: The extent of constraint violation of the SFT policy for different problems.
to equip LLMs with the ability to follow problem instructions and generate natural language descriptions of solutions provided by solvers.
has proven effective in the optimization domain 13 48
Specifically, we formulate CO as a next-token prediction task, treating it as a language generation problem where the L.M learns map textual problem descriptions to textual solution representations. For each CO problem instance p. we input the prompt o(p) (i.e., the TAI described in Section 4.1). The target output is the natural language description of the solution 15p (rr)), where sy is the high- quality solution generated by solver. Let be the trainable parameters of the LLM policy, and we minimize the standard language modelling loss during training:
11
LSFT
Σ
log Pro (v:l)())))
where y is the i-th token in the textual solution, and ycs denotes all previous tokens of the solution.
Our training data encompasses range of problem sizes and distribution settings, promoting general- ization across diverse CO problem instances. To ensure computational efficiency while preserving model performance, employ LoRA [49]. which introduces trainable matrices into the LLM while keeping most of the pre-trained weights frozen. The details of LoRA are provided in Appendix B
However, SFT alone sometimes leads to over-greedy behavior, where the LLM learns toward marginally violating specific constraints in pursuit improved objective values. We collect infeasible solutions resulting from constraint violations across 300 instances of OP, CVRP, and MIS, which are representative CO problems to illustrate this issue. As shown in Figure LLM-generated infeasible solutions and optimal ones reveals that most violations stem from slight oversteps of constraints, for example, traveling marginally farther in OP or serving slightly more customer demand in CVRP. These constraint violations a primary cause of solution infeasibility in practice. This limitation motivates our subsequent reinforcement learning approach in Section 4.3.
comparison between
4.3 Feesibbitt-add--piimall-----
Reinforcement Learning
Since LLMs trained via SFT primarily learn to generate natural language descriptions of solutions without explicit information about problem constraints, they often lack a comprehensive under- standing of solution fcasibility. Thus, the outputs may be infeasible suboptimal, particularly in constrained CO tasks. To address this issue, we propose the FOARL algorithm to mitigate the greedy bias introduced by SFT. It enhances the LLM's reliability as the end-to-end CO solver by fostering feasibility awareness and correcting infeasible behaviors through the exploratory "trial-and-emns nature of RL. More precisely, the state of the RL corresponds to @(p) for each instance while the action is the token predictions during generation. We define a feasibility-awee
reward R? based on the constraint set Cp {Cp.1. Cp.y, Cp.2..... Cp.m,, }, encouraging the model to recognize and satisfy all mp problem-specifi constraints. To ensure that the model also maintains optimality, we introduce an optimality-aware reward R.¹. These rewards are jointly used balance feasibility and optimality.
Specifically, we define the feasibility-awan reward function for any LLM-generated solution á, as:
Swos + Em (xpp)((p))
#C if
R.P (8p))
Ap P
5

---

where Ç is binary variable that indicates if the generated text follows the output format in TAI; Wo: .... Wmp are weighting parameters, which assign different levels of importance the constraints. In addition, the optimality-awan reward function is defined as:
I a 1I-Mo Mo 0
if c VPEP if f =(<=0%
Re (+p)
(4)
where is a parameter that controls the relative importance between optimality and feasibility. We use the linear combination of R. and R. as the reward for reinforcement learning: R = R2 RR. The training process of FOARL is built upon group relative policy optimization (GRPO), which addresses inefficiencies of actor-critic methods [22]. Unlike the approaches that require separate critic model, which often has a comparable size to the policy model, GRPO estimates the baseline directly from group-level rewards, significantly reducing the computational overhead while maintaining stable learning dynamics. More preciscly, given a TAI o(p), the algorithm samples solutions X, (.p,1, 2p.2,.... Ep.s) using the old LLM policy model To,old. and update the current model To (i.e., update the LoRA modules of the LLM) by maximizing the following objective function:
LFOARI (0) -E -BM ((o))
d(p))
1
min (r!allo A, clip (r.atio, 1 e, +)) A.) (Tol(TollTTT))) (5)
S
where DP is the training dataset for conducting reinforcement learning; r. To =o(2))1000)
Te me ((p)
measures how much the current policy differs from the old policy; and / are hyperparameters: DRL (x (er)) is the Kullback-Leibles (KI.) divergence between the current policy and the reference
policy; A; R.. mean( denotes the advantage of solution Sp.i computed using group of sud(R
rewards RIP
'grup (R] R....., R2J corresponding to the sampled solutions within each group.
4.4 Best-of-N Inference
While SFT and FOARL provide LLMs with the capability to learn solution generation patterns, the autoregressive nature of these models inherently limits their ability to maintain globally optimal solutions throughout the generation process. Unlike traditional CO solvers that can explore multiple branches backtrack upon reaching dead ends (50,52), autoregressive models commit to each decision and cannot easily revise earlier choices and evaluate constraint satisfaction, leading to suboptimal outcomes. To address this limitation, we employ Best-of-N (BoN) sampling during inference for test-time solution exploration. BoN sampling involves generating N distinct solution candidates from the fine-tuned LLM and selecting the highest-qualins feasible solution. Formally, given an instance we generate N candidate solutions (.p,1, $p.2, Fp,N) } and select:
f = arg min ipp E xo,, E [1,2,...,NJ]
(6)
Experiments
We fine-tune Qwen2.5-7B 53 to our dedicated and-to-end CO solvers. For SFT, generate 500,000 instances per CO problem, and an additional set with at most 3,200 instances is used for FOARL. To improve training efficiency, we adopt the Unsloth framework [54) and apply LoRA for parameter-efficient fine-tuning. During inference, we set the temperature of the LLM to 0 for a single generation and use top-p sampling (p- = 0.7) for BoN inference (N 8 solutions are generated by default). The optimality gaps are calculated using the domain-specific solvers of each problem, which are specified in Appendix The detailed experiment settings are provided in Appendix C
5.1 Baselines
General-purpose LLMss We first compare our method with general-purpose L.MSs, including both closed-source and open-source models, all of which have significantly more parameters than our

---

Table Evaluation of feasibility (fea.), optimality (opt.), and average time (Avg. Time) for different methods on the 7 studied CO problems. The best results are in bold.
Method
TSP
OF
CVRP
MIS
MVC
PESP
JSSP
Avg. Time
Ven.
opt.
Ten.
fca.
fea.
fea.
Foa.
opt.
Rra.
ope.
Gemeral-purpowe
Models
GPT-fo
39%
33.79% 2.15
218.7
76.62%aaT.
11.70
16.67%a7u
88%
20.57% 2n.
97.85% 233.
GPI-4ommiil
28%
53.38%
70.0016 ase.3
us0.1
0.00%
29.5218
7996
21.471
Clade-Somett
66%
20. 49%
34.62%
213.
12.5198
6.25%
1005%
18.42%
90.009--22..
5.4.
Claude Haika
45%
38.60% and 26%
51.26% 4:4.3
1%
61.48% e12.1
2%
23.33% a6.
6%
13.01% u93.3
73%
20.58% 4744
9%
95.51%
5.1s
DoepSrek-V3 V3
73%
25.
50%
46.10% 214.4
21%
28:229
5%
12.09%
15%
37.15%
224
58%
20.818 2*44
52%
103.
103.199 a.
26.46
Llama3.5-208
50%
69
69.0896a31.4
27%
48.98%
31%
97.331%
85
57.1156
20%
22,8695
213.6
98%
21.97%
2996
105.0118
a24.5
2.15
Quen2.5-726 20%
26.8
52%
49,
208.6
61%
180.91%
14%
20.50 21.
556
63.209
988
21.15
5398
163.90%
12.5%
Reasoning Models
GPT-o3 mini
91%
1395 2.3.7
9,23
2.98
98%
16.97% axu
77.86% 77.86% g3m.
GPT-o1
54%
27669-224
51%
20.901
1548
82%
8,09
3.58%
8958
1486%
81. 81.905
DeepSickk R1 48%
70399%
00%
40.5498
2:3.7
20%
30.40%
215.1
41%
1.00
38%
4.37%
100%
16.6596
5%%
26 ua.
6.5m
Prompi Stralogies
DPRO
59%
R5%
31.99ai1 21%
7%
5958
IPS
41.699
U9P
18.2
65%
2.
LMEA
77%
2658-111
45%
66.18%
24%
61.21
5%
25.0%
13%
34,229
98%
14.31% a7.
46%
83. 19.199-222.0
38. g4. 5.3m
PHP
84%
33 23.44
43%
36,0886
58.11%
11,6792
92%
17.2546
104.04%6 220.
98%
20
24.3
23.4
1..44%
3.62%
3.8392g74
4,48%
Ours
SET
89%
2.30% 54%
2.32
59%
6.02%% o
80%
L.71%
98%
2.41%
100%
2.22% 2/4
100%
11.01% a
5.0s
SPT-RL
91%
2,32% 222
92%
4.25
50%
8.27
83%
L.345aas
98%
2 2.39%
100%
2.12%
100%
10,949%677
5.6s
SPT+RLABBN 100%
1.07%ano
100%
1.85%
100%
4.53%
94%
1.04% a3.
100%
1.29%
100%
1.03%
100%
9.20%
9.8
fine-tuned model. The used models include OpenAl GPT-4o, GPT-4o-mini, Anthropic Claude-3.7- Sonnet-20250219, Baude-3.5-Haiki DeepSeck- V3-671B, LLaMA-3.3-708 and Qwen2.5-72B.
Reasoning LLMs. With the rapid development of reasoning models, many previously challenging mathematical tasks have become tractable. Therefore, we also include state-of-the-ar art reasoning models for comparison, such as OpenAl GPT-o3-mini, GPT-ol, and DeepSeek-RI.
Prompt Strategies. We consider representative LLM--bseed optimization methods for comparison. These include Optimization by PROmpting (OPRO) [9), which steers solution generation using ver- bal gradients; LMEA (LLM-driven Evolutionary Algorithm) 34, which treats LLMs as evolutionary optimizers by selecting parent solutions from the current population and applying crossover and mutation to produce offspring; and progressive-hint prompting (PHP) [55), which scales test-time performance by incorporating previous outputs as hints to guide subsequent reasoning. We also evaluate the methods that leverage LLMs for program generation, such as self self-guiding exploration (SGE) (56). All prompt-basee baselines are implemented using DeepSeck- V3-671B IB for consistency.
Domain-specific methods. We employ OR-Tools CVRP. We also use ant colony optimization (ACO) routing problems. Some heuristics are also introduced, such as the nearest neighbor (NN) and farthest insertion (FI) for TSP, the greedy method, greedy insertion, and Tsili algorithm (59 for OP, the sweeping and parallel savings (PS) algorithm for CVRP, the greedy minimum degree (Greedy) and dagree-based add (Degree) heuristic for MIS, the Approx method [60]. greedy maximum degree (Greedy) and degree-based removal (Degree) heuristic for MVC, the Plamer's [6] and Nawaz, Enscore, and Ham (NEH) heuristic [62] for PFSP, and commonly used dispatching rules for JSSP, such shortest processing time (SPT), first in first out (FIFO), and apparent tardiness cost (ATC).
5 heuristic solver that solve TSP and
58 serving as the metaheuristic to solve the
More details of the baselines are elaborated in Appendix D. Our code and data are publicly available at ftthtps::// //githb.. com Soumee/ 142851 Btt.:5G//LMMMMMooloo
5.2 Main Results
First, we compare our method against a wide range of advanced LLMs and LLM-based optimization baselines, with the results summarized in Table while the solving times of each problem are provided in Appendix E It is observed that general-purpose LLMs generally fail to produce feasible solutions for most CO tasks. An exception is the PFSP task, where models only need to generate a permutation of a few job indices, which is relatively simpler compared to other problems.
Although some general-purposs LLMs and advanced reasoning models can occasionally generate feasible solutions for certain tasks (e.g., GPT-o3-mini for TSP and Claude-3.7-Some for PFSP), they exhibit substantial gaps in solution optimality. Moreover, the inference time of reasoning models is
7

---

Table Performance comparison on CO problems with different scales of graphs.
Small graphs
Medium graphs
Large graphs
Method
Gap
Gap@1 Gap@s 5 Gap @ 10
Gap
Cap@1 Cap@5 Gap @ 10
Gap
Gap Gap@5 @ap@ 10
OR-Tools
0.82%
76%
96%
99%
2.59%
28%
86%
99%
3.59%
12%
80%
99%
NN
19.36%
3%
5%
19%
24.13%
0%%
0%
1%
19%
01%
0%
2%
FI
2.27%
51%
82%
96%
4.41%
8%
64%
95%
4.86%
2%
53%
99%
ACO
1.98%
48%
88%
100%
17.98%
0%
1%
6%
36.69%
0%
Ours
0.14%
96%
100%
100%
0.70%
74%
100%
100%
1.34%
44%
100%
100%
Greedy
16.06%
4%
8%
25%
18.91%
0%
0%
5%
20.30%
0%
0%
3%
GI
9.07%
20%
37%
63%
11.91%
0%
12%
51%
13.63%
0%%
7%
32%
$ Tsili
3.85%
21%
68%
96%
9.54%
0%
2%
55%
13.80%
0%
0%
8%
ACO
3.49%
30%
76%
94%
6.24%
1%
35%
89%
7.95%
0%
15%
74%
Ours
1.47%
54%
95%
99%
2.04%
26%
96%
100%
2.10%
27%
96%
99%
OR-
3.60%
45%
69%
93%
7.87%
3%
24%
72%
8.84%
15%
71%
Sweep
18.36%
8%
18%
32%
20.59%
0%
1%
8%
22.07%
0%%
0%
3%
CVRP
PS
3.95%
24%
72%
93%
5.67%
2%
50%
89%
6.12%
0%
41 %
89%
ACO
2.52%
44%
81%
96%
17.07%
0%
2%
14%
49%
Ours
1.70%
52%
90%
97%
4.57%
8%
59%
98%
7.24%
1%
19%
84%
Degree
5.89%
57%
57%
67%
7.52%
32%
42%
64%
9.61%
20%
33%
59%
485
Greedy
2.56%
84%
84%
86%
2.79%
67%
71%
90%
3.36%
53%
60%
83%
Ours
0.38%
97%
98%
98%
L.05%
86%
87%
94%
2.29%
47%
57%
65%
Approx
49.79%
0%
0%
0%%
39.21%
0%
0%
0%
35,35%
0%
0%
0%
Greedy
2.80%
71%
72%
89%
2.62%
44%
79%
99%
2.21%
33%
89%
100%
Degree
3.53%
63%
63%
86%
2.78%
44%
78%
98%
2.63%
26%
83%
99%
Ours
0.48%
93%
93%
100%
1.25%
66%
94%
100%
2.35%
38%
87%
100%
Palmer's
30.52%
0%%
0%
1%
30.41%
(%%
0%%
0%
30.68%
(%%
0%
0%
ASS R8
NEH
1.33%
53%
97%
99%
2.78%
11%
90%
100%
3.56%
88%
100%
Ours
0.25%
85%
100%
100%
1.16%
40%
100%
100%
2.62%
6%
99%
100%
SPT
19.58%
2%
4%
17%
25.32%
0%
0%
1%
27.35%
0%
0%
0%
FIFO
24.38%
2%
4%
12%
32.97%
0%
0%
1%
39.00%
0%
0%
0%
ATC
20.71%
0%
12%
15%
24.30%
0%
0%
1%
27.99%
0%
0%
0%
Ours
2.86%
32%
79%
98%
9.56%
0%
8%
60%
16.25%
0%
0%
4%
significantly longer, as they attempt to solve CO problems through extended step-by-step thinking. While such approaches may work for very small-scale instances (e.g., fewer than 10 nodes), becomes impractical to reason clearly and effectively instance size grows. For example, we present the COT of DeepSeek-RI for TSP instance in Appendix E.2 where we find that the CoT is lengthy and ineffective. This causes the LLM to get stuck multiple times and cannot find good solution.
Although iterative prompting strategies (e.g., OPRO and PHP) can moderately improve performance. they still struggle to produce competitive results and remain far from practical deployment. Leveraging LLMs to generate code for (hera)heuristic algorithms, as done in SGE, enables feasible solutions for most instances. However, their solution quality remains limited, mainly because the generated algorithms are highly sensitive to hyperparameter tuning a process that requires significant human expertise and cannot be reliably automated by LLMs alone. Meanwhile, these prompting strategies rely on iterative reasoning or code execution, leading to long solving time compared to our method,
In contrast, our proposed SFT approach enables the LLM to generate mostly feasible solutions with relatively small optimality gap. By further combining SFT with FOARL and BoN inference. our method achieves a 100% feasibility rate across the test sets of TSP, OP, CVRP, MVC, PFSP, and JSSP. Both feasibility and optimality performance significantly surpass all other baselines, including those based on much larger models than our fine-tuned 7B model. A Additionally, as shown in Appendix E.3 our models also outperform a recent language-bar based CO solver proposed in 14, which integrates the LLMs with an NCO model, across most of the evaluated tasks, demonstrating its effectiveness.
We also compare against the LLM-based model-then-solve approaches. As demonstrated in Appendix E.4 our method can outperform these approaches, particularly when dealing with large instances.
5.3
Comparison with Domain-specific Methods
variety of domain specifccc algorithms have been developed for individual CO problems, typically based on (meta) heuristic strategies, and often characterized by distinct algorithmic structures. We compare our LLLM-based approach (i.e., the model trained by SFT+RL and with a BoN sampling) to these methods, with results summarized in Table 2 The evaluation is conducted across multiple prob- lem scales, with 100 instances used for each. Specifically, small, medium, and large graph instances defined follows: for scheduling problems, 5x5-10x100 10, 10x10-1xx1., and 15x15-20x22 20x200;
8

---

for other problems, 10-30, 40-60, and 70-100 nodes, respectively. We also introduce Gap@K, ea the percentage of instances solved with optimality gap below K%. As shown the table, our model can outperform the simple domain-specifi algorithms, especially on smaller graphs, indicating its strong potential for solving CO problems described by language.
Meanwhile, we also provide the comparative results between our method and the state-of- of-the-art heuristic solvers and classical exact solvers (i.e., Gurobi), which are provided in Appendix E.5 is shown that our method can achieve better performance on routing tasks than Gurobi under the same solving time budget. We also discuss the advantages of our method (i.e., ease of use, language-driven interaction, and generalizability) compared to these classical solvers in Appendix E.5
Moreover, it is possible to further enhance the performance of the LLM solver through scaling test-time exploration, we increase N for BoN sampling and report the results in Appendix [F.6] where find that the instances with large graphs be better solved with higher N. We also examine the impact of heuristic features in the TAI through an ablation study, as presented in Appendix E.7
5.4
Role of Reinforcement Learning
100
OP-SFT
500
DI-L CORP-SPY
Consriiit Magan
FOART.
250
CVRPRovan CP
SFT
Vallio (%)
60
-50
SFT
01
Gapail
Gapi8
Oapic10
(Avg:31.7)
SFT
(1.7)
OP
RL.
194.7) (Arg: 7.5)
SFT
CVRP
RL. (Avg: 8.3)
(Sample Size)
5
(a)
(b)
(c)
Figure 3: The role of FOARL. (a) RL does not necessarily cause performance drop in Gap@ K; (b)
Distribution of constraint margins before and after applying FOARL. Positive values indicate feasible solutions, while negative values reflect infeasibility due violations of inequality constraints; (c)
The reward comparison between policies with different N for BoN sampling.
According Table FOARL significantly improves feasibility in tasks such OP and CVRP, while incurring minor losses in optimality. This is primarily because FOARL enables the LLM to generate feasible solutions for more instances, rather than degrading the quality of solutions on previously solved ones. As illustrated in Figure (a). The Gap@ K metric does not exhibit a noteworthy decrease after applying RL. Furthermore, we observe slight improvements in optimality for tasks where the SFT model already exhibits high feasibility. To better understand the contribution of RL, we analyze its dual role using two representative tasks (i.e., OP and CVRP) as case studies, as detailed below.
Constraint relaxation operator. FOARL helps enforce fcasibility by mitigating violations of inequality constraints, which are common problems like OP and CVRP. We define the constraint margin as: I) the difference between actual travel distance and the distance limit in OP, 2) the difference between served demand and vehicle capacity in CVRP, and visualize them for solutions generated by both SFT and RL in Figure 3 (b). The increase in constraint margins of RL-trained policies indicates improved feasibility and correction of the over-greedy behavior introduced by SFT.
Sampling efficiency improver. More generally, the RL process improves sampling efficiency dur- ing inference. While is possible enhance the SFT policy through increased test-time exploration, such as scaling BoN sampling, RL allows for achieving better performance with fewer samples, thereby improving efficiency and reducing test-time computational cost. Specifically, we vary the scale of BoN sampling for both SFT policy and RL policy, evaluating them on instances with the large graphs. The change of reward R.P (defined by Equation 4), which can indicate both feasibility (e.g., R = 0 if solution is infeasible) and optimality, is illustrated in Figure 3 (c). We observe that models trained with RL require smaller N to reach comparable performance levels as their SFT-only counterparts with larger N. This also aligns with the conclusion of recent work [63]. Since computational efficiency is critical some real-time or resource-constranne decision-making scenarios, incorporating RL to improve inference efficiency is valuable and practical enhancement.

---

Table 3: Comparison study across TA instances. *: Results are drawn from the original literature.
TA 15x15
TA 20x15
TA 20x20
obj-
opt.
obj- opt.
obj-v opt.
Best-known solution
1228.9
1364.9
1617.3
SPT
1546.1
25.81%
1813.5
32.87%
2067.2
27.81%
FIFO
1657.4
34.87%
2008.4
47.15%
2297.1
42.03%
ATC
1586.8
29.12%
1794.3
31.46%
2114.1
30.72%
GA 100x100
1583.8
28.88%
1847.1
35.23%
2304.2
42.47%
L2D greedy
1522.3
23.88%
1813.4
32.86%
2130.2
31.21%
L2D sample
1543.8
25.62%
1779.7
30.39%
2134.2
31.96%
StarJob"
19.68%
26.91%
33.12%
Ours (N 8)
1403.6
14.22%
1653.7
21.16%
1994.2
23.30%
Ours (N = 64)
1368.2
11.34%
1600.5
17.26%
1940.9
20.01%
5.5 Unified CO solver
Recent research progress in neural network-bass solvers is being made towards the establishment of unified model, which can solve various CO problems. The existing unified models usually use task-specific encoders and decoders [4] or problem reduction [64], limiting their extensibility. By comparison, our method provides a more general approach using natural language as the interface. We fine-tune the LLM by learning to solve the seven CO problems together, and present the results in Appendix E.8 where we observe that a single LLM solver can also solve various CO problems.
5.6
Versatility and Generalizability
To show the versatility of our method, we additionally evaluate it using different LLMs (i.e., Llama- 3.B-8B and Gemma-2-99), as detailed in Appendix [E.9] We evaluate the performance of the trained LLMs for routing problems, as presented in Appendix EE There, demonstrate that the LLM solvers can also generalize to instances with OOD distributions.
(OOD)
5.7 Benchmarking Performance
To further demonstrate the generalizability, we evaluate the fine-tuned JSSP solver on Taillard (TA) benchmark (65). We test the instances with 15 jobs and 15 machines (15 15), 20 jobs and 15 machines (20 x 15). and 20 jobs and 20 machines (20 x 20). In addition to the dispatching rules, such as SPT, FIFO, and ATC, we also compare with the genetic algorithm (GA) (with a population size of 100 and 100 generations) [66]. the L2D method [67]. and StarJob (88) which solves JSSP using an LLM fine-tuned through SFT. The results are compared in Table When all solutions are feasible, our model (SFT+RL) outperforms all heuristic and learning based baselines, with performance further improved by increasing N 64 to enhance test-time exploration. Meanwhile, we also compare our method with other JLM-based methods on TSPLib, and the result is presented in Appendix E.TT
6 Conclusion
The paper investigates how LLMs be fine-tuned to end-to-end CO solvers, filling the gap in the literature on this topic. Taking CO problem solving as a language generation task, we propose two-stage fine-tuning framework, incorporating both SFT and FOARL, enable the LLMs to solve CO problems in an end-to-end manner. The tuned LLM solver achieves the average optimality gaps of 103-8.20% for different problems. Following the traditional heuristic solvers and NCO solvers, our method, mediated by language, promises to be new paradigm for CO, which provides more general end-to-end approach and reduces human expertise reliance. One major limitation of our approach, shared by most LLM-based methods, is that its solving efficiency is not yet par with traditional lightweight heuristies. Future directions include: 1) introducing efficient fine-tuning and inference strategies to solve larger-scale CO problems; 2) exploring more efficient and effective textual input representation, i.e., TAIs, to enhance learning performance; 3) integrating the L.M solver with heuristics to further address infeasibility and improve optimality.
10

---

Acknowledgments and Disclosure of Funding
This research supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG3-RP-2022-033 This work has also made use of resources and expertise provided by SURF Experimental Technologies Platform, which is part of the SURF cooperative in the Netherlands (No.EINF-13168),
References
[1] Nate Gruver, Marc Finzi, Shikai Qiu, and Andrew G Wilson. Large language models are zero- shot time series forecasters. In Thirty-sevntth Conference Neural Information Processing Systems, volume 36, pages 19622-19635, 2023.
[2] Yong Liu, Guo Qin, Xiangdong Huang, Jianmin Wang, and Mingsheng Long. Autotimes: Autoregressive time series forecasters via large language models. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, volume 37, pages 122154-122184, 2024.
[3] Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Eric J Topol. and Pranav Rajpurkar. Foundation models for generalist medical artificial intelligence. Nature, 616(7956):259 265, 2023.
[4] Xiaohong Liu, Hao Liu, Guoxing Yang, Zeyu Jiang. Shuguang Cui, Zhaoze Zhang, Huan Wang. Liyuan Tao, Yongchang Sun, Zhu Song, et al. A generalist medical language model for disease diagnosis assistance. Nature Medicine, pages 1-11, 2025.
[5] Ziyang Xiao, Dongxiang Zhang, Yangjun Wu, Lilin Xu, Yuan Jessica Wang. Xiongwei Han, Xiaojin Fu, Tao Zhong, Jia Zeng, Mingli Song, and Gang Chen. Chain-of-experts: When LLMs meet complex operations research problems. In The Twelfth International Conference Learning Representations, 2024.
[6] Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristics with reflective evolution. In The eighth- Annual Conference on Neural Information Processing Systems, 2024.
[7] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L. Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 125 2013.
[8] Ege Duran, Cemalettin Ozturk, and M Arslan Omeck. Combinatorial optimization methods for yarn dycing planning. Flexible Services and Manufacturing Journal, pages 1-38, 2024.
[9] Shuwan Zhu, Wenjuan Fan, Shanlin Yang, Jun Pei, and Panos Pardalos. Operating room planning and surgical case scheduling: review of literature. Journal of Combinatorial Optimization, 37:757-800 111577805,,1111
[10] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: towards efficient automatic algorithm design using large language model. In Proceedings of the 41 International Conference on Machine Learning, 2024.
[11] Pham Vu Tuan Dat, Long Doan, and Huynh Thi Thanh Binh. Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using 1lms. The 39th Annual AAAI Conference on Artificial Intelligence, 2025.
[12) Xia Jiang, Yaoxin Wu, Chenhao Zhang, and Yingqian Zhang. DRoC: Flevating large language models for complex vehicle routing via decomposed retrieval of constraints. In The Thirteenth International Conference Learning Representations, 2025.
[13] Caigao Jiang, Xiang Shu, Hong Qian, Xingyu Lu, Jun Zhou, Aimin Zhou, and Yang Yu. ILMOPT: Learning to define and solve general optimization problems from scratch. In The Thirteenth International Conference Learning Representations, 2025.
11

---

[14] Xia Jiang, Yaoxin Wu, Yuan Wang, and Yingqian Zhang, Bridging large language models and optimization: A unified framework for text-attributed combinatorial optimization. arXiv preprint arXiv:2408. 12214, 2024.
[15] Eldar Kurtic, Amir Moeini, and Dan Alistarh. Mathador-Im: A dynamic benchmark for mathematical reasoning on large language models. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 17020-17027, 2024.
[16] Janice Ahn, Rishu Verma, Renze Lou, Liu, Rui Zhang, and Wenpeng Yin. Large language models for mathematical reasoning: Progresses and challenges. arXiv preprint arXiv:2402.00157, 2024.
[17] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? Thirty-seventh Conference on Neural Information Processing Systems, 16:30840-30886 2023.
[18] Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, and Yongfeng Zhang. NvHardEval: Dynamic benchmark on reasoning ability of large language models via complexity classes. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages (092-4114, August 2024.
[19] Chengrun Yang, Xuezhi Wang. Yifeng Lu, Hanxiao Liu, Quoc V Le. Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024.
[20] Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and exploring large language models on graph computation. In The Thirteenth International Conference on Learning Representations, 2025.
[21] Alex Duchnowski, Ellie Pavlick, and Alexander Koller. EHOP: A dataset of everyday NP-hard optimization problems. arXiv preprint urXiv:2502.13776, 2025.
[22] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprini urXiv:2501.12945 2025.
[23] Giorgio Ausiello, M. Protasi, A. Marcheti--ppaccamela. G. Gambosi, P. Crescenzi, and V. Kann. Complexity and Approximation: Combinatorial Optimization Problems and Their Approxima- bility Properties. Springer-Verkle Berlin, Heidelberg, 1st edition, 1999. ISBN 3540654313.
[24] Daniel J Rosenkrantz, Richard E Stearns, and Philip M Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563- 581, 1977.
[25] Kemal Altinkemer and Bezalel Gavish. Parallel savings based heuristics for the delivery problem. Operations research, 39(3):456 469, 1991.
[26] Fei Liu, Rui Zhang, Zhuoliang Xie, Rui Sun, Kai Li, Xi Lin, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Llm4ad: A platform for algorithm design with large language model. arXiv preprint 24X.::2412.12288 2024.
[27] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint w:Xiv:661..099/ 2016.
[28] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
[29] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34:513855111 31-51149, 2021.
[30] Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, et al. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2306.171 17100, 2023.
12

---

[31] Chenguang Wang, Zhouliang Yu, Stephen McAleer, Tianshu Yu, and Yaodong Yang. Asp: Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 46 (0):4102-4114, 2024.
[32]
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
[33] Jihai Zhang, Wei Wang, Siyan Guo, Li Wang, Fangquan Lin, Cheng Yang, and Wotao Yin. Solving general natural-language--e -eceeiigdesiiiitionn optimization problems with large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 490, June 2024.
[34] Shengcai Liu, Caishun Chen, Xinghua Qu. Ke Tang, and Yew-Soon Ong. Large language models as cvolutionary optimizers. In 2024 IEEE Congress on Evolutionary Computation, pages 1-8, 2024.
[35] Zixiao Huang, Lifeng Guo, Junjie Sheng. Haosheng Chen, Wenhao Li, Bo Jin, Changhong Lu, and Xiangfeng Wang. Graphthought: Graph combinatorial optimization with thought generation. arXiv preprini arXiv:2502. /607, 2025.
[36] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. In Thirty-fifth Conference on Neural Information Processing Systems, 2021.
[37] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchrr Nakano, et al. Training verifiers to solve math word problems. arXiv preprint 0rXiv:2110.14166 2021.
[38] Kunhao Zheng, Jesse Michael Han, and Stanislas Polu. miniF2F: a cross-system benchmark for formal olympiad-eveel mathematics, In International Conference Learning Representations, 2022.
[39] Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. In Advances in Neural Information Processing Systems, volume 35, pages 4913 4927, 2022.
[40] Shuo Jiang, Min Xie, and Jianxi Luo. Large language models for combinatorial optimization of design structure matrix. arXiv preprint arXiv:2411. 12577 2024.
[41] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
[42] Shunyu Yao, Dian Yu, Jeffrey Zhao Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 18:9190111882 2023.
[43] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazii, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17682-17690, 2024.
[44] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. GOAL: A generalist combinatorial opti- mization agent learner. In The Thirteenth International Conference on Learning Representations, 2025.
[45] Keld Helsgaun. An extension of the in-Keemighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
[46] Maryam Karini-Mamaghan, Mehrdad Mohammadi, Bastien Pasdeloup, and Patrick Meyer. Learning to select operators in meta- meta-heuristics: An integration of q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 304 2023.
13

---

[47]
Jing Zhou, Chenglin Jiang, Wei Shen, Xiao Zhou, and Xiaonan He. Leveraging web-crawled data for high-quality fine-tuning. Findings of the Association for Computational Linguisties: EMNLP 2024, pages 11297-11312, November 2024.
[48] Henrik Abgaryan, Ararat Harutyunyan, and Tristan Cazenave. STARJOB: Dataset for LLM-driven job shop scheduling. 2024. URL http:://ppenrroiev.tttffoooommmp
Z4Ho599u0L
[49] Edward Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
[50] John D. C. Little, Katta G. Murty, Dura W. Sweeney, and Caroline Karel. An algorithm for the traveling salesman problem. Operations Research, 1((6):972-99,, 1963.
[51] llyess Bachiri, Jonathan Gaudreault, Claude-Guy Quimper, and Brahim Chaib-draa. RLBS: An adaptive backtracking strategy based on reinforcement learning for combinatorial optimization. In 2015 IEEE 27th International Conference Tools with Artificial Intelligence, pages 936-942, 2015.
[52] Congsong Zhang, Yong Gao, and James Nastos. A grapp--nerra--eetor----owooee solver framework for graph optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 35(9): 1746-11760, 2024.
[53] An Yang. Baosong Yang. Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan
Li, Dayiheng Liu, Fei Huang, Haoran Wei, et al. Qwen2. 5 technical report. arXiv preprint arXiv:2412. 15115, 2024.
[54] Michael Han Daniel Han and Unsloth team. Unsloth, 2023. URL http::/github..com com/ umslothai/umslotl
[55] Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. Progressive-hint prompt- ing improves reasoning large language models. In for Math Workshop@ ICML 2024.
[56] Zangir Iklassov, Yali Du, Farkhad Akimov, and Martin Takáč. Self-guiding exploration for combinatorial problems. In The eiirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[57] Vincent Furnon and Laurent Perron. Or-tools routing library. 2024. URL https://
Geveloppers.goggle comm/pptiniiaatiioo/oottttgg
[58] Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE Compula- tional Intelligence Magazine, 1(4):28- 2006.
[59] Theodore Tsiligirides. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9):797-809 1984.
[60] Reuven Bar- Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted vertex cover problem. In North-Holland Mathematics Studies, volume 109, pages 27-45. Elsevier, 1985.
[61] Douglas Palmer. Sequencing jobs through multi-stage process in the minimum total time a quick method of obtaining near optimum. Journal of the Operational Research Society, 16(1): 101-107, 1965.
[62] Pawel Jan Kalczynski and Jerzy Kamburowski. On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega, 35(1):53 60, 2007.
[63] Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang. Yang Yue, Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in 1lms beyond the base model? arXiv preprint arXiv:2504.1330 2025.
[64] Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, and Junchi Yan. UniCO: On unified combinatorial optimization via problem reduction to matrix-encoded general TSP. In The Thirteenth International Conference on Learning Representations, 2025.
14

---

[65] Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278-285 1993.
[66] Robbert Reijnen, Kjell van Straaten, Zaharah Bukhsh, and Yinggian Zhang. Job shop scheduling benchmark: Environments and instances for learning and non-learning methods. arXiv preprint arXiv:2308.1273 2023.
[67] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 1621-1632, 2020.
[68] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizzabee neural methods for vehicle routing problems. In International Conference on Machine Learning, 2023.
[69] Gorka Kobeaga, María Merino, and Jose A. Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers Operations Research, 90:42-59, 2018.
[70] Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural-enhancee ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[71] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[72] Chenyu Huang. Zhengyang Tang, Shixi Hu, Ruoqing Jiang, Xin Zheng, Dongdong Ge, Benyou Wang, and Zizhuo Wang. ORLM: A customizable framework in training large models for automated optimization modeling. Operations Research, 2025.
[73] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems, 2021.
[74] Gerhard Reinelt. Tsplib traveling salesman problem library. ORSA Journal on Computing, 344)3376-384, 1991.
[75] Fei Liu, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Algorithm evolution using large language model. arXiv preprint arXiv:2311.15249, 2023.
[76] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang. and Bryan Hooi. Monte carlo tree search for comprehensive exploration in I1m- based automatic heuristic design. In Proceedings of the 42nd International Conference on Machine Learning. 2025.
15

---

Large Language Models as End-to-end Combinatorial Optimization Solvers (Appendices)
A Specification of the Studied Problems
This section provides detailed definitions of the seven combinatorial optimization problems studied in this paper, which also includes their instance generation procedures, textual instance representations (i.e., TAIs), and the FOARL reward settings tailored to each task.
Note that incorporate problem-specifie heuristic features in the TAIs in order to facilitate effective learning while preserving the generality and efficiency of our language-based approach. These heuristic features based on classical greedy principles, and are tailored each CO problem but follow a consistent philosophy: they should be 1) computationally inexpensive, 2) representative of well-known heuristic behavior, and 3) easily expressible in natural language. For example, in routing problems like TSP and CVRP, we include the top-k nearest neighbors for each node along with their distances, inspired by nearest-neighbor heuristics. scheduling problems like PFSP, we select the top-k jobs with the shortest processing times, aligning with the common dispatching rules such as Shortest Processing Time. Importantly, because they can be concisely described in text, they are naturally suited to the language input format required by L.Mss. This contrasts with more complex or learned heuristics, which often require code-level specifications or internal neural representations that are difficult to translate into promptable natural language. By embedding these features into the input, we provide informative, domain-aligned cues that help the LLM better solve different CO problems.
A.1 Traveling Salesman Problem (TSP)
A.1.1 Problem Definition
The TSP involves finding the shortest possible route that visits each city exactly once and returns
to the origin. Formally, given set of nodes V = {0, 1, 2, n }} and distance matrix where di represents the distance between nodes i and j. we introduce binary decision variables Zij where Fyy if the tour includes direct trip from node node j. and Zig = 0 otherwise. The mathematical model of TSP is as:
minimize
Σ
Σ
dijzij
1= i=
subject
Σ Fij ViEV
(8)
0=
Σ Fij =1 AjEV
(9)
i=0,ff)
Σ
Fij S |S| - V Sn
(10)
(.ES
Tiz E 10 Vi.jeViijj
(11)
where S represents any proper subset of nodes. Constraints and ensure that each node is visited exactly once, while constraint 3 (subtour elimination constraints) ensures the solution forms single tour covering all nodes rather than multiple disconnected subtours.
A.1.2 Instance Generation
We generate cross-size and cross-distribution instances for the TSP by randomly sampling node numbers from [10, 100) nZ and node coordinate distributions from [1, 1000) following a uniform
distribution and two Gaussian mixture (GM) distributions. The GM distribution is parameterized
16

---

by cluster and scale and we use c= 2,1 = and 3,1 10 respectively. The overall generation process follows the existing work 688] We also calculate the top-2 nearest neighbors while transforming the numerical instances to TAIs using KD-Tree. The solutions (labels) of the generated instances are obtained by the LKH-3 solver, which can produce optimal solutions for TSP with node number from 10 to 100. An example TAI used for SFT is shown below:
Example TAI of TSP
### Instruction: Solve the Traveling Salesman Problem (TSP) for the given list of 81 cities. Each city is represented as a node with coordinates (x, y). Identify the shortest route that visits every city exactly once and returns to the starting city. The input includes city coordinates, the 2 nearest neighbors for each city, and their respective distances. Provide the solution in the following format: 1. Route: List the nodes in the order they are visited. 2. Objective: The objective value (total travel distance).
### Input: Node O, coordinates: [374, 950], neighbors: [69: 23.7, 12: 184.3]: Node 1,
coordinates: [731, 598], neighbors: [43: 39.1, 46: 47.0]; Node 2, coordinates: [156, 155), 46: neighbors: [7: 37.5, 28: 78.9]; Node 3, coordinates: [58, 866], neighbors: [21: 49.2, 36:
73.6]; Node 4, coordinates: [601, 708], neighbors: [68: 83.2, 78: 88.6]; Node 5, coordinates:
[20, 969], neighbors: [16: 49.7, 34: 56.6]...
### Output: Route: [0, 27, 57, 60, 63, 26, 56, 17, 25, 40, 59, 44, 31, 67, 77, 70, 52, 75, 58,
35, 38, 14, 10. 15, 24, 65, 39, 61, 18, 41, 72, 54, 55, 7,2, 49, 28, 74, 29, 66, 62. 11, 42, 30,
71, 48, 73, 19, 47, 46, 1, 47, 78, 4, 68, 12, 53, 22, 80, 51, 23, 32, 13, 76, 20, 64, 50,
45, 33, 36, 3, 21, 16, 34, 69, 0), Objective: 6833.347
A.1.3 Reward Funetion
We male-based rewards represent constraint satisfaction for all the CO problems. According to the definition of the TSP, we define the feasibility reward as R2 wps + wie + W202, where visited exactly
wi 0.2, w1 0.5, and 42 0.3. Here, e 1 if all nodes 0), and (2 = 1 if the route returns to the starting point (otherwise 0). represents whether the route be extracted using the specific format (which is shown in the example TAI) from the generated textual output. For simplicity, we omit the notation of the problem class P and the instance
(otherwise
A.2
Orienteering Problem (OP)
A.2.1 Problem Definition
The OP involves finding a path from starting point, visiting subset of nodes maximize the total collected prize while keeping the total distance within a given limit. Formally, given set of nodes V (0, 1, 2,...... n }} with prizes 8; for each node i, a distance matrix where d; represents the distance between nodes and and distance limit B, we introduce binary decision variables J; where x; if node visited, and x; = otherwise, and binary decision variables Vij where Yi if the path includes a direct trip from node to node j. The mathematical model of OP is as:
17

---

maximize
8
(12)
subject to
yoj =1
(13)
E Mij = zi
ViEV {n 1}
(14)
j 0,311
n-1
Σ =
vjEV
(15)
0,141
E
Σ diyUi" SB
(16)
j=0
Σ
. -
V |S| nn
(17)
(JES
iES
Constraint 1 ensures that the path starts at node O. Constraints 2 and ensure flow conservation at each visited node. Constraint 4 ensures the total distance does not exceed the distance limit B. Constraint 5 (subtour elimination constraint) ensures the solution forms single path rather than disconnected subtours. The final two constraints define the binary decision variables.
A.2.2 Instance Generation
The size and node distributions of the generated instances are the same as TSP. The prize of each node randomly sampled from [1, 10] n Z. for the route limit, we firstly use a simple heuristic, i.e., the nearest neighbor method, obtain the approximated route length LT for the TSP that corresponds to the OP instance, and randomly sample float number from [0.5LT, 0. 0.7 as the value of B. For simplicity, we specify that the route does not have to return to the depot. The optimal solutions are obtained by a recent state-of of-the-art solver for the OP based on a genetic algorithm [69] Below an example TAI for the OP task:
Example TAI of OP
### Instruction: Solve the Orienteering Problem with 23 nodes. Each node has (x, y) coordinates and a prize for visiting it. You must plan route that starts at depot O, collecting the maximum total prize possible, subject to maximum route length T 2682.5. You may visit subset of nodes, but the total distance traveled must not exceed T. The input includes city coordinates, the 2 nearest neighbors for each city, and their respective distances. Provide the solution in the following format: 1. Route: The ordered list of visited nodes. Objective: The objective value (summation of the collecting prizes).
### Input: Node O, coordinates: [0, 871], prize: 0, neighbors: [2: 84.6, 5: 142.2]; Node 1,
coordinates: [208, 957], prize: 5, neighbors: [4: 81.0, 3: 82.2]; Node 2, coordinates: [46,
800], prize: 5, neighbors: [O: 84.6, 5: 150.9]; Node 3, coordinates: [138, 1000], prize: 2,
neighbors: [4: 44.4, 5: 76.2]; Node 4, coordinates: [127, 957], prize: 10, neighbors: [5: 33.4,
3: 44.4]; Node 5, coordinates: [132, 924], prize: 6, neighbors: [4: 33.4, 3: 76.2]
### Output: Route: [0. 2, 6, 11, 19, 22, 18. 16. 14, 10, 13, 12, 9, 5], Objective: 98.00
A.2.3 Reward Function
The feasibility reward the orienteering problem defined as R, = w/C + wiC1 w202 + 43 where = 0.2, w1 = 0.1, w1 0.2, and 0.5. Specifically, = 1 if the route starts from the depot (otherwise 0); 62 = if each node is visited at most once (otherwise 0); c3 = 1 if the total travel distance is within the distance limit B (otherwise 0). The LLM can easily violate the distance
18

---

limit constraint, so we assign higher weight to it during reinforcement learning. The optimality reward of OP is R.p (3pp) Ee because try to maximize the collected prizes.
A.3
Capacitated Vehicle Routing Problem (CVRP)
A.3.1 Problem Definition
The CVRP involves finding optimal routes for fleet of vehicles to deliver goods from a depot to customers, where each vehicle has a limited capacity (we use homogeneous capacity for all the vehicles for simplicity). Formally, given set of nodes V = {0, 2.......... tu where node 0 represents the depot, a distance matrix d where dig represents the distance between nodes i and j. customer demands a; for each node E V (0), fleet of K identical vehicles each with capacity Q, introduce binary decision variables Tajk where Tiýk = if vehicle & travels directly from node to node and Fiik 0 otherwise. The mathematical model of CVRP is as:
K
minimize
diyFish
(18)
k= K
im0 j=U,jæb
n
subject to
Tijk =1 ViE V \ {0}
(19)
==
a
Σ Tojk =
Ak E f1..... K}
(20)
Tihk =
Σ
Jhjk
the V,KE {I...., K}
(21)
==0
1=0
Tiok
Ak E (1....,K K}
(22)
t=0
Σ
Σ
Piiiyk S Q
Ak E (1, (1....,K)
(23)
(EV) JEV
Σ Zisk S |S|
AA c V (0),1S) 2, fI.....KK K}
(24)
Tijk E (0,1)
W.jEV, vk (I...., K}
(25)
Constraint ensures that each customer is visited exactly once by exactly one vehicle. Constraints 2 and ensure that each vehicle starts and ends at the depot. Constraint ensures flow conservation at each node (a vehicle that enters node must also leave it). Constraint 5 ensures that the total demand served by each vehicle does not exceed its capacity Q. Constraint (subtour elimination constraints) ensures that each vehicle's 's route forms single tour connected the depot rather than disconnected subtours. The final constraint defines the binary decision variables.
A.3.2 Instance Generation
The size and node distributions of the generated instances are also the same as TSP (10-100 nodes with 3 different distributions). The values of customer demands y are randomly sampled from 10 nZ, Z, and the capacity of each vehicle is set to the average value among all the demands. The near-optimal solutions used for fine-tuning are also produced by the LKH-3 solver. Below is an example TAI for the CVRP:
19

---

Example TAI of CVRP
### Instruction: Solve the Capacitated Vehicle Routing Problem (CVRP) with 45 customers and depot (node 0). Each customer node has demand. All vehicles have the same capacity of 111. You must assign each customer exactly one route and ensure that the sum of demands on each route does not exceed the vehicle capacity. Minimize the total distance traveled. The input includes city coordinates, the nearest neighbors for each city, and their respective distances. Provide the solution in the following format: 1. Route: A list of routes, each route as an ordered list of visited nodes (start/end the depot). Objective: The total distance of all routes.
### Input: Node coordinates: [428, 688), demand: 0, neighbors: [6: 42.6, 14: 53.1]: Node
1. coordinates: [58, 915], demand: 9, neighbors: [15: 35.4, 17: 46.6); Node 2, coordinates:
[442, 239], demand: neighbors: [44: 159.4, 27: 170.8]; Node 3, coordinates: [93, 182],
demand: 9, neighbors: [8: 89.8, 10: 129.0]: Node 4, coordinates; [934, 638], demand: 7,
neighbors: [21: 67.0, 40: 102.1]; Node 5, coordinates: [516, 657], demand: 4, neighbors:
[14: 52.6, 0: 93.3]
### Output: Routes: [[O. 6, 35, 1, 15, 17, 12, 7, 10, 3, 27, 45, 9, 28, 23, 2, 32, 39, 41, 0]. [0. 5, 37, 19, 22, 21, 40, 4, 20, 24, 25, 0}, [0, 43, 44, 29, 26, 42, 38, 34, 11, 16, 13, 33, 31, 30, 36,
18. 14, O]]. Objective: 6643.76
A.3.3 Reward Function
The fcasibility reward of the CVRP is similar to OP, which is defined R, woS WiC1 Wgt2 w3C3, where wip = 0.2, W1 = 0.1, w1 = 0.1, and W3 0.6. Specifically, Ci = if the route starts from the depot (otherwise 0); C2 if all customer nodes visited exactly once; eg 1 if the capacity constraint is satisfied (the total demand served by each vehicle does not exceed Q) (otherwise 0).
A.4 Maximal Independent Set (MIS)
A.4.1 Problem Definition
The MIS problem involves finding the largest subset of vertices in a graph such that two vertices in the subset are adjacent. Formally, given an undirected graph G' = EV) where V = = ... n. } is the set of vertices and the set of edges, we introduce binary decision variables x; where x; vertex is included in the independent set, and = 0 otherwise. The mathematical model is as:
maximize
Σ Fi
(26)
1=1
subject to
24 + xj S V(i,) E x E 10 ViEV
(27)
(28)
The first constraint ensures that no two adjacent vertices are both included in the independent set (if (i,5) is an edge, then most one of the vertices i and can be in the independent set). The second constraint defines the binary decision variables.
A.4.2 Instance Generation
For the instances of MIS, we need to generate the graphs using Python networkx package. We randomly choose the graph type from two options: Erdös-Rényl Rényi graph (ER) or Barabási-Albert (BA) graph. ER graph chosen, the edge probability sampled from 10.1, 0.4]; if EA graph is chosen, the number of edges each new node attaches to is randomly sampled from [1,4] n Z. The number of nodes of an MIS instance also sampled from [10, 100] 0 Z. The optimal solution of the MIS obtained by Gurobi. An example of TAI for MIS is as:
20

---

Example TAI of MIS
### Instruction: Given undirected graph with 10 nodes (0..9) and edges specified below. For each node, we also provide up to 2 neighbors connected to it. Find a maximum indepen- dent set: the largest
of vertices where no vertices share an edge. The input includes the edges of the graph and the top-2 neighbors for each node in the format N[,,b,Hc.Hd]] where and are the top-2 neighbors, #c the degree of a, and #d is the degree of b. Output format: 1. Set: The list of vertices in the maximum independent set. 2. Objective: The size
of that set.
### Input: Edges: (10994/2....50000.01110000oo3313
NO:[9,t4); N1:[9.6.#4.##3) N2:[1,6.#4,##3, N3:[11,, N4:13,5 N5:99,4444H
N7:0: N8:[]: N9:[1,6,#44#3
### Output: Set: [0, 3, 5, 7, 8). Objective:
A.4.3 Reward Function
There is only constraint for the MIS problem, which is specified in Equation 27 Therefore, the feasibility reward is R, = wow + WiCI, where wh = 0.2 and W1 = 0.8. The value of c₁ is if there adjacent vertices in the set, otherwise O. Notably, the optimality reward of MIS is defined as de because the goal of the problem is maximize the objective instead of minimizing
R.. (#p)
A.5 Minimum Vertex Cover (MVC)
A.5.1 Problem Definition
The MVC problem aims at finding the smallest subset of vertices in graph such that every edge has at least one endpoint in the subset. Formally, given an undirected graph V = (1, .2. n is the set of vertices and E is the set of edges, we introduce binary decision variables x, where 2; = vertex included in the vertex cover, and æ; = otherwise. The mathematical model of MVC problem is as:
(V, E) where
minimize
Σ 32
(29)
1=1
subject to
I; + 21
V(t,j) E
(30)
I; [0,1] ViV
(31)
The first constraint ensures that for every edge in the graph, least one of its endpoints included in the vertex cover. The second constraint defines the binary decision variables.
A.5.2 Instance Generation
We follow the same graph generation process as MIS for generating MVC instances, and the optimal solution is also produced by Gurobi. Below is an example TAI of MVC:
21

---

Example TAI of MVC
### Instruction: Given undirected graph with 11 nodes (0..10) and edges specified below. For each node, we also provide up to neighbors with the largest degrees. Find a minimum vertex cover: a smallest set of vertices such that every edge has at least one endpoint this set. The input includes the edges of the graph and the top-2 neighbors for each node in the format N[a.b,#c,#d]] where and are the top-2 neighbors, #c is the degree of a, and #d is the degree of b. Output format: 1. Set: The list of vertices in the minimum vertex cover. 2.
Objective: The size of that set. ### Input:
Edges: htt.://ho....110........00000000
(5.))
N1:[0,3,#9.H55;
N2:[0.7,H9,#21]
N3:[0,5.#9.H44] N4:10,1,#9,H3) N8:(0.3:9,455]:
(5:(0,3,4,445]
N6:10,4,
N7:15.2.#4.42):
N9:[0.3,H9.45];
N10:[0,5,H9,HH*
### Output: Set: [0, 3, 4, 7], Objective: 5
A.5.3
Reward Function
The feasibility reward of MVC is R, waS + w1C1, where win = 0.2 and w1 = 0.8. The value of c₁ if all edges are covered by the solution, otherwise O.
A.6
Permutation Flow Shop Scheduling Problem (PFSP)
A.6.1 Problem Definition
The goal of the PFSP is to find the optimal sequence of jobs to be processed on a set of machines, where each job must be processed on all machines in the same order. Formally, given set of jobs where Pij is the processing time of job j on machine i, we introduce binary decision variables 2ikk where Zyk if job j assigned to position & in the sequence, and Σソı = 0 otherwise. Additionally, let C.k represent the completion time of the job in position on machine i. The mathematical model of PFSP is as:
= {1, 2,.,,,,.,77 n and set of machines M = {1, .1.......7.. m..
minimize
Cmk
(32)
subject to Σ Tyk= =1 1=1
Ak E [1,...,n]
(33)
Zjk =
Vj E f1.....
(34)
1=1
C1k = C1,6-1 +
Σ
Pijaik
Vk E [I.
(35)
b=1
Ca C1-11 +
Σ
PijTz1
Vi (2,...,
(36)
j=1
Ci 2 Cr,6-1 +
Pijish Wi (2...., mm,, vk E (2.
(37)
Ci C- Σ
Pijaizk Vi (2....,m), vk E (2..... n}
(38)
Cio =
(39)
CiD 0 Vi E (1,...,m)
(40)
Cok = O Vk (1, (1,....,11
(41)
2y E (0,1) Vj,k [1....,m3
(42)
22

---

Constraints and 2 ensure that each position in the sequence is assigned exactly one job and each job assigned to exactly one position. Constraint computes the completion time of jobs on the first machine. Constraint 4 computes the completion time of the first job on each machine. Constraints 5 and 6 ensure that a job cannot start on machine until has completed processing on the previous machine and the previous job has completed processing on the current machine. Constraints 7, 8, and 9 set the initial conditions. The final constraint defines the binary decision variables.
A.6.2 Instance Generation
The instance of PFSP is a matrix with rows and M columns, with each element representing the processing time for a job on machine. We randomly sample J and M from [5, 20), and sample the processing time from [1, 100j n E. The near-optimal solutions for the instances are obtained by the Q-learning- iterated greedy (QIG) method [46. Below is example TAI of PFSP:
Example TAI of PFSP
Solve the Permutation Flowshop Scheduling Problem (PFSP) with jobs and 5 machines. Each machine can process only one job time, and each job can be processed by only one machine at time. Jobs must be processed on each machine in the same order. Identify the job order that minimizes the maximum completing time. The input includes the processing times of each machine on every job, the jobs with the lowest processing time for each machine, and their respective processing times. Provide the solution in the following format: 1. Order: List the order that jobs are processed on each machine. 2. Objective: The objective value (maximum completing time).
### Instruction:
### Input: Machine O. processing times: [32, 22, 26, 49, 44, 14]. jobs with lowest processing
time: [5: 14, 1: 22]; Machine 1, processing times: [49, 87, 91, 98, 13, 31, jobs with lowest
processing time: [5: 3, 4: 13]; Machine 2, processing times: [56, 46, 96, 10, 46, 23), jobs
with lowest processing time: [3: 10, 5: 23]; Machine processing times: [99, 21, 6, 65, 4, 76). jobs with lowest processing time: [4: 4, 2: 6]; Machine 4, processing times: [56, 27, 59,
9, 70, 64), jobs with lowest processing time: [3: 9, 27].
### Output: Order: [6. 2. 4]. Objective: 471
A.6.3 Reward Function
The solution of the PFSP is feasible if it covers all the jobs exactly once, which naturally satisfies all the constraints. As a result, the feasibility reward of PFSP is R2 = woy + W1 where wy = 0.2 and Wi = 0.8, and c1 1 if the solution sequence contains each job exactly once (otherwise 0).
A.7 Job Shop Scheduling Problem (JSSP)
A.7.1 Problem Definition
The JSSP involves scheduling set of jobs sequence of operations that must be processed in a specific order. Formally, given a set of jobs - (..,..... n and set of machines A {1, 2. m). where each eachjob j consists of sequence of operations O51. Oz....., Ojn,, and each operation Oj must be processed on machine Mya for duration Pjs, we introduce variables Syz to represent the start time of operation Oje and binary decision variables bji for operations that share the same machine. Let E = {[j, i, h, k) Mys Phk. (j. # (h, k)} be the set of all pairs of operations that use the same machine.
of machines, where each job consists of
minimize subject to
Cmax
(43)
851 + PJ S 81841
(44)
8jz + Pjt S 8hk M(1 M(1-2j(An) kij,i,h,k)&BB
(45)
SKA + Phkk S S3j + Majui V(j,ū,h,k)
(46)
8j1 + Pj S Cmax
J,i=1, .,....
(47)
8ji 2 0 Vj E 1,i=,....,""
(48)
Tji. E {0,1) V(ji, k,) E E
(49)
23

---

Constraint I ensures operation precedence within each job. Constraints 2 and 3 prevent machine conflicts by ensuring that operations sharing the same machine are processed sequentially. Constraint 4 defines the makespan as the maximum completion time. Constraint 5 ensures non-negative start times. The final constraint defines the binary decision variables. M is sufficienlly large constant.
A.7.2 Instance Generation
The generation of processing time is the same PFSP, they have the same structure. Morcover, each job randomly assigned to a machine. The near-optimal solution is calculated based on the CP-SAT solver of OR tools with time limit of 300s. Below is example of JSSP TAI:
Example TAI of JSSP
### Instruction: Solve the Job Shop Scheduling Problem (JSSP) with jobs and machines. Each job consists of 6 operations which need to be sequentially processed specific machines. Each machine can process only one job a time, and each job can be processed by only one machine a time. Identify the schedule that minimizes the maximum completion time (makespan). The input includes the information of operations for each job, including their specific machine and processing time, well as the operators with the lowest processing time and their respective machines and processing times. Provide the solution in the following format: 1. Schedule: List the order that jobs processed each machine. 2. Objective: The makespan of the schedule.
#### Input: Job 0, machines and processing times for operations: [(2, 73), (4, 84), (0, 70),
(3, 7), (1, 62), (5, 30)], operators with lowest processing time: [3: (3, 7), 5: (5, 30)]: Job machines and processing times for operations: [(3, 4), 90), (1, 12), (2, 92), (0, 21), (5, 66)]. operators with lowest processing time: [O: (3, 4), 2: (1, 12)]; Job 2, machines and processing times for operations: [(3, 4), 37), (2, 24), (5, 20), (0, 80), (4, 92)], operators
with lowest processing time: [0: (3. 4), 3: (5, 20)]...
#*# Output: Schedule: [[2. 3, 4], [2, 1, 0, 5), [0, 2. 1,
1,4. 5]. [1, 5, 0, 4. 4. [1.
0, 5, 4, 21, [5, 2, 4, 3, 1, O]], Objective: 466
A.7.3 Reward Function
The feasibility reward of JSSP is R, wa0 W1C1 + w202 + W3C3, where wp 0.2, w1 0.2, We = 0.2 and = 0.4. The value of C1 is 1 if all jobs are scheduled (otherwise 0), C2 = if there are no machine conflicts (otherwise 0), and c3 1 if the precedence constraint is satisfied (otherwise 0). The optimality reward of JSSP still follows Equation 4.
B Low-Rank Adaptation
Training LLMs from scratch or through full-parameter fine-tuning requires significant computational resources and storage, especially with billions of parameters. To enable efficient adaptation of LLMs to CO tasks, we employ Low-Rank Adaptation (LoRA) [49] for all SFT and RL experiments in our framework. Specifically, LoRA is parfiietereffficientt fine-tuning technique for large pre-trained models that injects small, trainable, low-rank matrices into selected layers while keeping the original model weights (backbone) frozen. In effect, LoRA optimizes a significantly smaller proportion of parameters (only 2.08% in our implementation) compared to full fine-tuning.
Concretely, let Wo R&dx denote weight matrix from pre-trained LLM,, such as those found in the linear projection layers the self-attention mechanism or the feed-forward sublayers within each transformer block. During standard full-model fine-tuning, each element of Wo would be updated, which becomes computationally and memory-intensive for large and k. LoRA addresses this by introducing a low-rank decomposition for the weight update. Specifically, instead of updating Wo directly, the adaptation is parameterized as:
W Wo AW,
where the trainable update AW is represented as a product of two low-rank matrices:
AW BA,
24

---

with A R'x* and B E Rdxr, where is a tunable rank parameter and r < min(d, k). Here, A projects the imput from dimension & down a small intermediate rank r, and B projects back up to dimension d. Both A and B are randomly initialized and are the only trainable parameters during fine-tuning, while Wo remains frozen. At inference time, the low-rank adaptation can be merged into Wo so that the model incurs no additional computational cost compared to the original LLM.
Additionally, because our fine-tuning strategy guides the LLMs better follow instructions specific to CO problem solving, restricting training to only the LoRA modules- while keeping the backbone frozen preserves the general-purpose capabilities of the original LLM.
LoRA typically targets specific layers in the transformer. In this paper, the trainable components include the query, key, value, and output projections in the attention layers, well as the gate, up, and down projections in the feed-forward layers.
C Experiment settings
The LLMs are fine-tuned with context length of 20,000 tokens. Both the LoRA rank and scaling factor are set to 64 for surameter-efficien fine-tuning. For the SFT process, we use a batch size of 4, with gradient accumulation step of 4, resulting in effective batch size of 16. Optimization is performed using the AdamW optimizer, with learning rate of x 10-4, and a linear decay scheduler with decay rate of 0.01. For the FOARL process, we set the hyperparameters The batch size is set to 8, while S = 8 generations are produced for each instance to calculate the group advantage A;. We the weighting parameter a = 1 to balance the optimality and feasibility of the generated solutions. The learning rate for reinforcement learning is set to 1 X 10-6, and the rest of the parameters are the same as the SFT process. We use Alpaca-style prompt template for model fine-tuning, and the template is as below, and the fields with "()" (Instruction, Input, and Response) are filled with the TAIs during training.
0.1 and / 0.05.
Prompt Template for fine- fine-tuning
Below is an instruction describing a combinatorial optimization problem. It is paired with an input that provides the data of the instance. Your task is produce feasible solution that optimizes (minimizes or maximizes) the given objective. ### Instruction:
### Input:
### Response:
During evaluation, we use 100 randomly generated instances (following the instance generation pro- cess specified in Appendix A for each COP. For baseline comparisons involving OpenAI, Anthropic, and DeepSeek models, we utilize their official APIs. The API calls of Llama and Qwen are provided by Groq and Siliconflow, respectively. The experiments related to LLMs are conducted 3 times independently. and the best result is reported. All experiments are conducted on a server equipped with an AMD EPYC 7F72 CPU (3.2 GHz) and NVIDIA H100 GPU. As reference, the SFT process for the JSSP task requires approximately 65 hours of training time and consumes around 28 GB of graphic memory.
D Baseline Details
General-purpose LLMs and Reasoning models. We prompt the LLMs by inserting a random feasible solution after the TAI of the instance. Specifically, the prompt skeleton is as "Below is an example of feasible solution for the problem. IRANDOM SOLUTION]. Please directly give me the (near)optimal solution that strictly follows the format the solution above". : By doing so, the LLMs can follow the output format and get hints from the example solution. The reasoning models can construct the CoT for the solution improvement process by taking the random solution as the starting point. Generally, the generation of the LLMs will benefit from the given random solution, and the performance can be even worse without it.
We generate 5 feasible random solutions and ask the LLM to give a better solution than the random solutions. The prompt is organized as follows: "Below
Optimization by PROmpting (OPRO) 19
25

---

are some previous solutions and their costs. The solutions are arranged in descending order based on their costs, where lower values are better: [RANDOM SOLUTIONS]. Give me new solution that is different from all solutions above, and has a cost lower than any of the above. Please directly give me the answer strictly following the format as the solutions above." " The process repeats 4 iterations, and the best solution during the iterations is preserved.
LLM-driven Evolutionary Algorithm (LMEA) 34 Inspired by the LMEA method [34, which is originally designed for TSP, we develop an extension that takes LLMs as evolutionary algorithmic operators to evolve initial solutions. We first generate a population of feasible solutions using random sampling. For each iteration, the LLM is prompted to evolve the population by selecting two parent solutions and applying evolutionary operators to produce new offspring. The prompt explicitly describes different crossover and mutation strategies depending on the problem type. The LLM is guided to perform several evolutionary steps in each outer iteration, and the top solutions are retained for the next generation. More specifically, we design various prompts for crossover and mutation strategies tailored to different types of CO problems. For routing problems, the crossover operators as: 1) Order Crossover (OX): Description: OX randomly selects segment from parent 1, copies it to the offssring, and fills in the remaining positions with the missing elements in the order in which they appear in parent 2. 2) Partially Mapped Crossover (PMX): Description: PMX randomly selects a segment from parent 1, copies it to the offspring, and maps the remaining positions based on parent 2. Creates mapping between conflicting elements and resolves them systematically" and the mutation operators are: " 1) Swap Mutation: Randomly selects two positions and swaps the elements at those positions. 2) Insert Mutation: Randomly selects one element and moves to another random position. 3) Inversion Mutation: Randomly selects two positions and reverses the order of elements between them". For graph CO problems, the crossover operators are as: "I) Uniform Crossover: For each position, randomly choose the bit from either parent 1 or parent 2. 2) aangl-point Crossover: Choose a random crossover point, take the first part from parent 1 and second part from parent 2", while the mutation operators are "1) Bit-flip Mutation: Randomly flip some bits in the solution (0->1 or I 1->0). 2) Neighborhood Mutation: Focus mutations on vertices that are neighbors in the graph". For scheduling problems, the crossover operators are: "I) Job Order Crossover (JOX): Preserve relative job order from parents while creating valid schedules. 2) Linear Order Crossover (LOX): Select subset of jobs from parent I and fill remaining positions with parent 2's order", and the mutation operators are as: "I) Job Swap Mutation: Swap the positions of two randomly selected jobs. 2) Job Insert Mutation: Remove job and insert it at different position. 3) Job Inversion Mutation: Reverse the order of jobs in a randomly selected subsequence". We use a population size of 3 and 3 evolutionary iterations to balance solution quality and efficiency.
Progressive-hine hint prompting (PHP) (55]. The PHP process starts with a randomly generated solution and 4 progressive iterations. If the generation is infeasible, prompt: "The solution is not feasible. Please make sure to follow all problem constraints and the output format". If the new generation is better than the previous one and achieves optimality gap lower than 5%, we call the LLM by the prompt: "The solution is feasible with objective value {obj_ ) This is very close to optimal". If the new generation is better than the previous one and achieves an optimality gap larger than 5%, we call the LLM by the prompt: "The solution is feasible with objective value _bb_ue and gap gap. This is an improvement over previous solutions, but please try to optimize it further". If the new generation is worse than the previous one, we call the LLM based on the prompt "The solution is feasible but suboptimal with objective value vabje] ) and gap {gap). This is (obj_diff') worse than the best solution found so far ((best_ __j___o________ee__ value )). Please try to minimize the objective further".
call the LLM using the
Self-guiding exploration (SGE) (56). The SGE method invokes the LLM to generate the programs of multiple heuristics or metaheuristics and solves the CO problems in parallel. We implement the SGE by calling the LLM to produce the name for 3 different methods simultaneously, and then generating the code for each method. there any error during the generation of method names, we set the default method set to be the genetic algorithm, simulated annealing, and greedy algorithm, which are general approaches for the CO problems. The solution is regarded as infeasible if all the generated programs cannot be executed successfully.
Ant colony optimization (ACO) 77]. We use the ACO algorithm, a general metaheuristic, to solve different CO problems. The implementation is based on (70). In order to maintain similar
26

---

Table Detailed solving time for different methods on various CO problems.
Solving Time
Method
TSP
OP
CVRP
MIS
MVC
PFSP
JSSP
General-purpose Language Models
GPT-4o
7.5s
4.8s
6,8s
3.7s
3.9s
4.38
5.8s
GPT-4o-mini
5.1s
2.4s
5.5s
3.28
3.2s
3.1s
9.0s
Claude-3.7-Somme
6.7s
4.4s
6.7%
3.68
3.9%
3.6s
9.2s
Claude-3.5- Haiku
5.0s
4.3s
3.5s
4.9s
4.3s
4.8s
9.0s
DeepSeek- V3-67 IB
33.0s
22.8s
36.3s
20.3s
20.0s
26.1s
26.2s
Llama3.3-70B
2.6s
1.8s
2.2s
1.8s
1.7s
1.5s
3.1s
Qwen2.5-72B
13.5s
13.38
13.6s
6.9s
11.0s
6.9s
22.1s
Reasoning Models
GPT-o3-mini
57.2s
109.8s
60.5s
109.4s
90.4s
108.6s 6s
45.9s
GPT-ol
118.7s
120.7s
72.1s
293.5s
264.3s
380.3s
98.2s
DeepSeek-RI
240.0s
521.3s
360.5s
402.9s
420.4s
437.2s
364.8s
Prompt Strategies
ORPO
150.2s
123.7s
121.6s
103.1s
110.5s
96.3s
191.2s
LMEA
418.8s
276.7s
415.2s
241.9s
248.5s
202.8s
432.0s
PHP
96.1s
95.9s
104.2s
85.3s
98.1s
79.3s
125.2s
SGE
166.9s
234.3s
308.8s
163.7s
168.0s
201.4s
260.5s
Ours
SFT
7.0s
4.6s
6.9s
3.2s
4.8s
1.8s
10.7s
SFT+RL
7.0s
4.6s
6.9s
3.2s
4.8s
1.8s
10.7s
SFT+RL+BoN
11.7s
10.8s
11.3s
4.0s
7.1s
3.1s
20.7s
computational time, use 100 ants and 500 iterations for all the TSP instances, and 50 ants and 100 iterations for both OP and CVRP.
Other heuristics. The heuristics of TSP, including both NN and FI, are based on the implementation of the pyCombinatorial p It incorporates local search process in FI for better performance. Moreover, we use sampling size of 1280 for the Tsili method [59] for solving the OP, which shows much better performance than the greedy one.
E
Additional Experiment Results
E.1
Detailed Solving Time
The solving times for various baselines across CO tasks are presented in Table 4 These results show that our 7B-parameter LLM solver is substantially more efficient than reasoning-basee models, while also achieving superior solution quality. Notably, despite Llama3.3- 3. and Qwen2.5-77 2-BB having similar parameter sizes, Llama3,3-708 demonstrates significantly faster solving times. This discrepancy arises from differences in implementation details and the hardware environments of the respective APIs, which are factors beyond control.
E.2 Example Thinking Process
Taking DeepSeek-RR and TSP instance with 48 nodes as an example, when we prompt the LLM to generate the answer, it produces a CoT with more than 10000 tokens. In order to briefly show the content, we present the main thinking content below, where we use ellipses (i.e.... ...) to indicate omitted content, while preserving the rambling and ineffective style of the LLM's reasoning, We can find that the LLM gets stuck multiple times while processing the instance and tries to switch between different strategies. Finally, it just produces random answer, which is far from the optimal solution.
27

---

DeepSeek CoT for TSP Instance
Okay, need to solve the TSP for 48 cities using coordinates and nearest neighbors per city. TSP is NP-hard, so I'll try a heuristic. Maybe nearest neighbor? But that might cause loops...
Alternatively, maybe I can start building the route by choosing a starting city and then always moving the nearest unvisited neighbor...
Alternatively, I could use some kind of greedy heuristic that selects the globally shortest available edge that doesn't 't create a cycle...
Alternatiely. perhaps I can use the given neighbor data to form minimum spanning tree... Alternatively, maybe I can look at the set of neighbors and try to trace a Hamiltonian cycle manually...
Hmm... Christofides algorithm? No, we lack full distance matrix...
Alternatively, maybe can use the neighbor data to identify subtours and then link them... Wait, I'm stuck at Node 16. Maybe start over...
Looks like two clusters based on Y-coordinates. Let's try connecting them. From Node 29 to Node 40 seems shortest (=:333 units)...
Alternativel., maybe can build tour per cluster and then stitch them...
Wait, how to close the cycle?
Still missing cities...
Mayhe patch cycles? Or build a spanning tree? Fulerian? No, degrees don't match... Let's just assume inter-cluster links. Total distance? No idea. Maybe 5000? Actually, forget it - too complex manually.
approximate the route, sum known neighbor distances, and plug in
Alternatively, the problem may have a specific structure where the route can be determined by connecting each node...
But as before, this gets stuck. Given the time I've spent and recognizing that a precise manual solution isn't 't feasible, I'll provide the route as per the nearest neighbor heuristic, acknowledging that it may not visit all nodes but following the given instructions as best as possible.
**Final *nswer** 1. Route: [0, 34, 22, 26, 6, 21, 12, 9, 8, 13, 16, 14, 1, 2, 10, 4, 5, 17, 18, 19, 24, 32, 25, 15, 31, 20, 28, 23, 29, 40, 35, 41, 37, 39, 42, 47, 43, 36, 46 38, 45, 44, 35, 40, 29, 23, 28, 20, 31, 15, 25, 21, 3, 12, 9, 8, 7, 13, 16, 14, 1, 2, 10, 4, 5, 17,
18, 19, 24, 32, 22, 27, 34, 33, 30, 0]
2. Objective: The total travel distance is the sum of all the provided neighbor distances plus the inter-cluster connections. However, due to the complexity and lack exact distance calculations for all segments, the precise objective value cannot be determined manually within the given constraints. For the purposes this problem, the objective value would be calculated by summing the distances of each consecutive node pair in the route using their coordinates and Euclidean distance.
E.3
Comparative Evaluations
Table 5: Comparative evaluations of average objective (obj.), feasibility rate (fea.), and optimality
gap (opt.) between language- CO solvers.
TSP
CVRP
MIS
MVC
Mothod
obj-1
fea.t
opt.
obj-J
fea.1
opt...
obj.1
fea.t
opt...
obj-I
fea."
opt...
LNCS
5.79
1.64%
10.74
3.62%
23.82
13.03%
32.101 101
11.42%
Ours
5.73
100%
0.67%
10.81
100%
4.32%
21.07
100%
0.40%
29.05
100%
0.83%
This section compares the proposed method with Language-basse based Neural COP Solver (LNCS) 14] a recent study that also takes as input the textual description for CO problem solving. Different from our method, LNCS utilizes the LLM as the encoder and inserts a Transformer-lie like NCO model after LLM to decode solutions, following a similar solution generation process to the Pointer network 77 This method ensures the feasibility of all the generated solutions by masking all nodes that cause infeasibility during decoding. However, LNCS not as universal as our method because of the limitation of the specialized decoder: it requires the update of the numerical constraints
28

---

Table Comparison with sondellthhe-sslle approaches across different routing problems and scales.
TSP-small
TSP-meding
TSP-large
Method
fea.t
opt.
fea.t
opt.
fea.t
opt.
LLMOPT
100%
0.00%
100%
1.00%
100%
7.39%
DRoC
100%
0.00%
100%
0.00%
100%
2.48%
ORLM
100%
0.18%
100%
18.43%
73%
301.00%
Ours
100%
0.14%
100%
0.70%
100%
1.34%
OP-small
OP-medium
OP-large
fea.t
opt.
fea.t
opt..
fea.t
opt..
LLMOPT
100%
0.74%
100%
13.91 %
100%
66.00%
DRoC
100%
1.04%
100%
9.73%
100%
42.93%
ORLM
100%
2.97%
100%
21.68%
100%
56.16%
Ours
100%
1.47%
100%
2.04%
100%
2.10%
CVRP-small
CVRP-medium
CVRP-large
fea.t
opt.
fea.t
opt..
fea.
opt..
LLMOPT
100%
2.59%
63%
35.25%
5%
68.98%
DRoC
100%
7.96%
78%
48.45%
9%
96.51%
ORLM
100%
13.83%
97%
163.00%
90%
192.00%
Ours 100%
1.70%
100%
4.57%
100%
7.24%
vector (to record the constraint satisfaction situations), which is used as part of the decoding context, making the input composed of language-based features and number-based features. Meanwhile, the structure of LNCS determines that cannot process some tasks very well, as it delivers unsatisfactory performance on graph CO problems such MIS and MVC.
We compare our approach against LNCS on four representative CO tasks-TSP. CVRP, MIS, and MVC, which also evaluated in the paper of LNCS. Both methods utilize LLMs with 7B parameters to ensure a fair comparison. The test dataset consists of 1,000 instances, each with 50 nodes, following the instance distribution specified in [14. As reported in Table our method achieves performance on par with LNCS for the routing problems (TSP and CVRP), while demonstrating a significant advantage the graph-based problems (MIS and MVC). These results indicate that method is more generalizable to different types of text-atrributed CO problems.
E,4 Comparison with Model-then-solve Methods
We also compare our method against three recent state-of-the-arr model-then-soovee baselines: LL- MOPT [3], DRoC [2], and ORLM [72]. These approaches follow the "model-then-solvee pipeline by generating structured problem formulations and invoking specific solvers such as CPLEX (for LLMOPT), Gurobi (for DRoC), or COPT (for ORLM). For faimess, we restrict all methods to a similar runtime budget (as defined in Table 4 and use the solver-calling programs generated by these approaches to solve the instances of the studied routing problems. The solving process is considered failed if feasible solution is found within the given time budget. Additionally, for ORLM, consider solutions with objective values exceeding le6 to be infeasible. Below, we report the average feasibility rate and optimality gap the same benchmark instances used in Table
According to the table, we can find that our method maintains 100% feasibility across all problem types and scales, while feasibility rates for LLMOPT and DRoC degrade sharply- essecillyyy large- scale CVRP (down to 5-9%). In terms of solution quality, our optimality gaps remain consistently low, particularly in medium and large instances, where code solver integration issues and inefficient formulations.
pipelines struggle due to
E.5 Comparison with Classical Solvers
We also compare our method with classical exact and heuristic solvers. We evaluate LKH for TSP, HGS (Hybrid Genetic Search) for CVRP, EA4OP for OP (69), and QIG for PFSP. We also use Gurobi the exact solver to solve all the problems with roughly similar time budget our method
29

---

Table
Performance comparison across different optimization problems
Method
TSP
CVRP
OP
MIS
MVC
PFSP
JSSP
Heuristic solver
0.00%
-0.19%
1.60%
0.00%
Exact solver
1.82%
35.09%
21.96%
0.00%
0.00%
0.46%
2.45%
Ours
1.07%
4.53%
1.85%
1.04%
1.29%
1.03%
8.20%
Table 8: Evaluation of LLM solver performance with different values of N for BoN sampling.
TSP
OP
CVRP
MIS
MVC
PFSP
JSSP
Value
fea.
opt.
fea. 1 opt.
fea. f
opt.
fea. f opt.
fea.
opt.
fea. 1 opt.
fea. f
opt.
82%
3.41%
77%
4.40%
72%
11.80%
52%
1.34%
92%
3.69% 100% 4.48% 99% 23.37%
N 2 97% 2.47%
91%
2.31%
91%
10.51%
57%
1.76%
99%
3.34%
100% 3.61% 100%
20.17%
N = 4 100%
1.98%
98%
2.86%
97%
8.84%
68%
2.70%
100%
2.69%
100%
3.03%
100%
18.52%
N 8 100%
1.34%
100%
2.15%
100%
7.24%
75%
2.29%
100%
2.35%
100%
2.62%
100%
16.25%
N 16 100% 1.08%
100%
1.70%
100%
6.04%
76%
2.28%
100%
1.90%
100%
1.98%
100%
14.45%
N 32 100% 0.90%
100%
1.31%
100%
4.76%
85%
2.61%
100%
1.52%
100%
1.85%
100%
13.54%
N 61 100% 0.73%
100%
0.98%
100%
4.30%
92%
2.23%
100%
1.22%
100%
1.54% 100%
11.63%
(is).,1ss). For CVRP, we use the classical three-index vehicle formulation model by Gurobi. Table 7 shows the average optimality gap over the evaluation dataset. It can be found that the performance of our method is close to the heuristic solvers, which are actually used to generate high-quality supervision data for training. Meanwhile, Gurobi performs very well on certain problems, particularly MIS and MVC, where the MIP formulations are tight and effective. However, on more complex or heavily constrained problems like routing problems, our method significantly outperforms Gurobi model achieves nearly 8x smaller optimality gaps than
under similar time budgets. Notably, Gurobi on CVRP (4.53% vs. 35.09%) and solves OP with far better quality.
Despite the better performance of the classical solvers on certain tasks, our method offers several practical advantages: Ease of use: there is no need for formal modeling, solver licenses, or programming interfaces. 2) Language-de driven interaction: users can specify problems in natural language, making more accessible for non-experts. 3) Generalizability: a single model architecture handles diverse CO problems without customization or manual solver integration. While exact solvers remain preferred applications demanding guaranteed optimality with long runtime, our method offers compelling alternative when flexibility, usability, or rapid prototyping is prioritized.
E.6 Scaling Test-time Exploration
Since Best-of-N (BoN) sampling enhances test-time exploration by generating multiple solution trajectories, increasing the value of N can further improve the performance of the LLM-based CO solver. To evaluate the impact N of BoN sampling, we conduct sensitivity analysis on based on the instances with large graphs, which can be more challenging due to the larger problem scale. Specifically, we vary N across [1, 2, 4, 8, 16, 32, 64) and compare the model performance in terms of both feasibility and optimality. As shown in Table 8, performance improves consistently with larger values of N. These results highlight that the scale of test-time exploration is a critical factor in achieving balance between solution quality and computational efficiency, which is an important consideration for practical deployment in real-world decision makinn scenarios.
E.7 Latent Solution-space Exploration
Table 9: The results of the ablation study on heuristic features.
TSP
OP
CVRP
Problem
fea. t
opt. 4
fea. f
opt.
fea. f
opt.
Ours (Full)
100% 100%
1.07%
100%
1.85%
100%
4.53%
w/o features
1.17%
100%
2.47%
97%
4.72%
30

---

0.5
0.5
01.5
0.4
without heuristie features
with leatures
SFT Looe ((P)
0.4
without houristic fastures
houristic ftatures
SFT oss (CVRP)
0.4
without bouristic faatures
heuristic faatures
0.3
0.3
0.2-
0.1
0
4K.
9K 12K 16K 20K 24K 28K 32K
0
4K SK. 12K 16K, 20K 24K 28K 12K
4K SK.
12K 16K 20K 24K 28K 32K
Trinnig Steps
Training Steps
Training Steps
(b)
(c)
Figure 4: The training curves of the routing problems with and without heuristic features. A running average with smoothing window of is applied. (a) TSP training curves; (b) OP training curves; (c) CVRP training curves.
We incorporate general heuristic features, such the top-k nearest neighbors, into the input prompt to facilitate latent solution- space exploration. These features serve a role similar to feature engineer- ing, providing useful features that help the LLM learn more effective solution generation patterns. Specifically, the features can bias the model toward more promising region in the solution space (e.g., generating the next token that represents the node with the lowest distance). To assess the contribution of this component, we conduct an ablation study for the routing problems in which the model is fine-tuned without the inclusion of heuristic features. Table shows that there is a performance drop without the inclusion of the heuristic features, and this finding also aligns with the previous study [1.. We also visualize the comparison of training curves of routing problems in Figure 4 where we find that incorporating the features consistently leads lower loss during the whole training process. These findings indicate that the LLM can utilize the heuristic features during both training and inference stage to explore more effective solutions.
E.8
Unified CO Solver
Table 10: The performance of the unified LLM CO solver.
TSP
OP
CVRP
MIS
MVC
PFSP
JSSP
fea. ?
100%
96%
93%
84%
93%
100%
100%
opt.
0.86%
1.15%
4.50%
1.89%
2.47%
1.31%
8.25%
To demonstrate the potential of our approach in enabling unified CO solver, we fine-tune single Qwen2.5-7B model using the combined training datasets from all studied CO problems via SFT. The performance of this unified CO solver, which is evaluated with N 8 BoN sampling, is reported in Table 10 showing strong results in both feasibility and optimality for various CO problems.
These results suggest that training across multiple problem types does not significantly compromise performance. With further scaling in model size, diversity of CO tasks, and prompt design, LLMs hold significant promise as foundation models for combinatorial optimization.
E.9
Versatility Study
To further demonstrate the versatility of our proposed framework, we fine-tune another two widely adopted open-source LLMs, Llama-3.1-88 and Gemma-2-9B, as the end-to-end CO solvers. The fine-tuning configurations are the same the Qwen-2.5-7B model. The results for the models trained with supervised fine-tuning alone (denoted Llama-SFT and Gemma-SFT and the complete pipeline incorporating reinforcement learning and Best-of-N inference with N 8 (denoted Llama-Full and Gemma-Full Full) are presented in Table 11 While the performance of Llama-3 3.1 3.1-8B is slightly inferior to that of the Qwen model used in our primary experiments, our method still effectively enables the LLM to produce feasible solutions in most cases and yields good results with low optimality gaps. Despite the different implementations in model architectures and training schemes of different L.MMs, the proposed method consistently maintains its effectiveness across all CO tasks.
31

---

Table 11: Comparison between different LLMs on the studied CO problems.
Qwen-SFT
Qwen-Full
Llama-SFT
Llama-Full
Gemma-SFT
Gemma-Full
Problem
fea. f
opt.
fea. f
opt.
fea. 1
opt.
fea.
opt.
fea. 1
opt. 4
fea. f
opt. |
TSP
89%
2.30%
100%
1.07%_o. 71% 1.8
94%
1.17%=10
81%
1.91% 100% 1.03%
54%
2.32% 126
100%
2.28% 100%
2.13%
56%
2.35%
100% 1.81%
CVRP
59%
6.02% 13.9
100%
4.53% 3.5 35%
7.71%
80%
5.15% 62%
6.68% 15.62
100%
4.56% -4.4
MIS
80%
1.71%
94%
1.34%=3. 84%
2.03%=+4.
91%
0.82%=24
84%
2.01%++4.
1.48%
MVC
98%
2.41% 4333
100%
1.29%_2. 95%
2.61%=337 100%
1.24%=2.1 96%
2.43%
100%
1.22%
PFSP
100%
2.22%%
100%
1.03%
-11 100%
3.11% 100%
1.49% 100%
2.94%
100%
1.50%
JSSP
100%
17.0
100%
8.20%
6.3 69% 8.34% 80%
7.15%L7.
99%
10.00%
100%
8.07% 6.3
E.10
Out-of-distribation Performance
Table 12: Comparative evaluations of feasibility rate (fea.) and optimality gap (opt.) between
in-distribution (InD) and out-of-distribution (OOD) data.
TSP
OP
CVRP
Method
fea.1
opt.
fea.
opt.
fea.
opt.
InD
100%
1.07%
100%
1.85%
100%
4.53%
OOD (clustered)
100%
1.41%
100%
1.89%
100%
5.12%
OOD (mixed)
100%
1.23%
100%
2.30%
100%
5.04%
To evaluate the out-of-distribution (OOD) performance of the trained models, we adopt two OOD distributions, i.c., clustered and mixed, commonly used as benchmarks for routing problems in prior work [73) The clustered distribution generates city nodes by first sampling centroids uniformly at random, followed by sampling node locations from a normal distribution centered at each centroid with a standard deviation of 0.1. The mixed distribution combines both uniform and clustered characteristics by sampling half of the city nodes uniformly and the other half from the clustered distribution. The evaluation results on TSP. OP, and CVRP are shown in Table 12] According the table, we can find that there is slight performance drop when evaluating on the OOD datasets. Since the drop is not significant, the cross-distribution generalizability of our models proven.
E.11 Benchmarking Performance of TSP
Table 13: Optimality gap comparison of LLM-based methods on TSPLIB instances.
Instance
AEL
ReEvo
MCTS-AHD
Ours
eil51.tsp
10.84%
6.50%
15.98%
2.02%
berlin52.tsp
12.91%
17.99%
7.08%
4.54%
st70.tsp
4.10%
6.42%
15.45%
0.00%
ei176.tsp
10.26%
7.34%
12.46%
2.91%
pr76.tsp
9.06%
12.17%
10.41%
3.87%
Average Gap
9.43%
10.08%
12.28%
2.69%
To further demonstrate the generalizability of our method, we evaluate the TSP model on a benchmark dataset. Specifically, we use representative instances with fewer than 100 nodes from TSPLIB 77.. which are derived from real-world routing scenarios, and compare our results with those of other LLLM-based methods. Since existing end-to-end LLM- LLM-based solvers (e.g., OPRO) struggle to effectively solve CO problems, we instead compare our approach with heuristic-discovery methods, including AEL 75). ReEvo [6), and MCTS-AHD 76). These approaches aim to reduce reliance on domain expertise by automating the design of algorithms leveraging LLMs. We use the best-reported constructive heuristics generated by these methods for comparison, and the optimality gaps are presented in Table 13] We also find that our method outperforms other baselines, which indicates can generalize to the benchmark instances that represent real-world scenarios.
32

---

Broader Impacts
Solving CO problems with LLMs has the potential lower the technical barrier for users tackling decision-making and optimization tasks commonly encountered in real-world applications. By en- suring that the LLM -e---eeee solutions are largely feasible and near-optimal, our method offers user-friendly yet powerful tool for practical optimization. This approach holds promise for impactful deployment sectors such as transportation, logistics, and manufacturing. However, this capability comes at cost: the training procedure required to fine-tune LLMs introduces significant compu- tational demands, which can lead to increased financial costs and raise sustainability concerns due to the associated carbon emissions. Future work should explore more efficient training methods or model distillation techniques to mitigate these drawbacks.
G Licenses
The licenses and resources of the code and software used in this paper listed in Table 14
Table 14: List of licenses for the codes used this work
Resource
Type Code
Link
License
OR-Tools
Apache-2.0
cense
LKH-3
Code
Available for academic
LKH-3/
research use
Gurobi
Software
https://ww..urobbl
Academic Li-
cense
PyCombinatorial
Code
https://gittub..com/lalllad
GNU General
pyCombinatorial
Public License
Compass
Code
Apache-2.0
Unsloth
Code
sttps///gghuu.cccmmmmaaclllaaaap
Apache-2.0
DeepACO 70
Code
attgss//gghhubocc/m//rrryyyy///p
MIT License
OPRO 19
Code
Apache-2.0
SGE 56
httpo://gttaub.comm/nngg//1L1111 Code
Available for
academic use
ReEvo 6
Code
httpss//gtthub.coo/aae//eeeee
MIT License
MCTS-AHD
Code
httpss//g.ttubb.comz11166
MIT License
766
McTtee
TSPLIB 74
Dataset
http://coopp..ii.uu-eeiiiio de/ sof software/1SPL.195
Available for any
commercial use Available for
Taillard 65
Dataset
http: http://mistic.heig vd. ch/taillard/ /
problemes. hag.lamms.ddr/rrrddnnnnneeeeee
academic use
ordonnancement..ter html
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:We We present our key contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
34

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We present adequate information in both the main text and Appendix for paper reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer: [Yes]
Justification:
The implementation code and data are included in the Github repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeeee //nips.com htte:/uulllllliiiee/e//eeeuaaass ssiniiiicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Experimental details are presented in both the main text and Appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provided standard error of the results in the main table (Table 1) and error bar in Figure 3(c).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
36

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report computational resources in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader impacts are discussed in Appendix F.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cite the original paper that produced the code package or dataset, and provides the license information in Appendix G.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We include the implementation code and tutorial in the Github repository.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cood/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
39

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
The core methodology and research contributions do not involve LLMs as an original or non-standard component.
Justification:
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
40


Reviews:
[{"review_id": "LOw2dFaYMS", "reviewer": "Reviewer_egzu", "summary": "This paper presents a two-stage fine-tuning framework that turns a 7B-parameter LLM into an end-to-end solver for combinatorial optimization problems. First, SFT teaches solution patterns from solver-generated examples. Second, a feasibility-and-optimality-aware reinforcement learning (FOARL) stage uses a combined constraint-satisfaction and optimality reward to correct infeasible outputs. At test time, Best-of-N sampling further improves solution quality. Empirically, the method achieves near-100% feasibility and optimality gaps of 1–8% across seven CO problems on small to medium sized instances, outperforming both general-purpose, reasoning LLMs and previous LLM as optimizer works.", "questions": "1- You compare primarily to NN, FI, sweep, ACO, etc. Why not include modern VRP solvers such as HGS or ALNS, which are widely regarded as state-of-the-art for CVRP? (Similarly for other problems.) Without them, claims of “outperforming problem-specific heuristics” are overstated.\n\n2- Appendix E.1 reports LLM inference times, but you do not compare to MIP solvers like Gurobi/CPLEX on the same tasks. For your instance sizes the exact solutions should be tractable (at least given a target gap@k). Can you provide both solution quality and runtime from a standard solver to justify the benefit of your pipeline?\n\n3- The heuristic features are expert-crafted and problem-specific. How sensitive is your method to the choice or number of such features? How do they affect generalization across problem types if they must be designed by an expert? Could heuristic-feature selection itself be treated as parameter tuning?\n\n4- FOARL improves feasibility, but how does the number or type of constraints affect infeasibility rates? For instance, if you add more constraints (such as time windows or precedence constraints in VRP), does performance degrade gracefully, or not?\n\n5- You evaluate on small/medium/large graphs (Table 2) but, if I understand correctly, always train and test on the same scale. Have you tried training on one size or distribution (e.g., uniform coordinates) and testing on another (e.g., clustered or larger instances) to assess out-of-distribution robustness?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\t\n- First to directly map natural-language CO descriptions to solutions via SFT + RL without intermediate code execution.\n- Solid integration of SFT and RL with a clear mathematical formulation. Introduces FOARL to explicitly enforce constraints in language outputs.\n- Thorough experiments: seven diverse CO tasks, 3 different problem sizes, BoN sampling study, ablations on heuristic features, and runtime breakdown.\t\n- Methodology clearly described; prompt templates, reward definitions, LoRA settings, and problem-instance conversions are fully documented (Sections 4, Appendices A-C).\n- Demonstrates that a relatively small LLM can match or exceed much larger LLMs on CO tasks in feasibility and solution quality.\n\n\nWeakness: \n- Claims of outperforming “problem-specific heuristics” rest on comparisons to simple methods (NN, FI, PS, ACO) rather than modern state-of-the-art metaheuristics (e.g., HGS, ALNS). No justification is given for excluding these stronger baselines.\n-The description of “heuristic features” (e.g., top-k nearest neighbors) is brief and lacks detail on selection rationale or how different feature choices affect performance and generalization. \n- The paper does not benchmark against exact solvers (e.g., Gurobi, CPLEX) on any task, leaving it unclear when one would prefer this approach over off-the-shelf MIP solvers.\n- For the problem sizes addressed, the computational efficiency might still be lower than both classical heuristics and MIP solvers, raising doubts about practical value. Further experiments are needed.", "was_revised": true, "final_justification": "The proposed LLM-as-solver method is not competitive with (1) general-purpose solvers or (2) problem-specific SOTA heuristics, and its scalability is limited (e.g., fails on 1,000-node TSP with huge gaps) \n\nHowever, the stated goal is not to replace specialized/general solvers for complex, professional-grade problems, but to assist non-experts with simpler, everyday optimization tasks.\n\nWithin this scope, the results are significant:\n\n- The method clearly outperforms prior LLM-as-solver approaches. Better gaps and larger problems.\n- Rebuttal experiments show it also surpasses “model-then-solve” methods with similar aims.\n\nOverall, this is a clear step forward in LLM-as-solver research and merits publication.", "rebuttal": "Dear Reviewer egzu,\n\nThank you for the valuable comments and for recognizing the solid methodology, thorough experiments, and clear description in our paper. We will address your concerns below.\n\n**[W1.1., Q1] No justification is given for excluding stronger baselines (e.g., HGS, ALNS)**\n\nThanks for raising the point. We acknowledge the strength of advanced metaheuristics like HGS, which are highly effective for specific problems and often used to generate (near-)optimal reference solutions in previous literature. However, their specialization limits their versatility compared to our approach. Our goal is not to outperform these specialized algorithms in terms of raw solution quality. Some of them, such as LKH for TSP, are actually used in our pipeline to generate high-quality data for training. Rather, we aim to show that LLMs can learn to serve as *general-purpose, end-to-end, language-driven CO solvers*, without requiring problem-specific algorithm design, expert-crafted heuristics, or specialized solver integration.\n\nSince our method does not yet outperform top metaheuristics in optimality, we focused on widely used heuristics that better **reflect the trade-offs between solution quality, generality, and human effort**. Thus, we used “problem-specific heuristics” instead of “problem-specific metaheuristics”. To the best of our knowledge, this already marks a significant step forward for LLMs in addressing CO problems, while prior approaches have not even surpassed simple heuristics [1,2].\n\nHowever, for your information, we have evaluated some advanced metaheuristics or local search methods. We evaluate LKH for TSP, HGS for CVRP, EA4OP for OP, and QIG for PFSP. Due to the lack of open-source implementations or widely used SOTA heuristics, we use Gurobi for MIS, MVC, and JSSP. The results are summarized below (in the form of opt.(time)):\n\n|                           |       TSP    |    CVRP   |       OP      |       MIS      |    MVC      |   PFSP  |    JSSP   |\n|----------------------|---------------|---------------|---------------|----------------|---------------|--------------|-----------|\n| SOTA method   |0.00%(0.3)|-0.19%(1.2)| 1.60%(0.3)|0.00%(1.0)|0.00%(1.0)|0.00%(2.0)|2.45%(10.0)|\n|         Ours        |1.07%(11.7)|4.53%(11.3)|1.85%(10.8)|1.04%(4.0)|1.29%(7.1)|1.03%(3.1)| 8.20%(20.7)|\n\n\n**W1.2. The description of “heuristic features” is brief and lacks detail on selection rationale**\n\nThe heuristic features in our work are deliberately simple, and aligned with domain knowledge to guide LLMs toward promising regions of the solution space, without relying on explicit multi-step reasoning or solver-specific templates. Broadly, they reflect **standard greedy principles** found in traditional heuristics. For example, the features often mirror decisions a classical greedy solver would make at each step. Our selection is guided by two main reasons:\n\n(1) **They are easily computable and widely used in classical heuristics**. For example, top-k nearest neighbors are often used in a well-established greedy strategy for routing, while top-k jobs with the shortest processing times are commonly used in scheduling problems. These features embody canonical greedy schemes that are efficient and effective in many practical scenarios.\n\n(2) **They are naturally compatible with the language modality**. Unlike complex heuristics (e.g., metaheuristics), which are difficult or inefficient to encode in text, our greedy cues can be expressed briefly by text. This ensures they can be included in the LLM input without significant token overhead or representational ambiguity.\n\n**[W2., Q2] The paper does not benchmark against exact solvers**\n\nWe agree that comparing against exact solvers is valuable for practitioners to better understand the trade-offs. To this end, we benchmark the CO tasks in our paper using Gurobi. We report results with time limits of 1s and 10s, with the latter roughly matching the average computation time of our method. The results are summarized below:\n\n| Method           |   TSP  |   CVRP |     OP    |    MIS   |   MVC   |  PFSP  |  JSSP  |\n|--------------------|----------|------------|------------|-----------|-----------|-----------|-----------|\n| Gurobi (1s)     | 5.76% |         -    | 49.42% |  0.00% |  0.00% |  2.28% | 41.34%|\n| Gurobi (10s)   | 1.82% | 35.09% | 21.96% |  0.00% |  0.00% |  0.46% |  2.45% |\n| Ours               | 1.07% |  4.53%  | 1.85%   |  1.04% |  1.29% |  1.03% |  8.20% |\n\nAs expected, Gurobi performs very well on certain problems, particularly MIS and MVC, where the MIP formulations are tight and effective. However, on more complex problems like routing, our method significantly outperforms Gurobi **under similar time budgets**. Notably, our model achieves nearly **8× smaller optimality gaps** than Gurobi on CVRP (4.53% vs. 35.09%) and solves OP with far better quality.\n\nImportantly, our method offers several advantages: 1) **Ease of use**: there is no need for formal modeling, solver licenses, or programming interfaces. 2) **Language-driven interaction**: users can specify problems in natural language, making it more accessible for non-experts. 3) **Generalizability**: a single model architecture handles diverse problems without customization. While **exact solvers remain preferred in applications demanding guaranteed optimality** with long runtime, our method offers a compelling alternative when flexibility or rapid prototyping is prioritized.\n\n**W3. The computational efficiency might still be lower than both classical heuristics and MIP solvers**\n\nIndeed, constructive heuristics like NN are extremely fast, often producing solutions within 1s. However, as shown in Table 2, our method significantly outperforms them in solution quality. For instance, on large-graph TSP, our model achieves nearly 20× smaller optimality gaps compared to NN. This suggests that the modest trade-off in inference time yields substantial gains in solution quality.\n\nWe have also compared our model against Gurobi (see the response to W2), and the results show that, under a similar time budget, our method delivers comparable or even better performance on certain tasks.\n\nIt is also important to note that the core contribution of our paper is not superior efficiency, but the introduction of a unified, language-based paradigm for CO. Unlike traditional solvers, our approach requires no problem modeling or coding, and can generalize across problems using a single fine-tuned model.\n\n**Q3. The effect of heuristic features**\n\nIndeed, there is a trade-off between the number of heuristic features and the performance of the model. While incorporating more features may improve solutions, it also increases input length, leading to higher token usage and training cost. In this sense, feature selection can **indeed be treated as a form of parameter tuning**, as you noted.  In Appendix E.4, we presented an ablation analysis to study the performance with and without these features. Taking TSP as an example, we further study the impact of different numbers of heuristic features: We vary the value of k from 0 to 2, and the optimality gaps are [1.17%, 1.10%, 1.07%], while the training time (min) per 1K instances are [75, 112, 150].\n\n**Regarding generalization**: our features represent **simple greedy patterns**, such as NN relationships in routing or shortest processing times in scheduling, which are well-known, easy to compute, and generally applicable. As such, incorporating them does not require much domain expertise.\n\n**Please note: **even** without these features**, our model still outperforms all general-purpose LLMs.\n\n**Q4. FOARL improves feasibility, but how does the number or type of constraints affect infeasibility rates**\n\nThis is a very insightful question. Our current study focuses on a set of well-established problems that include common constraint types (e.g., capacity constraints in CVRP).  We emphasize that these NP-hard problems are more difficult than some previous benchmark studies, and this shows an impressive improvement of LLM in solving intractable problems.\n\nDue to the time limitations of the rebuttal phase, it is not feasible to generate new datasets and retrain models for tasks with more and diverse constraints. But we are happy to explore this in future work. \n\nWe also recognize that different constraint types, such as arithmetic, logical, or global constraints, may pose varying levels of difficulty for LLM reasoning and RL-based correction. Exploring constraints themselves can be an independent work, which is a bit out of the scope of this work. \n\nFrom our current results, we observe that FOARL improves feasibility, especially on problems with inequality-type constraints, such as in OP and CVRP. As discussed in Section 5.4, we find that RL plays a role similar to a constraint relaxation mechanism, guiding the model toward feasible regions even when initial generations are suboptimal. We believe the discussion there already offers some insights on the influence of constraints.\n\n**Q5. OOD performance**\n\nWe agree that OOD performance is important for a CO solver. To this end, we evaluate the models on routing problems with two OOD distributions, namely cluster and mixed distributions [3]. We set the number of clusters to 7, and the results are summarized below, indicating that our models still perform well when there is a distribution shift.\n\nmetric              | tsp-fea.      | tsp-opt.       | op-fea.     | op-opt.       | cvrp-fea.     | cvrp-opt. \n---------------------|----------|------------|----------|------------|----------|------------\nIn-distribution          | 100%     | 1.07%      | 100%     | 1.85%      | 100%     | 4.53%\nOOD (clustered)     | 100%      | 1.41%      | 100%     | 1.89%      | 100%     | 5.12%\nOOD (mixed)          | 100%     | 1.23%      | 100%     | 2.30%      | 100%     | 5.04%\n\n**We will incorporate all the results and discussion above into the paper for clarity.**"}, {"review_id": "OgwVABIwj5", "reviewer": "Reviewer_umUz", "summary": "This paper introduces a novel framework that employs LLMs as end-to-end solvers for combinatorial optimization problems. The method involves a two-stage training process: (1) supervised fine-tuning to predict solutions, followed by (2) a reinforcement learning phase that is explicitly aware of feasibility and optimality to reduce constraint violations and improve performance. The approach demonstrates strong results across seven benchmark datasets, outperforming the considered baselines.", "questions": "1. For fair comparison, should all LLM-based methods enforce equal sampling with the same N? It is better to explicitly report how many samples are generated per instance, whether BoN is used, and if multi-round prompting (e.g., OPRO, PHP) is applied.\n2. In Appendix E.7, do the baseline methods leverage any prior information from the generated seven COP datasets?\n3. Only 5 instances from TSPLIB are used for out-of-distribution experiments in Appendix E.7. These are relatively small-scale, while the paper claims to address scalability up to 100 nodes. Should all TSPLIB instances that meet certain criteria be considered for testing, instead of using only selected examples?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1. The approach enables LLMs to solve COPs directly from natural language problem descriptions, eliminating the need for custom solvers or intermediate code-generation pipelines.\n\n2. The method achieves strong performance across seven COP datasets, compared to the considered baselines.\n\n3. It has a comprehensive experimental scope, including ablations, sensitivity, and generalization.\n\n\n\n\n\n**Weaknesses:**\n\n1. Unfair comparison: It appears that the LLM-based baselines do not utilize prior information from the generated COP datasets, whereas the proposed method does (by fine-tuning). The authors may clarify on the fairness and rationale of this comparison.\n\n2. Limited baselines: Among LLM-based methods, only OPRO is included as a baseline, despite the existence of other relevant approaches treating LLMs as end-to-end solvers (lines 87-90). The authors should justify the exclusion of these methods. Additionally, for domain-specific baselines, it is unclear why state-of-the-art solvers like Gurobi and LKH3 (which are used for label generation) are not included for comparison.", "was_revised": true, "final_justification": "The rebuttal has addressed all of my concerns. I acknowledge the empirical improvements and the contributions to LLM-based optimization solvers.", "rebuttal": "Dear Reviewer umUz,\n\nWe sincerely appreciate your recognition of our study’s motivation, strong performance, and comprehensive experiments. Thank you for your thoughtful feedback, and we hope the responses below address your concerns effectively.\n\n**W1. Unfair comparison: It appears that the LLM-based baselines do not utilize prior information from the generated COP datasets.**\n\nThank you for raising this concern. While the general-purpose LLM baselines (e.g., GPT-4o) are not fine-tuned on our generated datasets, we ensure fairness by using a one-shot prompting strategy. Specifically, each model receives a randomly selected instance and its feasible solution as an example before solving a test instance (see lines 780–787). This provides task-relevant guidance and avoids a purely zero-shot setup, aligning with the models' intended inference usage.\n\nThis evaluation approach follows common practice in the LLM literature, especially for cross-domain applications where fine-tuned task-specific models are compared with general-purpose foundation models. For example, [1] compares a fine-tuned LLaMA-2 13B with GPT models for biomedical NLP, and [2] contrasts a fine-tuned model on graph computation with GPT under zero-/few-shot prompting.\n\nWe agree that leveraging prior knowledge from training data could further improve LLM-based baselines. To explore this, we implemented a **retrieval-augmented generation (RAG)** variant for two strong LLMs: Claude-3.7-Sonnet and GPT-4o. Taking TSP, CVRP, and MVC as examples, we built an RAG memory using 3,200 randomly selected training instances per task and used the top retrieved example to guide generation. This allows the model to draw from prior examples in a way conceptually similar to fine-tuning, without modifying model weights. The results are shown in the table below (in the form of fea.(opt.)).\n\n| Method                        |          TSP       |        CVRP      |        MVC       |\n|------------------------------ |--------------------|--------------------|-------------------|\n|    GPT-4o (RAG)         | 35% (43.42%) | 30%(50.16%) | 7% (11.11%)  | \n| Claude-Sonnet (RAG) | 67%(27.14%) |  35%(35.20%)   |  3% (8.47%)  |\n|           Ours                  | 100%(1.07%)  | 100%(4.53%) |100%(1.85%) | \n\nEven with RAG, general-purpose LLMs still fall short of our method. This underscores our key contribution: a fine-tuned, lightweight LLM can outperform larger general models regardless of training data access, due to its task-aligned optimization. To our knowledge, this is the first work to fine-tune an LLM for directly solving diverse CO problems from natural-language descriptions.\n\n**W2. Only OPRO is included as a baseline, despite the existence of other approaches(lines 87-90). Additionally, it is unclear why solvers like Gurobi and LKH are not included**\n\nThank you for the thoughtful comment. We address both aspects below.\n\n**LLM-based end-to-end solvers:**\n\nWe reviewed the relevant literature and cited key works (lines 87–90). Two are benchmarking studies evaluating general-purpose LLMs on small or synthetic CO tasks using zero-/few-shot prompting—aligned with our baselines (e.g., GPT-4o, Claude, DeepSeek), which we evaluate using consistent one-shot prompting for fairness.\n\nA nice recent work, [35], uses “graph thought” reasoning for small TSP instances (10–20 nodes) but reports a 3.6% optimality rate. In contrast, our method solves 96% of TSP instances at this scale within 1% optimality gap, showing significant gains. Additionally, [35] does not release code or models, preventing direct comparison.\n\nOPRO [19] and LMEA [34] represent two distinct strategies: OPRO treats LLMs as verbal optimizers using prompt gradients, while LMEA uses LLMs as evolutionary operators. Both were originally developed for TSP. In our work, we extended OPRO to all 7 CO tasks. To strengthen the comparison, we further adapt LMEA to the same task suite.\n\nIn each LMEA generation, the LLM selects parent solutions from the population and performs crossover and mutation via prompting. We designed tailored prompt-based operators to handle the differing solution structures across CO problems. As shown in the table below (reported as fea.(opt.)), our models still significantly outperform LMEA across all tasks.\n\n|Method|        TSP     |       CVRP     |         OP       |       MIS     |       MVC      |        PFSP     |     JSSP      |\n|----------|-----------------|------------------|------------------|---------------|------------------|-------------------|-----------------|\n| LMEA | 77%(265%) |24%(61.24%)|48%(66.18%)|5%(25.0%)|13%(34.22%)|98%(14.31%) | 44%(83.19)|\n| Ours  | 100%(1.07%) |  100%(4.53%)  | 100%(1.85%)   |  94%(1.04%) |  100%(1.29%) | 100%( 1.03%) |  100%(8.20%) |\n\n**Domain-specific solvers:**\n\nWe agree that comparing with traditional solvers is important, as also requested by Reviewer egzu. We compare our method with leading domain-specific (meta)heuristics and Gurobi. We evaluate LKH for TSP, HGS for CVRP, EA4OP for OP, and QIG for PFSP.  The results are shown below in the form of opt.(time). Notably, our method achieves better performance than Gurobi on routing problems with a similar time budget.\n\n|                           |       TSP    |    CVRP   |       OP      |       MIS      |    MVC      |   PFSP  |    JSSP   |\n|--------------------|---------------|---------------|---------------|----------------|---------------|--------------|-----------|\n| SOTA method |0.00%(0.3)|-0.19%(1.2)| 1.60%(0.3)|       -          |          -       |0.00%(2.0)| - |\n| Gurobi |1.82%(9.3)| 35.09%(9.8 )|21.96%(9.8)|0.00%(1.0)|0.00%(1.0)|0.46%(9.3)|2.45% (10.0)|\n|         Ours      |1.07%(11.7)|4.53%(11.3)|1.85%(10.8)|1.04%(4.0)|1.29%(7.1)|1.03%(3.1)| 8.20%(20.7)|\n\nHowever, we emphasize that the goal of our work is not to surpass all the state-of-the-art solvers. While our method may not outperform highly specialized algorithms, it offers a **user-friendly, language-driven interface** that requires **no coding or domain-specific formulations**. Though it may not always match the optimality of LKH or Gurobi, it delivers strong performance with high feasibility, low optimality gaps, and broad generalizability across multiple CO tasks.\n\n**Q1. Should all LLM-based methods enforce equal sampling with the same N? It is better to explicitly report how many samples are generated per instance, whether BoN is used, and if multi-round prompting (e.g., OPRO, PHP) is applied.**\n\nIn our experiments, the general-purpose and reasoning LLMs are configured to generate a single solution per instance, aligning with our SFT+RL method, which also produces **one generation without BoN**.  Therefore, the equality holds for the sampling budget of the LLM-based methods. Given the equality, our method achieves significantly better performance in both feasibility and optimality, as shown in Table 1. This indicates that our fine-tuned model not only performs well under equal constraints but also provides robust solutions without relying on test-time sampling tricks.\n\nFor the prompting strategies, we have indicated their settings in Appendix D. For example, OPRO runs 4 iterations, generating 5 random solutions each (20 total). They inherently perform multi-round or multi-sample generation, so we do not apply BoN. Despite their extensive exploration, our one-shot SFT+RL model still significantly outperforms them in solution optimality, showing the power of end-to-end learning over handcrafted prompting.\n\nTo further address your concern, we also conducted a BoN vs. BoN comparison using DeepSeek-R1, the strongest reasoning model baseline. The results below show that with 8 samples per instance for both models, our method still outperforms DeepSeek-R1:\n\n|           Method       |        TSP       |        OP        |       CVRP       |        MIS       |     MVC      |      PFSP    |       JSSP     |\n|-------------------------|-------------------|-----------------|--------------------|------------------|----------------|---------------|---------------|\n| DeepSeek + BoN |75%(55.43%)|68%(41.73%)| 44%(32.65%) | 62%(1.81%) |51%(4.02%)|  100%(13.31%) | 10%(25.20%)|\n|            Ours          | 100%(1.07%) |  100%(1.85%)  | 100%(4.53%)   |  94%(1.04%) |  100%(1.29%) | 100%( 1.03%) |100%(8.20%) |\n\n**Q2. In Appendix E.7, do the baseline methods leverage any prior information**\n\nThere are three types of baselines involved in this section: 1) heuristics (e.g., FIFO and ATC), 2) evolving-based heuristics (e.g., ReEvo and MCTS-AHD), and learning-based methods (e.g., L2D and StarJob). \n\nAmong these, the **evolving-based** and **learning-based** methods do leverage prior training data. Specifically, evolving-based methods such as ReEvo and MCTS-AHD use LLMs to generate algorithmic components, which are then evaluated on a training set to compute fitness scores during evolution. This means their algorithmic design is explicitly influenced by performance on prior instances.  Learning-based methods such as L2D and StarJob train neural models or LLMs on large synthetic CO datasets via supervised or reinforcement learning, deeply tying them to training data. It means all the baseline methods are benefiting from prior knowledge of the instances. Despite this, our method still outperforms them all.\n\n**Q3. Should all TSPLIB instances that meet certain criteria be considered**\n\nIn our experiments, we select TSPLIB instances with fewer than 100 nodes and EDGE_WEIGHT_TYPE = EUC_2D, i.e., defined by 2D Euclidean coordinates. We exclude instances without this property (e.g., non-Euclidean or distance-matrix-only) because our model is trained on continuous 2D coordinates.\n\nHowever, training a similar model using **distance matrices** is also possible by adapting input representations or fine-tuning a model variant on such data. We see this as a promising direction for future work, especially for generalized TSP variants and real-world cases lacking coordinate data"}, {"review_id": "WsiQ6UDWKh", "reviewer": "Reviewer_qC4e", "summary": "The paper fine-tunes a Qwen-2.5 model to act as an *end-to-end* solver for seven standard NP-hard combinatorial-optimization (CO) tasks (TSP, OP, CVRP, …), using two stages: (1) supervised fine-tuning (SFT) on solutions produced by classical solvers and (2) a feasibility-/optimality-aware RL phase (FOARL). A Best-of-N decoder is applied at inference. Training relies onsynthetic instances per problem and achieves 1 – 8 % average optimality gaps while remaining slower than lightweight heuristics.", "questions": "1. What is the wall-clock latency of SFT+RL+BoN on problems with 1 000+ nodes, and how does that compare with OR-Tools?\n\n\n2. FOARL appears to give small gains; did the authors try simply weighting feasibility in the loss during SFT?", "limitations": "I think the biggest limitation is that there exists no real-world application scenario that pushes experts/practitioners to apply LLM to solve a CO problem. I don't see the benefit of motivation of the research. Please feel free to correct me if the claim above makes a mistake.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n* Extensive quantitative tables comparing against large general-purpose LLMs and several prompt-engineering baselines;\n\n**Weaknesses**\n\n* [Crucial]**No practical application scenario.**  I see no real-world application scenario that requires LLMs to solve CO problems. Why don't people work on domain-specific models/heuristics?\n\n* **Only one base LLM is actually trained.** The core results rely on Qwen-2.5-7B; the versatility check with a tiny 8 B LLaMA is relegated to an appendix. Generality across architectures and scales therefore remains unproven;\n\n\n* **Efficiency gap acknowledged by the authors.** Even after LoRA and BoN sampling, the method is “not yet on par with traditional lightweight heuristics”, undermining its value as a drop-in solver.;\n\n* **Marginal contribution of RL.** Table 1 shows RL changes feasibility but barely improves optimality; ablations suggest most quality comes from brute-force BoN decoding, not from the proposed FOARL.;\n\n* **Limited insight that SFT helps.** It is unsurprising that imitating expert solutions boosts an LLM; the paper does not illuminate *why* language modelling is preferable to standard neural CO architectures.", "was_revised": true, "final_justification": "Please refer to the final response to the authors.", "rebuttal": "Dear Reviewer qC4e,\n\nThanks for acknowledging the comprehensive experiments in our work. We appreciate your feedback and hope the responses address your concerns.\n\n**W1. No practical application scenario.**\n\nWe agree that domain-specific methods have long been, and will continue to be, the backbone of high-performance solvers. However, our work is motivated by **a growing need for generality, flexibility, and usability** in real-world decision-making, especially in scenarios involving: 1) **non-expert users**, 2) **costly or impractical solver integration**, and 3) **fast prototyping needs**.\n\nA core belief motivating this work is that **“not everyone has domain expertise or can code, but everyone may have a need to solve optimization problems”**. As LLMs become increasingly embedded in personal assistants, the ability to solve CO problems via natural language becomes **practically valuable**. For example, a user might request a travel plan that includes several tourist destinations, which naturally maps to TSP. Another user might explore social network dynamics or citation patterns between research papers, which can be framed as MIS. In these cases, an LLM can interpret the request and produce solutions—all through natural language, making CO accessible to non-experts without code or formal modeling.\n\nMeanwhile, recent works increasingly explore **language-to-optimization pipelines** that align closely with the vision of this paper. For example, benchmark datasets such as EHOP [1] frame everyday NP-hard problems from natural language, while GraphArena [2] evaluates LLMs on CO tasks over real-world graphs. Beyond benchmarks, there is a growing body of work focused on developing LLM-based CO solvers—e.g., a recent Google DeepMind paper [3] studies LLMs for TSP. Furthermore, a systematic review [4] has identified **broad recent progress in LLMs for CO**, reflecting the growing interest from both academic and industrial communities.\n\nWhile researchers will, and should, continue to develop specialized solvers, we emphasize that there is **no conflict** between these methods and LLM approaches. Our goal is not to replace the solvers but to **complement** them by exploring LLMs as language-driven optimizers, particularly in interactive, no-code settings where traditional solvers may be hard to integrate or inaccessible to non-experts.\n\nWe believe our motivation is well-founded, supported by both **practical application scenarios** and a rapidly **growing body of research in this area**. Extensive experiments show our method outperforms all LLM baselines, proving fine-tuned LLMs can be effective end-to-end solvers and enable a more accessible CO approach.\n\n**W2. Only one base LLM is actually trained**\n\nThe main results are indeed based on Qwen-2.5, chosen for its strong open-source performance. However, we agree that generality across architectures is important. To this end, we include additional results with LLaMA3.1 in Appendix E.6, which already show that our method remains effective even with a different backbone.\n\nTo further verify generality across architectures, we fine-tuned a third model (Mistral-7B-Instruct-v0.3) on two representative tasks (CVRP and PFSP) for 10,000 steps within the limited rebuttal period. The results are shown below:\n\n|                 |  CVRP |   PFSP  |\n|------------- |-----------|------------|\n|      fea.     |   95%   |   100%  | \n|      opt.     |  6.25% |  1.89%  | \n\nThese results show our method **retains its effectiveness on Mistral**, reinforcing its versatility. Due to time constraints, we couldn’t run full experiments across all tasks and LLMs during rebuttal.  However, **we commit to including results on other LLMs in the final paper.**\n\n**W3. Efficiency gap is acknowledged by the authors**\n\nWe fully acknowledge that traditional heuristics are efficient, often generating solutions in seconds. However, as shown in Table 2, our method yields much better quality. For example, on large-graph TSP, our model produces solutions with **nearly 20× smaller optimality gaps** than the NN heuristic.\n\nWhile not as fast as traditional heuristics, our method **consistently outperforms** them on Gap@K across all tasks. Importantly, our objective is not to develop a one-size-fits-all solver that dominates in every metric, but to introduce a language-based paradigm that broadens access and enables end-to-end optimization via natural language.\n\nWe see our method as a complementary alternative, particularly valuable in **language-driven or no-code environments**, not a direct replacement for traditional heuristics in latency-critical tasks. We recognize that efficiency remains an open challenge, and we are actively exploring directions such as **compact TAI representations** and **optimized LLM inference techniques** (e.g., quantization, distillation) to narrow this gap in future work. Meanwhile, the value of this work lies in advancing LLMs for NP-hard CO, where prior methods struggled, delivering the first end-to-end LLM framework with notable performance gains, which is an important step for the field.\n\n**W4. Marginal contribution of RL**\n\nWe highlight that Table 1 shows FOARL does lead to explicit improvements in optimality across 4 tasks (e.g., 1.71%-1.34% on MIS). While the gains in optimality alone may appear modest, we emphasize that the **primary motivation** of FOARL (as described in lines 182–193) is to **mitigate the over-greedy behavior of SFT** and improve feasibility on certain tasks.\n\nIn this regard, FOARL delivers clear and significant benefits: feasibility rises from **54% to 92% on OP and 59% to 80% on CVRP**. We believe this is a non-trivial and impactful gain, as infeasible solutions are unusable in practice, no matter their objective quality.\n\nWe also acknowledge the effectiveness of BoN as a test-time enhancement. However, FOARL works during training to improve model behavior in **single-shot generation**, adding no inference-time cost, while BoN requires multiple samples and extra latency. As detailed in Section 5.4, FOARL acts as a *constraint relaxation operator* and *sampling efficiency booster*, enhancing generation quality even before BoN is applied (see Figure 3).\n\n**W5. Unsurprisingly, imitating experts boosts an LLM; why language modelling is preferable to NCO**\n\nWe emphasize that **achieving strong CO capabilities through language modeling alone is far from trivial**. Prior work (e.g., [2]) shows SFT helps only on small-scale graphs. In contrast, we show that SFT enables LLMs to generalize to diverse, larger CO problems, positioning them as viable general-purpose CO solvers—a capability not previously demonstrated at this scale.\n\nImportantly, our contributions go beyond simply applying SFT. We **identify an underexplored limitation** of imitating solutions using SFT: its **over-greedy behavior**, which leads to infeasibility on constrained tasks. To fix this, we introduce FOARL, which significantly improves feasibility and overall performance. This highlights that language modeling for CO not only works but also presents **distinct challenges** that we explicitly study.\n\nWe clarify that our goal is **not to replace standard neural CO**, which remains strong in scalability and performance. Rather, we aim to **establish a new, complementary paradigm**, where LLMs serve as accessible, language-driven solvers. This is especially compelling because **natural language serves as a unified interface** for describing various CO problems, enabling a single model to operate across tasks without task-specific architectural changes. We have seen LLMs are reforming different domains, equipping traditional learning paradigms with the unified representation power and user-friendliness of natural language (e.g., automated driving [6], recommendation systems [7]). This work falls in such efforts, offering an early step toward end-to-end LLM solvers.\n\n**Q1. What is the wall-clock latency on problems with 1 000+ nodes, and how does that compare with OR-Tools?**\n\nCurrent LLM architectures are not well-suited for directly handling such large-scale CO problems, primarily due to input length limitations. We note that prior LLM-based work mostly targets small instances (10–30 nodes) [2, 3, 5], while our work advances them by scaling to 100-node problems, which we believe is a significant step forward in extending the potential of LLM in solving NP-hard problems.  \n\nTo explore the scalability of our approach, we ran an **exploratory experiment** during the rebuttal. We generated 2,000 TSP instances with 1,000 nodes (noting the high cost of generating pseudo-optimal labels) and fine-tuned a 7B LLM. After fine-tuning, the model produced fully feasible solutions with an average inference time of ~3 minutes (no BoN). For reference, OR-Tools solves these instances in a similar time with ~10% optimality gap.\n\nThese early results suggest that, while LLMs are **not yet practical drop-in replacements** for very large-scale CO, they may still produce competitive solutions with further training, while the training may require more data for supervision. This paper offers the first end-to-end LLM approach for CO on problems larger and more complex than prior work [2,3,5]. Improving efficiency and scaling LLM-based solvers to large instances remains an open challenge we plan to pursue in future work.\n\n**Q2. Did the authors try simply weighting feasibility in the loss during SFT?**\n\nWe agree that adding feasibility to the SFT loss is intuitive, but this would be insufficient to address the feasibility challenge. **SFT operates under a teacher-forcing regime** and exposes the LLM only to feasible solutions, limiting its ability to recover from infeasible ones. Thus, it lacks the **exploration capability** needed to correct feasibility errors at inference time. FOARL, however, lets the model sample outputs, get feasibility feedback, and adapt its policy. We believe this again highlights RL's necessity."}, {"review_id": "QtBKGhfXnq", "reviewer": "Reviewer_u6T1", "summary": "The authors leverage supervised fine-tuning (SFT) and reinforcement learning (RL) techniques to post-train a Qwen2.5-7B model for end-to-end combinatorial optimization (CO).\nProblem instances with best known solutions are converted into text descriptions using the TAI tool, and the Qwen model is fine-tuned to generate solutions directly from these textual inputs. The RL phase incorporates feasibility and optimality rewards within the GPRO framework. Empirical results demonstrate surprisingly strong performance compared to other LLMs and heuristic baselines.", "questions": "1. Since the paper does not emphasize the LLM’s reasoning process, what explains its strong performance? Have you compared against supervised GNN-based methods to provide further context?\n\n2.  How well does the method generalize to unseen problem classes? Could the TAI tool be extended to other combinatorial optimization tasks?\n\n3. In Table 2, the label \"ours\" is ambiguous—does it refer to the SFT-only model, RL-finetuned version, or an ensemble?\n\nOther comments:\n\n1. Some key messages in the main results could be highlighted more clearly.\n2. In line 269, the authors should provide additional supporting evidence for their claim: \"While such approaches (reasoning models) may work for very small-scale instances (e.g., fewer than 10 nodes), it becomes impractical to reason clearly and effectively as instance size grows.\"", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- Extensive experiments and strong empirical performance\n- Clear and well-written paper, easy to follow.\n\n**Weaknesses**\n- The model with optimality gaps of 1.03-8.20% is not end-to-end to me. \n- Generalizability to OOD instances is unclear (no systematic evaluation).\n- Lack of interpretability—no insights into how the model derives predictions.", "was_revised": true, "final_justification": "The strong performance in the OOD case is added. However, the model's prediction is still a black-box, and it is still not clear why the LLM performs so well. Given the strong empirical performance, I will keep my score.", "rebuttal": "Dear Reviewer u6T1,\n\nWe would like to thank the reviewer for recognizing the comprehensive experiments, strong performance, and clear writing of our paper. We believe the feedback from the reviewer is valuable for improving our paper, and we will address the raised concerns below.\n\n**W1. The model with optimality gaps of 1.03-8.20% is not end-to-end to me.**\n\nThank you for the question. The model achieves optimality gaps of 1.03-8.20% was trained through SFT and RL, and we used BoN for scaling test-time inference. We acknowledge that the use of BoN during inference might give the impression that the model is not strictly \"end-to-end.\" However, it is important to clarify that our model remains fully language-driven: it takes natural language as input and produces a complete solution in natural language, **without invoking any external solver, code execution, or symbolic post-processing**.\n\nThe BoN strategy simply samples multiple outputs from the same LLM, selecting the best one based on a predefined metric (e.g., cost or feasibility). This is a standard inference enhancement used widely in LLM research to boost performance at test time and does not compromise the end-to-end nature of the model. Therefore, we view our method as end-to-end within the language modeling paradigm: the model is trained and deployed to generate solutions directly from natural language descriptions, with no intermediate calls to optimization solvers or algorithmic modules.\n\n**W2. Generalizability to OOD instances is unclear.**\n\nThank you for pointing this out. We fully agree that evaluating OOD generalization is critical for assessing the practical utility of a CO solver. To address this, we conducted additional experiments on routing problems using two commonly adopted OOD settings: the clustered and mixed spatial distributions, as described in [4]. For the clustered case, we used 7 clusters per instance to create a challenging shift from the uniform training distribution.\n\nThe results are summarized below and show that our model **maintains strong performance and feasibility under these distributional shifts**, demonstrating its ability to generalize beyond the training regime. We will include these findings in the final version of the paper to provide a more systematic evaluation of our method’s cross-distributional generalizability.\n\nmetric          | tsp-fea.      | tsp-opt.       | op-fea.     | op-opt.       | cvrp-fea.  | cvrp-opt. \n--------------|----------|------------|----------|------------|----------|------------\nIn-distribution          | 100%     | 1.07%      | 100%     | 1.85%      | 100%     | 4.53%\nOOD (clustered)     | 100%      | 1.41%      | 100%     | 1.89%      | 100%     | 5.12%\nOOD (mixed)          | 100%     | 1.23%      | 100%     | 2.30%      | 100%     | 5.04%\n\n\n**W3. Lack of interpretability—no insights into how the model derives predictions.**\n\nWe agree that interpretability is a critical concern, especially for decision-making scenarios in CO. While our current work primarily focuses on demonstrating the viability of a language-driven paradigm for solving CO problems, we fully recognize the value of understanding how and why the model arrives at particular predictions.\n\nLLMs are often viewed as black-box models, making interpretability challenging. However, our framework opens several promising directions for future interpretability analysis. For example, techniques such as attention visualization, saliency mapping, or input perturbation studies could be used post hoc to probe the model’s internal decision mechanisms. In addition, because our model operates entirely in natural language, it inherently provides human-readable inputs and outputs, which can serve as a starting point for qualitative inspection.\n\nWe will explicitly acknowledge this limitation in the revised paper for readers to explore it more systematically in future work.\n\n**Q1. Since the paper does not emphasize the LLM’s reasoning process, what explains its strong performance? Have you compared against supervised GNN-based methods to provide further context?**\n\nThank you for the insightful questions. While explicit reasoning, such as chain-of-thought (CoT), has shown success in many NLP tasks, it becomes limited when it attempts to simulate structured search over large, discrete spaces. It is revealed that explicit reasoning may not be the best solution due to the constraints of the language representation space, since long CoT can be verbose and assigns uniform computation to all tokens, and struggles with scalability [1]. This is particularly true of domains like CO, where the solution space grows combinatorially.\n\nInstead of relying on explicit CoT, our method learns to imitate expert behavior from domain-specific solvers and enhances solution space exploration using lightweight heuristic features embedded directly into the natural language input. This approach enables the model to bypass rigid step-by-step reasoning while still achieving strong performance, particularly in terms of feasibility and optimality on complex CO tasks.\n\nRegarding the second part of your question, we agree that comparing with graph-based neural methods, such as GNNs, would provide valuable context. To that end, we conduct a comparison with two well-known architectures: **Graph Convolutional Networks (GCN)** [2] and **Graph Attention Networks (GAT)** [3], on 300 uniformly distributed TSP instances. The results are compared in the Table below. Despite these models having direct access to numerical graph inputs, our language-based model outperforms both GCN and GAT, further highlighting the capability of LLMs as general CO solvers, even when operating solely in the language domain.\n\n|                 |  GCN   |    GAT  |   Ours |\n|------------- |-----------|-----------|----------|\n|      opt.     | 3.10%  | 1.76% | 0.71% | \n\n**Q2. How well does the method generalize to unseen problem classes? Could the TAI tool be extended to other combinatorial optimization tasks?**\n\nGeneralization to unseen problem classes is indeed an important consideration. In our current framework, generalization is feasible when the new task **shares similar structural properties** with those the model was trained on.\n\nFor example, we tested the model trained on OP instances on an unseen task: Prize-Collecting TSP (PCTSP). While PCTSP introduces a different objective: minimizing tour length plus penalties for skipped nodes while meeting a prize quota, it still shares a similar routing structure with OP. On 100 small-scale PCTSP instances (with a node-skip penalty of 1000), our model with BoN sampling achieved 100% feasibility and 24.59% optimality, outperforming GPT-4o, which reached only 68% feasibility.\n\nHowever, this form of transferability relies on a shared solution structure. If the new problem is fundamentally different, e.g., shifting from routing to scheduling, the model's performance naturally degrades. Exploring this broader generalization frontier is an exciting direction, and as part of our future work, we plan to develop a benchmark that systematically tests LLMs' generalizability across diverse CO domains.\n\nSeparately, the proposed TAI tool is **highly extensible**. Since it operates over natural language representations, it can be applied to a wide range of CO problems, offering a unified, model-agnostic interface that abstracts away low-level solver details. This supports our broader vision of creating general-purpose, accessible LLM solvers.\n\n**Q3. In Table 2, the label \"ours\" is ambiguous—does it refer to the SFT-only model, RL-finetuned version, or an ensemble?**\n\nThank you for pointing this out. We agree that the label “Ours” in Table 2 is ambiguous without clarification, and we appreciate your careful reading. To clarify: the results reported under \"Ours\" refer to the model that has been fine-tuned with RL (following SFT) and evaluated using BoN sampling at inference time. This represents our full method, as described in the main experimental setup. We acknowledge that this was not clearly stated in the table caption or main text, and we have updated the revised manuscript to make this explicit.\n\n**Other comments**\n\nThanks for the helpful suggestions! Due to the page limit, we were unable to give more messages for the main result in the main text, but we will incorporate more discussion in the final version of the paper, as an additional content page is allowed.\n\nRegarding the claim in line 269, we now provide additional supporting evidence. For instance, we analyzed how DeepSeek-R1 attempts to solve a TSP instance with 48 nodes. The model generates over **11,000 tokens** (see below), producing a verbose and incoherent reasoning trace that ultimately leads to **ineffective and suboptimal solutions.** We will include this example and further empirical support in the appendix of the revised version to make our conclusions more transparent and well-supported.\n\n**[DeepSeek’s CoT for a TSP instance]:**\n\n*Okay, I need to solve the TSP for 48 cities using coordinates and two nearest neighbors per city. TSP is NP-hard, so I’ll try a heuristic. Maybe nearest neighbor? But that might cause loops...*\n\n*Alternatively, maybe I can start building the route by choosing a starting city and then always moving to the nearest unvisited neighbor...*\n\n*Alternatively, I could use some kind of greedy heuristic that selects the globally shortest available edge that doesn't create a cycle...* \n\n*Alternatively, perhaps I can use the given neighbor data to form a minimum spanning tree...*\n\n*Alternatively, maybe I can look at the set of neighbors and try to trace a Hamiltonian cycle manually...*\n\n*Hmm... Christofides algorithm? No, we lack full distance matrix...*\n\n*Alternatively, maybe I can use the neighbor data to identify subtours and then link them...*\n\n*Wait, I'm stuck at Node 16. Maybe start over...*\n\n*Looks like two clusters based on Y-coordinates. Let's try connecting them...*\n\n*...*"}]

Author rebuttal:

Meta-review: The paper proposes a two-stage fine-tuning framework that enables Large Language Models (LLMs) to serve as end-to-end combinatorial optimization (CO) solvers. The method utilizes supervised fine-tuning (SFT) and a feasibility-and-optimality-aware reinforcement learning (FOARL) process to directly map natural language problem descriptions to solutions, eliminating the need for external solvers or code generation. 
Most reviewers acknowledged the framework's novelty, clear methodology, and comprehensive experiments. Although Reviewer qC4e did not provide further feedback during the discussion phase, their final concern regarding a lack of convincing evidence against the "model-then-solve" approach was addressed by the authors. As noted by Reviewer egzu, the authors conducted additional experiments compared to several "model-then-solve" baselines (e.g., LLMOPT, ORLM, and DRoC), demonstrating their method's superior performance. Overall, the authors have addressed all major concerns raised by the reviewers. Therefore, I recommend accepting this paper.
Decision: Accept (poster)