4 cumulative citations
View corpus contextLarge language models often produce infeasible decisions on operational optimization tasks: the top model attains only 65% feasibility and no model surpasses a 30.5% rate of both feasible and near-optimal solutions; when solutions are feasible they tend to be close to solver optima, making feasibility the primary obstacle to trustworthy automation.
ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization
On a 200-instance benchmark of constrained optimization tasks verified by Gurobi, frontier LLMs struggle mainly with feasibility (best model 65% feasible), though feasible outputs are typically near-optimal while joint feasibility-and-near-optimality rates remain low (≤30.5%).
Citation observations
Cumulative provider counts captured on specific dates; providers are never combined.
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% feasibility, 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 85.0% in the facility location 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.
Summary
Main Finding
ConstraintBench is a new benchmark that measures whether LLMs can directly produce correct solutions to fully specified constrained-optimization problems (not just formulate solver code). Evaluating six frontier LLMs on 200 solver-verified problems across 10 OR domains shows the primary failure mode is feasibility: models often violate constraints even when, conditional on feasibility, their objective values are close to the solver-optimum. The best model achieves 65.0% feasibility; feasible outputs typically reach 89–96% of the Gurobi-optimal objective, but joint feasibility+near-optimality (within 0.1%) is low (max 30.5%). Per-domain difficulty varies dramatically (feasibility 85.0% down to 0.8%), and common failure modes include misunderstanding temporal/duration constraints, entity hallucination, and a feasibility–optimality decoupling (high feasibility but 0% optimality in some domains).
Key Points
- New benchmark (ConstraintBench) tests direct-solution ability: models must return structured decision outputs (JSON) that are independently verified against every constraint and an optimal solver reference.
- Coverage: 10 operations-research domains (facility location, production mix, order fulfillment, job-shop scheduling, shift scheduling, crew assignment, project planning, vehicle routing, bin packing, portfolio optimization). 200 problems total (20 per domain), all generated and verified by Gurobi.
- Evaluation metrics:
- Feasibility: satisfies all constraints and integrality.
- Objective quality: (1 − |gap|) × 100 where gap = (f(x) − f(x)) / |f(x)|.
- Near-optimality: fraction of feasible solutions with |gap| < 0.1%.
- Aggregate results (high-level):
- Best model: GPT-5.2-pro — Feasibility 65.0%, objective quality among feasible 95.2%, % optimal (≤0.1%) 30.5%.
- Other models show similar pattern: feasibility often < 65% and objective quality among feasible typically 89–96%.
- Per-domain variation:
- Facility location: high feasibility (avg 85.0%; one model 100%) but 0% joint optimality across models.
- Crew assignment: extremely hard (avg feasibility 0.8%).
- Vehicle routing and some scheduling domains show feasibility–optimality decoupling.
- Common failure modes identified: duration/temporal constraint misinterpretation, hallucinated entities (using IDs not in the problem), parse/format errors, and local reasoning that satisfies constraints but misses cost-optimal structure.
Data & Methods
- Problem generation pipeline:
- Seed space: combinatorial product of industry context, scale, urgency, region, specialization (~28k seeds/domain).
- LangGraph agent (LLM-assisted) used to expand seeds into natural-language scenarios; agent had limited tools (sandbox Python, structural validation, Gurobi feasibility checks) and could iterate using Gurobi IIS feedback to produce feasible, solver-verifiable tasks.
- Gurobi used to build MIP, solve to proven optimality, and extract ground-truth solutions. Tasks discarded if Gurobi could not prove optimality within limits.
- Benchmark dataset: 200 solver-verified MIP instances (20 per domain) with ground-truth feasible optimal solutions.
- Models evaluated: GPT-5.2-pro, GPT-5.2, Claude Opus 4.6, Claude Opus 4.5, o4-mini, Gemini 3 Pro Preview. Each model given only the natural-language prompt and output schema; no solver or feedback at test time.
- Output and verification:
- Models must return a single-turn structured JSON conforming to domain schema.
- Verification steps: parse/structural validation → per-constraint binary checks (diagnostics provided) → recompute objective from raw decision variables → compute gap against Gurobi-proven optimum.
- Parse/API failures counted as infeasible. Feasible = zero constraint violations; optimal = feasible and within 0.1% of solver objective.
- Key quantitative snapshots:
- Aggregate feasibility range across domains: best domain mean 85.0% (facility location) to worst 0.8% (crew assignment).
- Conditional objective quality among feasible solutions typically 89–96%.
- Joint feasibility+0.1% optimality ranged 0–30.5% across models; several domains show 0% joint optimality for all models.
- Limitations explicitly noted by authors:
- Focus on MIPs with linear constraints and linear objectives.
- 200 tasks (balanced breadth vs. scale); domains not calibrated for equal difficulty.
- Benchmark evaluates single-turn, solver-less direct outputs only.
Implications for AI Economics
- Deployment risk vs. reward
- Risk: Direct deployment of LLMs for constrained operational decision-making risks infeasible decisions at non-trivial rates (best model ~35% infeasible). Constraint violations can cause operational failure, regulatory breaches, or financial loss in real-world settings.
- Reward: When feasible, model solutions are near-optimal (often >90% of optimum), so LLMs can generate high-quality candidate plans if feasibility is ensured.
- Best-practice architectures for practitioners and purchasers
- Hybrid workflows: Use LLMs to propose candidate solutions or high-quality warm starts, but always verify and (if necessary) repair with a formal solver (e.g., Gurobi) before execution. This leverages the LLM’s strong objective performance while guarding against infeasibility.
- Human-in-the-loop / automated checks: Integrate deterministic verifiers and constraint-checkers as gating controls. Treat any LLM-generated solution as provisional until solver-verified.
- Procurement evaluation: Benchmark prospective LLMs on constraint-specific tests (e.g., ConstraintBench) matching the firm’s constraint types before trusting them for operational use.
- Economic and product implications
- Cost-benefit tradeoffs: If feasible outputs average 90–95% of optimum, LLMs could yield substantial cost savings relative to naive heuristics—but only for the fraction of instances where feasibility holds. Expected realized savings = feasibility_rate × (objective_quality × solver_optimal_benefit).
- Insurance and regulatory concerns: For regulated domains (healthcare scheduling, finance), infeasibility or constraint violation may have outsized legal/cost implications, increasing the need for solver-backed guarantees.
- Research and model-improvement directions with economic value
- Objective: raise feasibility rate rather than only optimize objective quality. Engineering incentives and training regimes should reward constraint satisfaction (e.g., supervised fine-tuning on solver-verified feasible solutions; RL with feasibility rewards).
- Specialized modules: incorporate constraint-aware decoding, symbolic reasoning modules, or mixed discrete-continuous planners in model stacks to improve combinatorial constraint reasoning.
- Verification-aware loss/feedback: use solver-derived IIS or counterexamples during training to teach models where and why constraints fail.
- Hybrid optimization products: build products that orchestrate LLM planning + solver verification + local repair heuristics; ConstraintBench indicates this hybrid approach likely offers the best economic return vs risk.
- Policy / procurement guidance for economists and decision-makers
- Require solver-verification in SLAs for any LLM-driven operational decision system.
- Use constraint-specific benchmarks like ConstraintBench during vendor selection to measure feasibility rates relevant to your domain.
- Model selection should weigh feasibility capability more than raw language-model benchmark scores for constrained decision tasks.
- Research utility
- ConstraintBench provides a reproducible, solver-verified evaluation pool that can guide model development toward constraint satisfaction capabilities. Its public release should accelerate improvements that have direct operational and economic impact.
Summary recommendation: Treat LLMs today as powerful heuristic/generator components for constrained problems, not as standalone solvers. For economically consequential operations, combine LLM outputs with formal solver verification and invest in model training or system designs that explicitly prioritize constraint satisfaction.
Assessment
Paper Typedescriptive
Evidence Strengthmedium — Provides systematic empirical evaluation with ground-truth optima verified by a state-of-the-art solver (Gurobi) across 200 tasks and 10 domains, which gives credible evidence about LLM capability on these benchmarks; however, the scope is limited to the selected tasks, prompt/formatting choices, and six models, so conclusions about broader real-world performance or alternative model families remain limited.
Methods Rigorhigh — Uses deterministic verification of constraints and solver-proven optima, covers multiple OR domains, analyzes per-domain performance and failure modes, and evaluates multiple frontier models—methodological safeguards (Gurobi verification, structured outputs, deterministic checker) increase rigor; potential weaknesses are sample/design choices rather than verification procedures.
Sample200 constrained optimization tasks spanning 10 operations-research domains (e.g., facility location, vehicle routing, crew assignment), each presented as a natural-language scenario with entities, constraints, and an objective; ground-truth solutions and optima computed with Gurobi; six state-of-the-art LLMs evaluated producing structured outputs checked by a deterministic verifier.
Themesproductivity org_design human_ai_collab
GeneralizabilityLimited to the 10 selected operations-research domains and 200 task instances—may not reflect all optimization problem types or real-world complexity, Evaluated on six specific frontier models; other model families or future models may perform differently, Problems are fully specified and solver-verifiable; performance on partially specified, noisy, or real-time decision settings is unknown, Prompting, output formatting requirements, and verifier strictness may affect results and are task/implementation specific, Benchmarks measure standalone model output without integration into end-to-end human+tool workflows, limiting claims about deployed productivity gains
Claims (10)
| Claim | Direction | Outcome | Confidence & Evidence | Details |
|---|---|---|---|---|
| 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. Other | positive | benchmark_coverage_and_verification |
Reading fidelity
high
Study strength
high
|
not reported
|
| 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. Decision Quality | positive | verifier_checked_feasibility_and_optimality |
Reading fidelity
high
Study strength
high
|
not reported
|
| We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. Decision Quality | negative | feasibility_vs_optimality |
Reading fidelity
high
Study strength
high
|
n=200
|
| The best model achieves only 65.0% feasibility. Decision Quality | negative | feasibility_rate |
Reading fidelity
high
Study strength
high
|
n=200
65.0% feasibility
|
| Feasible solutions average 89 to 96% of the Gurobi-optimal objective. Decision Quality | positive | objective_value_relative_to_optimum |
Reading fidelity
high
Study strength
high
|
n=200
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. Decision Quality | negative | joint_feasibility_and_optimality_rate |
Reading fidelity
high
Study strength
high
|
n=200
30.5%
|
| Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Decision Quality | mixed | per-domain_feasibility_rate |
Reading fidelity
high
Study strength
high
|
85.0% (facility location) to 0.8% (crew assignment)
|
| 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. Decision Quality | negative | failure_modes_and_error_types |
Reading fidelity
high
Study strength
medium
|
not reported
|
| 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? Other | neutral | research_gap_identification |
Reading fidelity
high
Study strength
medium
|
not reported
|
| ConstraintBench and all evaluation infrastructure will be publicly released. Adoption Rate | positive | data_and_infrastructure_release |
Reading fidelity
high
Study strength
medium
|
not reported
|