PaperlayerView exact revision on arXiv

Source-linked AI summary

OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling

Zhicheng Yang, Yiwei Wang, Yinya Huang, Zhijiang Guo, Wei Shi, Xiongwei Han, Liang Feng, Linqi Song, Xiaodan Liang, Jing Tang

arXiv:2407.09887v4cs.LGmath.OC

TL;DR

LLM evaluation in optimization needs to cover nonlinear and tabular tasks; this paper introduces OptiBench and ReSocratic, a reverse, stepwise data-synthesis method. Fine-tuning on RESOCRATIC-29K improves open-source model accuracy on OPTIBENCH.

  • Problem

    LLMs’ mathematical reasoning in practical optimization remains an open question, while large-scale benchmark coverage of nonlinear and tabular instances was lacking.

    Source: §1 · pp. 1–2

  • Method

    They introduce OptiBench for code-based end-to-end optimization solving and ReSocratic, which builds formatted demonstrations stepwise before translating them into questions.

    Source: §1 · p. 2, §4 · p. 6

  • Results

    ReSocratic outperforms forward synthesis; SFT with RESOCRATIC-29K raises OPTIBENCH accuracy from 0.0% to 30.6% for Llama-2-7B-Chat and 13.6% to 51.7% for Llama-3-8B-Instruct.

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

  • Takeaways & Limitations

    ReSocratic synthetic data can improve open-source models on OPTIBENCH after supervised fine-tuning.

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

Abstract

from arXiv · show

Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning. Solving realistic optimization (OPT) problems in application scenarios requires advanced and applied mathematics ability. However, current OPT benchmarks that merely solve linear programming are far from complex realistic situations. In this work, we propose OptiBench, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs. OptiBench contains rich optimization problems, including linear and nonlinear programming with or without tabular data, which can comprehensively evaluate LLMs' solving ability. In our benchmark, LLMs are required to call a code solver to provide precise numerical answers. Furthermore, to alleviate the data scarcity for optimization problems, and to bridge the gap between open-source LLMs on a small scale (e.g., Llama-3-8b) and closed-source LLMs (e.g., GPT-4), we further propose a data synthesis method namely ReSocratic. Unlike general data synthesis methods that proceed from questions to answers, \ReSocratic first incrementally synthesizes formatted optimization demonstration with mathematical formulations step by step and then back-translates the generated demonstrations into questions. Based on this, we synthesize the ReSocratic-29k dataset. We further conduct supervised fine-tuning with ReSocratic-29k on multiple open-source models. Experimental results show that ReSocratic-29k significantly improves the performance of open-source models.

1 INTRODUCTION

The paper frames optimization solving as a practical test of LLMs’ mathematical and coding abilities, then introduces OptiBench and ReSocratic to address benchmark and data-scarcity gaps. It reports that fine-tuning with ReSocratic-29k significantly improves open-source model performance on OptiBench.

1 INTRODUCTION

  • Optimization problem solving tests mathematical formulation and solver use, extending beyond the mathematical reasoning abilities previously demonstrated by LLMs.The paper motivates the task by its applications in supply chains, energy scheduling, marketing, and quantitative trading.Source: §1 · p. 1
  • Prior optimization benchmarks cover limited settings: some assess formulation alone, while others solve with a solver but remain small or focus only on linear programming.The paper identifies nonlinear problems and practical tabular data as missing from prior benchmarks.Source: §1 · p. 2
  • OptiBench is a manually verified 605-question benchmark spanning linear and nonlinear programming, integer and mixed-integer variables, and tabular data.Models generate Python code to obtain numerical variable values and the objective function.Source: §1 · p. 2
  • ReSocratic addresses optimization-data scarcity by generating formatted demonstrations step by step in reverse, then back-translating them into questions.The authors contrast this process with methods that generate questions before answers.Source: §1 · p. 2
  • Llama-2-7B-Chat rises from 0.0% to 30.6%, and Llama-3-8B-Instruct from 13.6% to 51.7%, after supervised fine-tuning with ReSocratic-29k on OptiBench.The dataset contains 29k samples.Source: §1 · p. 3

2 RELATED WORK

The related-work section contrasts OptiBench and ReSocratic with earlier benchmarks and synthesis methods. It identifies gaps in end-to-end evaluation of practical optimization problems and in high-quality optimization data.

Benchmarks for Optimization Modeling

  • NL4OPT evaluates formulation construction, while Optimus and ComplexOR have fewer than 70 test samples; prior benchmarks also omit nonlinear problems and tabular data.The authors position OptiBench as a manually checked, end-to-end benchmark with 605 samples across linear, nonlinear, and tabular problems, including continuous, integer, and mixed-integer variables.Source: §2 · pp. 3–4

Data Synthesis for Mathematical Reasoning

  • Earlier mathematical-reasoning synthesis methods address informal or formal reasoning, but the authors identify a scarcity of high-quality data specifically for optimization problems.They state that this scarcity limits direct application of prior approaches to optimization.Source: §2 · p. 4

Socratic Method

  • Prior Socratic approaches use stepwise reasoning or back-translation, whereas ReSocratic reverse-constructs optimization problems from answers and claims superiority to forward Socratic synthesis.The authors distinguish back-translation as only one small step in ReSocratic.Source: §2 · p. 4

3 OPTIBENCH: BENCHMARK FOR OPTIMIZATION MODELING

OPTIBENCH evaluates end-to-end optimization solving across linear and nonlinear problems, with and without tabular data, using natural-language questions and numerical outputs. Its questions are collected and annotated with solver code, while the benchmark also examines diversity across problem formats, variable counts, and text lengths.

3 OPTIBENCH: BENCHMARK FOR OPTIMIZATION MODELING

  • OPTIBENCH spans linear and nonlinear problems with and without tables, taking natural language as input and numerical variable and objective values as output.The benchmark is designed to evaluate end-to-end optimization problem-solving.Source: §3 · p. 5
  • Questions are collected from textbooks and university coursework, with workers writing Python code that calls PySCIPOpt to solve each problem.Each sample provides the question and results.Source: §3 · p. 5
  • Across four formats—linear or nonlinear, each with or without tables—OPTIBENCH exhibits diversity in question types, number of variables, and text length.The four formats are linear with table, linear without table, nonlinear with table, and nonlinear without table.Source: §3 · p. 5
  • The evaluation has the model generate solution code, executes it, and then checks extracted numerical answers against ground truth for every variable and objective.A problem is solved only when all variables and objectives are correctly matched.Source: §3 · pp. 5–6, Figure 2 · p. 5

4 RESOCRATIC: DATA SYNTHESIS WITH REVERSE SOCRATIC

ReSocratic synthesizes optimization demonstrations step by step from formatted seeds, then translates them into code and questions. Its three stages formalize seeds, generate and filter demonstrations, and translate demonstrations into executable code and natural-language questions.

4 RESOCRATIC: DATA SYNTHESIS WITH REVERSE SOCRATIC

  • ReSocratic reverses question-first synthesis by incrementally generating optimization demonstrations from formatted seeds, then translating them into code and questions.The method has three stages: seed demonstration formalization, new demonstration synthesis, and question and code translation.Source: §4 · p. 6
  • Seed demonstrations are organized into labeled steps that pair a natural-language narrative with a mathematical formalization.Examples of step headers include defining variables, objective function, and constraints.Source: §4 · p. 6
  • An LLM generates new demonstrations from two sampled seeds, and rule and similarity filters screen the results.The similarity filter removes demonstrations whose TF-IDF vectors exceed a cosine-similarity threshold against generated ones.Source: §4 · p. 7
  • Demonstrations are translated into code and plain-text or table-form questions; demonstrations with incorrect code execution are deleted.Generated code is executed automatically to check for bugs.Source: §4 · p. 7

5 EXPERIMENTS AND ANALYSIS

The experiments evaluate OptiBench and ReSocratic-29K across multiple model and data settings. They report strong gains from fine-tuning on the synthetic data, alongside differences in difficulty across problem types.

5.1 BASELINES AND SETTINGS

  • Evaluation uses answer accuracy and code pass rate across zero-shot, few-shot, and supervised fine-tuning settings, with several model families as baselines.The data-synthesis setup uses DeepSeek-V2 to produce 29k samples; fine-tuning uses Llama-2-7B-Chat and Llama-3-8B-Instruct.Source: §5.1 · p. 7

5.2 DATA STATISTICS AND VISUALIZATION

  • For OPTIBENCH and RESOCRATIC-29K, variable-number distributions generally follow a long-tail pattern; question lengths are long-tailed in OPTIBENCH but more balanced in RESOCRATIC-29K.RESOCRATIC-29K has diversity in question types, variable numbers, question length, and text semantics.Source: §5.2 · p. 7

5.3 MAIN RESULTS

  • Fine-tuning with ReSocratic-29K raises Llama-2-7B-Chat from 0.0% to 30.6% and Llama-3-8B-Instruct from 13.6% to 51.1%; GPT-4 performs best overall.Llama-3-8B-Instruct exceeds GPT-4 on linear questions with tables.Source: §5.3 · p. 8, Table 2 · p. 9

5.4 PERFORMANCE ANALYSIS ON DATA SPLIT

  • Nonlinear questions are harder than linear ones, and questions with tables are harder than those without; performance also declines as variable counts rise.Across GPT-4 and GPT-3.5-Turbo, linear performance is 66.9% and nonlinear performance is 30.8%; GPT-3.5-Turbo degrades on long questions while GPT-4 is more balanced.Source: §5.4 · p. 8, Figure 6 · p. 9

5.5 ABLATION STUDY ON RESOCRATIC

  • The ablation reports that both the rule and similarity filters are valid, and that generated step questions improve solving ability.The authors relate the filter finding to RFT's observation that redundant data can negatively affect language models.Source: §5.5 · p. 9, Table 3 · p. 10

5.6 COMPARISON BETWEEN REVERSE SYNTHESIS AND FORWARD SYNTHESIS

  • Compared with forward synthesis, ReSocratic performs better in fine-tuning experiments, and a manual review finds its generated data more accurate.The comparison uses 1,000 samples from each method for fine-tuning and manually checks 30 samples from each.Source: §5.6 · pp. 9–10, Table 4 · p. 10

6 CONCLUSION

The conclusion presents OptiBench for end-to-end evaluation of mathematical optimization solving and ReSocratic as a reverse data-synthesis method. It reports that ReSocratic-29K outperforms forward synthesis and that fine-tuning with it improves two open-source models.

6 CONCLUSION

  • The authors plan to extend ReSocratic to other complex reasoning tasks and evaluate more models on OptiBench.These are stated future directions.Source: §6 · p. 10
  • The conclusion reports that ReSocratic outperforms forward data synthesis.It characterizes ReSocratic as a reverse data-synthesis approach.Source: §6 · p. 10
  • Fine-tuning with ReSocratic-29K significantly improves Llama-2-7B-Chat and Llama-3-8B-Instruct.The conclusion presents this as evidence of the synthesis method's effectiveness.Source: §6 · p. 10

A MORE COMPARISONS WITH OTHER BENCHMARKS

OptiBench evaluates end-to-end optimization solving, while NL4OPT evaluates mathematical formulation construction; the authors report that LLMs nearly solve NL4OPT but still find OptiBench challenging. The paper distinguishes explicit numerical problems from implicit abstract-modeling problems.

A MORE COMPARISONS WITH OTHER BENCHMARKS

B.1 FINE-GRAINED ERROR ANALYSIS

The analysis finds that nonlinear problems pose greater code-generation challenges, while formulation and code-transfer errors vary by model and prompting setup. It also examines prompting, repeated generation, and code runtime.

B.1 FINE-GRAINED ERROR ANALYSIS

  • The Code Pass rate is lower for nonlinear than linear problems, and smaller open-source models make more formulation errors than larger models.The authors attribute the coding challenge to nonlinear problems and relate formulation-error patterns to model mathematical-reasoning capacity.Source: §B.1 · pp. 16–17, Table 6 · p. 16, Table 7 · p. 17
  • gpt-4o achieves the sota performance on both formulation and code-transfer processes, while weaker models have lower code-transfer accuracy in zero-shot than few-shot settings.The authors report relatively few formulation errors for gpt-4o, gpt-4o-mini, and deepseek-v2.5; they also report 19/20 human-LLM label agreements in the error analysis.Source: §B.1 · pp. 17–18, Table 8 · p. 17

B.2 IMPACT OF DIFFERENT PROMPTING STRATEGIES

  • “First reason” prompting—reasoning before code generation—does not significantly improve performance over the original few-shot prompt.The comparison is reported in Table 9.Source: §B.2 · p. 18, Table 9 · p. 18

B.3 PASS@K PERFORMANCE

  • Model performance improves as the number of generation attempts increases in the reported Pass@k results.The experiments use temperature 0.7.Source: §B.3 · p. 18, Table 10 · p. 18

B.4 SOLVING EFFICIENCY OF THE GENERATED CODES

  • LLM-written code has efficiency akin to human-written code on samples where the LLM gives correct answers; formulation accuracy and error-free code generation remain principal challenges.The runtime comparison is limited to samples with correct LLM answers.Source: §B.4 · p. 18, Table 11 · p. 19

B.5 POTENTIAL OF LLMS TO EXTEND PROBLEM COMPLEXITY

The authors test whether an LLM can expand optimization-problem complexity and report that 9 of 10 expanded samples passed human review. They also describe additional ReSocratic details and the similarity between the synthetic dataset and its demonstration pool.

B.5 POTENTIAL OF LLMS TO EXTEND PROBLEM COMPLEXITY

  • Human review found 9 of 10 LLM-expanded samples correct for variable relevance, constraint reasonableness, and formulation correctness.The authors frame this as a foundation for future work on model self-improvement, not as a demonstrated self-improvement result.Source: §B.5 · pp. 20–21

C.1 SEED DEMONSTRATIONS

  • The data distribution of ReSocratic-29K is similar to that of the formatted demonstration pool.The authors refer to Figure 4 for the distribution of formatted demonstrations and Figure 8 for demonstration-pool statistics.Source: §C.1 · p. 21, Figure 8 · p. 21

C.2 TABULAR DATA SYNTHESIZE

ReSocratic uses distinct prompts for linear and nonlinear synthesis and for back-translating questions with or without tables. The paper reports correct back-translations in all 20 reviewed samples and formats training examples as question-and-code pairs.

C.2 TABULAR DATA SYNTHESIZE

  • Different prompts are used to synthesize linear and nonlinear data, and separate back-translation prompts produce questions with or without tables.The prompts are provided in Sections E.2.1–E.2.3.Source: §C.2 · p. 22

C.3 BACK-TRANSLATION

  • Back-translation is described as nearly equivalent to extracting the natural-language portion of a demonstration, and all 20 reviewed question samples were correct.Reviewers checked whether generated questions included the demonstration’s information and remained consistent with its question.Source: §C.3 · p. 22

C.4 TRAINING SAMPLE FORMAT

  • Each training sample pairs a synthetic question with its verified code in a prompt that asks for a PySCIPOpt solution.The sample replaces the {Question} and {Code} placeholders with those materials.Source: §C.4 · pp. 22–23

D.1 MORE DETAILS OF DATA COLLECTION AND ANNOTATION

This appendix details OptiBench data collection and formats, along with prompts and templates for solving, judging, and generating optimization examples. It illustrates how scenarios are translated into mathematical formulations, PySCIPOpt code, and questions, including linear and nonlinear cases.

D.1 MORE DETAILS OF DATA COLLECTION AND ANNOTATION

  • Questions were sourced from textbooks and university assignments or exams, independently modeled by four annotators, solved with PySCIPOpt, and relabeled when their results disagreed.The cited textbooks are Bertsimas & Tsitsiklis (1997), Conforti et al. (2014), and Wolsey (2020). Six master’s-level annotators staffed the process; four labeled and two corrected inconsistent samples.Source: §D.1 · p. 23

D.2 DATA FORMAT

  • OptiBench JSON samples store a natural-language question, results, a four-way problem type, and an index.Results give optimal values for described variables and objectives; when annotators cannot confirm a unique optimum, they record only the objective and its optimal value.Source: §D.2 · pp. 23–24
  • ReSocratic-29k samples are stored in JSON with a natural-language question and corresponding Python code solution.The question supplies the background, objective, and constraints for identifying variables, modeling the problem, and obtaining numerical results with a solver.Source: §D.2 · p. 24

E.1.1 ZERO-SHOT PROMPT

  • The zero-shot prompt asks the model to solve a question in Python using a PySCIPOpt code template for variables, objective, constraints, optimization, and output.The template also handles cases where the problem cannot be solved to optimality.Source: §E.1.1 · p. 25

E.1.2 FEW-SHOT PROMPT

  • The few-shot prompt provides cake-production and widget-production examples before asking the model to solve a new question with Python.The examples demonstrate a linear cake-profit problem and a widget profit-rate objective with resource constraints.Source: §E.1.2 · pp. 25–26

E.1.3 FEW-SHOT (FIRST REASON) PROMPT

  • The first-reason few-shot prompt requires a step-by-step mathematical formulation before generating PySCIPOpt code.Its demonstrations formulate both a cake-profit problem and a widget profit-rate problem before presenting code.Source: §E.1.3 · pp. 27–28
  • The few-shot prompt illustrates integer decision variables, a profit-rate objective, and material and production-time constraints in a solver-code example.The sample also requires at least 10 units of each widget, while the code defines variables, sets the objective, adds constraints, and optimizes.Source: §E.1.3 · p. 28

E.1.5 LLM AS A JUDGE PROMPT

  • The judge prompt asks an evaluator to extract the student code’s mathematical formulation, compare it with ground truth, and return Correct or Wrong.It supplies placeholders for the ground-truth formulation and student code.Source: §E.1.5 · p. 29

E.2.1 LINEAR DEMONSTRATION GENERATION

  • The linear-generation prompt requests a real-world linear scenario with a new background, correct mathematical logic, variable domains, one objective, and constraints.Its format pairs natural-language descriptions with formal definitions.Source: §E.2.1 · p. 29

E.2.2 NONLINEAR DEMONSTRATION GENERATION

  • The nonlinear-generation prompt similarly requests a real-world nonlinear scenario with a new background, correct logic, variable domains, one nonlinear objective, and constraints.The scenario format presents natural-language descriptions alongside formal definitions.Source: §E.2.2 · p. 30

E.2.3 QUESTION GENERATION

  • The question-generation prompt converts scenarios into clear, concise questions without exposing formal solutions or omitting information, including when scenario data is presented in a table.The examples include a table of widget prices, costs, and production times and translate scenario constraints into natural-language questions.Source: §E.2.3 · pp. 30–32

E.2.4 CODE GENERATION

  • The template asks the assistant to solve optimization scenarios in Python with PySCIPOpt, and its examples show defining variables, objectives, and constraints before solving and reporting results.The code sets the objective through an auxiliary variable because PySCIPOpt does not support a nonlinear objective directly.Source: §E.2.4 · p. 33
  • The cylindrical-jar example minimizes metal cost using radius and height variables, a surface-area objective, and a minimum-volume constraint.The example gives metal a cost of $10 per square meter and requires a volume of at least 1000 cubic centimeters.Source: §E.2.4 · p. 33
  • The poster example minimizes used-paper area with top and bottom margins of 2 inches, side margins of 1 inch, and a poster-area constraint of 100 square inches.Its objective is (w + 2) * (h + 4), subject to w * h = 100.Source: §E.2.4 · pp. 33–34

E.1.4 RESULTS EXTRACTION PROMPT

The final-answer prompt asks for an answer after code execution and specifies a numerical, boxed format rounded to five decimal places.

E.1.4 RESULTS EXTRACTION PROMPT

  • The prompt asks for a final answer according to the code output.Source: §E.1.4 · p. 29
  • The answer must be boxed and given in numerical form only.Source: §E.1.4 · p. 29
  • The numerical answer should be rounded to five decimal places.Source: §E.1.4 · p. 29

Related papers

Loading 2407.09887v4…