OptiMUS

Optimization Modeling Using Solvers and LLMs

By Stanford University, 2024. Optimization. Formalize and solve.

An LLM translates natural-language optimization problems into Mixed-Integer Linear Programs and Gurobi solver code, repairs bugs from runtime errors, and solves the model to optimality.

Read the paper

The loop

Proposes
Mathematical objective and constraint formulations plus executable Gurobi Python code, generated by specialized GPT-4 agents
Judged by
The Gurobi MILP solver and automated checks that surface runtime errors from executing the generated code
Steers
Runtime errors from executing the generated code go back to the formulator or programmer agents.

Headline result

At ICML 2024, OptiMUS solved 78.8% of NL4OPT (vs 64.2% for Chain-of-Experts), 66.7% of ComplexOR (vs 38.1%), and 72.0% of the authors' graduate-level NLP4LP benchmark (vs 53.1%). Removing the solver-guided debugging loop in ablations dropped NLP4LP accuracy from 71.6% to 58.2%.

What this does not prove

Gurobi certifies the exact optimum of the generated MILP, not that the MILP faithfully captures every nuance of the English prompt. If the model writes a plausible but semantically wrong constraint that still compiles and solves feasibly, the solver optimizes the wrong problem.

How it generalizes the harness

Instead of asking the LLM to guess numeric variable assignments, the LLM compiles the problem into a formal MILP and hands the combinatorial search and optimality certificate to Gurobi.

Classification

Classification of OptiMUS (Optimization Modeling Using Solvers and LLMs)
What it proposes	Formal specification
Generative model	GPT-4 (frozen), structured across formulator, programmer and evaluator agents with a connection graph
Algorithmic authority	Gurobi Mixed-Integer Linear Programming (MILP) solver plus automated execution checks
Feedback	Verifier errors
What gets updated	Prompt context
When it runs	At inference time
Validity	Formal (machine-checked)
Evidence	Experiments reported
Lineage	Original system