ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization
作者: Joseph Tso, Preston Schmittou, Quan Huynh, Jibran Hutchins
分类: cs.AI
发布日期: 2026-02-28
💡 一句话要点
ConstraintBench：评估LLM在直接优化中约束推理能力的基准测试
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大型语言模型 约束优化 基准测试 运筹学 可行性 最优性
📋 核心要点
- 现有基准测试侧重于评估LLM将优化问题转化为求解器代码的能力，忽略了直接求解约束优化问题的能力。
- ConstraintBench通过自然语言场景描述约束优化问题，要求LLM直接生成满足约束并接近最优解的结构化方案。
- 实验表明，现有LLM在可行性方面表现不佳，难以同时保证可行性和最优性，不同领域问题难度差异显著。
📝 摘要（中文）
大型语言模型越来越多地应用于运筹决策，其底层结构是约束优化。现有基准测试评估LLM是否可以将优化问题公式化为求解器代码，但留下了一个互补的问题：LLM是否可以在没有求解器的情况下，直接为完全指定的约束优化问题生成正确的解决方案？我们引入了ConstraintBench，这是一个用于评估LLM在10个运筹学领域中直接约束优化能力的基准测试，所有ground-truth解决方案都经过Gurobi求解器验证。每个任务都提供了一个自然语言场景，其中包含实体、约束和优化目标；模型必须返回一个结构化的解决方案，确定性验证器会根据每个约束和求解器证明的最优解进行检查。我们评估了200个任务上的六个前沿模型，发现可行性而非最优性是主要瓶颈。最佳模型仅达到65.0%的约束满足率，但可行解的平均目标值达到Gurobi最优值的89%到96%。在求解器参考值的0.1%范围内，没有模型在联合可行性和最优性方面超过30.5%。按领域分析显示，难度差异很大，平均可行性从生产组合领域的83.3%到乘务员分配领域的0.8%不等。此外，系统性失效模式包括持续时间约束误解、实体幻觉以及设施选址和车辆路径中的可行性-最优性解耦，在这些问题中，模型实现了高可行性但0%的最优性。ConstraintBench和所有评估基础设施将公开发布。
🔬 方法详解
问题定义：论文旨在评估大型语言模型（LLM）在直接解决约束优化问题方面的能力。现有方法主要关注LLM将问题转化为求解器代码的能力，而忽略了LLM直接生成可行且接近最优解的能力。这种直接求解能力在实际应用中非常重要，因为并非所有场景都允许或需要使用外部求解器。
核心思路：论文的核心思路是构建一个基准测试集，该测试集包含一系列用自然语言描述的约束优化问题，并要求LLM直接生成结构化的解决方案。通过确定性的验证器来检查LLM生成的解决方案是否满足所有约束条件，并评估其目标函数值与Gurobi求解器得到的最优解的接近程度。
技术框架：ConstraintBench基准测试包含以下几个关键组成部分： 1. 任务定义：每个任务都包含一个自然语言描述的约束优化问题，涉及实体、约束和优化目标。 2. LLM推理：LLM接收任务描述，并生成一个结构化的解决方案。 3. 确定性验证器：验证器检查LLM生成的解决方案是否满足所有约束条件。 4. 最优性评估：将LLM生成解决方案的目标函数值与Gurobi求解器得到的最优解进行比较，评估其最优性。 5. 性能指标：主要评估指标包括约束满足率（可行性）和目标函数值与最优解的接近程度（最优性）。
关键创新：ConstraintBench的主要创新在于它提供了一个专门用于评估LLM直接约束优化能力的基准测试。与现有基准测试不同，ConstraintBench不依赖于LLM生成求解器代码，而是直接评估其生成可行且接近最优解的能力。此外，ConstraintBench还提供了详细的领域分析，揭示了LLM在不同类型约束优化问题上的表现差异。
关键设计：ConstraintBench包含10个运筹学领域的问题，涵盖了各种类型的约束和优化目标。每个任务都经过精心设计，以确保其难度适中，并且可以使用Gurobi求解器获得最优解。为了评估LLM的性能，论文使用了约束满足率和目标函数值与最优解的接近程度这两个关键指标。此外，论文还对LLM的失效模式进行了分析，揭示了LLM在处理不同类型约束时遇到的挑战。
🖼️ 关键图片
📊 实验亮点
实验结果表明，现有LLM在ConstraintBench上的表现远未达到理想水平。最佳模型仅达到65.0%的约束满足率，且在联合可行性和最优性方面，没有模型超过30.5%。不同领域问题难度差异显著，例如在乘务员分配领域，平均可行性仅为0.8%。这些结果表明，LLM在直接约束优化方面仍面临诸多挑战，需要进一步的研究和改进。
🎯 应用场景
ConstraintBench的研究成果可应用于评估和改进LLM在运筹学、供应链管理、资源分配、智能调度等领域的决策能力。通过该基准测试，可以更好地了解LLM在处理复杂约束优化问题方面的优势和局限性，从而指导LLM在实际应用中的部署和优化，提升决策效率和质量。
📄 摘要（原文）
Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% constraint satisfaction, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 83.3% in the production mix domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.