arXiv cs.AI· Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou·· 12 小时前AI 评分34
SAGE：用 LLM 引导进化符号加速不等式族，优化 MILP 求解
LLM-Guided Evolution of Symbolic Acceleration Inequality Families for MILP
AI 导读
研究提出 SAGE 框架，通过 LLM 初始化候选加速不等式族，经可采纳性与影响筛选后，用进化交叉和变异智能体迭代精炼，实现 MILP 建模层面的符号发现自动化。在七个 MILP 基准上，SAGE 将最优性差距最多缩小 62.1%，并以 shifted geometric mean 计最多快 5.51 倍达到目标差距。消融实验显示其在不同 LLM 后端、求解器及内部割设置下均保持稳健。
正文 · 原文
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: this https URL
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2508.11850 [cs.AI] |
| (or arXiv:2508.11850v3 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2508.11850 arXiv-issued DOI via DataCite |
|
| Journal reference: | Transactions on Machine Learning Research (2026) |
Submission history
From: Milad Yazdani [view email]
[v1]
Sat, 16 Aug 2025 00:13:49 UTC (680 KB)
[v2]
Thu, 12 Feb 2026 20:22:23 UTC (4,464 KB)
[v3]
Mon, 19 Oct 2026 20:07:13 UTC (2,497 KB)
来源：arXiv cs.AI · arxiv.org