💬 NLP

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

This paper introduces OPT-Engine, a scalable benchmark framework for evaluating Large Language Models on optimization modeling tasks, revealing that current paradigms struggle with robustness as complexity increases and identifying automated constraint formulation as the primary bottleneck for solver-integrated reasoning.

Original authors: Yitian Chen, Cheng Cheng, Yinan Sun, Zi Ling, Dongdong Ge

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yitian Chen, Cheng Cheng, Yinan Sun, Zi Ling, Dongdong Ge

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, well-read robot how to solve complex logistics puzzles, like figuring out the best way to deliver packages to 100 cities or how to pack a truck with the most valuable items without breaking the weight limit. This is the world of Optimization Modeling.

The paper you provided, titled "OPT-Engine," is essentially a giant, adjustable gym for these robots. The researchers built a framework to test how well Large Language Models (LLMs)—the brains behind AI chatbots—can handle these puzzles as they get harder and harder.

Here is the breakdown of their findings using simple analogies:

1. The Gym: OPT-Engine

Most previous tests were like asking a robot to solve a math problem from a 5th-grade textbook. They were too easy and didn't reflect real life.

The Innovation: The authors built OPT-Engine, a "gym" where they can dial up the difficulty. They can take a simple puzzle (like packing 5 items) and scale it up to a nightmare scenario (packing 50 items with weird rules).
The Goal: They wanted to see at what point the robot's brain breaks down when the puzzle gets too big or too complicated.

2. The Two Athletes: "The Thinker" vs. "The Calculator"

The paper compares two different ways these AI models try to solve problems:

Athlete A: Pure-Text Reasoning (PTR)
- The Analogy: This is like a brilliant philosopher who tries to solve the puzzle entirely in their head. They write out a long story, step-by-step, using only words and logic. They never use a calculator or a computer program.
- The Result: When the puzzle is small, this philosopher is great. But as the puzzle gets bigger (more cities, more items), the philosopher gets confused. They start making math errors, forgetting rules, or getting lost in their own story. Their performance crashes hard.
Athlete B: Solver-Integrated Reasoning (SIR)
- The Analogy: This is like a project manager who knows the rules perfectly but isn't good at doing the actual math. When they get a puzzle, they write down the rules clearly and then hand the job to a super-fast, perfect calculator (a specialized software solver like Gurobi) to do the heavy lifting.
- The Result: This athlete stays strong even when the puzzle gets huge. Because they offload the hard math to the calculator, they don't make arithmetic mistakes.

3. The Big Discovery: The "Tool" Trap

The researchers asked: What if we give the "Thinker" (Athlete A) a calculator to help?

The Experiment: They let the "Thinker" use Python code to do the math but still forced them to figure out the logic of the puzzle themselves.
The Finding: The calculator helped with the math, but the robot still failed. Why? Because the robot couldn't figure out the global rules.
- Analogy: Imagine you ask a robot to pack a suitcase. You tell it, "Don't put the heavy books on top of the fragile glass." The robot might calculate the weight perfectly, but if it forgets the rule about the glass because the instruction was phrased in a slightly new way, the whole plan fails. The robot is good at local math but bad at keeping the "big picture" rules in mind.

4. The Real Bottleneck: "The Twist"

The most surprising finding was about where the robots fail.

It's not about the words: If you make the problem description sound more complicated or use fancy vocabulary, the robots handle it fine.
It's not about the goal: If you change the goal slightly (e.g., "minimize cost" vs. "minimize cost plus a flat fee"), the robots handle it fine.
It IS about the rules: The robots fail miserably when you add new constraints or twist the rules.
- Analogy: If you ask a robot to solve a standard "Traveling Salesman" puzzle (visit 5 cities), it's great. But if you say, "Visit 5 cities, BUT you must skip the road between City 2 and City 3, and you must visit City 4 before City 1," the robot often forgets these specific twists. It relies on patterns it saw in its training data (standard textbook examples) rather than truly understanding the new, specific rules of the moment.

Summary

The paper concludes that:

LLMs are bad at doing the math themselves when the problem gets big; they need to use external tools (solvers).
Even with tools, they struggle with complex rules. They are great at solving "textbook" versions of problems but fail when real-world constraints are added or twisted.
The biggest hurdle isn't understanding the language or the math; it's formulating the constraints correctly when the problem isn't a standard, clean example.

In short, AI is currently a great "textbook student" but a shaky "real-world engineer" when it comes to optimization. It needs to learn how to handle the messy, rule-heavy reality of actual logistics and planning.

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

1. Problem Statement

While Large Language Models (LLMs) have demonstrated promising capabilities in interpreting natural language and generating mathematical models for optimization, their application to real-world Operations Research (OR) remains brittle. Existing benchmarks often rely on static, fixed-scale instances or textbook-style problems that fail to capture the combinatorial complexity and structural density of industrial applications. Furthermore, a significant performance gap exists between LLMs' success in competitive mathematics and their ability to formulate and solve complex optimization problems, particularly as problem scale increases. The community lacks a rigorous, extensible framework to systematically probe the limits of automated problem formulation and to distinguish between the efficacy of different reasoning paradigms (Pure-Text Reasoning vs. Solver-Integrated Reasoning) under controlled complexity scaling.

2. Methodology: The OPT-Engine Framework

To address these gaps, the authors introduce OPT-Engine, an extensible benchmark framework designed to generate problem instances with quantifiable and controllable complexity.

2.1. Benchmark Taxonomy

OPT-Engine encompasses ten canonical OR problem classes, divided into two tiers:

Linear Programming (LP): Inventory, Portfolio Allocation, Production, Transportation, and Pollution Control problems.
Mixed-Integer Programming (MIP): Traveling Salesman Problem (TSP), Knapsack, Bin Packing, Job-Shop Scheduling, and Minimum-Cost Network Flow.

2.2. Scalable Generation Pipeline

The framework employs a four-stage pipeline to generate verifiable problem instances:

Numeric Instance Generation: A generator $G$ maps a problem class and a difficulty control vector $\theta$ (e.g., number of cities $N_{cities}$ for TSP) to a numeric instance. Crucially, this stage utilizes a solver template to compute the ground-truth optimal solution and objective value.
Canonical Problem Construction: The numeric instance is mapped to a formal, canonical problem statement $s_c$ using a structured template.
Problem Augmentation: A dedicated LLM agent rephrases the canonical statement into diverse, context-rich natural language narratives ( $s_r$ ) to simulate real-world scenarios while preserving the underlying mathematical structure.
Instance Validation: A validation module, combining an LLM-as-a-Judge and rule-based verifiers, ensures that the rephrased narratives maintain structural equivalence and numerical consistency with the ground truth.

2.3. Evaluation Paradigms

The framework evaluates two primary reasoning approaches:

Pure-Text Reasoning (PTR): The LLM uses Chain-of-Thought (CoT) to deduce the solution end-to-end without external tools.
Solver-Integrated Reasoning (SIR): The LLM translates the problem into executable code (e.g., Gurobi/COPT) which is then solved by an external deterministic solver.
Computational PTR (CompPTR): An intermediate approach where the LLM uses Python primitives for local calculations but is restricted from invoking global optimization solvers.

3. Key Results

3.1. Scaling and Robustness

SIR Superiority: As problem complexity scales (increasing dimensions and constraints), SIR maintains high accuracy or exhibits only minor degradation. In contrast, PTR suffers from a critical robustness gap, with performance collapsing significantly as problem size increases.
Model Scale Effects: While smaller models (e.g., Qwen3-4B) may outperform SIR at low complexity due to code-generation failures in SIR, this advantage is transient. With Reinforcement Learning from Verifiable Rewards (RLVR) to improve code generation, SIR consistently outperforms PTR across all dimensions.

3.2. Mechanistic Failure Modes

Arithmetic vs. Structural: Error decomposition reveals that PTR failures are dual-faceted: as complexity grows, models first fail to satisfy global logical constraints (feasibility collapse) and subsequently fail to achieve numerical precision.
Limitations of Computational Aids: While CompPTR (adding Python tools to PTR) mitigates arithmetic errors and improves local feasibility, it fails to enforce global optimization constraints. The model cannot internalize holistic combinatorial dependencies, leading to performance degradation similar to standard PTR at high scales.

3.3. Diagnostic of Bottlenecks

The authors conducted diagnostic experiments to isolate the primary sources of failure:

Linguistic Complexity: Varying the perplexity (PPL) of problem descriptions had a negligible impact on accuracy.
Objective Perturbations: Adding constant shifts to objective functions did not significantly degrade performance.
Constraint Augmentation: The introduction of additional, mathematically straightforward constraints (e.g., "exactly one of two roads must be included") caused a substantial and consistent accuracy drop across all problem classes and paradigms.

Conclusion on Bottlenecks: The primary bottleneck for current SOTA LLMs in optimization is not linguistic understanding or objective formulation, but the automated formulation of constraints. Models struggle to generalize beyond canonical, textbook-style formulations to handle the rich, constraint-heavy variations found in real-world applications.

4. Contributions

OPT-Engine Framework: A comprehensive, extensible benchmark enabling fine-grained, scalable control over mathematical structure and language for evaluating LLMs in optimization modeling.
Paradigm Evaluation: Empirical evidence demonstrating that PTR lacks robustness at scale, while SIR is essential for maintaining accuracy in high-complexity scenarios.
Tool Integration Analysis: Findings that while external computational tools aid local calculations, they do not resolve the fundamental inability of LLMs to adhere to global optimization constraints without solver integration.
Bottleneck Identification: Pinpointing constraint formulation as the critical failure point, distinguishing it from problem comprehension or objective perturbation.

5. Significance and Claims

The paper claims that OPT-Engine provides a necessary diagnostic rigor to move the field beyond isolated demonstrations and side-by-side comparisons on static datasets. By establishing a protocol for complexity scaling, the framework reveals that current LLMs rely heavily on patterns from canonical training data and fail to robustly reason about novel constraint combinations.

The authors assert that these findings clarify the limitations of current paradigms and offer a structured roadmap for developing next-generation LLMs. They emphasize that for optimization modeling to be viable in industrial settings, models must move beyond "reasoning illusions" and achieve fidelity in constraint formulation. The paper concludes by acknowledging that while it focuses on exact solutions (LP/MIP), future work should explore heuristics for NP-hard problems and extend the framework to nonlinear and stochastic domains. The code and data are released to facilitate this future research.