OPT-Engine: Benchmarking the Limits of LLMs in Optimization Modeling via Complexity Scaling

AI summary

Overview

• Research area: Natural language processing / LLM reasoning applied to Operations Research, specifically automated optimization modeling (natural language to mathematical formulation to solved solution).
• Technical level: Intermediate. Readers should be comfortable with basic optimization vocabulary (variables, objectives, constraints, LP, MIP, solvers) but the paper's arguments are presented at a conceptual level.
• Scope (one sentence): The paper introduces OPT-ENGINE, a programmatically generated benchmark of ten Operations Research problem classes with controllable difficulty, and uses it to compare solver-integrated reasoning (SIR) against pure-text Chain-of-Thought reasoning (PTR) and to isolate the primary failure mode of current LLMs in optimization.

What This Paper Is About

Existing benchmarks for LLM-driven optimization modeling mostly score aggregate accuracy on static, textbook-style instances that never grow in size or difficulty, so they cannot reveal where models break down. The authors build OPT-ENGINE, a pipeline that generates optimization problems with tunable structural complexity, rewrites them into varied natural-language narratives, and validates them against solver-computed ground truth. The goal is to probe how two competing paradigms, PTR and SIR, behave as problem complexity scales, and to identify which part of the modeling task is actually hardest for LLMs.

Key Contributions

1. OPT-ENGINE framework: An extensible benchmark spanning ten canonical Operations Research problem classes, split into five Linear Programming classes (inventory, portfolio allocation, production, transportation, pollution control) and five Mixed-Integer Programming classes (traveling salesman problem, knapsack, bin packing, job-shop scheduling, minimum-cost network flow). Difficulty is modulated by structural parameters such as the number of cities in TSP or the number of assets in portfolio allocation.
2. A four-stage generation pipeline: Numeric instance generation, canonical problem construction, problem augmentation (LLM-based rephrasing), and instance validation combining an LLM-as-a-Judge with a rule-based verifier, producing instances with verifiable optimal solutions.
3. Empirical comparison of PTR and SIR: PTR via classical Chain-of-Thought is shown to suffer a critical robustness gap as complexity grows, whereas solver integration maintains accuracy at scale.
4. Diagnosis of the bottleneck: Through controlled perturbations of linguistic complexity, objective functions, and constraints, the authors identify automated constraint formulation, not comprehension or objective perturbation, as the primary bottleneck of the SOTA SIR paradigm.

Main Findings

• PTR degrades sharply with scale, SIR does not. On both DeepSeek-V3.2 and GPT-5.1, SIR sustains high accuracy or shows only minor degradation as complexity increases across LP and MILP classes, while PTR performance drops substantially.
• Small models show the opposite ordering at low complexity. Qwen3-4B-Instruct's PTR outperforms its SIR at low-complexity settings, but the advantage is transient and reverses as problem scale expands, attributed to limited code-generation capability under SIR.
• Reinforcement learning post-training improves SIR execution. Qwen3-4B-RL, initialized from Qwen3-4B-Instruct and further optimized, consistently outperforms standard PTR across all problem dimensions. Execution rates rose from 23.1% to 38.1% on TSP (+15.0%), 23.1% to 99.6% on Knapsack (+76.5%), and 35.6% to 38.1% on Inventory (+2.5%).
• PTR exhibits dual failure. Error decomposition on DeepSeek-V3.2 shows PTR fails both on constraint feasibility and on numerical precision as complexity grows. For example, TSP PTR falls from 73.3% feasibility / 58.3% accuracy / 1.07% optimality gap at Easy to 64.0% / 2.0% / 11.72% at Hard. Network flow PTR falls from 40.0% / 10.0% at Easy to 0.0% / 0.0% at Hard.
• SIR accuracy is contingent on structural feasibility. Because numerical execution is offloaded to a solver, errors are purely structural; when the correct constraints and objective are captured, optimality is guaranteed. SIR on network flow reaches 100.0% feasibility and 100.0% accuracy at every level, and on Knapsack 100.0% feasibility at every level (92.3%, 91.7%, 95.7% accuracy).
• Computational tools help but do not close the gap. CompPTR, which augments PTR with Python primitives such as scipy or itertools while being barred from invoking external solvers for global optimization, sits at an intermediate level: better than PTR but below SIR. It mitigates arithmetic errors and some infeasibility, yet still suffers reasoning collapse as size grows.
• PTR behavior shifts strategy mid-scaling. On TSP with DeepSeek-V3.2, the model first enumerates Hamiltonian cycles explicitly, with search space of size (n-1)!, increasing token usage with complexity. Past a critical threshold, and just before accuracy collapse, it reduces token budget and switches to lightweight heuristics such as nearest neighbor and cheapest insertion, holding token use flat while lowering solution quality.
• Linguistic complexity is not the bottleneck. Varying problem descriptions across easy, moderate, and hard tiers measured by perplexity (PPL) leaves accuracy stable when the underlying mathematical structure is fixed.
• Objective perturbation is not the bottleneck. Adding a randomly sampled constant K to the objective, min f(x) → min f(x) + K, has negligible impact on accuracy across problem classes, since the optimal solution is invariant under the shift.
• Constraint augmentation is the bottleneck. Adding mathematically simple constraints, which preserve the problem class and introduce only O(1) new constraints without new variables, causes a consistent and substantial accuracy drop for both PTR and SIR. Failure traces point to formulation errors such as omitted constraints, which propagate to solvers in SIR or produce incorrect objectives in PTR.
• Symptoms of pattern matching rather than principled formulation. The canonical TSP, Knapsack, and related problems resemble textbook examples likely abundant in training data, while constrained variants introduce novel combinations that models are less likely to have seen.

Methodology in Plain English

The authors built a generator rather than a fixed dataset. For each of ten problem classes, a numeric generator takes a difficulty parameter (like number of cities or assets) and produces instance data, using a per-class solver template to compute the exact optimal objective value and decision variables as ground truth. If a random draw is infeasible, the generator resamples until a valid instance appears.

That numeric instance is then mapped through a structured template into a canonical problem statement, which serves as the formal reference. An LLM agent then rephrases the canonical statement into richer, domain-specific narratives to simulate varied real-world scenarios. A validation module pairs an LLM judge with a rule-based verifier to check numerical correctness and structural preservation between the canonical and rephrased versions; failed rephrasings are regenerated until valid.

For evaluation, the authors generate ten distinct instances per problem class per complexity level and report avg@10. A solution counts as correct if its relative error against the ground truth optimum satisfies |ŷ − y*| / (|y*| + 10⁻⁶) < 10⁻³. They compare two paradigms: PTR, where the model reasons all the way to a final answer in text, and SIR, where the final reasoning step is executable code run in an external solver. A third condition, CompPTR, allows Python computational primitives such as scipy or itertools but forbids calling an external solver for global optimization.

Diagnostic experiments then hold the mathematics fixed while varying one factor at a time: linguistic complexity of the description (measured by perplexity), a constant shift added to the objective, and small additions of constraints to the formulation.

Why This Matters

Impact on research. Static, textbook-scale benchmarks cannot distinguish between a model that genuinely formulates an optimization problem and one that recalls a familiar template. By scaling complexity systematically, OPT-ENGINE reframes evaluation around robustness rather than aggregate accuracy, and it provides a mechanistic explanation for why frontier LLMs perform near human level on competition mathematics yet fall below 50% accuracy on the most challenging optimization benchmark. The constraint-augmentation result specifically redirects attention toward semantic formulation fidelity as the open problem.

Real-world applications. The ten problem classes map directly onto operational settings:

• Inventory management and production planning, where order caps and minimum stock levels must be respected.
• Portfolio allocation, where the number of assets scales the decision space.
• Transportation and minimum-cost network flow, central to logistics and supply chain design.
• Combinatorial scheduling such as job-shop scheduling and bin packing, plus routing via the traveling salesman problem.
• Pollution control, an example of regulatory constraints layered onto an optimization model.

Industry relevance. The paper argues that real optimization tasks rarely appear as clean canonical problems; they accumulate constraints from operational and regulatory requirements. If frontier models silently drop such constraints, an auto-generated model can be passed to a solver and return a confidently wrong optimum. That makes formulation fidelity a deployment blocker for LLM-driven optimization pipelines, not a cosmetic concern. Solver-integrated reasoning is identified as the requisite framework for high-complexity, industrial-scale challenges, while pure-text reasoning remains brittle.

Future Directions

• Add heuristic-oriented tracks. The authors acknowledge that exact modeling is often computationally prohibitive for large-scale NP-hard problems. They propose reporting optimality gaps, runtime, and robustness under time budgets, and evaluating whether LLMs can design or select effective heuristics.
• Extend beyond linear structure. The current benchmark covers LP and MIP formulations; extending OPT-ENGINE to nonlinear, stochastic, and dynamic programs is named as an important direction.
• Vary training signals and evaluation criteria. The paper calls for testing different training signals and evaluation criteria for heuristic generation, moving away from a single exact-solution paradigm.
• Close the constraint-formulation gap. Since constraint augmentation is the identified bottleneck, an open question is how to train or prompt models so they internalize auxiliary constraint logic rather than relying on patterns tied to canonical textbook formulations.

Target Audience

Researchers and practitioners working at the intersection of LLMs, automated reasoning, and Operations Research will benefit most. This includes benchmark designers who need scalable evaluation protocols, NLP researchers studying reasoning robustness and failure modes in chain-of-thought systems, and industrial OR teams evaluating whether to trust LLM-generated formulations before handing them to a solver such as Gurobi or COPT. Readers with no optimization background can still follow the paradigm comparison, but will need some familiarity with LP and MIP concepts to interpret the feasibility and optimality-gap metrics.

Authors’ abstract

We investigate the capabilities and scalability of Large Language Models (LLMs) in optimization modeling, a domain requiring structured reasoning and precise formulation. To this end, we introduce OPT-ENGINE, an extensible benchmark framework with quantifiable and controllable complexity. OPT-ENGINE spans ten canonical Operations Research problems, systematically scaling from Linear Programming to Mixed-Integer Programming, providing a structured environment to probe the limits of automated problem formulation and solving. Utilizing OPT-Engine, we address three pivotal research questions. First, we examine whether Pure-Text Reasoning (PTR) via classical Chain-of-Thought can efficiently tackle optimization tasks, finding that PTR suffers from a critical robustness gap as task complexity increases. Second, we examine whether integrating external computational tools can mitigate PTR's arithmetic weaknesses and improve performance. Our results indicate that while such tools help with local calculations, they still fail to adhere to global optimization constraints. Finally, we pinpoint that for the current SOTA paradigm, Solver-integrated Reasoning (SIR), the automated formulation of constraints represents the primary bottleneck. These findings clarify the limitations of current paradigms and provide a structured roadmap for developing next-generation LLMs for optimization modeling. We release our code and data to facilitate future research (https://github.com/Cardinal-Operations/OPTEngine).