FormuEvo: LLM-Guided Evolution for Discovering Solver-Efficient Mixed-Integer Programming Formulations
2026-08-24 • Computation and Language
Computation and LanguageNeural and Evolutionary Computing
AI summaryⓘ
The authors present FormuEvo, a new method that helps improve how mixed-integer programming (MIP) problems are set up for solvers. Instead of just making sure the problem is correct, their approach uses an evolutionary process guided by large language models (LLMs) to find formulations that solvers can solve more efficiently. FormuEvo learns from solver feedback to refine formulations and remembers useful strategies to speed up learning on new problems. Tests show it creates better formulations than human experts or previous AI methods, making solvers work up to 5.5 times faster.
Mixed-Integer Programming (MIP)Large Language Models (LLMs)Evolutionary OptimizationSolver EfficiencyFormulation StrengthCrossover and MutationProgrammatic ModelingSolver FeedbackTransfer LearningOperations Research
Authors
Haofeng Yuan, Jianing Peng, Jieyi Bi, Ni Zhang, Shiji Song, Zhiguang Cao
Abstract
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.