FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations

📄 arXiv: 2608.23353v1 📥 PDF

作者: Haofeng Yuan, Jianing Peng, Jieyi Bi, Ni Zhang, Shiji Song, Zhiguang Cao

分类: cs.CL, cs.NE

发布日期: 2026-08-24

备注: 27 pages, 6 figures, and 9 tables. To appear in the Proceedings of EMNLP 2026

💡 一句话要点

提出FormuEvo以自动发现高效的混合整数规划模型

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 混合整数规划 自动建模 进化优化 大型语言模型 求解器效率 结构化记忆 知识迁移

📋 核心要点

  1. 现有方法在自动化混合整数规划建模中，虽然注重语义正确性，但忽视了模型的有效性，导致求解效率低下。
  2. 本文提出FormuEvo，通过进化优化框架，利用LLM生成、评估和选择更强的MIP模型，提升模型的求解效率。
  3. 实验表明，FormuEvo发现的模型在多种线性和非线性问题上，性能显著优于专家设计的模型，求解器加速可达5.5倍。

📝 摘要（中文）

混合整数规划（MIP）是运筹学和工业优化的核心。尽管大型语言模型（LLMs）在从自然语言自动建模MIP方面展现出潜力，但它们往往优先考虑语义正确性，而忽视了模型的有效性，严重制约了下游求解器的效率。为此，本文提出了FormuEvo，一个基于LLM的进化框架，用于自动发现高效的MIP模型。FormuEvo将MIP模型设计视为在符号空间中的进化优化，通过迭代生成、评估和选择更强的候选模型，利用LLM驱动的交叉、变异和修复操作。该方法引入了解算器信息诊断机制，利用细粒度的求解器统计数据作为目标优化的依据。此外，结构化记忆将先前经验抽象为可重用的建模策略，从而避免冗余探索，并实现零样本迁移。实验结果表明，FormuEvo发现的模型在性能上显著优于专家设计的模型和现有LLM方法，求解器速度提升可达5.5倍。

🔬 方法详解

问题定义：本文旨在解决现有大型语言模型在混合整数规划（MIP）建模中，忽视模型有效性的问题，导致求解器效率低下。

核心思路：FormuEvo通过将MIP模型设计视为在符号空间中的进化优化，利用LLM生成和选择更强的模型，旨在提升求解器的效率。

技术框架：FormuEvo的整体架构包括生成、评估和选择三个主要阶段，结合LLM驱动的交叉、变异和修复操作，同时引入求解器信息诊断机制和结构化记忆模块。

关键创新：最重要的创新在于引入了求解器信息诊断机制，利用细粒度的求解器统计数据作为优化依据，显著提升了模型的有效性和求解器的效率。

关键设计：在参数设置上，FormuEvo采用了结构化记忆来存储和重用建模策略，避免冗余探索，并实现了零样本迁移到未见问题的能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，FormuEvo发现的MIP模型在多种线性和非线性问题上，性能显著优于专家设计的模型，求解器速度提升可达5.5倍，且知识迁移效果良好，能够有效适应不同问题和模型规模。

🎯 应用场景

该研究的潜在应用领域包括运筹学、工业优化和智能决策系统。通过自动发现高效的MIP模型，FormuEvo能够在实际问题中显著提升求解效率，具有广泛的实际价值和未来影响力，尤其是在复杂优化问题的解决中。

📄 摘要（原文）

Mixed-integer programming (MIP) lies at the core of operations research and industrial optimization. While large language models (LLMs) have recently shown promise in automated MIP modeling from natural language, they prioritize semantic correctness but overlook formulation strength, severely bottlenecking the efficiency of downstream solvers. We propose FormuEvo, an LLM-guided evolutionary framework for automated discovery of solver-efficient MIP formulations. FormuEvo frames MIP formulation design as evolutionary optimization over the symbolic space of MIP formulations, represented as executable modeling programs, by iteratively generating, evaluating, and selecting stronger candidates via LLM-driven crossover, mutation, and repair operations. To move beyond blind exploration, FormuEvo introduces a solver-informed diagnosis mechanism that exploits fine-grained solver statistics as verbal gradients for targeted refinement. Additionally, a structured memory abstracts prior experience into reusable modeling strategies, avoiding redundant exploration while enabling zero-shot transfer to unseen problems and bootstrapping smaller LLMs. Experiments across diverse linear and non-linear problems demonstrate that FormuEvo discovers formulations that significantly outperform both expert-designed formulations and existing LLM-based approaches, accelerating solvers by up to 5.5$\times$, with distilled knowledge transferring effectively across problems and model scales.