Large Language Models as End-to-end Combinatorial Optimization Solvers

Dear Reviewer u6T1,

We 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.

W1. The model with optimality gaps of 1.03-8.20% is not end-to-end to me.

Thank 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.

The 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.

W2. Generalizability to OOD instances is unclear.

Thank 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.

The 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.

W3. Lack of interpretability—no insights into how the model derives predictions.

We 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.

LLMs 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.

We will explicitly acknowledge this limitation in the revised paper for readers to explore it more systematically in future work.

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?

Thank 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.

Instead 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.

Regarding 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.

Q2. How well does the method generalize to unseen problem classes? Could the TAI tool be extended to other combinatorial optimization tasks?

Generalization 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.

For 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.

However, 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.

Separately, 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.

Q3. In Table 2, the label "ours" is ambiguous—does it refer to the SFT-only model, RL-finetuned version, or an ensemble?

Thank 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.

Other comments

Thanks 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.

Regarding 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.

[DeepSeek’s CoT for a TSP instance]:

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...

Alternatively, maybe I can start building the route by choosing a starting city and then always moving to the nearest unvisited neighbor...

Alternatively, I could use some kind of greedy heuristic that selects the globally shortest available edge that doesn't create a cycle...

Alternatively, perhaps I can use the given neighbor data to form a 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 I 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...

...

Dear Reviewer u6T1,

With less than 8 hours remaining in the discussion phase, we want to ensure that all your questions and concerns have been fully addressed. We deeply value the time and effort you dedicate to the review process. Thank you so much for your consideration.

If you have any additional questions or points for clarification, please let us know—we will do our utmost to address them promptly. Thank you again for your thoughtful feedback. We look forward to hearing from you.

Sincerely,

Authors of Submission15371

Dear Reviewer qC4e,

Thanks for acknowledging the comprehensive experiments in our work. We appreciate your feedback and hope the responses address your concerns.

W1. No practical application scenario.

We 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.

A 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.

Meanwhile, 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.

While 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.

We 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.

W2. Only one base LLM is actually trained

The 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.

To 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:

These 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.

W3. Efficiency gap is acknowledged by the authors

We 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.

While 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.

We 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.

W4. Marginal contribution of RL

We 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.

In 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.

We 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).

W5. Unsurprisingly, imitating experts boosts an LLM; why language modelling is preferable to NCO

We 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.

Importantly, 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.

We 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.

Q1. What is the wall-clock latency on problems with 1 000+ nodes, and how does that compare with OR-Tools?

Current 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.

To 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.

These 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.

Q2. Did the authors try simply weighting feasibility in the loss during SFT?

We 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.

Dear authors,

Thank you very much for your prompt and detailed response. I truly appreciate you taking the time to conduct additional experiments, which have been very helpful. Your thorough explanations have addressed most of my concerns. However, I still have a concern on one remaining point regarding the methodology.

I am in complete agreement with your perspective that the primary goal is not for LLMs to replace specialized solvers for complex, professional-grade problems, but rather to assist ordinary people with simpler, everyday optimization tasks.

Given this objective, I am curious about the rationale for fine-tuning the LLM to generate solutions directly, as opposed to leveraging function calling to invoke an established solver like Gurobi. My thinking is that a function-calling approach could offer distinct advantages:

1. the fine-tuning process itself might be simpler,

2. the resulting solutions would be verifiably accurate, and, perhaps most importantly, it would better preserve the model's crucial generalization capabilities.

The current fine-tuning approach risks degrading these general abilities, which seems to conflict with the goal of serving the diverse needs of an "ordinary person."

On a related note, regarding the 1000-node TSP experiment, you mentioned the LLM found a "feasible" solution in three minutes. For a TSP designed on Euclidean space, any tour that visits each node exactly once is technically feasible. Could you clarify what "feasible" signifies in this context? Was the challenge simply to produce any valid tour, or were there other quality metrics involved?

Dear Reviewer qC4e,

With less than 8 hours remaining in the discussion phase, we want to ensure that your final concern has been fully addressed. We greatly appreciate the time and effort you have devoted to this review process.

Please also let us know if you have any additional questions or points for clarification. We will do our best to address them promptly. Thank you again for your feedback.

Best regards,

Authors of Submission15371

Dear Reviewer umUz,

We 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.

W1. Unfair comparison: It appears that the LLM-based baselines do not utilize prior information from the generated COP datasets.

Thank 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.

This 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.

We 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.)).

Even 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.

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

Thank you for the thoughtful comment. We address both aspects below.

LLM-based end-to-end solvers:

We 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.

A 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.

OPRO [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.

In 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.

Domain-specific solvers:

We 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.

However, 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.

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.

In 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.

For 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.

To 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:

Q2. In Appendix E.7, do the baseline methods leverage any prior information

There 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).

Among 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.

Q3. Should all TSPLIB instances that meet certain criteria be considered

In 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.

However, 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

Dear Reviewer egzu,

Thank 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.

[W1.1., Q1] No justification is given for excluding stronger baselines (e.g., HGS, ALNS)

Thanks 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.

Since 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].

However, 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)):

W1.2. The description of “heuristic features” is brief and lacks detail on selection rationale

The 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:

(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.

(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.

[W2., Q2] The paper does not benchmark against exact solvers

We 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:

As 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.

Importantly, 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.

W3. The computational efficiency might still be lower than both classical heuristics and MIP solvers

Indeed, 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.

We 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.

It 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.

Q3. The effect of heuristic features

Indeed, 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].

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.

Please note: even without these features, our model still outperforms all general-purpose LLMs.

Q4. FOARL improves feasibility, but how does the number or type of constraints affect infeasibility rates

This 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.

Due 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.

We 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.

From 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.

Q5. OOD performance

We 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.

We will incorporate all the results and discussion above into the paper for clarity.

Dear Reviewer egzu,

As the discussion phase is set to close in less than 8 hours, we want to ensure that all your questions and concerns have been fully addressed. We have carefully reviewed your feedback and provided detailed responses to each of your comments. We sincerely hope our clarifications meet your expectations and resolve any outstanding issues.

If you have any further concerns, we will also do our best to address them. Thank you for your valuable feedback. We look forward to hearing from you!

Sincerely,

Authors of Submission15371