OptiTree: Hierarchical Thoughts Generation with Tree Search for LLM Optimization Modeling

AI summary

Overview

Research area: Automated optimization modeling in operations research (OR) using large language models (LLMs), with tree search over a hierarchy of standard problem types.

Technical level: Advanced. The paper assumes familiarity with optimization modeling (variables, constraints, objectives), solver code generation (Gurobi), LLM prompting strategies, and tree search.

Scope: The paper proposes OptiTree, a prompt-based method that adaptively decomposes a complex OR problem into simpler subproblems retrieved by searching a "modeling tree," then synthesizes hierarchical modeling thoughts to guide model generation.

What This Paper Is About

Turning a natural-language description of an operations research problem into a correct optimization model and solver code is technical, slow, and requires expert knowledge. Existing LLM methods break the task into a fixed sequence of steps (define variables, then constraints, then objective), but this rigid decomposition ignores how complex a problem is and performs poorly on difficult instances. OptiTree instead decomposes a complex problem into a chain of progressively simpler subproblems drawn from a tree of standard OR problem categories, and uses the modeling knowledge stored at those tree nodes to guide the final model.

Key Contributions

1. A formal notion of modeling subproblems and statement thoughts. The paper defines when one OR problem is a subproblem of another (equations 1 and 2), and identifies subproblems through natural language by distilling each problem into a set of atomic "statement thoughts" and testing semantic containment (denoted as P̃ ⊆_S P).

2. A modeling tree that organizes OR problems by taxonomy and complexity. Each node represents a problem category and stores a schema with the problem type, statement thoughts for identification, and modeling thoughts covering variable definition, constraint formulation, objective formulation, and Gurobi code templates. Parent nodes are subproblems of their children; the root is an abstract class of combinatorial optimization problems. The structure is defined as "subproblem order-preserving" (Definition 4.1), and Proposition 4.2 states the tree remains so during updates.

3. A tree search procedure for subproblem identification and global thought construction. Starting from the root, the method selects the child whose statement thoughts best match the target problem using an LLM similarity score, recurses down, and retrieves modeling thoughts from the deepest matched node (the "maximum subproblem"), integrating them into a global modeling thought.

4. An automated tree construction and update pipeline. The tree is built without human curation from OR-Instruct 3K data; a problem is only added as a node if the existing tree fails to reproduce its ground-truth answer, after which node expansion rules preserve the order-preserving property.

Main Findings

• Accuracy gains on hard benchmarks: In Table 1, OptiTree with DeepSeek-V3 reaches 98.3 on NL4Opt, 96.9 on MAMO EasyLP, 81.5 on MAMO ComplexLP, 84.2 on ComplexOR, 54.0 on IndustryOR, 74.7 on OptiBench, and 52.4 on OptMATH. With GPT-4o it reaches 96.2, 95.6, 81.0, 84.2, 48.0, 71.9, and 45.8 respectively. The paper reports approximately a 10% improvement on the challenging datasets MAMO ComplexLP, ComplexOR, and IndustryOR, and the abstract states over 10% improvements on the challenging benchmarks.

• Outperforms reasoning LLMs and fine-tuned modeling LLMs: On MAMO ComplexLP and IndustryOR, OptiTree exceeds DeepSeek-R1 (57.3 and 38.0), OpenAI-o1 (54.5 and 40.0), ORLM (37.4 and 38.0), Evo-Step (61.6 and 36.4), OptMATH (54.1 and 31.0), and LLMOPT (68.0 and 46.0).

• Motivating error analysis: CoT on IndustryOR shows that over 70% of errors in Medium and Hard problems come from incorrect variable definitions.

• Subproblem decomposition is common and identifiable: Using 50 standard problems from a textbook as ground truth, the LLM identified subproblems for 69% of IndustryOR problems, and manual verification found over 63% of problems associated with correct subproblems.

• High coverage: OptiTree identifies subproblems (excluding the root node) for an average of 88% of problems across benchmarks.

• Efficiency: OptiTree inference time is 13.9 s (NL4Opt), 9.3 s (MAMO EasyLP), 13.3 s (MAMO ComplexLP), 31.0 s (ComplexOR), and 19.9 s (IndustryOR), versus 103.2–190.1 s for MCTS and 26.4–81.8 s for CoE and OptiMUS. The one-time tree construction cost across the benchmarks is under three hours, and solver code execution is under a second.

• Ablations show both components matter: Removing tree search or modeling thoughts lowers accuracy, with a particularly large drop on challenging datasets when modeling thoughts are removed. Limiting search depth to 1 or 3 reduces performance relative to unrestricted search (for DeepSeek-V3 on ComplexOR: 68.4 at depth 1, 79.0 at depth 3, 84.2 unrestricted; on IndustryOR: 48.0, 50.0, 54.0). Removing statement thoughts drops DeepSeek-V3 to 87.1 on NL4Opt and 68.4 on ComplexOR, versus 98.3 and 84.2 with them.

• Code quality: OptiTree attains a 100.0 code pass rate on NL4Opt, MAMO EasyLP, MAMO ComplexLP, and ComplexOR with both GPT-4o and DeepSeek-V3, and 98.0 (GPT-4o) and 99.0 (DeepSeek-V3) on IndustryOR.

• Partial-credit evaluation: On 100 problems from the OptMATH training set, OptiTree matches ground-truth model statistics at rates of 90.0 (variables), 92.0 (binary variables), 83.0 (integer variables), 68.0 (constraints), and 71.0 (objective), the highest among compared methods.

• Generalizes to more backbones: Adding OptiTree improves DeepSeek-R1 (IndustryOR 38.0 to 57.0), OpenAI-o1 (40.0 to 53.0), Qwen2.5 14B (31.0 to 37.0), and Llama3.1-8B (24.0 to 28.0).

• Search depth correlates with difficulty: The greatest observed search depth across datasets is 4 (NL4Opt), 4 (MAMO EasyLP), 10 (MAMO ComplexLP), 9 (ComplexOR), and 10 (IndustryOR).

Methodology in Plain English

The researchers first check whether complex OR problems tend to contain simpler standard subproblems, and whether LLMs can spot them. They find both hold, and that giving an LLM a known model for a simpler subproblem before modeling the full problem helps.

Based on this, they build a tree of OR problem categories rather than a flat list. Simpler, foundational problems sit at the top; progressively more complex variants sit deeper, and each parent problem is a subproblem of its children. For example, a VRP branch might split into dynamic VRP and VRP with time windows. Every node stores two things: a short set of "statement thoughts" describing what the problem is about, and "modeling thoughts" giving concrete guidance on defining variables, writing constraints, forming the objective, and coding it in Gurobi.

To model a new problem, the system summarizes it into statement thoughts, walks down the tree choosing the child that best matches, recurses until no child qualifies, and then takes the thoughts from the deepest matched node and combines them with the original problem description into a global modeling thought. That global thought then drives generation of the optimization model and solver code.

The tree itself is built automatically from a dataset of problems with ground-truth models. For each problem, if the current tree already produces the right answer, nothing changes; if it fails, the problem is added as a new node under the deepest matched subproblem, placed either as a parent or a sibling of existing children so that the subproblem ordering is preserved. The construction uses 400 randomly selected problems from OR-Instruct, a 3,000-problem set, and is validated on seven evaluation benchmarks.

Why This Matters

Impact on research: The paper reframes LLM-based optimization modeling as a search over a structured space of problem taxonomy rather than a search over variables and constraints, which can grow exponentially. It also shows that retrieval of structured, hierarchical domain knowledge (analogous to retrieval-augmented generation) can beat a straightforward chain-of-thought step decomposition, and it reports gains over reasoning models such as DeepSeek-R1 and OpenAI-o1 and over fine-tuned modeling LLMs.

Real-world applications:

• Route planning and vehicle routing variants such as VRP with time windows, where a base VRP model is extended incrementally.
• Production planning, where a modeling assistant can draft a solver-ready model from a written business description.
• Economics and other domains where analysts need mixed-integer or linear programs built quickly from natural-language specifications.
• Industry settings with many one-off problem variants, where a shared tree of reusable subproblem knowledge reduces repeated expert modeling effort.

Industry relevance: The method is prompt-based, so it works on top of existing pre-trained models without fine-tuning, and its measured inference time is lower than multi-agent and MCTS baselines. The authors construct the tree using problems drawn from real-world industry datasets, and the work is a collaboration involving Noah's Ark Lab at Huawei.

Future Directions

• Extending tree coverage beyond 400 construction problems. The tree is built from 400 randomly selected problems of a 3,000-problem set, so how performance scales with more construction data or with a different source dataset is an open question; the paper's appendix section on constructing the tree with different datasets begins but is not fully available in the provided content.
• Better evaluation beyond solving accuracy. The authors state that defining a robust partial-credit metric is a significant challenge because most benchmarks lack annotated ground-truth models, so more reliable model-level comparison metrics are needed.
• Controlling search depth. Deeper search improved results, and the greatest observed depth reached 10 on MAMO ComplexLP and IndustryOR; how to decide the right depth per problem rather than leaving it unrestricted is not resolved.
• Generalization to non-standard problems. The method depends on matching an input problem to an existing subproblem; the paper reports subproblems identified for an average of 88% of problems, leaving open how to handle the remainder, including problems whose structure is not represented in the tree.

Target Audience

Researchers and practitioners working at the intersection of operations research and large language models, especially those building prompt-based or agent-based modeling assistants. It is also relevant to applied scientists who need to convert natural-language problem statements into solver-ready optimization models, and to readers interested in structured retrieval and tree search as alternatives to fixed-step chain-of-thought prompting. A working understanding of linear and mixed-integer optimization and of LLM prompting is assumed.

Authors’ abstract

Optimization modeling is one of the most crucial but technical parts of operations research (OR). To automate the modeling process, existing works have leveraged large language models (LLMs), prompting them to break down tasks into steps for generating variables, constraints, and objectives. However, due to the highly complex mathematical structures inherent in OR problems, standard fixed-step decomposition often fails to achieve high performance. To address this challenge, we introduce OptiTree, a novel tree search approach designed to enhance modeling capabilities for complex problems through adaptive problem decomposition into simpler subproblems. Specifically, we develop a modeling tree that organizes a wide range of OR problems based on their hierarchical problem taxonomy and complexity, with each node representing a problem category and containing relevant high-level modeling thoughts. Given a problem to model, we recurrently search the tree to identify a series of simpler subproblems and synthesize the global modeling thoughts by adaptively integrating the hierarchical thoughts. Experiments show that OptiTree significantly improves the modeling accuracy compared to the state-of-the-art, achieving over 10\% improvements on the challenging benchmarks. The code is released at https://github.com/MIRALab-USTC/OptiTree/tree/main.