TLDR: A new research paper introduces a framework enabling large language models (LLMs) to act as end-to-end solvers for combinatorial optimization (CO) problems. Through a two-stage training strategy—supervised fine-tuning (SFT) and feasibility-and-optimality-aware reinforcement learning (FOARL)—the LLMs learn to directly map natural language problem descriptions to high-quality solutions. The method, which also incorporates Best-of-N inference, achieves high feasibility and low optimality gaps across seven NP-hard CO problems, outperforming general-purpose LLMs and competitive with domain-specific heuristics, while offering a unified and language-driven approach.
Combinatorial optimization (CO) problems are critical in many real-world decision-making scenarios, from managing logistics to optimizing manufacturing processes. Traditionally, solving these problems has required specialized algorithms and deep domain expertise, making them complex and often inaccessible to non-experts.
Recent advancements in large language models (LLMs) have sparked interest in their potential to automate CO problem-solving. However, previous approaches often relied on intermediate steps, such as generating code for solvers or invoking external optimization tools. While these methods showed promise, they still demanded significant domain knowledge and limited the LLMs’ ability to act as truly end-to-end solutions.
A New Approach to Combinatorial Optimization
A new research paper, titled “Large Language Models as End-to-end Combinatorial Optimization Solvers,” introduces a novel framework that transforms LLMs into direct, end-to-end CO solvers. Authored by Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, and Yingqian Zhang, this work proposes a unified, language-based pipeline that maps natural language problem descriptions directly to solutions, significantly reducing the need for extensive code execution or manual adjustments for different problems.
The core of this framework is a two-stage training strategy designed to enhance LLMs’ capabilities in solving complex CO problems:
1. Supervised Fine-Tuning (SFT): In the first stage, LLMs are fine-tuned using supervised learning. They learn solution generation patterns by observing high-quality solutions produced by existing, domain-specific CO solvers. This process teaches the LLM how to interpret problem descriptions and generate potential solutions. However, initial findings showed that SFT alone could lead to “over-greedy” behavior, where the LLM might slightly violate problem constraints in pursuit of better objective values.
2. Feasibility-and-Optimality-Aware Reinforcement Learning (FOARL): To address the constraint violation issue and refine solution quality, the second stage introduces a reinforcement learning process. FOARL explicitly mitigates constraint violations and improves the overall quality of the solutions. It uses a reward system that balances both feasibility (ensuring all constraints are met) and optimality (achieving the best possible objective value). This stage helps the LLM develop a deeper understanding of problem constraints and generate more reliable solutions.
Enhancing Solution Quality with Best-of-N Inference
To further boost performance during inference, the framework employs a technique called Best-of-N (BoN) sampling. Instead of generating a single solution, the fine-tuned LLM generates multiple distinct solution candidates. The system then selects the highest-quality feasible solution among these candidates, effectively exploring the solution space more thoroughly and improving the chances of finding an optimal outcome.
Impressive Results Across Diverse Problems
The researchers evaluated their method across seven NP-hard CO problems, including the Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), and Job-Shop Scheduling Problem (JSSP). The results were compelling:
- The method achieved a high feasibility rate and significantly reduced the average optimality gap to a range of 1.03–8.20% by fine-tuning a 7-billion-parameter LLM.
- It outperformed general-purpose LLMs (like GPT-4o) and reasoning models (like DeepSeek-R1), which often struggled with feasibility and optimality, especially on larger instances.
- Compared to traditional domain-specific heuristics, the LLM-based solver demonstrated competitive performance, particularly on smaller problem scales.
- The reinforcement learning stage was crucial, not only in improving solution feasibility but also in enhancing the sampling efficiency during inference, meaning better results could be achieved with fewer generated samples.
The paper also highlights the potential for a unified CO solver, demonstrating that a single LLM can be fine-tuned to solve multiple CO problems simultaneously without significant performance compromise. Furthermore, the model showed strong versatility and generalizability, performing well even on out-of-distribution datasets and when applied to different LLM architectures like Llama-3.1-8B and Gemma-2-9B.
Also Read:
- Teaching Neural Networks to Solve Knapsack: A Two-Phase Algorithmic Approach
- How Different Languages Enhance AI’s Mathematical Abilities
A New Paradigm for Optimization
This research marks a significant step towards a new paradigm for combinatorial optimization. By enabling LLMs to act as end-to-end solvers, the framework offers a language-driven, generalizable alternative to traditional solver design. It reduces reliance on specialized human expertise and simplifies the problem-solving pipeline, making complex optimization tasks more accessible. While acknowledging that solving efficiency is still an area for future improvement compared to lightweight heuristics, the work lays a strong foundation for integrating LLMs into real-world decision-making systems. You can read the full paper here.
