Research map / Large language models / Agents, code and math
Large Language Models as End-to-end Combinatorial Optimization Solvers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Fine-tunes a 7B Qwen2.5 with SFT on solver-generated solutions and then FOARL (GRPO-based feasibility- and optimality-aware RL) plus best-of-N inference to act as an end-to-end LLM solver for seven NP-hard combinatorial optimization problems.
Problem
LLMs struggle to map natural-language-described NP-hard combinatorial optimization problems directly to feasible, high-quality solutions; prior approaches rely on code generation or solver calls, and SFT alone yields constraint-violating over-greedy outputs.
Approach
Treat CO solving as language generation: SFT on textual (instruction, heuristic-feature input, solver solution) pairs, then GRPO-based RL with rule-based feasibility rewards plus an optimality reward to correct constraint violations, and best-of-N sampling at inference.
Key results
- SFT+RL+BoN achieves 100% feasibility on TSP, OP, CVRP, MVC, PFSP, JSSP and average optimality gaps of 1.03-8.20% across the seven problems with a 7B model.
- GPT-4o reaches only 39% feasibility on TSP and 15% on CVRP; DeepSeek-R1 reaches 48% on TSP.
- On TA JSSP 15x15, the method with N=8 reaches 14.22% gap versus 19.68% for StarJob and 23.88% for L2D greedy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add FOARL after SFT (ablation) | Qwen2.5-7B CO solver · OP | feasibility rate: 54% -> 92% | Helped |
| add FOARL after SFT (ablation) | Qwen2.5-7B CO solver · CVRP | feasibility rate: 59% -> 80% | Helped |
| add FOARL after SFT (ablation) | Qwen2.5-7B CO solver · OP | optimality gap: 2.32%$_{\pm2.6}$ -> 4.25%$_{\pm2.9}$ | Hurt |
| add FOARL after SFT (ablation) | Qwen2.5-7B CO solver · TSP | optimality gap: 2.30%$_{\pm1.9}$ -> 2.32%$_{\pm2.2}$ | No clear effect |
| add Best-of-N inference (ablation) | SFT+RL Qwen2.5-7B CO solver · TSP | feasibility rate: 91% -> 100% | Helped |
| add Best-of-N inference (ablation) | SFT+RL Qwen2.5-7B CO solver · OP | feasibility rate: 92% -> 100% | Helped |
| add Best-of-N inference (ablation) | SFT+RL Qwen2.5-7B CO solver · CVRP | feasibility rate: 80% -> 100% | Helped |
| increase BoN sample count from N=8 to N=64 (ablation) | SFT+RL JSSP solver · Taillard 15x15 | optimality gap: 14.22% -> 11.34% | Helped |
| increase BoN sample count from N=8 to N=64 (ablation) | SFT+RL JSSP solver · Taillard 20x15 | optimality gap: 21.16% -> 17.26% | Helped |
| increase BoN sample count from N=8 to N=64 (ablation) | SFT+RL JSSP solver · Taillard 20x20 | optimality gap: 23.30% -> 20.01% | Helped |
| remove heuristic features from TAI prompts (ablation) | Qwen2.5-7B CO solver · CO problems | optimality gap | Mixed |
Surprising findings
- SFT alone produces over-greedy behavior, marginally violating constraints (e.g., distance limits in OP, capacity in CVRP) in pursuit of better objectives.
- Reasoning models such as o1 and R1 generate lengthy, ineffective chains of thought on CO instances and often get stuck.
Limitations
- Solving efficiency is not on par with traditional lightweight heuristics.
- Scaling to larger-scale CO instances remains unresolved; the approach is evaluated on at most about 100 nodes.
- Optimality gaps are computed against domain solvers, and feasibility is not guaranteed for all problems (e.g., OP and MIS below 100%) without BoN.
Experimental setup
Datasets: solver-generated synthetic instances for TSP, OP, CVRP, MIS, MVC, PFSP, JSSP Taillard (TA) benchmark TSPLib
Benchmarks: Synthetic test sets for seven CO problems (TSP, OP, CVRP, MIS, MVC, PFSP, JSSP) Taillard JSSP benchmark (TA 15x15, 20x15, 20x20) TSPLib
Metrics: feasibility rate average optimality gap Gap@K average solving time
Baselines: GPT-4o GPT-4o-mini Claude-3.7-Sonnet Claude-3.5-Haiku DeepSeek-V3 Llama3.3-70B Qwen2.5-72B GPT-o3-mini GPT-o1 DeepSeek-R1 OPRO LMEA
Builds on: GRPO LoRA Instruction tuning Text-attributed instance framework
Closest papers by meaning
- SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search (NeurIPS 2025 · similarity 0.90)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.89)
- LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch (ICLR 2025 · similarity 0.89)
- Self-Guiding Exploration for Combinatorial Problems (NeurIPS 2024 · similarity 0.88)
- Solver-Informed RL: Grounding Large Language Models for Authentic Optimization Modeling (NeurIPS 2025 · similarity 0.88)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.