用大模型指导进化,自动找到让求解器更快的优化模型。
FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations

- 将建模过程视为符号空间中的进化优化,用大模型生成和优化模型。
- 在多个问题上使求解速度提升最高5.5倍,优于专家和现有方法。
- 能复用经验、零样本迁移,适合想自动化建模的研究者和工程师。
混合整数规划(MIP)是运筹学与工业优化的核心。尽管大语言模型(LLMs)在从自然语言自动生成MIP模型方面展现潜力,但其仅关注语义正确性,忽视公式强度,严重制约下游求解器效率。我们提出FormuEvo,一种由大模型引导的进化框架,用于自动发现求解器高效的MIP公式。FormuEvo将MIP建模设计为在可执行建模程序构成的符号空间中的进化优化,通过大模型驱动的交叉、变异和修复操作,迭代生成、评估并选择更强的候选方案。为避免盲目探索,FormuEvo引入求解器感知诊断机制,利用细粒度求解器统计信息作为语义梯度,实现针对性优化。此外,结构化记忆将过往经验抽象为可复用的建模策略,避免重复探索,并支持零样本迁移至未见问题,同时可帮助小型模型快速启动。在多种线性和非线性问题上的实验表明,FormuEvo发现的公式显著优于专家设计及现有基于大模型的方法,求解速度最高提升5.5倍,且提炼的知识可在不同问题和模型规模间有效迁移。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。