PaperlayerView exact revision on arXiv

Source-linked AI summary

LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch

Caigao Jiang, Xiang Shu, Hong Qian, Xingyu Lu, Jun Zhou, Aimin Zhou, Yang Yu

arXiv:2410.13213v2cs.AIcs.LG

TL;DR

LLM-based optimization methods remain limited in solving accuracy and the range of problem types they can model, despite the need to automate expert-intensive formulation and coding. LLMOPT combines a universal five-element formulation with multi-instruction tuning, model alignment, and self-correction, achieving state-of-the-art generalization and an 11.08% average solving accuracy improvement. The evaluation covers six real-world datasets spanning roughly 20 domains and multiple optimization types.

  • Problem

    LLM-based methods have limited optimization generalization, encompassing both solving accuracy and the ability to model diverse problem types.

    Source: §1 · p. 2

  • Method

    LLMOPT uses a five-element universal formulation, multi-instruction fine-tuning, model alignment, and self-correction to define and solve optimization problems.

    Source: §1 · p. 2, §3.3.1 · p. 5, §3.3.2 · p. 6

  • Results

    LLMOPT achieves state-of-the-art optimization generalization with an 11.08% average solving accuracy improvement across diverse optimization tasks.

    Source: §1 · p. 3, §6 · p. 10

  • Takeaways & Limitations

    LLMOPT models linear, nonlinear, mixed-integer, and combinatorial optimization problems across six real-world datasets spanning roughly 20 domains.

    Source: §1 · pp. 2–3

    High-quality optimization training data remain scarce, with some datasets containing incorrect labels or lacking optimal-solution annotations.

    Source: §5 · p. 10

Abstract

from arXiv · show

Optimization problems are prevalent across various scenarios. Formulating and then solving optimization problems described by natural language often requires highly specialized human expertise, which could block the widespread application of optimization-based decision making. To automate problem formulation and solving, leveraging large language models (LLMs) has emerged as a potential way. However, this kind of approach suffers from the issue of optimization generalization. Namely, the accuracy of most current LLM-based methods and the generality of optimization problem types that they can model are still limited. In this paper, we propose a unified learning-based framework called LLMOPT to boost optimization generalization. Starting from the natural language descriptions of optimization problems and a pre-trained LLM, LLMOPT constructs the introduced five-element formulation as a universal model for learning to define diverse optimization problem types. Then, LLMOPT employs the multi-instruction tuning to enhance both problem formalization and solver code generation accuracy and generality. After that, to prevent hallucinations in LLMs, such as sacrificing solving accuracy to avoid execution errors, the model alignment and self-correction mechanism are adopted in LLMOPT. We evaluate the optimization generalization ability of LLMOPT and compared methods across six real-world datasets covering roughly 20 fields such as health, environment, energy and manufacturing, etc. Extensive experiment results show that LLMOPT is able to model various optimization problem types such as linear/nonlinear programming, mixed integer programming, and combinatorial optimization, and achieves a notable 11.08% average solving accuracy improvement compared with the state-of-the-art methods. The code is available at https://github.com/caigaojiang/LLMOPT.

1 INTRODUCTION

LLMOPT addresses limited accuracy and generality in LLM-based formulation and solving of natural-language optimization problems with a unified learning framework. It introduces a five-element formulation and combines tuning, alignment, and self-correction, achieving improved performance across diverse optimization types.

  • Optimization problems require specialized expertise and substantial time to formalize from natural language and implement as solver code.Complex domain-specific constraints can make expert intervention crucial for accurate solutions.Source: §1 · p. 1
  • Prior LLM methods remain limited in optimization generalization, measured by both solving accuracy and the diversity of problem types they can model.Source: §1 · p. 2
  • LLMOPT uses a five-element formulation, multi-instruction tuning, model alignment, and self-correction to improve automated problem definition and solving.The framework is evaluated on six real-world datasets spanning roughly 20 domains.Source: §1 · p. 2
  • LLMOPT achieves an 11.08% average solving accuracy improvement over state-of-the-art methods across diverse optimization problems.It handles linear and nonlinear programming, mixed integer programming, and combinatorial optimization.Source: §1 · p. 3

2 RELATED WORK

Prior work applies LLMs to optimization through prompt-based workflows and learning-based fine-tuning. These approaches include agentic reasoning, tailored prompting, instruction tuning, synthetic-data generation, and benchmark construction.

  • Prompt-based methods use LLM interfaces or specialized workflows to extract information and solve optimization problems.Chain-of-Expert assigns reasoning stages to LLM agents, while OptiMUS targets linear and mixed-integer linear programming.Source: §2 · p. 3
  • Learning-based methods fine-tune models or generate synthetic training data to improve optimization modeling and code generation.LLaMoCo uses code-to-code instruction tuning, and ORLM addresses the data demands of optimization modeling.Source: §2 · p. 3
  • Other research uses LLMs as optimizers or as components inside optimization algorithms, including genetic and Bayesian optimization workflows.Examples include prompt optimization, trajectory generation for traveling-salesman problems, and multi-objective optimization.Source: §2 · p. 3

3 METHODOLOGY

LLMOPT combines a universal five-element representation with augmented and expert-labeled data, multi-instruction fine-tuning, model alignment, and auto-testing with self-correction. These components connect natural-language problem descriptions to solver code and iterative correction.

3.1 AN OVERVIEW OF THE PROPOSED LLMOPT FRAMEWORK

  • LLMOPT comprises data preparation, learning, and auto-testing components for defining and solving optimization problems.The learning stage includes multi-instruction supervised fine-tuning and model alignment, while auto-testing adds self-correction.Source: §3.1 · p. 3, Figure 2 · p. 4

3.2.1 UNIVERSAL FORMULATION TO DEFINE GENERAL OPTIMIZATION PROBLEMS

  • The five-element formulation represents Sets, Parameters, Variables, Objective, and Constraints, preserving numerical and descriptive information needed for accurate problem definition.It can capture implicit properties such as positive-integer constraints and support linear, nonlinear, integer, and multi-objective formulations.Source: §3.2.1 · p. 4

3.2.2 DATA AUGMENTATION AND LABELING

  • LLMOPT augments 1,763 seed problems with seven instruction types, reserves test data, and uses expert review to improve training diversity and quality.Experts and GPT-4 label five-element formulations and solver code, with expert desirability labels identifying potentially incorrect GPT-4 outputs.Source: §3.2.2 · p. 5

3.3.1 MULTI-INSTRUCTION SFT

  • Multi-instruction SFT trains formulation and solving datasets so the model learns both five-element problem definition and solver-code generation.Solving examples map either natural-language problems or formulations to solver code, with expert-validated labels.Source: §3.3.1 · p. 5

3.3.2 MODEL ALIGNMENT

  • KTO model alignment uses expert desirability labels on GPT-4 completions to reduce hallucinated or inaccurate outputs without relying on ranking-based reward-model procedures.The method aligns completions for both formulation and code-generation instructions.Source: §3.3.2 · p. 6

3.4 AUTO-TESTING: FORMULATION, SOLVING AND SELF-CORRECTION

  • Auto-testing formulates the problem, generates and executes solver code, analyzes logs, and routes errors back to formulation or code generation for self-correction.This creates an iterative workflow that determines whether further resolution is needed or an optimal solution has been reached.Source: §3.4 · p. 6

4 EXPERIMENT

The experiments evaluate LLMOPT across six real-world datasets spanning diverse optimization problems and compare it with prompt-based, learning-based, and GPT-4 methods. Results show strong optimization generalization, while ablations identify the effects of five-element formulation and model alignment.

4 EXPERIMENT

  • The experiment directly tests learning-based advantages, generalization, five-element problem definition, and model-alignment effectiveness.These four questions organize the comparisons and ablation studies across the experimental sections.Source: §4 · p. 7

4.1 EXPERIMENTAL SETUP

  • The evaluation uses Execution Rate, Solving Accuracy, and Average Solving Times to assess executable code, optimal solutions, and self-correction frequency.Self-correction is capped at 12 re-solves, and the benchmark combines six datasets with strictly separated training and testing data.Source: §4.1 · p. 7, §4 · p. 7

4.2 ANALYSIS OF OPTIMIZATION GENERALIZATION

  • Compared with GPT-4o and GPT-4-Turbo, complete LLMOPT attains higher solving accuracy with fewer solving times across all six datasets.A Qwen1.5-14B model trained only with supervised fine-tuning also achieves comparable performance to GPT-4o.Source: §4.2 · p. 8, Figure 3 · p. 8, Figure 4 · p. 9
  • 11.08% average solving-accuracy improvement over state-of-the-art methods is achieved across six datasets.LLMOPT attains state-of-the-art solving accuracy against both prompt-based and learning-based methods.Source: Table 1 · p. 7, §4.2 · p. 8, Table 2 · p. 8
  • Relative to learning-based methods, five-element formulation and self-correction raise accuracy by 14.83% on four datasets.Relative to prompt-based methods, supervised fine-tuning and model alignment yield a 10.67% average improvement across three datasets.Source: §4.2 · p. 8
  • LLMOPT achieves state-of-the-art results across six datasets covering seven optimization types and more than 20 fields.The datasets include linear, nonlinear, integer, mixed-integer, multi-objective, and combinatorial optimization, with two datasets excluded from training yet still reaching state-of-the-art performance.Source: §4.1 · p. 7, §4.2 · pp. 8–9

4.3 ABLATION STUDY

  • Five-element formulation improves solving accuracy across all six datasets but can slightly reduce execution rate.Without the formulation, the model may produce error-free but inaccurate code; the formulation instead favors correct code generation and higher solving accuracy.Source: §4.3 · p. 9
  • KTO alignment significantly increases solving accuracy and reduces average solving times across all six datasets.Combining five-element formulation with KTO alignment improves solving accuracy and average solving times on complex datasets.Source: §4.3 · p. 9

5 DISCUSSION

The discussion examines larger models, OpenAI o1, general-task transfer, and training-data quality as practical considerations for LLMOPT.

Attempt on Larger Models

  • Qwen2-72B improves LLMOPT’s Solving Accuracy and Execution Rate on Mamo Complex and IndustryOR, but higher training and deployment costs motivate retaining Qwen1.5-14B.Qwen1.5-14B already achieves state-of-the-art performance in the authors’ evaluation.Source: §5 · p. 10

Compared with OpenAI o1 Model

  • OpenAI o1 solves 7 of 10 easy and 5 of 10 complex Mamo problems in single calls, while limited access and high costs favor fine-tuning open models with LLMOPT.The comparison is limited by o1’s restricted API availability and weekly trial limits.Source: §5 · p. 10

The Seesaw Issue of LLMs

  • Fine-tuning improves 6 of 10 general tasks and declines on 4, yielding a 0.3% average increase without a significant seesaw effect.The tested tasks include math, code, classification, information extraction, question answering, generation, brainstorming, rewriting, and summarization.Source: §5 · p. 10

About High-Quality Training Data

  • High-quality optimization training data remain scarce because existing datasets contain incorrect or incomplete labels, while expert annotation is time-consuming and large-scale structured data remain underexplored.The authors identify efficient collection, synthesis, and generation of diverse labeled data as an unresolved issue.Source: §5 · p. 10

6 CONCLUSION

The paper presents LLMOPT as a learning-based framework for improving both optimization-solving accuracy and the range of problem types LLMs can handle.

6 CONCLUSION

  • LLMOPT achieves state-of-the-art optimization generalization across evaluated tasks, with an 11.08% average solving-accuracy improvement.The framework combines multi-instruction supervised fine-tuning, model alignment, and a five-element formulation for diverse optimization problems.Source: §6 · p. 10

ETHICS AND REPRODUCIBILITY STATEMENT

The paper reports that its evaluation uses public data without human subjects, personal data, sensitive information, or proprietary information, and provides implementation details and code for reproducibility.

ETHICS AND REPRODUCIBILITY STATEMENT

  • The study uses publicly available test datasets and excludes human subjects, personal data, sensitive information, and proprietary or confidential information.The authors also report following recommendations for Azure OpenAI service use.Source: ETHICS AND REPRODUCIBILITY STATEMENT · p. 11
  • Experimental settings and datasets are documented in the paper and appendices, and the project code is publicly available on GitHub.Source: ETHICS AND REPRODUCIBILITY STATEMENT · p. 11

A.1 THE INTRODUCTION OF DATASETS

The appendices describe the benchmark datasets, training-data construction, implementation settings, and additional comparisons used to evaluate LLMOPT across optimization tasks.

A.1 THE INTRODUCTION OF DATASETS

  • NL4Opt contains 1,101 annotated linear-programming word problems across six domains, with target-domain problems reserved for development and testing.Source: §A.1 · p. 14
  • Mamo provides 652 easy MILP problems and 211 complex LP/MILP problems for progressively challenging optimization tasks.Source: §A.1 · p. 14
  • IndustryOR contains real operations-research problems from eight industries, spanning five optimization types and three difficulty levels, with 3,000 unlabeled training instances and 100 labeled test instances.Source: §A.1 · p. 14
  • NLP4LP includes 65 textbook- and lecture-derived problems with descriptions, parameter files, and optimal values across applications such as facility location, network flow, scheduling, and portfolio management.Source: §A.1 · p. 14
  • ComplexOR contributes 19 specialist-curated problems covering supply chains, scheduling, and warehousing logistics from academic, textbook, and industrial sources.Source: §A.1 · p. 14

A.2 TRAINING DATASETS FOR MULTI-INSTRUCTION SFT AND MODEL ALIGNMENT

  • After augmentation, the SFT dataset contains 9,828 instances and the KTO alignment dataset contains 19,563 instances, supplemented with randomly selected open-source data.Source: §A.2 · pp. 14–15

B DETAIL SETTING OF MULTI-INSTRUCTION SFT AND MODEL ALIGNMENT.

C DETAILED RESULTS

  • Across six datasets, LLMOPT outperforms GPT-4 in Solving Accuracy and Execution Rate and often performs better on Average Solving Times.Source: C DETAILED RESULTS · p. 15

E GENERALIZATION ON OTHER TASKS

This section evaluates generalization across diverse optimization tasks, documenting the templates, augmentation rules, and representative five-element formulations used for broad modeling. It illustrates how natural-language problems in allocation, geometric optimization, selection, and routing are translated into sets, parameters, variables, objectives, and constraints.

E GENERALIZATION ON OTHER TASKS

  • LLMOPT is evaluated before and after fine-tuning across 10 tasks, including Math, Code, Classification, Extraction, Open QA, Closed QA, Text Generation, and Brainstorming.The supplied passage lists these tasks but does not provide the corresponding numerical results.Source: E GENERALIZATION ON OTHER TASKS · p. 15

F SCENARIOS OF DATASETS

H TEMPLATES FOR INSTRUCTIONS ON LEARNING AND AUTO-TESTING

  • The instruction templates formalize optimization as minimizing or maximizing an objective over decision variables subject to constraints, with Sets and Parameters supplying index meanings and values.This abstraction maps specific problem scenarios into formal mathematical problems before Pyomo code generation.Source: H TEMPLATES FOR INSTRUCTIONS ON… · pp. 18–19
  • The instruction templates support five-element formulation, Pyomo solver-code generation, and self-correction by asking models to model, execute, and judge formulation and code correctness.The templates require explicit Variables, Objective, Constraints, Sets, and Parameters, and include prompts for solver output and correctness analysis.Source: H TEMPLATES FOR INSTRUCTIONS ON… · pp. 18–20

I TEMPLATES FOR DATA AUGMENTATION

  • Data augmentation generates new optimization problems by changing scenarios, problem types, constraints, objectives, variables, parameters, or wording while preserving the original meaning when required.The template randomly selects one rule from the listed augmentation strategies.Source: I TEMPLATES FOR DATA AUGMENTATION · pp. 20–21

J EXAMPLES OF FIVE-ELEMENT FORMULATION FOR DIFFERENT OPTIMIZATION PROBLEMS

  • Seven examples illustrate five-element formulations spanning linear, integer, mixed-integer, nonlinear, and combinatorial optimization, demonstrating the approach across diverse problem types.The examples are presented to show broad applicability to general optimization problems.Source: J EXAMPLES OF FIVE-ELEMENT FORMULATION… · p. 21
  • A mixed-integer distribution problem selects facilities and transportation quantities to satisfy six stores’ demands while minimizing opening and shipping costs.The formulation uses transportation variables x_ij, binary facility-opening variables y_i, demand and capacity constraints, and non-negativity constraints.Source: J EXAMPLES OF FIVE-ELEMENT FORMULATION… · p. 23
  • A geometric optimization example maximizes the area of a circular fountain constrained within an eight-vertex polygon by choosing its center and radius.The formulation defines polygon vertices as parameters, uses (x_c, y_c) and r as variables, and imposes center-inside-polygon and distance-to-edge constraints.Source: J EXAMPLES OF FIVE-ELEMENT FORMULATION… · p. 24
  • The 0-1 knapsack example models selecting among four items to maximize total value subject to a total weight limit of 5.Binary variables indicate item selection, with an objective maximizing value and a weight constraint enforcing the capacity limit.Source: J EXAMPLES OF FIVE-ELEMENT FORMULATION… · p. 25
  • The traveling-salesman example minimizes a symmetric four-city tour using binary route indicators, visit-order variables, degree constraints, and subtour elimination.The cities are A, B, C, and D, with pairwise distances specified and a route required to visit each city once before returning to its start.Source: J EXAMPLES OF FIVE-ELEMENT FORMULATION… · p. 25

K DETAILED PROCESS OF DATA LABELING AND AUGMENTATION

The data-labeling and augmentation process combines staged review, expert annotation, expert review, and aggregation to produce feasible, reviewed optimization examples. It uses independent labeling and senior review, with reported pass rates supporting process reliability.

Data labeling and augmentation

  • Four stages—preliminary review, expert labeling, expert review, and data aggregation—filter infeasible problems, create five-element formulations and executable solver code, resolve disagreements, and compile reviewed data.Difficult problems receive additional expert attention, and controversial or incorrectly labeled cases enter an independent challenging dataset.Source: K DETAILED PROCESS OF DATA LABELING… · p. 26
  • Twelve experts completed the process, spanning optimization-trained students, a university optimization professor, and operations-research algorithm engineers.Experts labeled independently, and questions were not assigned to the same expert twice during the first three stages.Source: K DETAILED PROCESS OF DATA LABELING… · p. 26
  • Review pass rates exceeded 90% for simple-question labeling and 80% for complex-question labeling.The reported statistics were considered alongside senior-expert review when assessing labeling reliability and effectiveness.Source: K DETAILED PROCESS OF DATA LABELING… · p. 26

L MORE EXPERIMENTS FOR GENERALIZATION PERFORMANCE

Additional experiments examine LLMOPT across optimization-problem types and inference correction settings. The results support broad problem-type coverage while identifying variation across datasets and stronger self-correction than the tested alternatives.

Generalization across optimization types

  • LLMOPT is reported as universal across optimization types, solving almost all kinds of problems, although accuracy varies with the distribution of formulation difficulties across datasets.The analysis covers LP, IP, MIP, NP, CO, MOP, and other problem categories, with SA reported as correctly solved problems over dataset size.Source: L MORE EXPERIMENTS FOR GENERALIZATION… · p. 26, Table 10 · p. 27
  • Table 10 organizes LLMOPT’s solving accuracy by optimization-problem type across different datasets.Bracketed values represent the number of correctly solved problems divided by the number of problems in each dataset.Source: L MORE EXPERIMENTS FOR GENERALIZATION… · p. 26, Table 10 · p. 27

Inference models and correction mechanisms

  • Table 11 compares the performance of different inference models and correction mechanisms.Source: Table 11 · p. 27

M MORE ABLATION EXPERIMENTS FOR CORRECTION MECHANISM

The ablation experiments compare self-correction with GPT-4o correction and repeated inference across datasets of differing difficulty. They report that error identification and correction outperform simply repeating executions under the tested settings.

Correction mechanism ablations

  • LLMOPT’s self-correction achieves higher solving accuracy than GPT-4o correction when Qwen-1.5 is used as the inference model.The comparison uses NL4Opt and IndustryOR, representing relatively simple and complex problems respectively.Source: M MORE ABLATION EXPERIMENTS FOR… · p. 27
  • Best-of-12 repeated inference improves performance but remains less effective than self-correction, where one correct result among 12 repetitions would count as solved.The finding highlights the tested importance of identifying and correcting errors rather than merely repeating executions.Source: M MORE ABLATION EXPERIMENTS FOR… · p. 27

Related papers

Loading 2410.13213v2…