《 Large Language Models as End-to-end Combinatorial Optimization Solvers 》（ NeurIPS 2025 ）提出 SFT+FOARL 两阶段策略，将组合优化（CO）视为条件语言生成任务。先通过 SFT 让 LLM 学会表述解决方案，再用 FOARL 注入约束与优化偏好，推理时结合 BoN 选最优解。基于 Qwen2.5-7B 在 7 类 CO 问题测试，6 类可行率达 100%，平均最优性差距 1.03%-8.20%，优于通用 LLM 与传统启发式方法，为交通、制造等领域 CO 问题提供通用且友好的端到端解法。

研究概览

引言

组合优化问题（如旅行商问题 TSP、车辆路径规划 VRP、调度问题等）广泛存在于交通、制造、医疗等现实场景。传统解法往往依赖人工设计的启发式算法或调用开源/商业求解器，需要大量领域知识，迁移性差。大语言模型（Large Language Models， LLMs）的兴起有望给组合优化带来新的解决思路。

以往 LLM 解决 CO 的路径多依赖生成可执行代码或与求解器交互，对用户的领域知识要求高，且需要获取求解器许可或配置代码运行环境；而端到端思路希望直接由文本输入得到解答，更通用且对非专业用户更友好。现状难点在于：CO 问题约束复杂，LLM 在可行性与最优性上常表现不稳定（如 GPT-3.5 在 50 节点 TSP 上平均最优性差距达 133%）[2]，即便更先进的语言模型在小规模实例上的可行率也仅约 50% 左右，这使端到端CO求解能力无法满足要求 [3]。

本文尝试回答：“如何让 LLM 从自然语言出发，稳定地产生可行且优质的 CO 解？”作者提出 SFT+FOARL 的两阶段策略，并在 7 类问题上系统验证，显示在可行率与最优性上均优于通用/推理型 LLM 与若干领域特定启发式方法。

方法描述

本文方法框架

目标：把 CO 视为条件语言生成任务；用 SFT 学会“如何表述解决方案”，再用 FOARL 显式注入“满足约束与优化目标”的偏好，最后以 BoN 做测试期探索。

1. 任务形式化与文本实例（TAI, text-attributed instance）

令单个实例

其中为候选解空间， 为目标函数，为约束集合。将数值实例转为文本输入 （TAI：包含 Instruction 与 Input），同时把由领域特定的求解器生成的高质量解（如Gurobi）转成文本标签（如 TSP 的“Route/Objective”）。为引导潜在解空间探索，在输入中加入低成本启发式特征（如“每个节点 top-2 近邻及距离”）[4]。

实现提示：车辆路径类问题的 TAI 会嵌入“top-k 近邻”等可文本化的经典启发信息，有助于模型在训练/推理期偏向更优区域。消融表明添加该特征可以提升性能。

2. 监督微调（SFT）

思路：用领域专用求解器（如LKH3）产出（问题→解）的配对数据，把“生成解”视作下一个 token 的预测。

目标函数（条件语言建模）：

这里 是文本解的第 个 token。借助LoRA做参数高效微调，覆盖多尺度与多分布的组合优化实例数据以提升泛化。

SFT策略的现象与问题：仅用 SFT 时模型会出现过度贪心（为更优目标值而轻微违反约束，如 OP 超距离、CVRP 超载），导致不可行解。这提示需要在训练目标中显式注入可行性。

3. 可行-最优性感知强化学习（FOARL）

动机：SFT 学到“如何写出解”，但对约束结构缺乏全局理解。FOARL 通过联合奖励与组相对策略优化（Group Relative Policy Optimization，GRPO）来校正。

3.1 联合奖励设计

可行性奖励（满足输出格式且尽量满足所有约束）：

其中ζ判定输出是否符合 TAI 格式，c_p,i∈{0,1}表示是否满足第i个约束。

最优性奖励（与最优性差距反比）：

总奖励R_p。不同任务可设不同权重（附录给出了 OP/JSSP 等的具体设定示例）。

解读：这种分解让 RL 同时“拉高”可行率（满足硬约束/格式）与“拉低”目标值（或提高收益）。从附录可见，OP 中对距离约束赋予更高权重，以抑制最常见的违规。

3.2 基于 GRPO 的策略更新

对每个φ(p)采样S个解，使用组内标准化的优势项 进行更新（无须单独 critic）：

其中，r_i为新旧策略比，D_KL为约束策略漂移的KL散度。该目标与 PPO 形式相近，但基于组相对优势构造，训练成本更低。

4. 推理期的 Best-of-N（BoN）

自回归的LLM生成难以全局回溯或通过不同分支来进行解的探索，因此引入BoN 在推理时生成个候选，并取最优可行解以增强推理时探索：

结果

1. 主结果与范围

基于Qwen2.5-7B（使用LoRA微调）在 7 类问题上评测。SFT 约50 万/问题的训练实例，FOARL 额外至多 3,200 实例；推理期单样本温度设为 0，BoN 采用 top-p=0.7 与 (N=8) 默认值。

可行率整体较高，经过RL和BoN后在6类问题上达到100%可行率，平均最优性差距 1.03%–8.20%；相较通用/推理型 LLM 与若干启发式基线，端到端方法在可行性与目标值上更稳健。

主要结果

2. 与领域方法的对比与分析

与常用启发式方法：端到端LLM组合优化求解器可以超越常用的启发式求解器与算法， 如Or-tools、贪婪算法等。

与经典求解器：在车辆路径类任务（如 CVRP），在相近时延预算下，端到端 LLM 的平均最优性差距显著小于 Gurobi（如 CVRP：4.53% vs 35.09%）；在 MIS/MVC 等紧致 MIP 上，Gurobi 表现仍更强，体现了问题结构对方法偏好。

与“model-then-solve”方法：在较大规模车辆路径问题上，端到端方法在可行率与目标值上更稳定，避免了代码-求解器集成与公式构建的脆弱性。

3. 强化学习的功能

约束松弛：FOARL 显著降低了 OP/CVRP 等任务的约束违例，Gap@K 基本不降（或略升），说明 RL 增益主要来自“通过松弛部分约束，让更多实例达到可行”，而不是牺牲已可行实例的质量。

提高采样效率：FOARL 后模型以更小的达到与SFT更大相当的性能，这在时延/算力受限场景尤为有价值。

4. BoN、特征消融与 OOD

BoN 敏感性：增大 通常持续提升性能，可按部署预算取舍“质量-时延”。

启发特征消融：去掉“top-k 近邻”等 TAI 中启发式特征，性能下降，训练曲线也更高（收敛更慢）。

分布外（OOD）：在 TSP/OP/CVRP 的混合/聚簇分布上，性能有轻微下降，但总体保持稳定可行与较小最优性差距。

总结

贡献小结

端到端范式：把 CO 视作语言生成，绕开中间环节（代码/求解器）与复杂 prompt 工程；

两阶段训练：SFT 学“解题表达”，FOARL 学“约束满足+目标优化”并提升采样效率；

稳健评测：7 类 NP-hard 问题与多规模实例，平均最优性差距1.03%–8.20%，6类问题上可行率达到100%，显著优于通用型与推理型LLM。

展望

更高效的训练/推理（蒸馏、短上下文策略、可微可行性检查）；

更丰富的 TAI 设计（结构化文本、混合符号提示）；

与传统启发式的混合（如 RL 预筛 + 局部搜索微调），在大规模/强约束任务上进一步降低差距。

参考文献

[1] Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, and Yingqian Zhang. "Large Language Models as End-to-end Combinatorial Optimization Solvers." *In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.

[2] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024.

[3] Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and exploring large language models on graph computation. In The Thirteenth International Conference on Learning Representations, 2025.

[4] Xia Jiang, Yaoxin Wu, Yuan Wang, and Yingqian Zhang. "Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization." arXiv:2408.12214 (2024).

---

文章改编转载自微信公众号：运筹OR帷幄

原文链接：https://mp.weixin.qq.com/s/76snrBHba_YK8GHPMCDGqg

论文链接：arxiv.org/pdf/2509.16865

 Github: https://github.com/Summer142857/LLMCoSolver

《 Large Language Models as End-to-end Combinatorial Optimization Solvers 》（ NeurIPS 2025 ）提出 SFT+FOARL 两阶段策略，将组合优化（CO）视为条件语言生成任务。先通过 SFT 让 LLM 学会表述解决方案，再用 FOARL 注入约束与优化偏好，推理时结合 BoN 选最优解。基于 Qwen2.5-7B 在 7 类 CO 问题测试，6 类可行率达 100%，平均最优性差距 1.03%-8.20%，优于通用 LLM 与传统启发式方法，为交通、制造等领域 CO 问题提供通用且友好的端到端解法。

研究概览

引言

组合优化问题（如旅行商问题 TSP、车辆路径规划 VRP、调度问题等）广泛存在于交通、制造、医疗等现实场景。传统解法往往依赖人工设计的启发式算法或调用开源/商业求解器，需要大量领域知识，迁移性差。大语言模型（Large Language Models， LLMs）的兴起有望给组合优化带来新的解决思路。

以往 LLM 解决 CO 的路径多依赖生成可执行代码或与求解器交互，对用户的领域知识要求高，且需要获取求解器许可或配置代码运行环境；而端到端思路希望直接由文本输入得到解答，更通用且对非专业用户更友好。现状难点在于：CO 问题约束复杂，LLM 在可行性与最优性上常表现不稳定（如 GPT-3.5 在 50 节点 TSP 上平均最优性差距达 133%）[2]，即便更先进的语言模型在小规模实例上的可行率也仅约 50% 左右，这使端到端CO求解能力无法满足要求 [3]。

本文尝试回答：“如何让 LLM 从自然语言出发，稳定地产生可行且优质的 CO 解？”作者提出 SFT+FOARL 的两阶段策略，并在 7 类问题上系统验证，显示在可行率与最优性上均优于通用/推理型 LLM 与若干领域特定启发式方法。

方法描述

本文方法框架

目标：把 CO 视为条件语言生成任务；用 SFT 学会“如何表述解决方案”，再用 FOARL 显式注入“满足约束与优化目标”的偏好，最后以 BoN 做测试期探索。

1. 任务形式化与文本实例（TAI, text-attributed instance）

令单个实例

其中为候选解空间， 为目标函数，为约束集合。将数值实例转为文本输入 （TAI：包含 Instruction 与 Input），同时把由领域特定的求解器生成的高质量解（如Gurobi）转成文本标签（如 TSP 的“Route/Objective”）。为引导潜在解空间探索，在输入中加入低成本启发式特征（如“每个节点 top-2 近邻及距离”）[4]。

实现提示：车辆路径类问题的 TAI 会嵌入“top-k 近邻”等可文本化的经典启发信息，有助于模型在训练/推理期偏向更优区域。消融表明添加该特征可以提升性能。

2. 监督微调（SFT）

思路：用领域专用求解器（如LKH3）产出（问题→解）的配对数据，把“生成解”视作下一个 token 的预测。

目标函数（条件语言建模）：

这里 是文本解的第 个 token。借助LoRA做参数高效微调，覆盖多尺度与多分布的组合优化实例数据以提升泛化。

SFT策略的现象与问题：仅用 SFT 时模型会出现过度贪心（为更优目标值而轻微违反约束，如 OP 超距离、CVRP 超载），导致不可行解。这提示需要在训练目标中显式注入可行性。

3. 可行-最优性感知强化学习（FOARL）

动机：SFT 学到“如何写出解”，但对约束结构缺乏全局理解。FOARL 通过联合奖励与组相对策略优化（Group Relative Policy Optimization，GRPO）来校正。

3.1 联合奖励设计

可行性奖励（满足输出格式且尽量满足所有约束）：

其中ζ判定输出是否符合 TAI 格式，c_p,i∈{0,1}表示是否满足第i个约束。

最优性奖励（与最优性差距反比）：

总奖励R_p。不同任务可设不同权重（附录给出了 OP/JSSP 等的具体设定示例）。

解读：这种分解让 RL 同时“拉高”可行率（满足硬约束/格式）与“拉低”目标值（或提高收益）。从附录可见，OP 中对距离约束赋予更高权重，以抑制最常见的违规。

3.2 基于 GRPO 的策略更新

对每个φ(p)采样S个解，使用组内标准化的优势项 进行更新（无须单独 critic）：

其中，r_i为新旧策略比，D_KL为约束策略漂移的KL散度。该目标与 PPO 形式相近，但基于组相对优势构造，训练成本更低。

4. 推理期的 Best-of-N（BoN）

自回归的LLM生成难以全局回溯或通过不同分支来进行解的探索，因此引入BoN 在推理时生成个候选，并取最优可行解以增强推理时探索：

结果

1. 主结果与范围

基于Qwen2.5-7B（使用LoRA微调）在 7 类问题上评测。SFT 约50 万/问题的训练实例，FOARL 额外至多 3,200 实例；推理期单样本温度设为 0，BoN 采用 top-p=0.7 与 (N=8) 默认值。

可行率整体较高，经过RL和BoN后在6类问题上达到100%可行率，平均最优性差距 1.03%–8.20%；相较通用/推理型 LLM 与若干启发式基线，端到端方法在可行性与目标值上更稳健。

主要结果

2. 与领域方法的对比与分析

与常用启发式方法：端到端LLM组合优化求解器可以超越常用的启发式求解器与算法， 如Or-tools、贪婪算法等。

与经典求解器：在车辆路径类任务（如 CVRP），在相近时延预算下，端到端 LLM 的平均最优性差距显著小于 Gurobi（如 CVRP：4.53% vs 35.09%）；在 MIS/MVC 等紧致 MIP 上，Gurobi 表现仍更强，体现了问题结构对方法偏好。

与“model-then-solve”方法：在较大规模车辆路径问题上，端到端方法在可行率与目标值上更稳定，避免了代码-求解器集成与公式构建的脆弱性。

3. 强化学习的功能

约束松弛：FOARL 显著降低了 OP/CVRP 等任务的约束违例，Gap@K 基本不降（或略升），说明 RL 增益主要来自“通过松弛部分约束，让更多实例达到可行”，而不是牺牲已可行实例的质量。

提高采样效率：FOARL 后模型以更小的达到与SFT更大相当的性能，这在时延/算力受限场景尤为有价值。

4. BoN、特征消融与 OOD

BoN 敏感性：增大 通常持续提升性能，可按部署预算取舍“质量-时延”。

启发特征消融：去掉“top-k 近邻”等 TAI 中启发式特征，性能下降，训练曲线也更高（收敛更慢）。

分布外（OOD）：在 TSP/OP/CVRP 的混合/聚簇分布上，性能有轻微下降，但总体保持稳定可行与较小最优性差距。

总结

贡献小结

端到端范式：把 CO 视作语言生成，绕开中间环节（代码/求解器）与复杂 prompt 工程；

两阶段训练：SFT 学“解题表达”，FOARL 学“约束满足+目标优化”并提升采样效率；

稳健评测：7 类 NP-hard 问题与多规模实例，平均最优性差距1.03%–8.20%，6类问题上可行率达到100%，显著优于通用型与推理型LLM。

展望

更高效的训练/推理（蒸馏、短上下文策略、可微可行性检查）；

更丰富的 TAI 设计（结构化文本、混合符号提示）；

与传统启发式的混合（如 RL 预筛 + 局部搜索微调），在大规模/强约束任务上进一步降低差距。

参考文献

[1] Xia Jiang, Yaoxin Wu, Minshuo Li, Zhiguang Cao, and Yingqian Zhang. "Large Language Models as End-to-end Combinatorial Optimization Solvers." *In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.

[2] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024.

[3] Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and exploring large language models on graph computation. In The Thirteenth International Conference on Learning Representations, 2025.

[4] Xia Jiang, Yaoxin Wu, Yuan Wang, and Yingqian Zhang. "Bridging Large Language Models and Optimization: A Unified Framework for Text-attributed Combinatorial Optimization." arXiv:2408.12214 (2024).

---

文章改编转载自微信公众号：运筹OR帷幄

原文链接：https://mp.weixin.qq.com/s/76snrBHba_YK8GHPMCDGqg

论文链接：arxiv.org/pdf/2509.16865

 Github: https://github.com/Summer142857/LLMCoSolver