谷歌的DeepMind团队近发表了一篇关于神经网络解决MIP的论文

本文对DeepMind最近关于用神经网络求解混合整数规划的论文给出了一些初步的解释事实上，与该领域近期的同类工作相比，DeepMind在MIP求解和开发的一些方面，如分支定界，启发式算法和使用神经网络的尝试等方面的工作更加精细化和高度工程化，与开源求解器的耦合度明显更高，取得了相对较好的进展，但并没有看到太多突破性和颠覆性的想法

谷歌的DeepMind团队最近发表了一篇关于神经网络解决MIP的论文。

一石激起千层浪，引起了国内外运营优化界的讨论。

一些吃瓜的围观群众纷纷表示:

这真是太酷了。

很高兴看到ML和组合优化的融合终于发生了。

打破OR只是时间问题。

一些从业者已经在要求代码:

代码是开源的吗很乐意在一些标准的难题上测试它

这里需要一些代码。

测试这个会很有趣。

事实上，机器学习和整数规划的结合并不是一个新的话题。

为什么谷歌的这篇论文会引起如此多的关注。

谷歌和DeepMind团队的名气当然是最大的因素从最近蛋白质结构预测的Go的AlphaGo到AlphaFold2，DeepMind的每一个镜头都是风口浪尖上的大动作，确实在一些领域带来了突破性的进展

但是这篇论文有没有颠覆性的研究成果，让它可以突破或现状，

DeepMind没有回应开源代码的要求，所以如果你想看他们的作品，你只能看论文。

山书科技的COPT求解器开发团队对本文进行了详细的研究和学习。

在这里，我们呈现团队的分析和讨论，从而进一步探讨机器学习和优化算法的结合。

MIP一般指满足线性约束Axle的混合整数线性规划，b和整数约束xisin在z的前提下，求解目标函数f=cmiddot，x的最小值。

其中数组x称为决策变量，数组c为这些决策变量的目标系数，矩阵a为线性约束矩阵，z为整数集。

整数规划在现实世界中有着广泛的应用，例如，它在航空航天，能源网格，制造，交通物流，军事和通信等领域发挥着不可替代的基础建模和求解功能。

可是，整数规划也是一个非常困难的问题在计算机复杂性理论中，它属于NP—hard问题，也是美国柯伦发表的七个数学千年奖问题之一在多项式时间内解决这类问题是否有精确的算法，目前还没有定论

整数规划的主要算法组件有:预解，分枝定界，启发式算法，割平面，冲突分析和线性规划求解器。

由于DeepMind的论文主要涉及分支算法和启发式算法，所以我们分别关注这两个方向。

下面首先分析DeepMind的基本结论，然后针对DeepMind论文中提到的两个成果分别介绍混合整数规划相关的背景知识，然后对比分析论文中新思想与传统算法的关系。

DeepMind论文的求解结果分析

DeepMind的论文引起了广泛关注，这不仅是因为该团队的声誉，还因为该论文报告了惊人的性能提升数据。

如论文摘要所述，在测试的五组问题中，三组分别取得了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中有graph20—20—1rand这个问题，而在MIPLIB 2017全集中有graph—20—80—1rand， graph—40—20—1rand， graph—40—40—1rand， graph—40—80—1rand四个结构高度类似的问题。

因此在训练集上获得的经验，必然会对求解最后的测试集有帮助而这些帮助能否泛化推广到任何通用问题集上，高度存疑

分支算法与Neural Branching

分支算法是整数规划求解器的核心框架。

求解MIP通常需要求解多个LP问题完成其中第一个LP问题是原始问题去掉全部的整数约束得来

如果第一个LP问题的最优解碰巧满足整数条件，则这个解也是整数规划的最优解如果LP松弛问题的解不都满足整数条件，则可以通过分支算法继续寻找整数解

分支算法通过选择一个取值不为整数的变量x=x进行分支，通过分别添加xle，floor和xge，ceil*这两个约束来把原始问题分解为两个子问题。

原整数规划问题的最优解一定在这两个分支之一。

接下来继续求解这两个新的问题，并以此类推，直到找到最优的整数解或者证明整数解不存在为止。

不难看出，分支算法的本质是枚举，在有n个0—1变量的混合整数规划问题里，最坏情况要遍历所有2的n次方个分支节点。

也因为混合整数规划问题是个NP难问题，所以目前精确求解的算法，基本上都基于分支算法的框架，最坏情况下复杂度是指数时间级别，耗时可能会极端漫长。

在实践中，求解整数规划通常远不需要枚举全部的节点。

这是因为分支算法可以以一种更聪明的方式选择进行分支的变量在众多分支算法中，最有效果的算法是完整的强分支算法

该算法原理非常简单，即通过分别对当前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只是其中一项，此外还有伪价格，可靠性和推断等公开和其他不公开的判断标准。

这些算法均是通过在求解的过程中积攒信息，并以此来判断，选择新的分支变量等。

启发式算法与Neural Diving

启发式算法，是在主体的分支定界算法之外寻找整数解的算法的总称。

启发式算法是MIP研究的一项热点，相关的论文不胜枚举，目前仅在SCIP中实现的启发式算法就有57种之多。

这些启发式算法又大致可以分为四类:取整，下潜，子问题和上述三类之外的其他算法。

取整启发式算法顾名思义，是在LP松弛解不满足整数约束时，对不满足的变量进行取整，以期望获得整数解。

下潜启发式算法的本质是深度优先搜索，它在LP松弛解不满足整数约束时，从当前节点出发，不断的选取最佳分支进行深度优先搜索，直到找到整数解或证明子问题为不可行为止。

这两类算法虽然原理简单，但是也都有多种实现变种，在这里不展开讨论。

子混合整数规划问题的启发式算法是一个大类，它通过构造并求解子MIP问题来寻找高质量的整数解。

在构造子问题的时候，又有多种构造方式，例如:固定或缩紧变量，添加约束以及修改目标函数值。

其中如固定变量类的算法，比较有名的有松弛导向邻域搜索，它的工作原理是当某个整数变量在LP松弛解中的值与当前最好整数解中的值一致，则将该变量固定在这个整数值。

如果大量变量可以被固定，则可以把这个固定变量后的子问题当作一个全新的MIP求解，以期望可以找到高质量的整数解。

由于大量的变量被固定了，子问题的搜索空间会变小，且预求解可以进一步的削减问题的规模，因此解子问题会相对容易些。

DeepMind提出的Neural Diving这个算法，是通过机器学习和神经网络，给定一个问题结构，预判如何固定部分整数变量的取值，然后去求解子MIP。

因此，尽管用到了Diving这个词，但是我们认为它还是可以归类为求解子问题的启发式算法可以看出这个算法在原理上和上述的RINS有诸多相似之处，只是固定变量的方式不同

虽然思路和很多既有启发式算法形式类似，但Neural Diving还是有它的独特之处Neural Diving最大的优势之一，是它可以在正式求解原始问题之前，即生成多组差异化的部分变量取值，启动启发式算法

这一方面提升了该算法找到高质量整数解的成功率，另一方面也提前了找到整数解的时间，因此可以较早的获得较小的Gap我们也认为这是DeepMind这篇论文的最有价值的部分

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

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

例如求解子MIP的启发式算法，是一个有效但非常耗时的算法。

我们在开发的过程中，求解大量的子问题，提取子问题特征，交给机器学习帮助判断预测某个子问题是否值得花时间启动求解，避开耗时且无效的方法，提升求解速度。

此外我们的线性规划LP求解器开发也得益于机器学习。

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

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

一个例子是国家电网安全约束机组组合问题问题。

SCUC问题的特点是规模不大，但是要求快速求解我们遇到的实际问题只有数千个整数变量，需要求每隔15分钟求解一次，并且要在15分钟内尽快解完

我们通过深度神经网络等机器学习的方法去预测MIP模型最优解中每个决策变量取1的概率，从而固定部分置信度最高的变量和对中间置信度的部分变量添加多变量分支的割平面，使得最后的问题可行的概率最高。

这样的方法能够有效减少分支定界树的搜索规模，一方面能够实现快速收敛，另一方面能够快速寻找到高质量的初始解。

最后的实验显示，借助该方法在达到相同质量解的速度提升为5—10倍左右。

其中不乏有原始问题3分钟无法完成求解，而结合使用机器学习算法仅需10秒就能完成求解的时候这种速度的提升对需要每15分钟都需要快速计算决策的SCUC问题非常重要

电网中的优化也是DeepMind指出的智能化MIP可以重点发力的领域。

但是，值得着重指出的是，电网另一个特性就是对于安全性和鲁棒性的极端要求。

而在新问题的数据结构突发巨变，历史数据已经不能指导未来的时候，例如战争，自然或者人为因素导致的发电厂和输电线路的极大变化，机器学习能起到的作用会弱化很多。

这个时候，更多的时候还是依靠MIP求解器自身六个模块那些独立于数据之外的经典算法的实现能力。

另一个例子是中国邮政的路由网络规划问题。

我们在实践中遇到的此类问题通常需要求解数十万整数变量的MIP来决定发车安排如果直接抛给求解器，则往往需要花费一至两个小时才能找到第一个整数解

通过观察，我们发现尽管无法预测全部的发车安排，但是可以预测部分高概率的车辆安排我们进而通过机器学习历史数据，形成了一套根据线性约束关系生成数千发车安排的部分初始解的方法

在此基础上，我们通过临时固定这些决策变量，构造子MIP问题，用求解器快速的计算，补全子问题的解这个子问题由于部分关键变量确定，使得预求解模块可以对问题规模进行大幅度的削减，促成快速求解

尽管这个子问题的最优解不是原始问题的最优解，但在实践中这个解明显优于花费一至两小时算出的第一个可行解。

而从预测到解子问题，通常只需要不到1分钟的时间因此可以说，机器学习帮助我们以50倍的速度提升找到了同等质量的整数解

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

而且也确实有很多学者在这个问题上取得了相对多的进展。

因此，交通领域也是机器学习，智能决策等技术近些年来一直关注的领域。

其实，不仅仅是路线规划。

在五年前，杉数就曾经与某国内最大的出行平台合作，考虑过司机与乘客的智能动态匹配系统，问题从最开始的单纯机器学习计算匹配系数，进行启发式算法分配，到后来进行全城的时间切片网络流匹配，再到将削峰填谷，智慧出行的理念融合，建立起整个系统的动态规划模型，并在强化学习框架下，进行未来趋势与决策的近似方法，最后得到一个在时间和空间上都接近全局优化的方案。

整个系统伴随着数据的完备，算力的到位，在双方携手建立的强化学习框架下不断进化，从简单的线性函数逼近到神经网络近似，越发智能与精准，在2017年的时候，就已经得到了广泛的应用，创造了极大的经济效益与社会效益。

结语

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

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

传统的MIP求解工具有数十年的理论论证和理论分析基础相较之下，MIP求解中的机器学习工具因其模型结构的复杂性，理论论证成果较少

大量的相关机器学习研究都是依靠某一类或者某几类的数据集的数值实验结果用以验证其有效性所以机器学习方法对现实中一般性问题求解的可靠性还有待进一步的论证

另一方面，绝大多数机器学习的算法设计是需要将模型转化成经典的整数，线性，凸或者非凸数学规划模型，再对其分析的。

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

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

皇甫琦，杉数科技副总裁，博士毕业于爱丁堡大学优化算法方向。

曾在XPRESS求解器工作多年，数学规划求解器开发领域的资深专家，曾获得国际著名优化期刊Mathematical Programming Computation的年度最佳论文奖，Computational Optimization and Applications的年度最佳论文奖。

葛冬冬，杉数科技联合创始人amp，首席科学官，上海财经大学交叉科学研究院院长，教授。

博士毕业于斯坦福大学运筹学专业开源求解器项目LEAVES和商业求解器项目COPT的负责人在人工智能，理论计算机，运筹学的期刊和会议NeurIPS，ICML，FOCS，SODA，Operations Research，Mathematical Programming等发表过多篇论文

论文地址: