PaperlayerView exact revision on arXiv

Source-linked AI summary

OptiMUS: Optimization Modeling Using MIP Solvers and large language models

Ali AhmadiTeshnizi, Wenzhi Gao, Madeleine Udell

arXiv:2310.06116v2cs.AI

TL;DR

Optimization modeling requires expertise that limits the wider use of optimization methods, while LLMs’ role in optimization remains underexplored. OptiMUS uses an LLM agent to formulate and solve problems from structured natural-language descriptions, and increases solve rate by 91% compared to direct prompting. The reported debugging process can fix minor errors but not fundamental modeling errors.

  • Problem

    Optimization modeling requires expert knowledge, and the role of LLMs in optimization remains underexplored amid a lack of comprehensive benchmarks.

    Source: §1 · p. 1

  • Method

    OptiMUS takes a structured natural-language problem description, generates a mathematical formulation and tests, then creates and revises solver code against errors or failed tests.

    Source: §3 · p. 4, §3.1 · p. 4

  • Results

    OptiMUS increases the solve rate by 91% compared to direct prompting.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Automating optimization modeling could help sectors without access to optimization experts improve efficiency using optimization techniques.

    Source: §1 · p. 1

    Debugging can fix minor errors such as missing constraints or syntax and semantic errors, but not fundamental modeling errors.

    Source: §5 · p. 9

Abstract

from arXiv · show

Optimization problems are pervasive across various sectors, from manufacturing and distribution to healthcare. However, most such problems are still solved heuristically by hand rather than optimally by state-of-the-art solvers, as the expertise required to formulate and solve these problems limits the widespread adoption of optimization tools and techniques. We introduce OptiMUS, a Large Language Model (LLM)-based agent designed to formulate and solve MILP problems from their natural language descriptions. OptiMUS is capable of developing mathematical models, writing and debugging solver code, developing tests, and checking the validity of generated solutions. To benchmark our agent, we present NLP4LP, a novel dataset of linear programming (LP) and mixed integer linear programming (MILP) problems. Our experiments demonstrate that OptiMUS solves nearly twice as many problems as a basic LLM prompting strategy. OptiMUS code and NLP4LP dataset are available at \href{https://github.com/teshnizi/OptiMUS}{https://github.com/teshnizi/OptiMUS}

1 INTRODUCTION

Optimization modeling still requires expertise that limits its use, while LLM capabilities in optimization remain underexplored. The paper introduces NLP4LP and OptiMUS, an agent for formulating and solving optimization problems, and reports a 91% solve-rate increase over direct prompting.

1 INTRODUCTION

  • Optimization modeling requires expertise to transform business problems into standard mathematical form, limiting access to optimization methods in many organizations.The paper notes that automating modeling could help sectors without access to optimization experts improve efficiency.Source: §1 · p. 1
  • The paper identifies LLMs as a potential route to wider access, while noting that their role in optimization remains underexplored and lacks comprehensive benchmarks.The authors aim to examine LLM capabilities and limitations in optimization.Source: §1 · p. 1
  • NLP4LP is a dataset of 52 LP and MILP problems with human-expert formulations, solutions, and code to check optimality.The dataset also includes sample formulations in markdown and code, and uses a standardized format for natural-language problem descriptions.Source: §1 · pp. 1–2
  • OptiMUS is an LLM-based agent that formulates and solves optimization problems.Its workflow is illustrated in Figure 1: it generates a mathematical formulation, writes and runs solver code, tests the solution, and revises code after errors or failed tests.Source: §1 · p. 2, Figure 1 · p. 2
  • OptiMUS increases the solve rate by 91% compared to direct prompting through problem rephrasing and automated testing and debugging.The latter techniques support self-fixing solutions.Source: §1 · p. 2

2 CHALLENGES OF OPTIMIZATION MODELING USING LLMS

The section identifies modeling and implementation demands alongside three challenges for LLM-based optimization: varied problem representations, large numerical inputs, and unreliable outputs. It motivates a multi-faceted approach combining language processing, optimization theory, and software engineering.

2 CHALLENGES OF OPTIMIZATION MODELING USING LLMS

  • Choosing a solver and producing a high-quality implementation are difficult because solver interfaces and functionality differ and manuals can be extensive.Switching solvers to find the best fit for a problem can add further difficulty.Source: §2 · p. 3
  • LLMs may struggle with varied terminology, notation, or omitted assumptions when representing the same optimization problem.Examples include vehicle versus car, different names for price and capacity, and unstated nonnegativity or integrality assumptions.Source: §2 · p. 3
  • Large numerical datasets can exceed LLM context limits, and performance can decrease as input context grows.Optimization data, such as customer or product attributes, may require gigabytes of memory; Figure 2 depicts separating numerical data from the description and having the LLM write code to interact with the data file.Source: §2 · p. 3, Figure 2 · p. 4
  • Generated code may be incorrect or non-executable, and a running program can still return an incorrect solution that is difficult to verify.Writing tests to check output correctness can also be complicated and time-consuming.Source: §2 · p. 3
  • Addressing optimization with language models calls for a multi-faceted approach combining natural language processing, optimization theory, and software engineering.The paper frames its agent and empirical analysis as responses to the identified challenges.Source: §2 · p. 3

3 METHODOLOGY

OptiMUS takes a structured natural-language problem description, formulates the optimization model, generates solver code, and checks and revises solutions. It can also rephrase problems and retry the same workflow.

3 METHODOLOGY

  • OptiMUS transforms a structured problem description into a mathematical formulation and tests, generates solver code, and revises it after execution errors or failed tests.The workflow repeats until the problem is solved or the maximum number of iterations is reached.Source: §3 · p. 4

3.1 STRUCTURED NATURAL LANGUAGE OPTIMIZATION PROBLEM (SNOP)

  • SNOP separates problem descriptions from data stored in JSON, giving OptiMUS a standardized input for developing formulations.The solver later joins the generated formulation with the data, which may be large.Source: §3.1 · p. 4, A SNOP has 6 fields (see Fig. 3) · p. 5

A SNOP has 6 fields (see Fig. 3):

  • A SNOP specifies problem type and information, input and output formats, objective, and solver.Problem parameters are marked in the description and replaced with problem data after formulation.Source: A SNOP has 6 fields (see Fig. 3) · pp. 4–5

3.2 FORMULATION

  • Given a SNOP, OptiMUS generates a markdown formulation that defines the optimization variables, constraints, and objective function.Source: §3.2 · p. 6

3.3 CODE GENERATION

  • OptiMUS turns the formulation into Python code that reads JSON data, calls a solver, and writes the output; prompts include solver-specific instructions to avoid recurring coding mistakes.The benchmark uses Gurobi and cvxpy.Source: §3.3 · p. 6

3.4 TESTS AND REVISION

  • OptiMUS generates tests for output formatting, constraint satisfaction, and consistency, then uses failed-test messages to revise code.Users can revise generated tests or add tests; the benchmark includes supervised tests for every problem, which the authors report take roughly five times less time to develop than equivalent tests from scratch.Source: §3.4 · p. 6

3.5 AUGMENTATION

  • OptiMUS automatically rephrases problems and retries the same workflow, using a solution from any successful rephrasing to solve the problem.Source: §3.5 · p. 6

4 DATASET

NLP4LP is a 52-instance benchmark of LP and MILP problems, with multiple problem and solution-related views for each instance.

4 DATASET

  • NLP4LP contains 52 problems: 41 LP and 11 MILP instances drawn from optimization textbooks and lecture notes.Source: §4 · p. 7
  • The source texts predate 2021 and may have appeared online, but NLP4LP modifies them as SNOPs and abstracts numerical values into parameters; the textbooks contain no code snippets.The authors note that LLMs still find these problems challenging to formulate and solve.Source: §4 · p. 7
  • Each problem includes a SNOP, validity tests, example data, an optimal value, and a sample optimal output.Source: §4 · p. 7

5 EXPERIMENTS AND ANALYSIS

Experiments compare OptiMUS components against simple prompting on NLP4LP using GPT-3.5 and GPT-4. For GPT-4, successive capabilities improve success, and augmentation improves both success and execution; GPT-3.5 responds differently to automated tests.

5 EXPERIMENTS AND ANALYSIS

  • The evaluation compares simple prompting, debugging, automatic or supervised tests, and the full OptiMUS pipeline, using success and execution rates.Success requires satisfying all constraints and finding an optimal solution; execution rate measures executable code that generates an output.Source: §5 · pp. 7–8
  • For GPT-4, success improves with each added capability, and augmentation improves both success and execution rates over the other modes.Figure 6 compares success and execution rates across modes on NLP4LP for GPT-3.5 and GPT-4.Source: Figure 6 · p. 8, §5 · pp. 8–9
  • For GPT-3.5, automated tests decrease performance because generated tests can be incorrect or misleading; supervised test-fixing returns performance to simple-prompting levels.Augmentation significantly improves GPT-3.5 success by offering multiple attempts with different rephrasings.Source: §5 · p. 9
  • One or two extra augmentations considerably improve performance, but further additions contribute little as rephrasings become similar to the initial problem.More augmentations also require more computation.Source: §5 · p. 9
  • One or two extra debugging iterations can significantly improve performance, but additional iterations are not useful when errors reflect fundamental modeling mistakes.Debugging can fix minor omissions or syntax and semantic errors, but not fundamental modeling errors.Source: §5 · p. 9
  • Successful runs generate an average of 4117.1 ± 1509.7 tokens and took less than 7 minutes in these experiments, excluding solver runtime.Formulation speed depends on internet speed, server responsiveness, model size, and account priority; augmented instances can be tackled in parallel.Source: §5 · p. 9

6 RELATED WORK

Related work spans LLMs for mathematical tasks and methods that connect language models to tools. OptiMUS instead uses optimization-problem structure in an LLM workflow with optimization solvers.

6 RELATED WORK

  • Prior mathematical-LLM work includes datasets for broad math topics and arithmetic, and model training on mathematical and scientific papers; these efforts evaluate or improve direct LLM performance without integrating other tools.Examples include Frieder et al. (2023), Yuan et al. (2023), and Lewkowycz et al. (2022).Source: §6 · pp. 9–10
  • Other work uses intermediate reasoning, program generation with runtime execution, or symbolic solvers to extend LLM performance through tools.Examples include Wei et al. (2023), Gao et al. (2022), and He-Yueya et al. (2023).Source: §6 · p. 10
  • Unlike general-purpose LLM approaches, OptiMUS exploits optimization-problem structure in a workflow that combines LLMs with optimization solvers.Source: §6 · p. 10
  • Optimization research also includes exact and heuristic algorithms, deep-learning enhancements to solvers, and direct use of LLMs as solvers.The authors note that progress in underlying LLMs may support their results.Source: §6 · p. 10

7 CONCLUSION

The paper presents OptiMUS and NLP4LP as a proof of concept for automating stages of optimization with LLMs and traditional solvers. It identifies broader problem coverage and unstructured inputs as directions for further work.

7 CONCLUSION

  • The paper presents OptiMUS for natural-language optimization modeling and NLP4LP as a dataset used to demonstrate the efficacy of its techniques.The authors characterize the work as a proof of concept for automating stages of optimization with LLMs and traditional solvers.Source: §7 · p. 10
  • Future work includes expanding NLP4LP with more instances and optimization classes, supporting unstructured natural-language inputs, and fine-tuning LLMs for optimization modeling and solving.The authors also identify prompt-quality improvements as an avenue for further investigation.Source: §7 · p. 10

A APPENDIX

The appendix figures present templates for problem formulation, code generation, tests, rephrasing, and error-driven code revision, alongside an example of SNOP and JSON formats.

A APPENDIX

Related papers

Loading 2310.06116v2…