LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP

Abstract

Integer programming (IP) is central to many combinatorial optimization tasks but remains challenging due to its NP-hard nature. A practical way to improve IP solvers is to manually design inequality families that exploit problem structure. However, this creative process requires deep expertise and has therefore been difficult to automate. Our proposed framework, Symbolic Acceleration via Generative Evolution (SAGE), automates symbolic discovery of acceleration inequality families at the modeling level. It reasons over a symbolic IP formulation and a natural language description of the problem to discover a reusable set of acceleration inequality families that can be instantiated for each problem instance. These acceleration inequality families are selected through empirical admissibility and impact screening rather than mathematical proofs. SAGE (i) initializes a population of candidate acceleration inequality families via an initializer agent that uses an LLM; (ii) it screens candidates for admissibility on a small development admissibility set for solution feasibility and the separation of the relaxation solution; and (iii) it iteratively refines the population of inequalities through evolutionary crossover and mutation agents. Across seven MILP benchmarks, SAGE reduces optimality gaps by up to $62.1\%$ relative to baseline MILP formulations solved with a fixed time budget and reaches target gaps up to $5.51\times$ faster according to shifted geometric mean speedup. Comprehensive ablations show its robustness across different LLM backends and across solvers and internal cut settings. Code: https://github.com/milad1378yz/sage