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

📄 arXiv: 2509.16865v1 📥 PDF

作者: Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, Yingqian Zhang

分类: cs.AI

发布日期: 2025-09-21

期刊: The 39th Annual Conference on Neural Information Processing Systems (NeurIPS 2025)

💡 一句话要点

提出基于大语言模型的端到端组合优化求解器，无需中间步骤。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 组合优化 大语言模型 端到端求解 强化学习 监督微调 自然语言处理 NP-hard问题

📋 核心要点

  1. 现有组合优化方法依赖于特定算法，需要大量领域知识，且LLM方法依赖中间步骤，通用性受限。
  2. 提出一种端到端框架，直接将自然语言问题描述映射到解决方案，无需中间步骤。
  3. 通过监督微调和强化学习，在七个NP-hard问题上超越通用LLM、推理模型和领域启发式方法。

📝 摘要（中文）

组合优化（CO）问题在物流和制造等决策场景中至关重要，传统上使用需要大量领域专业知识的特定问题算法来解决。虽然大型语言模型（LLM）在自动化CO问题求解方面显示出前景，但现有方法依赖于代码生成或求解器调用等中间步骤，限制了其通用性和可访问性。本文介绍了一种新颖的框架，该框架使LLM能够通过直接将自然语言问题描述映射到解决方案来充当端到端CO求解器。我们提出了一种两阶段训练策略：监督微调（SFT）使LLM掌握来自特定领域求解器的解决方案生成模式，而可行性和最优性感知强化学习（FOARL）过程明确地减轻了约束违反并改进了解决方案质量。在七个NP-hard CO问题上的评估表明，通过调整一个70亿参数的LLM，我们的方法实现了高可行性率，并将平均最优性差距降低到1.03-8.20%，超过了通用LLM（例如，GPT-4o）、推理模型（例如，DeepSeek-R1）和特定领域启发式方法。我们的方法为CO建立了一个统一的基于语言的管道，无需大量代码执行或针对不同问题的手动架构调整，从而为传统求解器设计提供了一种通用且语言驱动的替代方案，同时保持了相对可行性保证。

🔬 方法详解

问题定义：论文旨在解决组合优化（CO）问题，现有方法通常需要针对特定问题设计算法，依赖领域专家知识，且基于LLM的方法依赖代码生成或调用外部求解器，缺乏通用性和易用性。这些方法难以直接利用自然语言描述的问题进行求解。

核心思路：论文的核心思路是利用LLM直接学习从自然语言问题描述到解决方案的映射，避免中间步骤，实现端到端的组合优化求解。通过训练LLM理解问题约束和优化目标，并生成满足约束且接近最优的解。

技术框架：整体框架包含两个阶段：1) 监督微调（SFT）：使用领域特定求解器生成的数据对LLM进行微调，使其学习生成可行解的模式。2) 可行性和最优性感知强化学习（FOARL）：使用强化学习进一步优化LLM，通过奖励函数鼓励生成可行且高质量的解，同时惩罚违反约束的行为。

关键创新：最重要的创新在于提出了一个完全基于语言的端到端组合优化求解流程，无需代码生成或外部求解器。FOARL通过显式地建模可行性和最优性，有效地引导LLM生成高质量的解，克服了传统LLM在处理复杂约束优化问题上的局限性。

关键设计：SFT阶段使用领域求解器生成的数据进行训练，目标是让LLM初步具备生成可行解的能力。FOARL阶段，奖励函数的设计至关重要，需要平衡可行性和最优性。具体而言，奖励函数包括可行性奖励（惩罚违反约束）和最优性奖励（鼓励生成更优解）。论文中使用了PPO算法进行强化学习，并对奖励函数进行了精心设计，以确保训练的稳定性和收敛性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，该方法在七个NP-hard组合优化问题上取得了显著效果，通过调整一个70亿参数的LLM，实现了高可行性率，并将平均最优性差距降低到1.03-8.20%，超越了GPT-4o、DeepSeek-R1等通用LLM、推理模型以及领域特定启发式方法。

🎯 应用场景

该研究成果可广泛应用于物流、制造、调度等领域的决策优化问题。例如，优化车辆路线、生产计划、资源分配等。该方法降低了组合优化问题的求解门槛，使得非专业人员也能利用LLM解决实际问题，具有重要的实际应用价值和潜力。

📄 摘要（原文）

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.