OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models

1. Introduction

• Expertise requirements limit the adoption of optimization despite its potential applications across operations, economics, engineering, and computer science.The paper notes that 81% of Gurobi commercial solver users have advanced degrees, including 49% with operations-research degrees.Source: §1 · p. 1
• Ambiguous terminology, omitted assumptions, long descriptions, large data, and unreliable generated code make real-world optimization modeling difficult for LLMs.Failure modes include incorrect or non-executable code and apparently valid outputs based on omitted constraints.Source: §1 · pp. 1–2
• NLP4LP contributes an open-source dataset of 67 complex optimization problems designed to capture long descriptions and large problem data.The paper argues that existing natural-language optimization datasets are too easy for these challenges.Source: §1 · p. 2
• OptiMUS uses a modular LLM-based agent and connection graph to process constraints and objectives independently while separating data from problem descriptions.This design supports long descriptions and large data without excessively long prompts.Source: §1 · p. 2, Figure 1 · p. 2

2. Background and Related Work

• An optimization workflow formulates an objective and constraints mathematically, then solves the realization using data and an optimization solver.MILPs are defined through an objective function and a set of constraints.Source: §2 · p. 2
• Prior LLM approaches generate optimization solutions or intermediate formulations, but context-length degradation limits them to relatively small problems.The cited approach directly generates solutions without traditional solvers and is reported as limited by growing input context.Source: §2 · p. 3
• Optimization chatbots have focused on detecting infeasibility, answering model queries, or assisting modeling rather than providing the same end-to-end solver role.The paper distinguishes these assistants from its optimization-modeling objective.Source: §2 · p. 3
• Benchmark-driven work includes natural-language LP datasets, intermediate representations, cooperative multi-agent systems, and traditional MILP benchmarks such as MIPLIB.MIPLIB instances are mostly detached from their original formulations, whereas this paper focuses primarily on MILP modeling.Source: §2 · p. 3

3.1. Structured Problem

• OptiMUS preprocesses a natural-language problem into parameters, clauses, objective and constraints, background information, and a modular structured problem.The preprocessor separates numerical data for later use and initializes clauses for subsequent formulation and coding.Source: §3 · p. 3, §3.1 · p. 3

3.3. The connection graph

• The connection graph records relationships among constraints, objectives, parameters, and variables so prompts retrieve only relevant context for formulation, coding, and debugging.This keeps prompts short and is presented as central to consistency and scalability.Source: §3.2 · p. 4, §3.3 · p. 5

3.2. Agents

• The manager coordinates formulation, programming, and evaluation agents, repeatedly assigning tasks until clauses are formulated, coded, and validated.The workflow can revisit earlier steps when evaluators or programmers identify incorrect formulations or code.Source: §3.2 · pp. 4–5, §3.1 · p. 4
• The formulator defines variables and auxiliary constraints, writes or corrects mathematical formulations, and updates graph links for each clause.It identifies relevant parameters and variables and revises clauses marked incorrect by downstream agents.Source: §3.2 · p. 4, Figure 3 · p. 5
• The programmer writes and debugs solver code, while the evaluator executes it on data and flags runtime errors or bogus clauses for repair.The experiments use Python and Gurobi, although the design can target other solver and programming-language combinations supported by the LLM.Source: §3.2 · p. 5

4.1. Dataset

• NLP4LP contributes 67 challenging instances—54 LP and 13 MILP problems—with long descriptions, varied applications, sample data, and optimal values.The dataset includes facility location, network flow, scheduling, portfolio management, and energy optimization problems.Source: §4.1 · p. 6

4.2. Overall Performance

• OptiMUS outperforms standard prompting, Reflexion, and Chain-of-Experts in accuracy across all evaluated datasets by a large margin.The comparison uses accuracy because compilation and runtime error rates can be misleading when generated code is irrelevant or removes relevant sections.Source: §4.2 · p. 6

4.3. Ablation Study

• Ablations show that debugging and GPT-4 materially affect OptiMUS performance, while smaller models struggle with its longer, more complex, modular prompts.Fine-tuning smaller models on these prompt templates is proposed as a way to improve performance and reduce cost.Source: §4.3 · pp. 6–7

4.4. Sensitivity Analysis

• Allowing more manager-selected agent calls improves performance on ComplexOR and NLP4LP, where OptiMUS often iteratively fixes early mistakes.NL4OPT problems are usually solved after one selection of each formulator, programmer, and evaluator.Source: Figure 5 · p. 7, §4.4 · p. 7
• OptiMUS prompts remain nearly constant in length across datasets because modular calls retrieve only relevant context, unlike CoE prompts that grow on harder datasets.The modular approach is presented as enabling scaling to larger and longer problems.Source: §4.4 · p. 7

4.5. Failure Cases

• Failures include missing or wrong constraints, incorrect mathematical models, and code that remains erroneous after debugging, with incorrect modeling more common on complex datasets.The authors identify problem interpretation as a challenge and suggest fine-tuning as an important direction for future research.Source: §4.5 · pp. 7–8

• OptiMUS achieves state-of-the-art performance across existing datasets and scales to problems with large amounts of data and long descriptions.The paper also introduces NLP4LP, a dataset of long and challenging optimization problems.Source: §5 · p. 8
• The paper presents OptiMUS as a proof of concept for combining LLMs with traditional solvers to automate stages of optimization.Source: §5 · p. 8
• Real-world optimization problems remain complex and multifaceted, requiring domain-specific considerations and integration of existing optimization techniques.Source: §5 · p. 8
• Future work includes adapting prompts for smaller models, incorporating user feedback, selecting solvers automatically, and using reinforcement learning to improve agent coordination.Source: §5 · p. 8

• The authors state that their work may have societal consequences, but they do not identify any specific consequence for emphasis.Source: §6 · pp. 8–9

• Optimization solvers can perform better when structures such as SOS, indicator variables, and general constraints are explicitly specified during formulation.Source: A. Optimization Techniques · p. 11
• OptiMUS uses cheatsheet prompts to determine whether a listed structure applies to the current formulation.Source: A. Optimization Techniques · p. 11
• When a structure applies, OptiMUS adjusts the formulation to use the customized solver interface when available.Source: A. Optimization Techniques · p. 11

B.1. Manager Prompt

• The manager selects the next expert or declares the problem solved based on conversation history, while routing ambiguity to a user proxy and runtime errors to programming agents.Source: §B.1 · p. 12

B.2. Formulation generation prompt

• The formulation prompt asks an expert to express each problem clause in standard LP or MILP form using available context, variables, and parameters.Source: §B.2 · p. 13
• Formulation outputs use JSON containing descriptions, LaTeX expressions, variables, and auxiliary constraints, while forbidding new parameters and requiring any auxiliary variables to be declared.Source: §B.2 · p. 13

B.3. Formulation fixing prompt

• The formulation-fixing prompt instructs the agent to inspect an existing target formulation and return a corrected JSON formulation using the defined variables and parameters.Source: §B.3 · p. 14

B.4. Clause Coding prompt

• Clause coding converts modeled constraints into solver code, assumes imported gurobipy and defined inputs, and emits only delimited code or a comment when no code is needed.Source: §B.4 · p. 15

B.5. Variable coding prompt

• Variable coding generates indexed or scalar Gurobi variables from their definitions, preserving symbol conventions and using addVar for scalar variables.Source: §B.5 · p. 16

B.6. Debugging prompt

• Debugging isolates errors to the target modeling segment when imports, parameters, and variables are assumed correct, then either explains a formulation fault or returns fixed code.Source: §B.6 · p. 17