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

• URL: http://arxiv.org/abs/2509.16865v1
• Date: Sun, 21 Sep 2025 01:30:30 GMT
• Title: Large Language Models as End-to-end Combinatorial Optimization Solvers
• Authors: Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, Yingqian Zhang,
• Abstract summary: Combinatorial optimization (CO) problems, central to decision-making scenarios like logistics and manufacturing, are traditionally solved using problem-specific algorithms.<n>Existing approaches rely on intermediate steps such as code generation or solver invocation, limiting their generality and accessibility.<n>This paper introduces a novel framework that empowers large language models (LLMs) to serve as end-to-end CO solvers by directly mapping natural language problem descriptions to solutions.
• Score: 45.32050615257007
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization [28.52469449694436]
  Large language models (LLMs) have shown strong performance in math and logic reasoning.<n>But their ability to handle systematic optimization (CO) remains underexplored.<n>We introduce NLCO, a benchmark that evaluates LLMs on end-to-end CO reasoning.
  arXiv  Detail & Related papers  (2026-02-02T14:55:48Z)
• Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization [14.17648636921649]
  We introduce FALCON, a framework that ensures 100% feasibility through three key innovations.<n>FALCON achieves perfect feasibility while matching or exceeding the solution quality of state-of-the-art neural and LLM-based solvers.
  arXiv  Detail & Related papers  (2026-02-01T08:09:06Z)
• SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search [58.116954449750544]
  We introduce a training-free framework that leverages test-time scaling to solve diverse optimization problems.<n>Rather than solving directly, it generates mathematical formulations and translates them into solver-ready code, guided by a novel Monte Carlo Tree Search strategy.
  arXiv  Detail & Related papers  (2025-10-19T16:21:19Z)
• An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems [66.60904891478687]
  We propose an Agentic Framework with LLMs (AFL) for solving complex vehicle routing problems.<n>AFL directly extracts knowledge from raw inputs and enables self-contained code generation.<n>We show that AFL substantially outperforms existing LLM-based baselines in both code reliability and solution feasibility.
  arXiv  Detail & Related papers  (2025-10-19T03:59:25Z)
• Learn to Relax with Large Language Models: Solving Nonlinear Combinatorial Optimization Problems via Bidirectional Coevolution [10.160534429260228]
  We introduce the first end-to-end textbfAutomated textbfConst textbfOptimization (AutoCO) method, which revolutionizes NCOPs resolution through learning to relax with code.
  arXiv  Detail & Related papers  (2025-09-16T03:59:51Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.83882149157548]
  Large language models (LLMs) offer new opportunities for assisting with algorithm design.<n>We propose LLM4CMO, a novel CMOEA based on a dual-population, two-stage framework.<n>LLMs can serve as efficient co-designers in the development of complex evolutionary optimization algorithms.
  arXiv  Detail & Related papers  (2025-08-16T02:00:57Z)
• From Natural Language to Solver-Ready Power System Optimization: An LLM-Assisted, Validation-in-the-Loop Framework [1.7136832159667206]
  This paper introduces a novel Large Language Models (LLMs)-assisted agent that automatically converts natural-language descriptions of power system optimization scenarios into compact, solver-ready formulations.<n>The proposed method focuses on discovering a mathematically compatible formulation that can be efficiently solved by off-the-shelf optimization solvers.
  arXiv  Detail & Related papers  (2025-08-11T16:22:57Z)
• RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs [3.3894236476098185]
  We propose RL-SPH, a novel reinforcement learning-based start primal capable of independently generating feasible solutions even for ILP involving non-binary integers.<n> Experimental results demonstrate that RL-SPH rapidly obtains high-quality feasible solutions, achieving average a 44x lower primal gap and a 2.3x lower integral compared to existing primals.
  arXiv  Detail & Related papers  (2024-11-29T07:23:34Z)
• LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch [16.174567164068037]
  We propose a unified learning-based framework called LLMOPT to boost optimization generalization.<n>LLMOPT constructs the introduced five-element formulation as a universal model for learning to define diverse optimization problem types.<n>LLMOPT is able to model various optimization problem types such as linear/nonlinear programming mixed integer programming.
  arXiv  Detail & Related papers  (2024-10-17T04:37:37Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.