# R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling

arXiv: https://arxiv.org/abs/2508.15204 · HTML: https://mlsanity.com/paper/2508.15204/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 17 references that are in the map.
- First posted on arXiv 21 Aug 2025.

## Builds on (most cited first, 11 of 11)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions](https://mlsanity.com/paper/2303.08233/) (2023)
- [ORLM: A Customizable Framework in Training Large Models for Automated Optimization Modeling](https://mlsanity.com/paper/2405.17743/) (2024)
- [OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models](https://mlsanity.com/paper/2402.10172/) (2024)
- [CFBench: A Comprehensive Constraints-Following Benchmark for LLMs](https://mlsanity.com/paper/2408.01122/) (2024)
- [Planetarium: A Rigorous Benchmark for Translating Text to Structured Planning Languages](https://mlsanity.com/paper/2407.03321/) (2024)
- [Generating Streamlining Constraints with Large Language Models](https://mlsanity.com/paper/2408.10268/) (2024)
- [LLM-based Satisfiability Checking of String Requirements by Consistent Data and Checker Generation](https://mlsanity.com/paper/2506.16639/) (2025)

## Built on by (most cited first, 5 of 5)

- [CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in Dynamic Environments for LLM Tool-Use Agents](https://mlsanity.com/paper/2511.02734/) (2025)
- [PeakBench: Benchmarking Resource-Aware Tool Invocation in LLM Agents](https://mlsanity.com/paper/2608.24509/) (2026)
- [SCHEDBench: A Benchmark for Evaluating LLM Constraint Faithfulness in Natural-Language Combinatorial Scheduling](https://mlsanity.com/paper/2608.00991/) (2026)
- [SupChain-Bench: Benchmarking Large Language Models for Real-World Supply Chain Management](https://mlsanity.com/paper/2602.07342/) (2026)
- [Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions](https://mlsanity.com/paper/2608.18409/) (2026)

## Abstract (arXiv)

Effective scheduling under tight resource, timing, and operational constraints underpins large-scale planning across sectors such as capital projects, manufacturing, logistics, and IT fleet transitions. However, the reliability of large language models (LLMs) when reasoning under high-constraint regimes is insufficiently characterized. To address this gap, we present R-ConstraintBench, a scalable framework that evaluates models on Resource-Constrained Project Scheduling Problems (RCPSP), an NP-Complete feasibility class, while difficulty increases via linear growth in constraints. R-ConstraintBench incrementally increases non-redundant precedence constraints in Directed Acyclic Graphs (DAGs) and then introduces downtime, temporal windows, and disjunctive constraints. As an illustrative example, we instantiate the benchmark in a data center migration setting and evaluate multiple LLMs using feasibility and error analysis, identifying degradation thresholds and constraint types most associated with failure. Empirically, strong models are near-ceiling on precedence-only DAGs, but feasibility performance collapses when downtime, temporal windows, and disjunctive constraints interact, implicating constraint interaction, not graph depth, as the principal bottleneck. Performance on clean synthetic ramps also does not guarantee transfer to domain-grounded scenarios, underscoring limited generalization.