用自回归方法解决组合优化问题，让大模型生成符合约束的可行解。
ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention
- 基于自回归生成与动态注意力路由，实时校验约束条件。
- 在6类组合优化问题上优于主流方法，80亿参数模型媲美GPT-4。
- 首个端到端框架，适合研究大模型求解复杂规划问题的人。
大型语言模型（LLMs）展现出强大的推理能力，但其在NP难组合优化问题（CPs）中的直接应用仍较少。本文系统考察了LLMs在多种NP难组合优化任务中的推理能力，并提出ACCORD：一种结合路径路由与动态注意力机制的自回归约束满足生成框架。ACCORD采用新颖的数据表示和模型架构，利用LLM的自回归特性动态施加可行性约束，并通过注意力路由激活特定问题的LoRA模块。我们还构建了涵盖六类典型组合优化问题（TSP、VRP、Knapsack、FlowShop、JSSP、BinPacking）的ACCORD-90k监督数据集。大量实验表明，基于80亿参数Llama骨干网络的ACCORD模型，在多项任务中持续优于标准提示与输入输出方法，甚至超越更大规模的GPT-4模型。消融实验进一步验证了输出结构对解可行性提升的作用。据我们所知，这是首个大规模、端到端探索LLMs在广谱组合优化问题中应用的框架。代码已公开于https://github.com/starjob42/ACCORD。
原文摘要 · Abstract (English)
Large Language Models (LLMs) have demonstrated impressive reasoning capabilities, yet their direct application to NP-hard combinatorial problems (CPs) remains underexplored. In this work, we systematically investigate the reasoning abilities of LLMs on a variety of NP-hard combinatorial optimization tasks and introduce ACCORD: Autoregressive Constraint-satisfying generation for COmbinatorial optimization with Routing and Dynamic attention. ACCORD features a novel dataset representation and model architecture that leverage the autoregressive nature of LLMs to dynamically enforce feasibility constraints, coupled with attention-based routing to activate problem-specific LoRA modules. We also present the ACCORD-90k supervised dataset, covering six NP-hard combinatorial problems: TSP, VRP, Knapsack, FlowShop, JSSP, and BinPacking. Extensive experiments demonstrate that our ACCORD model, built on an 8B-parameter Llama backbone, consistently outperforms standard prompting and input-output methods, even when compared to much larger LLMs, such as gpt-4. Ablation studies further show that our output structure enhances solution feasibility. To the best of our knowledge, this is the first large-scale, end-to-end framework for exploring the applications of LLMs to a broad spectrum of combinatorial optimization problems. The codes are publicly available at https://github.com/starjob42/ACCORD
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。