Beyond Objective Equivalence: Constraint Injection for LLM-Based Optimization Modeling on Vehicle Routing Problems

背景

大型语言模型（LLMs）在将自然语言描述的优化问题转化为可执行的求解器代码方面展现出巨大潜力。然而，在约束密集的运筹学（Operations Research, OR）领域，现有的数据过滤和训练管道主要依赖于“目标等价性”（Objective Equivalence）信号，例如差分测试（differential testing）和答案一致性（answer agreement）。

这种评估方式存在显著缺陷：当某些约束在特定的测试实例中是非绑定（non-binding）的，即不改变最优解的目标函数值时，程序即使添加了虚假约束或静默省略了必要约束，依然可以通过测试。这意味着模型可能生成了看似正确（目标值匹配）但逻辑上错误（约束违反或过度约束）的代码。

核心内容

为了解决上述问题，研究人员提出了一种名为“约束注入”（Constraint Injection）的新方法，并基于此构建了端到端的优化建模框架。

1. 约束注入与双重验证器

研究团队提出了“约束注入”机制，旨在通过特定的探针（probes）来检测代码中的逻辑错误：

• 可行探针（Feasible Probes）：用于暴露虚假的过度约束（spurious over-constraint）。如果模型添加了不必要的限制，导致原本可行的解变得不可行，探针将捕捉到这一错误。
• 单约束违反探针（One-constraint-violating Probes）：用于揭示静默的约束省略。如果模型遗漏了关键约束，探针将检测到解违反了被省略的约束。

将约束注入与传统的差分测试相结合，形成了一种“双重验证器”（Dual Verifier），能够更全面地评估生成代码的正确性。

2. VRPCoder 模型与基准测试

研究团队以车辆路径问题（Vehicle Routing Problems, VRPs）为测试床，开发了一个名为 VRPCoder 的 8B 参数端到端模型。该模型能够将自然语言描述的 VRP 场景直接转化为 Gurobi 求解器脚本。

同时，团队构建了一个经过专家验证的 VRP 基准测试套件，涵盖了 21 种不同的 VRP 变体，为模型评估提供了标准化的测试环境。

3. 训练与优化策略

双重验证器在 VRPCoder 的训练过程中发挥了关键作用：

• 数据合成阶段：作为拒绝采样（rejection-sampling）的过滤器，确保合成的高质量训练数据符合约束逻辑。
• 策略优化阶段：作为组相对策略优化（Group Relative Policy Optimization, GRPO）中的每轮回报（per-rollout reward），指导模型学习更准确的约束建模能力。

4. 实验结果

在四个 VRP 基准测试中，经过 GRPO 优化的 VRPCoder 模型表现优异：

• 平均 Pass@1 达到 93%。
• 在三个基准测试中超越了 Gemini-3.1-Pro Preview。
• 平均得分比 Claude-Sonnet-4.5 高出 28 分。
• 相比之前的运筹学大模型（OR-LLMs），平均得分高出 78 分。

关键要点

• 现有评估的局限性：传统的基于目标函数值匹配的评估方法无法检测非绑定约束下的逻辑错误（如虚假约束或约束遗漏）。
• 双重验证机制：通过引入“约束注入”技术，结合可行探针和单约束违反探针，与差分测试共同构成双重验证器，有效识别代码中的约束逻辑错误。
• VRPCoder 模型：开发了专门的 8B 参数模型 VRPCoder，专注于将自然语言 VRP 场景转化为 Gurobi 脚本。
• 专家验证基准：构建了包含 21 种 VRP 变体的专家验证基准测试套件，提升了评估的可靠性。
• GRPO 优化：利用双重验证器作为 GRPO 的奖励信号，显著提升了模型的约束建模能力。
• 显著的性能提升：VRPCoder-GRPO 在多项基准测试中超越了包括 Gemini-3.1-Pro Preview 和 Claude-Sonnet-4.5 在内的顶级模型，大幅领先于现有的 OR-LLMs。

意义与影响

这项研究揭示了当前 LLM 在运筹学建模中的关键短板：即过度依赖目标函数等价性而忽视约束逻辑的完整性。通过引入约束注入和双重验证器，研究不仅提供了一种更鲁棒的评估和训练框架，还展示了如何通过针对性的数据合成和策略优化来提升模型在复杂约束环境下的表现。

VRPCoder 的成功表明，针对特定领域（如 VRP）的垂直优化模型，结合严格的逻辑验证机制，能够超越通用大模型在复杂组合优化任务上的能力。这为未来 LLM 在更广泛的运筹学、供应链管理和工业优化领域的应用提供了新的技术路径和评估标准。