Research map / Large language models / Agents, code and math
Autoformulation of Mathematical Optimization Models Using LLMs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames LLM-based autoformulation of LP/MILP models as a hierarchical MCTS search with SMT-based pruning of equivalent candidates and LLM rank/comparative evaluation, reaching higher formulation accuracy than GPT-4 baselines and ORLM on four benchmarks.
Problem
Automatically translating natural language optimization problem descriptions into solver-ready mathematical optimization models (autoformulation), which has a large problem-dependent hypothesis space, redundant equivalent candidates, and no reliable correctness signal.
Approach
Decompose optimization model formulation into four hierarchical levels (parameters/variables, objective, equality constraints, inequality constraints) and search them with MCTS where an LLM generates and ranks candidate components, SMT solvers prune functionally equivalent candidates, and terminal rewards combine solver feedback with a pairwise LLM comparison against baseline models.
Key results
- With N=3 rollouts, the autoformulator reaches 92.21% on NL4OPT and 61.4% on MAMO ComplexLP, versus 85.7% and 39.3% for finetuned ORLM-Llama3-8B at N=1.
- On ComplexOR the method reaches 72.2% (N=3) versus 66.7% for OptiMUS and 44.4% for ORLM.
- Comparative LLM evaluation gives a biserial correlation of 0.48 with correctness on IndustryOR, versus 0.23 for direct 1-100 scoring.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase MCTS rollouts from 1 to 3 | Autoformulator · NL4OPT | accuracy: 85.24 % -> 92.21 % | Helped |
| increase MCTS rollouts from 1 to 3 | Autoformulator · IndustryOR | accuracy: 35.0 % -> 42.0 % | Helped |
| increase MCTS rollouts from 1 to 3 | Autoformulator · MAMO (ComplexLP) | accuracy: 43.8% -> 61.4% | Helped |
| increase MCTS rollouts from 1 to 3 | Autoformulator · ComplexOR | accuracy: 66.7% -> 72.2% | Helped |
| replace MCTS search with Depth-First Search without uncertainty guidance or search feedback (ablation) | Autoformulator · NL4OPT | accuracy: 92.21 % -> 66.53% | Hurt |
| replace MCTS search with Depth-First Search without uncertainty guidance or search feedback (ablation) | Autoformulator · IndustryOR | accuracy: 42.0% -> 28.0% | Hurt |
| use sequential component sampling without structured search or pruning (ablation) | Autoformulator · NL4OPT | accuracy: 92.21 % -> 60.82% | Hurt |
| use sequential component sampling without structured search or pruning (ablation) | Autoformulator · IndustryOR | accuracy: 42.0% -> 28.0% | Hurt |
| use comparative evaluation against consistent baselines instead of independent direct scoring | IndustryOR formulation evaluation · IndustryOR problems with correct solutions | biserial correlation: 0.23 -> 0.48 | Helped |
| add LLM-based prior scores to guide greedy partial-formulation selection | MCTS autoformulator · Autoformulation search tree | formulation correctness | Helped |
| add symbolic pruning of redundant formulations | MCTS autoformulator · Formulation search | formulation generations required: 1000x | Helped |
Surprising findings
- Expert review found 82% agreement between objective-value-based accuracy and expert judgment, with some incorrect models matching the correct objective value.
- Categories with lower accuracy tended to have higher tree entropy, suggesting entropy may indicate formulation uncertainty.
Limitations
- Final correctness is measured by matching objective values, which the expert study shows does not always capture semantic correctness.
- SMT equivalence checks may be undecidable for mixed-integer or nonlinear formulations, so the method conservatively keeps such candidates.
- Evaluated only on LP/MILP benchmarks with GPT-4-0613; deterministic parser handled all experimental problems but may not generalize to complex transformations.
Experimental setup
Datasets: NL4OPT IndustryOR MAMO (ComplexLP) ComplexOR
Benchmarks: NL4OPT IndustryOR MAMO (ComplexLP) ComplexOR
Metrics: execution accuracy Pass@N Best-of-N
Baselines: Standard GPT-4 Reflexion Chain-of-Experts OptiMUS ORLM Tree-of-Thought Sequential sampling
Builds on: Monte-Carlo Tree Search UCT Reflexion Tree-of-Thoughts
Closest papers by meaning
- LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch (ICLR 2025 · similarity 0.90)
- Enhancing Decision Making Through the Integration of Large Language Models and Operations Research Optimization (AAAI 2025 · similarity 0.90)
- OptiTree: Hierarchical Thoughts Generation with Tree Search for LLM Optimization Modeling (NeurIPS 2025 · similarity 0.90)
- OptMATH: A Scalable Bidirectional Data Synthesis Framework for Optimization Modeling (ICML 2025 · similarity 0.89)
- OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling (ICLR 2025 · similarity 0.88)
- OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.