Large language models produce slower optimization models despite correct solutions
Right Answers, Costly Models: The Efficiency Gap in LLM-based Optimization Modeling
Machine LearningArtificial Intelligence
Summary
Optimization modeling is a way to turn real-world problems into math formulas so computers can find the best answers. The authors studied how well large language models (LLMs) can create these math models automatically. They found that while LLMs often produce correct models, these models usually take longer to solve than expert-made versions. They created new tests to compare the speed and correctness of models made by LLMs and experts and suggest evaluating both aspects, not just correctness.
What this means in practice
- •For optimization software developers: Improve automated model generation tools by integrating checks for solver efficiency alongside correctness.
- •For operations research teams: Use expert-designed modeling techniques as benchmarks to evaluate and select efficient automated optimization models.
Authors
Zhong Li, Xin Huang, Jinhui Wan, Xiangyi Wang, Shenkai Zhang, Ruiqi Chen, Wenyu Liu, Zaiwen Wen, Ziyan Luo
Abstract
Optimization modeling formulates real-world decision problems as mathematical programs that solvers can use to find optimal decisions. Large language models (LLMs) can automate this process, but the resulting correct formulations can require substantial time and memory to construct and solve, limiting practical scalability. Therefore, we systematically investigate whether LLMs can identify problem structure from natural-language descriptions and apply suitable optimization modeling techniques to generate mathematical models and solver code that solve the problems correctly and efficiently. To this end, we first curate OptTips, a knowledge base of 50 expert modeling techniques in eight families. Using this knowledge, we develop OptDachshund, a multi-agent framework that transforms problems from existing optimization benchmarks into new tasks for evaluating LLMs' use of modeling techniques. It constructs conventional and expert mathematical models with solver code for the same task and data, providing baselines for correctness and computational cost. The resulting EfficientOpt benchmark contains 561 expert-reviewed tasks with paired reference implementations. Evaluation of 11 representative LLMs reveals an efficiency gap on correctly solved tasks with comparable measurements: for every LLM, most generated programs take longer to solve than their expert counterparts. Within the comparable reference-size subset, 57\% of programs with correct objective values and fewer variables and linear constraints have longer recorded solver times. Case studies show that different modeling techniques can achieve the same optimal value at similar recorded cost. Faster solving may not reduce execution time if the code takes longer to prepare data and build the model. LLM optimization modeling should therefore be evaluated for both correctness and computational efficiency.