论文

超越目标等价:面向LLM优化的约束注入

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

模型训练强化学习奖励建模与过程监督RLVR

摘要

大型语言模型 (LLM) 越来越多地将自然语言优化问题转化为可执行的求解器代码。然而,对于约束密集的运筹学 (OR) 问题,现有的数据过滤和训练管道在很大程度上依赖于目标等价信号,例如差异测试和答案一致性,程序可以通过这些信号,同时添加虚假约束或默默地省略所需的约束,只要这些约束对测试实例不具有约束力。我们提出约束注入,它使用可行的探针来暴露虚假的过度约束和单约束违反探针来揭示静默的约束遗漏。与差分测试相结合,形成双重验证器。我们在车辆路径问题(VRP)上实例化并评估它,这是一个具有耦合操作约束的代表性约束密集组合优化测试台。我们开发了 VRPCoder,这是一种 8B 端到端模型,可将自然语言 VRP 场景转换为 Gurobi 脚本,以及经过专家验证的 VRP 基准套件,涵盖 21 个变体。验证器在数据合成期间被重新用作拒绝采样过滤器,并在组相对策略优化(GRPO)中作为每次推出的奖励。在四个 VRP 基准测试中,VRPCoder-GRPO 的平均 Pass@1 达到 93%,在三个基准测试中优于 Gemini-3.1-Pro Preview,超过 Claude-Sonnet-4.5 平均分 28 分,超过之前的 OR-LLM 平均分 78 分。

超越目标等价:面向LLM优化的约束注入:论文配图
图 1:省略子巡回消除约束的候选者仍然与参考最优值匹配,因此差分测试接受它。约束注入提供了一个违反此约束的断开子旅行探针:正确的程序将其视为不可行而拒绝,但有缺陷的候选程序接受它,从而暴露了遗漏。