谷歌的DeepMind团队最近发表了一篇关于神经网络解决MIP的论文一石激起千层浪，引起了国内外运营优化界的讨论
一些吃瓜的围观群众纷纷表示:
这太棒了！
很高兴看到ML和组合优化的融合终于发生了
打破OR只是时间问题
一些从业者已经在要求代码:
代码是开源的吗。我想在一些标准的难题上测试一下
需要在这里看到一些代码
测试这个会很有趣
事实上，机器学习和整数规划的结合并不是一个新的话题为什么谷歌的这篇论文会吸引这么多关注谷歌和DeepMind团队的名气当然是最大的因素从最近蛋白质结构预测的Go的AlphaGo到AlphaFold2，DeepMind的每一个镜头都是风口浪尖上的大动作，确实在一些领域带来了突破性的进展但这篇论文有没有颠覆性的研究成果，让它可以破OR
DeepMind没有回应开源代码的要求，所以如果你想看他们的作品，你只能看论文。本文原文可在arXiv上获得:
山书科技的COPT求解器开发团队对本文进行了详细的研究和学习在这里，我们呈现团队的分析和讨论，从而进一步探讨机器学习和优化算法的结合
MIP一般指混合整数线性规划，求解目标函数f =cx的最小值，其中数组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道不同结构的题组成，筛选时充分区分，与电网优化，nn验证等测试集有本质区别
算法性能提升效果并不如其他数据集明显的原因。
为了避嫌，Google 也一早就在论文中表明，训练集用的是 MIPLIB 完整版的 1000 多个问题，去掉这 240 个问题剩余的例子但是这依然难以避免训练集和测试集的结构相似性如 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
分支算法是整数规划求解器的核心框架求解 MIP 通常需要求解多个 LP问题完成其中第一个 LP 问题是原始问题去掉全部的整数约束得来如果第一个 LP 问题的最优解碰巧满足整数条件，则这个解也是整数规划的最优解如果 LP 松弛问题的解不都满足整数条件，则可以通过分支算法继续寻找整数解
分支算法通过选择一个取值不为整数的变量 x=x * 进行分支，通过分别添加 x≤floor 和 x≥ceil 这两个约束来把原始问题分解为两个子问题原整数规划问题的最优解一定在这两个分支之一接下来继续求解这两个新的问题，并以此类推，直到找到最优的整数解或者证明整数解不存在为止不难看出，分支算法的本质是枚举，在有 n 个 0—1 变量的混合整数规划问题里，最坏情况要遍历所有 2 的 n 次方个分支节点也因为混合整数规划问题是个 NP 难问题，所以目前精确求解的算法，基本上都基于分支算法的框架，最坏情况下复杂度是指数时间级别，耗时可能会极端漫长
在实践中，求解整数规划通常远不需要枚举全部的节点这是因为分支算法可以以一种更聪明的方式选择进行分支的变量在众多分支算法中，最有效果的算法是完整的强分支算法该算法原理非常简单，即通过分别对当前 LP问题的各个取值不为整数的变量进行分支，求解全部的分支后的 LP 问题，并通过 LP 的目标函数值判断选取哪个分支是可以最快的完成 MIP 求解实践中 FSB 所需要的计算量非常巨大，因此对每个 LP 节点使用很不现实在 MIP 求解过程中，会不定期的做限定循环数的 Strongbranching 来获取每个变量分支的最佳估计
Google 提出的 Neural branching 其本质是先通过神经网络离线学习 FSB 的真实计算结果，再在实际应用中模拟 FSB 计算，在追求 FSB 效果的同时，节省计算时间其实这项工作过去几年间有很多类似的论文Google 的论文在相关工作中也提到了其他 8 篇相关的研究论文，多数的基本想法是比较类似的因此论文在这个点上的创新有一定的局限性，正如 Google 的论文所说:是通过用 GPU 和 ADMM 方式大量计算原始问题的 FSB 近似值，以便可以生成大量的机器学习数据不过这也从另一个方面反应了 FSB 的计算量，即使产生离线学习的数据，都不得不设法让它算的更快一些
和传统的分支算法相比，Neural branching 以及其他在这个方面的研究确实是机器学习和优化算法的一种有趣的结合但值得指出的是，经典的分支算法，也是基于历史数据对将来分支的预测，它的本质也是一种在线的机器学习机制例如在杉数求解器里，使用 strongbranching 只是其中一项，此外还有伪价格 ，可靠性 和推断 等公开和其他不公开的判断标准这些算法均是通过在求解的过程中积攒信息，并以此来判断，选择新的分支变量等
启发式算法与 NeuralDiving
启发式算法，是在主体的分支定界算法之外寻找整数解的算法的总称启发式算法是 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 年的时候，就已经得到了广泛的应用，创造了极大的经济效益与社会效益
结语
最后，我们想强调，如 "机器学习之父"MichaelJordan 指出的，未来的人工智能最重要的突破应该与优化算法紧密结合而这正是运筹学的核心基础
在今天讨论的这个例子里，简单地说，神经网络和机器学习技术进展，更像是给 MIP 开发的六大模块中的两个模块探索的武器库增加了一些昂贵而有力的武器，丰富了这些模块加速的能力，远远谈不上攻破 OR这些技术展示出来的潜力是值得欢呼的，但是在现实中求解 MIP 问题，需要的数学技巧和工程经验是极其厚重的
传统的 MIP 求解工具有数十年的理论论证和理论分析基础相较之下，MIP 求解中的机器学习工具因其模型结构的复杂性，理论论证成果较少大量的相关机器学习研究都是依靠某一类或者某几类的数据集的数值实验结果用以验证其有效性所以机器学习方法对现实中一般性问题求解的可靠性还有待进一步的论证另一方面，绝大多数机器学习的算法设计是需要将模型转化成经典的整数，线性，凸或者非凸数学规划模型，再对其分析的
回到 MIP，可以说利用机器学习进行某些点上的突破是远远不够的一般性的整数规划乃至广大的 NP 难问题，在真正的颠覆性技术突破之前，依然可预期在未来很多年，会是人类智力的极限之一
说明:此文写作中获得了香港中文大学王子卓，斯坦福大学叶荫宇，纽约大学陈溪，约翰霍普金斯大学江弘亿等多位学者的指导和建议，在此一并表示感谢。
