用图论方法评估大模型优化建模能力，解决传统方法不一致、耗时问题。
ORGEval: Graph-Theoretic Evaluation of LLMs in Optimization Modeling
- 将优化模型转为图结构，通过图同构检测判断建模等价性。
- 在随机参数下实现100%结果一致性，运行速度远超传统求解器。
- 适用于评估大模型建模能力，尤其适合优化领域研究者使用。
工业场景中的优化问题建模需要大量人工投入与专业知识。尽管大语言模型（LLMs）在自动化建模方面展现潜力，但其性能评估仍缺乏可靠指标。现有基于求解器的方法常面临不一致、不可行及高计算成本等问题。为此，我们提出ORGEval，一种基于图论的评估框架，用于评估LLMs在构建线性与混合整数线性规划模型方面的能力。ORGEval将优化模型表示为图，将等价性检测转化为图同构测试。我们识别并证明了一个充分条件：当待测图为对称可分解（SD）时，Weisfeiler-Lehman（WL）测试可保证正确识别同构。基于此，ORGEval结合定制化的WL测试与SD检测算法，实现模型等价性评估。通过关注结构等价而非实例配置，ORGEval对数值扰动具有鲁棒性。实验表明，该方法在随机参数配置下实现100%一致结果，且在运行时间上显著优于求解器，尤其在复杂问题上表现突出。利用ORGEval，我们构建了Bench4Opt数据集，并对主流LLMs进行了基准测试。结果显示，尽管当前所有LLMs在建模任务中仍具挑战性，DeepSeek-V3和Claude-Opus-4在直接提示下达到最高准确率，甚至超越领先推理模型。
原文摘要 · Abstract (English)
Formulating optimization problems for industrial applications demands significant manual effort and domain expertise. While Large Language Models (LLMs) show promise in automating this process, evaluating their performance remains difficult due to the absence of robust metrics. Existing solver-based approaches often face inconsistency, infeasibility issues, and high computational costs. To address these issues, we propose ORGEval, a graph-theoretic evaluation framework for assessing LLMs' capabilities in formulating linear and mixed-integer linear programs. ORGEval represents optimization models as graphs, reducing equivalence detection to graph isomorphism testing. We identify and prove a sufficient condition, when the tested graphs are symmetric decomposable (SD), under which the Weisfeiler-Lehman (WL) test is guaranteed to correctly detect isomorphism. Building on this, ORGEval integrates a tailored variant of the WL-test with an SD detection algorithm to evaluate model equivalence. By focusing on structural equivalence rather than instance-level configurations, ORGEval is robust to numerical variations. Experimental results show that our method can successfully detect model equivalence and produce 100\% consistent results across random parameter configurations, while significantly outperforming solver-based methods in runtime, especially on difficult problems. Leveraging ORGEval, we construct the Bench4Opt dataset and benchmark state-of-the-art LLMs on optimization modeling. Our results reveal that although optimization modeling remains challenging for all LLMs, DeepSeek-V3 and Claude-Opus-4 achieve the highest accuracies under direct prompting, outperforming even leading reasoning models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。