论文
硬约束遇上软生成：基于 LLM 的组合优化的可行性保证
Hard Constraints Meet Soft Generation: Guaranteed Feasibility for LLM-based Combinatorial Optimization
摘要
大语言模型（LLM）已成为有前景的组合优化（CO）通用求解器，但其从根本上缺乏保证解可行性的机制，而这对真实部署至关重要。本文提出 FALCON，通过三项关键创新确保100%可行性：(i) 语法约束解码保证语法有效；(ii) 可行性修复层纠正语义约束违反；(iii) 自适应 Best-of-N 采样高效分配推理算力。为训练底层 LLM，我们在 LLM 训练中引入 Best 锚定目标引导的偏好优化（BOPO），按目标差距为偏好对加权，在无人工标签的情况下提供稠密监督。理论上，我们证明 BOPO 的收敛性并给出修复引起的质量损失界。实证上，在七个 NP 难组合优化问题上，FALCON 实现完美可行性，同时匹配或超越最先进神经与基于 LLM 的求解器的解质量。
