0
| 本文作者： 我在思考中 | 2021-08-16 14:14 |
作者 | 皇甫琦、葛冬冬、杉数科技COPT开发组
Google的DeepMind团队最近官宣了一篇神经网络(Neural Networks)求解MIP论文。一石激起千层浪，在国内外的运筹优化社群引起了讨论。
部分围观吃瓜群众纷纷表示：
"This is suber 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这个问题，而在MIPLIB2017全集中有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求解过程中，会不定期的做限定循环数的Strongbranching来获取每个变量分支的最佳估计。
Google提出的Neural branching其本质是先通过神经网络离线学习FSB的真实计算结果，再在实际应用中模拟FSB计算，在追求FSB效果的同时，节省计算时间。其实这项工作过去几年间有很多类似的论文。Google的论文在相关工作中也提到了其他8篇相关的研究论文，多数的基本想法是比较类似的。因此论文在这个点上的创新有一定的局限性，正如Google的论文所说：是通过用GPU和ADMM方式大量计算原始问题的FSB近似值，以便可以生成大量的机器学习数据。不过这也从另一个方面反应了FSB的计算量，即使产生离线学习的数据，都不得不设法让它算的更快一些。
和传统的分支算法相比，Neural branching以及其他在这个方面的研究确实是（离线）机器学习和优化算法的一种有趣的结合。但值得指出的是，经典的分支算法，也是基于历史数据对将来分支的预测，它的本质也是一种在线的机器学习机制。例如在杉数求解器里，使用strongbranching只是其中一项，此外还有伪价格(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年的时候，就已经得到了广泛的应用，创造了极大的经济效益与社会效益。
结语
最后，我们想强调，如"机器学习之父"MichaelJordan指出的，未来的人工智能最重要的突破应该与优化算法紧密结合。而这正是运筹学的核心基础。
在今天讨论的这个例子里，简单地说，神经网络和机器学习技术进展，更像是给MIP开发的六大模块中的两个模块探索的武器库增加了一些昂贵（算力资源需求）而有力的武器，丰富了这些模块加速的能力，远远谈不上攻破OR。这些技术展示出来的潜力是值得欢呼的，但是在现实中求解MIP问题，需要的数学技巧和工程经验是极其厚重的。
传统的MIP求解工具有数十年的理论论证和理论分析基础。相较之下，MIP求解中的机器学习工具因其模型结构的复杂性，理论论证成果较少。大量的相关机器学习研究都是依靠某一类或者某几类的数据集的数值实验结果用以验证其有效性。所以机器学习方法对现实中一般性问题求解的可靠性还有待进一步的论证。另一方面，绝大多数机器学习的算法设计是需要将模型转化成经典的整数，线性，凸或者非凸数学规划模型，再对其分析的。
回到MIP，可以说利用机器学习进行某些点上的突破是远远不够的。一般性的整数规划乃至广大的NP难问题，在真正的颠覆性技术突破之前（比如量子计算机的真正实用化），依然可预期在未来很多年，会是人类智力的极限之一。
说明：此文写作中获得了香港中文大学（深圳）王子卓、斯坦福大学叶荫宇、纽约大学陈溪、约翰霍普金斯大学江弘亿等多位学者的指导和建议，在此一并表示感谢。
雷锋网雷锋网雷锋网
雷峰网特约稿件，未经授权禁止转载。详情见转载须知。
