arXiv cs.AI· Milad Yazdani, Mahdi Mostajabdaveh, Samin Aref, Zirui Zhou·· 11 小时前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 后端、求解器及内部割设置下均保持稳健。
正文 · AI 翻译
摘要：整数规划（IP）是许多组合优化任务的核心，但由于其 NP 难特性，仍然具有挑战性。改进 IP 求解器的一种实用方法是手动设计利用问题结构的不等式族。然而，这一创造性过程需要深厚的专业知识，因此难以自动化。我们提出的框架——通过生成式进化实现符号加速（SAGE）——在建模层面自动发现加速不等式族的符号化方法。它对符号化 IP 公式和问题的自然语言描述进行推理，以发现一组可复用的加速不等式族，这些不等式族可针对每个问题实例进行实例化。这些加速不等式族通过经验可采纳性和影响筛选而非数学证明来选择。SAGE (i) 通过使用 LLM 的初始化代理初始化候选加速不等式族种群；(ii) 在小型开发可采纳性集上筛选候选者的可采纳性，以检验解的可行性以及松弛解的分离性；(iii) 通过进化交叉和变异代理迭代改进不等式种群。在七个 MILP 基准上，与在固定时间预算下求解的基线 MILP 公式相比，SAGE 将最优性差距最多缩小 $62.1\%$，并且根据平移几何平均加速比，达到目标差距的速度最多快 $5.51\times$。全面的消融实验表明，它在不同的 LLM 后端以及不同的求解器和内部割设置下都具有鲁棒性。代码：此 https URL
| 学科： | 人工智能（cs.AI） |
| 引用为： | arXiv:2508.11850 [cs.AI] |
| （或 arXiv:2508.11850v3 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2508.11850 由 DataCite 颁发的 arXiv DOI |
|
| 期刊 参考： | Transactions on Machine Learning Research (2026) |
提交历史
来自：Milad Yazdani [查看电子邮件]
[v1]
2025年8月16日星期六 00:13:49 UTC（680 KB）
[v2]
2026年2月12日星期四 20:22:23 UTC（4,464 KB）
[v3]
2026年10月19日星期一 20:07:13 UTC（2,497 KB）
来源：arXiv cs.AI · arxiv.org