MILP-Evo: 闭环全自动MILP求解器设计

# MILP-Evo: MILP 求解器的闭环全自动设计
来源：https://arxiv.org/html/2607.18252
聂金彪¹,² 冯克伟³,² 张小远² 印山¹ 王梓卓⁴ 董彬²,⁵  
¹北京邮电大学 ²北京智源人工智能研究院 ³北京理工大学 ⁴香港中文大学（深圳） ⁵北京大学

###### 摘要

机器学习方法已表明，数据驱动的策略能够加速混合整数线性规划（MILP）求解器，但许多此类方法因学习到的策略以外部预测器或其他黑箱模型表示，而难以检查、调整和部署。相比之下，显式的求解器逻辑更易于理解和集成，但通常是人工设计而非从求解器反馈中学习得来。本文研究是否可以将 MILP 求解器逻辑的自动设计转化为以 LLM 引导的闭环搜索，搜索对象为可执行的白箱组件，这些组件直接通过端到端求解器行为进行评估。为此，我们提出了一种针对 MILP 求解器自动设计的闭环程序进化框架，通过 PySCIPOpt 实现，并将其实例化于割选择器和分支规则的联合设计。候选程序被迭代生成、加载到 SCIP 中，并通过在 MILP 实例上直接执行来评估，由此产生的反馈信息指导基于性能的选择、定向修复、诊断性反思以及考虑多样性的种群维护。该方法输出显式的求解器组件，可在标准求解器工作流中检查、修改和部署。在四个基准测试系列上，我们发现 LLM 引导的程序进化能够在多种设置中发现具有竞争力的领域专用策略。

## 1 引言

组合优化（CO）是数学优化中基础且富有挑战性的领域，其应用涵盖生产规划、调度分配以及芯片设计等（Liu 等，2008 (https://arxiv.org/html/2607.18252#bib.bib7); Chen, 2010 (https://arxiv.org/html/2607.18252#bib.bib8); Ma 等，2019 (https://arxiv.org/html/2607.18252#bib.bib9)）。许多精确的 CO 任务可以自然地建模为混合整数线性规划（MILP），这是工业和基准优化实例的标准语言（Bengio 等，2021 (https://arxiv.org/html/2607.18252#bib.bib2); Gleixner 等，2021 (https://arxiv.org/html/2607.18252#bib.bib3)）。由于广泛的 MILP 类别是 NP 难的，精确优化的实际价值在很大程度上取决于现代求解器的效率。此类求解器建立在分支定界（B&B）和分支割界之上，将树搜索与割平面、预求解、原始启发式算法及其他内部机制相结合，以获得可证明的最优解（Achterberg, 2009 (https://arxiv.org/html/2607.18252#bib.bib1)）。

历史上，现代 MILP 求解器依赖于人工设计的策略来做这些决策。这些策略之所以广泛部署，是因为它们紧凑、高效、可靠，并且能自然集成到求解器工作流中。例如，分支规则和割选择规则通常实现为硬编码的评分函数或精心设计的程序，反映了数十年的优化专业知识。然而，设计这些策略需要大量的专家知识和手动调优，且通用规则可能无法捕捉重复出现的问题系列中的分布特定结构（Bengio 等，2021 (https://arxiv.org/html/2607.18252#bib.bib2); Lodi 和 Zarpellon, 2017 (https://arxiv.org/html/2607.18252#bib.bib4); Kuang 等，2024a (https://arxiv.org/html/2607.18252#bib.bib21)）。这种张力促使了日益增长的基于学习的工作，用数据驱动的策略替换或增强单个求解器决策，尤其是在分支（Gasse 等，2019 (https://arxiv.org/html/2607.18252#bib.bib6); Gupta 等，2020 (https://arxiv.org/html/2607.18252#bib.bib10); Lin 等，2024 (https://arxiv.org/html/2607.18252#bib.bib18)）、割管理（Huang 等，2022 (https://arxiv.org/html/2607.18252#bib.bib11); Paulus 等，2022 (https://arxiv.org/html/2607.18252#bib.bib12); Turner 等，2023 (https://arxiv.org/html/2607.18252#bib.bib23); Wang 等，2023 (https://arxiv.org/html/2607.18252#bib.bib13); Li 等，2023 (https://arxiv.org/html/2607.18252#bib.bib14); Puigdemont 等，2024 (https://arxiv.org/html/2607.18252#bib.bib15)）以及潜入式启发式和预求解等其他模块（Paulus 和 Krause, 2023 (https://arxiv.org/html/2607.18252#bib.bib16); Liu 等，2024a (https://arxiv.org/html/2607.18252#bib.bib17)）方面。

尽管学习到的策略能提高共享结构的问题分布上的求解效率，但许多策略实现为外部神经网络或图神经网络预测器。这引入了一系列不同的挑战：学习到的决策逻辑可能难以解释，可能需要大量的训练和推理基础设施，并且不容易作为生产求解器的原生部分部署。最近的工作通过学习更显式、可解释的求解器策略开始解决这个问题。特别是，像 Symb4CO 和 GS4CO 这样的符号策略方法学习了紧凑的分支规则，这些规则轻量级、可解释，且更接近传统求解器启发式算法的精神（Kuang 等，2024a (https://arxiv.org/html/2607.18252#bib.bib21), b (https://arxiv.org/html/2607.18252#bib.bib22)）。这些工作表明，自动算法发现可以产生白箱求解器策略，而不仅仅是黑箱预测器。然而，现有的可解释方法仍然主要关注单个求解器模块，最突出的是分支，并且通常通过模仿或代理目标而不是直接通过端到端求解器执行来优化策略。最近的工作也开始研究耦合的分支定界决策，如联合选择节点和变量（Du 等，2025 (https://arxiv.org/html/2607.18252#bib.bib26)），但更广泛的问题仍然存在：LLM 能否直接对可执行的求解器逻辑进行搜索，利用端到端的求解器反馈来优化相互作用的 MILP 组件，而不是分离的预测器或孤立的学得规则？

本文通过 LLM 引导的对基于 PySCIPOpt 实现的求解器程序的可执行搜索来研究这个问题。我们专注于分支和割选择作为此设置的实用测试平台。除了各自的重要性之外，这两个组件在基于分支定界的 MILP 求解中自然地交互：分支塑造了进化搜索树以及割的生成和应用的 LP 上下文，而割选择改变了边界进度、LP 松弛以及后续分支决策看到的候选状态。两者都可以通过直接的 PySCIPOpt 实现访问，使得它们适合在现实的求解器约束下研究端到端的代码级搜索。我们的框架使用 LLM 来提议、变异、修复和反思候选求解器程序，但使用 SCIP 执行而不是 LLM 自我评估来确定其质量。每个候选通过 PySCIPOpt（Maher 等，2016 (https://arxiv.org/html/2607.18252#bib.bib5); Achterberg, 2009 (https://arxiv.org/html/2607.18252#bib.bib1)）加载到 SCIP 中，通过端到端的求解行为进行评估，并受求解器接口有效性的约束。输出是一个明确的代码工件，带有具体的控制逻辑，使得得到的求解器行为更容易检查、调试、修改和作为原生求解器组件部署。我们在四个 learn2branch 问题系列上研究此框架：集合覆盖、组合拍卖、设施选址和独立集。

我们的贡献是：(i) 我们将 MILP 求解器组件自动设计表述为 LLM 引导的闭环搜索，搜索对象是基于 PySCIPOpt 回调的可执行组件，通过端到端的 SCIP 执行评估；(ii) 我们将此表述实例化于割选择和分支规则的联合设计，这是分支割搜索中的两个交互决策；(iii) 我们引入了一个执行引导的进化循环，结合了程序提议、定向修复、诊断性反思、基于性能的选择以及在求解器接口约束下考虑多样性的种群维护；(iv) 我们在四个 learn2bench 基准测试系列——集合覆盖、组合拍卖、设施选址和独立集——上评估发现的组件，并在多种设置中展示了具有竞争力的领域专用性能。

## 2 相关工作

### 2.1 MILP 求解器学习

学习增强的 MILP 求解器用从求解器数据训练的策略替换分支割中的人工设计组件。最成熟的研究线是关于变量分支的：基于变量-约束二分图的图神经网络策略使得能够在重复出现的 MILP 分布上模仿强分支（Gasse 等，2019 (https://arxiv.org/html/2607.18252#bib.bib6)），而后来通过混合推理和对比增强降低了部署成本或提高了样本效率和迁移能力（Gupta 等，2020 (https://arxiv.org/html/2607.18252#bib.bib10); Lin 等，2024 (https://arxiv.org/html/2607.18252#bib.bib18)）。另一条平行线研究割平面决策。早期的学得割选择器对局部候选割进行排序，通常利用模仿或前瞻信号（Huang 等，2022 (https://arxiv.org/html/2607.18252#bib.bib11); Paulus 等，2022 (https://arxiv.org/html/2607.18252#bib.bib12)）；最近的工作将控制面扩展到分割器配置、割移除、分层割选择以及跨分支割树全局割选择（Turner 等，2023 (https://arxiv.org/html/2607.18252#bib.bib23); Wang 等，2023 (https://arxiv.org/html/2607.18252#bib.bib13); Li 等，2023 (https://arxiv.org/html/2607.18252#bib.bib14); Puigdemont 等，2024 (https://arxiv.org/html/2607.18252#bib.bib15); Zeng 等，2025 (https://arxiv.org/html/2607.18252#bib.bib27)）。这些方法表明求解器决策暴露了可学习的结构，但学到的对象通常是附着于一个决策接口的预测器或策略。

最近的工作也超越了孤立的分支，走向更广泛的学习分支定界控制。符号策略方法如 Symb4CO 和 GS4CO 学习了紧凑的分支规则，比不透明的神经预测器更接近传统求解器启发式算法（Kuang 等，2024a (https://arxiv.org/html/2607.18252#bib.bib21), b (https://arxiv.org/html/2607.18252#bib.bib22)）。其他方法学习耦合决策，例如节点和变量选择（Du 等，2025 (https://arxiv.org/html/2607.18252#bib.bib26)），或表示整个分支定界树以通过强化学习选择搜索节点（Zhang 等，2025 (https://arxiv.org/html/2607.18252#bib.bib28)）。这种进展对我们的设置很重要，因为分支、节点选择和割管理通过求解器轨迹交互，而不是通过独立的单步决策。然而，这些工作仍然主要优化学习到的决策模型或符号公式，而我们的目标是直接搜索可执行的回调代码，这些代码联合实现交互的求解器模块。

LLM 最近通过互补的路径进入了 MILP 研究。MILP-Evolve 使用基于 LLM 的进化过程生成多样化的 MILP 问题类别，实现了基础模型在积分性差距预测、学习分支以及跨问题系列的实例-文本对齐方面的训练（Li 等，2024 (https://arxiv.org/html/2607.18252#bib.bib29)）。LLM-LNS 则使用双层自进化 LLM 代理为大规模 MILP 上的大邻域搜索设计邻域选择策略（Ye 等，2025 (https://arxiv.org/html/2607.18252#bib.bib30)）。这些研究表明 LLM 可以帮助暴露优化结构并合成有用的求解器启发式算法。我们的工作不同之处在于搜索的目标：我们不是生成训练实例或控制 LNS 修复启发式，而是使用 LLM 引导的执行反馈来进化在 SCIP 内部运行的原生 PySCIPOpt 分支割回调。

### 2.2 自动设计

评估器在环中的程序搜索已经成为发现可执行启发式算法和算法的一种通用机制。FunSearch 展示了 LLM 可以提出小型程序，其质量由外部执行而非自我评估决定（Romera-Paredes 等，2024 (https://arxiv.org/html/2607.18252#bib.bib19)）。启发式算法进化（Evolution of Heuristics）和 ReEvo 将这一思想应用于启发式设计，结合了 LLM 变异、选择和基于反馈的反思，对候选算法种群进行迭代（Liu 等，2024b (https://arxiv.org/html/2607.18252#bib.bib24); Ye 等，2024 (https://arxiv.org/html/2607.18252#bib.bib25)），而 AlphaEvolve 将代码进化扩展到科学和算法发现任务（Novikov 等，2025 (https://arxiv.org/html/2607.18252#bib.bib20)）。共同模式是将提议与评估分离：语言模型探索程序空间，而评估器提供选择压力。

我们的工作最接近这条可执行发现路线，但求解器设置使得搜索比独立的启发式算法设计受到更多约束。候选程序必须是有效的 Python 代码，满足 SCIP 的回调契约，返回合法的求解器对象和结果代码，并在分支割求解过程中重复调用时保持稳定。此外，评估的工件不是用于外部基准的单一评分函数；而是一对交互的原生求解器模块，其效果仅通过端到端 SCIP 执行可见。因此，贡献不仅仅是通用的 LLM 程序搜索，而是专门针对标准优化工作流中耦合的 MILP 求解器回调的可执行自动设计。

## 3 方法

### 3.1 LLM 引导的 MILP 求解器自动设计

我们提出了一个 LLM 引导的 MILP 求解器自动设计框架：通过端到端 SCIP 执行反馈，自动构建 MILP 求解器逻辑，进化原生 PySCIPOpt 回调程序。关键思想是使可进化的工件成为可执行的求解器组件，而不是外部的学习预测器。候选程序由 LLM 提议，通过回调接口加载到 SCIP 中，通过直接的分支割执行进行评估，并根据测量的求解行为而非 LLM 自我评估进行选择。

这种框架将我们的设置与学习增强的 MILP 策略和通用的 LLM 程序搜索区分开来。学习的分支或割选择方法通常训练一个预测器用于一个求解器决策接口，而我们的框架直接搜索在求解器内部运行的可执行求解器组件。通用的评估器引导程序搜索优化独立的代码片段（Romera-Paredes 等，2024 (https://arxiv.org/html/2607.18252#bib.bib19); Liu 等，2024b (https://arxiv.org/html/2607.18252#bib.bib24); Ye 等，2024 (https://arxiv.org/html/2607.18252#bib.bib25); Novikov 等，2025 (https://arxiv.org/html/2607.18252#bib.bib20)）；相反，我们的候选必须满足求解器接口契约，并在 SCIP 优化期间重复调用时保持稳定。因此，核心困难不仅在于生成代码，还在于生成可接受、可执行且有用的求解器逻辑。

图1 (https://arxiv.org/html/2607.18252#S3.F1) 总结了闭环及其主要工件。从一个 MILP 实例集、SCIP/PySCIPOpt API 和回调契约开始，LLM 通过变异或交叉对联合回调程序提出语义编辑。候选代码随后通过保持契约的修复和验证，然后才被接纳为配对的割选择器和分支规则。修复后的工件在 SCIP 中注册，通过分支割执行评估，并转换为轨迹和标量适应度 F(p; D) (函数未完全显示)。