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

arXiv: https://arxiv.org/abs/2509.16865 · HTML: https://mlsanity.com/paper/2509.16865/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 75 references that are in the map.
- First posted on arXiv 21 Sep 2025.

## Builds on (most cited first, 30 of 46)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Large Language Models Are Zero-Shot Time Series Forecasters](https://mlsanity.com/paper/2310.07820/) (2023)
- [MiniF2F: a cross-system benchmark for formal Olympiad-level mathematics](https://mlsanity.com/paper/2109.00110/) (2021)
- [Large Language Models for Mathematical Reasoning: Progresses and Challenges](https://mlsanity.com/paper/2402.00157/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Progressive-Hint Prompting Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2304.09797/) (2023)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch](https://mlsanity.com/paper/2410.13213/) (2024)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)

## Built on by (most cited first, 28 of 28)

- [An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems](https://mlsanity.com/paper/2510.16701/) (2025)
- [OPT-Engine: Benchmarking the Limits of LLMs in Optimization Modeling via Complexity Scaling](https://mlsanity.com/paper/2601.19924/) (2026)
- [Bridging Synthetic and Real Routing Problems via LLM-Guided Instance Generation and Progressive Adaptation](https://mlsanity.com/paper/2511.10233/) (2025)
- [DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization](https://mlsanity.com/paper/2601.06502/) (2026)
- [Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization](https://mlsanity.com/paper/2602.01090/) (2026)
- [OptiVerse: A Comprehensive Benchmark towards Optimization Problem Solving](https://mlsanity.com/paper/2604.21510/) (2026)
- [CP-SynC: Multi-Agent Zero-Shot Constraint Modeling in MiniZinc with Synthesized Checkers](https://mlsanity.com/paper/2605.01675/) (2026)
- [Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems](https://mlsanity.com/paper/2606.04816/) (2026)
- [PyVRP^+: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems](https://mlsanity.com/paper/2604.07872/) (2026)
- [Automated Large-scale CVRP Solver Design via LLM-assisted Flexible MCTS](https://mlsanity.com/paper/2605.03339/) (2026)
- [Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction](https://mlsanity.com/paper/2605.19975/) (2026)
- [A hybrid quantum-classical neural network for learning to route](https://mlsanity.com/paper/2609.00489/) (2026)
- [Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems](https://mlsanity.com/paper/2609.00859/) (2026)
- [A Unified Model for Multi-Task Drone Routing in Post-Disaster Road Assessment](https://mlsanity.com/paper/2510.21525/) (2025)
- [Failing to Explore: Language Models on Interactive Tasks](https://mlsanity.com/paper/2601.22345/) (2026)
- [EvoOpt-LLM: Evolving industrial optimization models with large language models](https://mlsanity.com/paper/2602.01082/) (2026)
- [Language-Grounded Multi-Agent Planning for Personalized and Fair Participatory Urban Sensing](https://mlsanity.com/paper/2603.24014/) (2026)
- [Infeasibility Aware Large Language Models for Combinatorial Optimization](https://mlsanity.com/paper/2604.01455/) (2026)
- [Dual-Cluster Memory Agent: Resolving Multi-Paradigm Ambiguity in Optimization Problem Solving](https://mlsanity.com/paper/2604.20183/) (2026)
- [HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization](https://mlsanity.com/paper/2605.07214/) (2026)
- [Large Language Models as Amortized Pareto-Front Generators for Constrained Bi-Objective Convex Optimization](https://mlsanity.com/paper/2605.12106/) (2026)
- [Sim2Schedule: A Simulator-Guided LLM Framework for Autonomous Open-Pit Mine Scheduling](https://mlsanity.com/paper/2606.10286/) (2026)
- [Large Language Models as Optimizers: A Survey of Direct vs. Tool-Augmented Approaches and Their Performance Frontiers](https://mlsanity.com/paper/2606.15577/) (2026)
- [Reinforcement Learning without Ground-Truth Solutions can Improve LLMs](https://mlsanity.com/paper/2606.27369/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)
- [Learning to Optimize through Solver-Grounded Self-Play](https://mlsanity.com/paper/2609.34205/) (2026)
- [VLM Fine-Tuning for End-to-End Combinatorial Optimization](https://mlsanity.com/paper/2609.37175/) (2026)
- [Think in Strategies, Act with Tools: Traceable Agentic Optimization for Combinatorial Problems](https://mlsanity.com/paper/2610.14736/) (2026)

## Abstract (arXiv)

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