让大模型求解组合优化问题时100%保证可行，不靠运气靠机制。
Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization
- 用语法约束+修复层+自适应采样三招，确保解一定满足约束。
- 在7个难问题上做到解全可行，质量还超过现有顶尖方法。
- 适合需要绝对可靠解的工业场景，如调度、资源分配。
大语言模型（LLM）在组合优化（CO）中展现出通用求解潜力，但缺乏保障解可行性的机制，这制约了其实际应用。本文提出FALCON框架，通过三项关键创新实现100%可行性：(i) 语法约束解码保证语法正确性，(ii) 可行性修复层纠正语义约束违规，(iii) 自适应Best-of-N采样高效分配计算资源。为训练底层LLM，提出基于最优锚点的目标引导偏好优化（BOPO），根据目标差距加权偏好对，实现无人工标注的密集监督。理论上证明了BOPO收敛性，并给出了修复导致质量损失的边界。实验表明，在七个NP-hard CO问题上，FALCON实现完全可行性，且解质量匹配或超越现有神经与基于LLM的最优求解器。
原文摘要 · Abstract (English)
Large language models (LLMs) have emerged as promising general-purpose solvers for combinatorial optimization (CO), yet they fundamentally lack mechanisms to guarantee solution feasibility which is critical for real-world deployment. In this work, we introduce FALCON, a framework that ensures 100\% feasibility through three key innovations: (i) \emph{grammar-constrained decoding} enforces syntactic validity, (ii) a \emph{feasibility repair layer} corrects semantic constraint violations, and (iii) \emph{adaptive Best-of-$N$ sampling} allocates inference compute efficiently. To train the underlying LLM, we introduce the Best-anchored Objective-guided Preference Optimization (BOPO) in LLM training, which weights preference pairs by their objective gap, providing dense supervision without human labels. Theoretically, we prove convergence for BOPO and provide bounds on repair-induced quality loss. Empirically, across seven NP-hard CO problems, FALCON achieves perfect feasibility while matching or exceeding the solution quality of state-of-the-art neural and LLM-based solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。