评 DeepMind 神经网络求解 MIP 论文：并非无所不能

作者信息

皇甫琦，葛冬冬

杉数科技 COPT 开发组

皇甫琦，杉数科技副总裁，博士毕业于爱丁堡大学优化算法方向。曾在 XPRESS 求解器工作多年，数学规划求解器开发领域的资深专家，曾获得国际著名优化期刊 Mathematical Programming Computation 的年度最佳论文奖（2018），Computational Optimization and Applications 的年度最佳论文奖（2015）。

葛冬冬，杉数科技联合创始人，首席科学官，上海财经大学交叉科学研究院院长、教授。博士毕业于斯坦福大学运筹学专业。开源求解器项目 LEAVES 和商业求解器项目 COPT 的负责人。在人工智能，理论计算机，运筹学的期刊和会议 NeurIPS，ICML，FOCS，SODA，Operations Research，Mathematical Programming 等发表过多篇论文。

引言

本文对 DeepMind 近期的神经网络求解 MIP（混合整数规划）的论文进行了一些初步解读。事实上，相较于此领域近期的类似工作，DeepMind 的工作在 MIP 的求解开发某些环节，如分支定界，启发式算法上所做的利用神经网络的尝试，更加的精细化和高度工程化，并且与开源求解器的耦合程度明显更高，也取得了相对良好的进展，但是并未看到太多有突破性和颠覆性的思想。

Google 的 DeepMind 团队最近官宣了一篇神经网络(Neural Networks)求解 MIP 论文。一石激起千层浪，在国内外的运筹优化社群引起了讨论。

原文报道：运筹OR帷幄：DeepMind与谷歌又出大招！用神经网络解决NP-hard的MIP问题

部分围观吃瓜群众纷纷表示：

“This is uber cool”

“Excited to see this merging of ML and combinatorial optimization finally happening”

“攻破 OR（运筹学）只是时间问题”

而一些实践派已经在伸手要代码了：

“Is the code open-source? Would love to test it on some standard hard problems”

“Going to need to see some code here”

“It would be very interesting to test this”

其实，把机器学习和整数规划结合在一起并不是一个新课题。为什么 Google 的这篇论文引起这么大的关注。Google 和 DeepMind 团队的名气当然是最大的因素，从围棋的 AlphaGo 到最近的蛋白质结构预测的 AlphaFold2，DeepMind 的每次出手都是风口浪尖上的大动作，也确实在某些领域带来过突破性的进展。但这篇论文是否有颠覆性的研究成果，以至于可以“攻破 OR（运筹学）”？

DeepMind 并没有回应开源这部分代码的要求，因此想要看看他们的工作只能读论文。这篇论文的原文可在 arXiv 获取：https://arxiv.org/abs/2012.13349。杉数科技的 COPT 求解器开发团队详细地学习、研究了这篇论文。在此我们把团队的分析讨论奉上，以资对机器学习和优化算法结合做进一步探讨。

MIP（混合整数规划）一般特指混合整数线性规划，它在满足线性约束条件 Ax≤b 和整数约束条件 x∈Z 的前提下，求解目标函数 f(x) = c·x 的最小值。其中数组 x 叫做决策变量，数组 c 是这些决策变量的目标系数，矩阵 A 是线性约束矩阵，Z 是整数集合。整数规划在现实世界中的用途极为广阔，例如在航空航天，能源电网，生产制造，交通物流，军事与通讯等领域都起着不可替代的基础建模与求解功能。但是整数规划也是非常困难的问题，在计算机的复杂性理论上，是属于 NP 难问题类的，也是美国库兰所公布的数学七个千年大奖难题之一，对于此类问题，是否存在多项式时间的精确求解算法，至今仍未有定论。

求解整数规划的主要算法部件有：预求解、分支定界、启发式算法、割平面、冲突分析和线性规划求解器等模块。鉴于 DeepMind 此次的论文主要涉及分支算法和启发式算法，我们分别重点从这两个方向进行探讨。下文会对 DeepMind 的基本结论先做一个分析，然后分别就 DeepMind 论文中提到的 Neural Branching 和 Neural Diving 这两项成果，介绍混合整数规划相关的背景知识，然后对比分析论文中的新思路和传统算法的关系。

文末，也对杉数科技在求解器内部开发和外部应用过程中对机器学习、强化学习等技术探索和使用做了一些简单的举例，也是想说明运筹与优化技术从诞生的第一天起，就注定了是一门广泛交叉的科学，多种大数据与人工智能技术的兴起，为它注入了新的活力，在智能决策的领域，可以预见将会发挥越来越大的作用。

DeepMind 论文求解结果分析

DeepMind 的论文引起了广泛的关注，并不止因为团队的名声，也来自于论文中报告了非常惊人的性能提升数据。如论文摘要中提到的，对于测过的 5 组问题里，在 3 组上分别实现了 1.5 倍，2 倍，以及 1 万倍的更好的 Gap。

其实这里玩了一个小小的文字游戏。作为 MIP 求解器开发人员，一般不把一定时间内能拿到的 Gap 作为主要衡量标准。因为这有一定的误导性。设想一类较特殊的整数规划问题，如可行性问题，它没有目标函数，只需要找到一组整数解即可完成。那么在找到整数解之前，其 Gap 就是 100%，找到之后就是 0%。如果某个启发式（或者割平面）算法，在开启和关闭的的情况下，分别可以于 1 小时和 3 小时找到可行解。则如果以两小时为观察点，则可以说在开启这项算法的前提下，实现的 Gap 提升就是无穷多倍，而若以半小时或者三个小时作为观察点，则 Gap 没有提升。鉴于 DeepMind 并未公布计算这些性能指标的原始数据，我们无法用 MIP 业内的公认方式来对它做出评价。一般来说，根据目前公认的测试标准，一般是在 MIPLIB 的问题集上，以两小时为限，考虑能求解的问题数量和平均求解时间进行比较。

对于特定的测试集取得惊人的性能提升并不意外，因为这正是机器学习擅长的地方：它可以捕捉同一类问题的特征结构，并且给出优化趋势的判断。如后文所述，我们自己在开发的过程中也有类似的经历。真正值得关注的是它在 MIPLIB 上的表现。MIPLIB 2017 由 1000 多个来自各行各业的实例构成，而 MIPLIB2017 Benchmark 则是其中挑选的 240 个结构各异的问题组成，在筛选的时候就充分的做到了差异化，因此它和电网优化和ＮＮ Verification 等测试集有本质的区别。这也解释了在 MIPLIB 上算法性能提升效果并不如其他数据集明显的原因。为了避嫌， Google 也一早就在论文中表明，训练集用的是 MIPLIB 完整版的 1000 多个问题，去掉这 240 个问题剩余的例子。但是这依然难以避免训练集和测试集的结构相似性。例如 MIPLIB 2017 的完整版在收集的时候，往往会从同一个来源收集多个大小不同稍有差异的算例。在遴选测评（Benchmark）集的时候，为了避免测评集的重复性，会尽量避免使用来自同一个来源的例子，这使得 MIPLIB 2017 完整版中剩下的例子包含了测评（Benchmark）集的高度结构相似问题。如 MIPLIB 2017 Benchmark 中有 graph20-20-1rand 这个问题，而在 MIPLIB 2017 全集中有 graph-20-80-1rand, graph-40-20-1rand, graph-40-40-1rand, graph-40-80-1rand 四个结构高度类似的问题。因此在训练集上获得的经验，必然会对求解最后的测试集有帮助。而这些帮助能否泛化推广到任何通用问题集上，高度存疑。

分支算法与 Neural Branching

分支（Branching) 算法是整数规划求解器的核心框架。求解 MIP 通常需要求解多个 LP（线性规划）问题完成。其中第一个 LP 问题是原始问题去掉全部的整数约束得来。如果第一个 LP 问题的最优解碰巧满足整数条件，则这个解也是整数规划的最优解。如果 LP 松弛问题的解不都满足整数条件，则可以通过分支算法继续寻找整数解。

分支算法通过选择一个取值不为整数的变量 x=x*进行分支，通过分别添加 x≤floor(x*)（即取值不大于 x*的最大整数下界）和 x≥ceil(x*)（即取值不小于 x*的最小整数上界）这两个约束来把原始问题分解为两个子问题。原整数规划问题的最优解一定在这两个分支之一。接下来继续求解这两个新的问题，并以此类推，直到找到最优的整数解或者证明整数解不存在为止。不难看出，分支算法的本质是枚举，在有 n 个 0-1 变量的混合整数规划问题里，最坏情况要遍历所有 2 的 n 次方个分支节点。也因为混合整数规划问题是个 NP 难问题，所以目前精确求解的算法，基本上都基于分支算法的框架，最坏情况下复杂度是指数时间级别，耗时可能会极端漫长。

在实践中，求解整数规划通常远不需要枚举全部的节点。这是因为分支算法可以以一种更聪明的方式选择进行分支的变量。在众多分支算法中，最有效果的算法是完整的强分支算法（Full strong branching 简称 FSB）。该算法原理非常简单，即通过分别对当前 LP（线性规划）问题的各个取值不为整数的变量进行分支，求解全部的分支后的 LP 问题，并通过 LP 的目标函数值判断选取哪个分支是可以最快的完成 MIP 求解。实践中 FSB 所需要的计算量非常巨大，因此对每个 LP 节点使用很不现实。在 MIP 求解过程中，会不定期的做限定循环数的 Strong branching 来获取每个变量分支的最佳估计。

Google 提出的 Neural branching 其本质是先通过神经网络离线学习 FSB 的真实计算结果，再在实际应用中模拟 FSB 计算，在追求 FSB 效果的同时，节省计算时间。其实这项工作过去几年间有很多类似的论文。Google 的论文在相关工作中也提到了其他 8 篇相关的研究论文，多数的基本想法是比较类似的。因此论文在这个点上的创新有一定的局限性，正如 Google 的论文所说：是通过用 GPU 和 ADMM 方式大量计算原始问题的 FSB 近似值，以便可以生成大量的机器学习数据。不过这也从另一个方面反应了 FSB 的计算量，即使产生离线学习的数据，都不得不设法让它算的更快一些。

和传统的分支算法相比，Neural branching 以及其他在这个方面的研究确实是（离线）机器学习和优化算法的一种有趣的结合。但值得指出的是，经典的分支算法，也是基于历史数据对将来分支的预测，它的本质也是一种在线的机器学习机制。例如在杉数求解器里，使用 strong branching 只是其中一项，此外还有伪价格(Pseudocost)、可靠性(Reliability)和推断(Inference)等公开和其他不公开的判断标准。这些算法均是通过在求解的过程中积攒信息，并以此来判断、选择新的分支变量等。

启发式算法与 Neural Diving

启发式算法，是在主体的分支定界算法之外寻找整数解的算法的总称。启发式算法是 MIP 研究的一项热点，相关的论文不胜枚举，目前仅在 SCIP 中实现的启发式算法就有 57 种之多。这些启发式算法又大致可以分为四类：取整（Rounding）、下潜（Diving）、子问题（Sub-MIP）和上述三类之外的其他算法。

取整（Rounding）启发式算法顾名思义，是在 LP 松弛解不满足整数约束时，对不满足的变量进行取整，以期望获得整数解。下潜（Diving）启发式算法的本质是深度优先搜索，它在 LP 松弛解不满足整数约束时，从当前节点出发，不断的选取最佳分支进行深度优先搜索，直到找到整数解或证明子问题为不可行为止。这两类算法虽然原理简单，但是也都有多种实现变种，在这里不展开讨论。

子混合整数规划问题（Sub-MIP）的启发式算法是一个大类，它通过构造并求解子 MIP 问题来寻找高质量的整数解。在构造子问题的时候，又有多种构造方式，例如：固定或缩紧变量，添加约束以及修改目标函数值。其中如固定变量类的算法，比较有名的有松弛导向邻域搜索（Relaxation induced neighborhood search 或简称 RINS），它的工作原理是当某个整数变量在 LP 松弛解中的值与当前最好整数解中的值一致，则将该变量固定在这个整数值。如果大量变量可以被固定，则可以把这个固定变量后的子问题当作一个全新的 MIP 求解，以期望可以找到高质量的整数解。由于大量的变量被固定了，子问题的搜索空间会变小，且预求解可以进一步的削减问题的规模，因此解子问题会相对容易些。

DeepMind 提出的 Neural Diving 这个算法，是通过机器学习和神经网络，给定一个问题结构，预判如何固定部分整数变量的取值，然后去求解子 MIP。因此，尽管用到了 Diving 这个词，但是我们认为它还是可以归类为求解子问题的启发式算法。可以看出这个算法在原理上和上述的 RINS 有诸多相似之处，只是固定变量的方式不同。

虽然思路和很多既有启发式算法形式类似，但 Neural Diving 还是有它的独特之处。Neural Diving 最大的优势之一，是它可以在正式求解原始问题之前，即生成多组差异化的部分变量取值，启动启发式算法。这一方面提升了该算法找到高质量整数解的成功率，另一方面也提前了找到整数解的时间，因此可以较早的获得较小的 Gap。我们也认为这是 DeepMind 这篇论文的最有价值的部分。

人工智能与 MIP 结合的实例应用

杉数求解器在开发的过程中充分使用了机器学习工具。除了上文提到的本质就是在线学习的分支算法之外，我们还在许多其他不同的方向使用了机器学习工具。

例如求解子 MIP 的启发式算法，是一个有效但非常耗时的算法。我们在开发的过程中，求解大量的子问题，提取子问题特征（例如再次预求解效果，变量种类等），交给机器学习帮助判断预测某个子问题是否值得花时间启动求解，避开耗时且无效的方法，提升求解速度。

此外我们的线性规划 LP 求解器开发也得益于机器学习。例如我们对部分有特殊结构的 LP 使用机器学习的方式，预测一个变量是否在最优解的基解的一部分，并通过小幅的目标函数扰动将这个预测结果应用到 LP 问题上，实现快速求解。

除以上内嵌在求解器内部的机器学习成果之外，在过去几年里，杉数在使用求解器解决多个行业的困难问题时，也从机器学习、深度学习、强化学习中获益很大。

一个例子是国家电网安全约束机组组合问题（Security Constrained Unit Commitment 简称 SCUC）问题。SCUC 问题的特点是规模不大，但是要求快速求解。我们遇到的实际问题只有数千个整数变量，需要求每隔 15 分钟求解一次，并且要在 15 分钟内尽快解完。我们通过深度神经网络等机器学习的方法去预测 MIP 模型最优解中每个决策变量取 1 的概率，从而固定部分置信度最高的变量和对中间置信度的部分变量添加多变量分支的割平面，使得最后的问题可行的概率最高。这样的方法能够有效减少分支定界树的搜索规模，一方面能够实现快速收敛，另一方面能够快速寻找到高质量的初始解。最后的实验显示，借助该方法在达到相同质量解(Gap=0.01%)的速度提升为 5-10 倍左右。其中不乏有原始问题 3 分钟无法完成求解，而结合使用机器学习算法仅需 10 秒就能完成求解的时候。这种速度的提升对需要每 15 分钟都需要快速计算决策的 SCUC 问题非常重要。

电网中的优化也是 DeepMind 指出的智能化 MIP 可以重点发力的领域。但是，值得着重指出的是，电网另一个特性就是对于安全性和鲁棒性的极端要求。而在新问题的数据结构突发巨变，历史数据已经不能指导未来的时候，例如战争，自然或者人为因素导致的发电厂和输电线路的极大变化，机器学习能起到的作用会弱化很多。这个时候，更多的时候还是依靠 MIP 求解器自身六个模块那些独立于数据之外的经典算法的实现能力。

另一个例子是中国邮政的路由网络规划问题。我们在实践中遇到的此类问题通常需要求解数十万整数变量的 MIP 来决定发车安排。如果直接抛给求解器，则往往需要花费一至两个小时才能找到第一个整数解（Gap 在 30%左右甚至更差）。通过观察，我们发现尽管无法预测全部的发车安排，但是可以预测部分高概率的车辆安排。我们进而通过机器学习历史数据，形成了一套根据线性约束关系生成数千发车安排的部分初始解的方法。在此基础上，我们通过临时固定这些决策变量，构造子 MIP 问题，用求解器快速的计算、补全子问题的解。这个子问题由于部分关键变量确定，使得预求解模块可以对问题规模进行大幅度的削减，促成快速求解。尽管这个子问题的最优解不是原始问题的最优解，但在实践中这个解（Gap 在 10%之内）明显优于花费一至两小时算出的第一个可行解。而从预测到解子问题，通常只需要不到 1 分钟的时间。因此可以说，机器学习帮助我们以 50 倍的速度提升找到了同等质量（其实是更好）的整数解。

另一个更有广泛意义的例子是，在近期的科研论文与多个号称从事智能决策公司的宣称中，可以看到一些诸如车辆调遣，路线规划等交通类问题，因为其事件频次高，数据结构相对稳定，所以无论是分支策略，初始解固定，甚至割平面产生，都可以通过机器学习技术获得，从而加速问题的 MIP 模型求解。而且也确实有很多学者在这个问题上取得了相对多的进展。因此，交通领域也是机器学习、智能决策等技术近些年来一直关注的领域。

其实，不仅仅是路线规划。在五年前，杉数就曾经与某国内最大的出行平台合作，考虑过司机与乘客的智能动态匹配系统，问题从最开始的单纯机器学习计算匹配系数，进行启发式算法分配，到后来进行全城的时间切片网络流匹配，再到将削峰填谷、智慧出行的理念融合，建立起整个系统的动态规划模型，并在强化学习框架下，进行未来趋势与决策的近似方法，最后得到一个在时间和空间上都接近全局优化的方案。整个系统随着数据的完备，算力的到位，在双方携手建立的强化学习框架下不断进化，从简单的线性函数逼近到神经网络近似，越发智能与精准，在 2017 年的时候，就已经得到了广泛的应用，创造了极大的经济效益与社会效益。

结语

最后，我们想强调，如“机器学习之父“Michael Jordan 指出的，未来的人工智能最重要的突破应该与优化算法紧密结合。而这正是运筹学的核心基础。

在今天讨论的这个例子里，简单地说，神经网络和机器学习技术进展，更像是给 MIP 开发的六大模块中的两个模块探索的武器库增加了一些昂贵（算力资源需求）而有力的武器，丰富了这些模块加速的能力，远远谈不上攻破 OR。这些技术展示出来的潜力是值得欢呼的，但是在现实中求解 MIP 问题，需要的数学技巧和工程经验是极其厚重的。

传统的 MIP 求解工具有数十年的理论论证和理论分析基础。相较之下，MIP 求解中的机器学习工具因其模型结构的复杂性，理论论证成果较少。大量的相关机器学习研究都是依靠某一类或者某几类的数据集的数值实验结果用以验证其有效性。所以机器学习方法对现实中一般性问题求解的可靠性还有待进一步的论证。另一方面，绝大多数机器学习的算法设计是需要将模型转化成经典的整数、线性、凸或者非凸数学规划模型，再对其分析的。

回到 MIP，可以说利用机器学习进行某些点上的突破是远远不够的。一般性的整数规划乃至广大的 NP 难问题，在真正的颠覆性技术突破之前（比如量子计算机的真正实用化），依然可预期在未来很多年，会是人类智力的极限之一。

说明：此文写作中获得了斯坦福大学叶荫宇、纽约大学陈溪、约翰霍普金斯大学江弘亿等多位学者的指导和建议，在此一并表示感谢。