Large Language Models for Combinatorial Optimization: A Systematic Review

📄 arXiv: 2507.03637v1 📥 PDF

作者: Francesca Da Ros, Michael Soprano, Luca Di Gaspero, Kevin Roitero

分类: cs.AI

发布日期: 2025-07-04

💡 一句话要点

综述：大型语言模型在组合优化中的应用研究

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 组合优化 系统综述 机器学习 人工智能

📋 核心要点

  1. 组合优化问题复杂，传统方法面临计算瓶颈和泛化性挑战。
  2. 该综述旨在系统性地分析大型语言模型在组合优化中的应用现状与潜力。
  3. 通过对103篇相关文献的分类和分析，为未来研究方向提供指导。

📝 摘要（中文）

本系统性综述探讨了大型语言模型（LLM）在组合优化（CO）中的应用。我们使用系统评价和元分析的首选报告项目（PRISMA）指南报告了我们的发现。我们通过Scopus和Google Scholar进行了文献检索，检查了2000多篇出版物。我们根据与语言、研究重点、出版年份和类型相关的四个纳入标准和四个排除标准评估了出版物。最终，我们选择了103项研究。我们将这些研究分为语义类别和主题，以全面概述该领域，包括LLM执行的任务、LLM的架构、专门为评估LLM在CO中的性能而设计的现有数据集以及应用领域。最后，我们确定了在该领域利用LLM的未来方向。

🔬 方法详解

问题定义：组合优化问题涉及在有限的解空间中寻找最优解，传统方法如精确算法、启发式算法和近似算法在处理大规模、高复杂度问题时面临计算量大、求解时间长、泛化能力弱等问题。现有方法难以充分利用数据中的潜在模式和结构信息。

核心思路：利用大型语言模型（LLM）强大的学习和推理能力，将组合优化问题转化为LLM可以理解和处理的文本或序列形式，从而借助LLM的知识和能力来求解或辅助求解组合优化问题。这种方法旨在利用LLM的泛化能力和对复杂关系的建模能力，提高求解效率和质量。

技术框架：该综述对现有研究进行分类，主要关注以下几个方面：LLM在组合优化中执行的任务（例如，直接生成解、评估解的质量、指导搜索过程），LLM的架构（例如，Transformer、BERT、GPT系列），专门为评估LLM在组合优化中的性能而设计的数据集，以及应用领域（例如，车辆路径问题、旅行商问题、调度问题）。整体流程包括文献检索、筛选、分类和分析。

关键创新：该综述的关键创新在于系统性地总结和分析了LLM在组合优化领域的应用现状，并识别了未来的研究方向。它不仅关注了LLM在求解组合优化问题中的具体应用，还关注了LLM架构、数据集和应用领域的选择对性能的影响。

关键设计：该综述没有提出新的算法或模型，而是对现有研究进行梳理和总结。关键设计体现在文献检索和筛选策略上，采用了明确的纳入和排除标准，确保了研究的系统性和全面性。此外，对研究进行分类和分析，为读者提供了清晰的框架和视角。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

该综述分析了103篇相关文献，涵盖了LLM在组合优化中的多种应用场景和技术方法。通过对这些研究的分类和总结，揭示了LLM在组合优化领域的发展趋势和潜在价值，为未来的研究提供了重要的参考。

🎯 应用场景

该研究成果可应用于物流优化、生产调度、资源分配、网络设计等领域。通过利用LLM，有望提升组合优化问题的求解效率和质量，降低成本，提高资源利用率。未来，LLM有望成为解决复杂组合优化问题的重要工具。

📄 摘要（原文）

This systematic review explores the application of Large Language Models (LLMs) in Combinatorial Optimization (CO). We report our findings using the Preferred Reporting Items for Systematic Reviews and Meta-Analyses (PRISMA) guidelines. We conduct a literature search via Scopus and Google Scholar, examining over 2,000 publications. We assess publications against four inclusion and four exclusion criteria related to their language, research focus, publication year, and type. Eventually, we select 103 studies. We classify these studies into semantic categories and topics to provide a comprehensive overview of the field, including the tasks performed by LLMs, the architectures of LLMs, the existing datasets specifically designed for evaluating LLMs in CO, and the field of application. Finally, we identify future directions for leveraging LLMs in this field.