谷歌的DeepMind 团队最近发表了一篇关于使用神经网络解决MIP 的论文。一石激起千层浪，引发了国内外运筹学和优化界的讨论。
有看瓜吃瓜的人表示：
“这太酷了！”
“很高兴看到机器学习和组合优化的融合最终发生”
“OR（运筹学）被打破只是时间问题”
一些从业者已经开始寻求代码：
'代码是开源的吗？很想在一些标准的难题上测试它”
“需要在这里查看一些代码”
“测试这个会非常有趣”
事实上，将机器学习和整数规划结合起来并不是一个新话题。为什么谷歌的这篇论文引起如此多的关注？谷歌和DeepMind团队的声誉当然是最大的因素。从围棋中的AlphaGo到最近蛋白质结构预测中的AlphaFold2，DeepMind的每一步举动都是走在最前沿的一大步，也确实在一些领域带来了突破。进步。但这篇论文是否有能够打破OR（运筹学）的颠覆性研究成果呢？
DeepMind 没有回应开源这部分代码的请求，所以如果你想看到他们的工作，你只能阅读论文。这篇论文的原文可以在arXiv上找到：
杉树科技COPT求解器开发团队对本文进行了详细的研究和研究。这里我们呈现团队的分析和讨论，以进一步探索机器学习和优化算法的结合。
MIP（Mixed Integer Planning）一般指混合整数线性规划。它在满足线性约束Axb和整数约束xZ的前提下求解目标函数f(x)=cx的最小值。数组x称为决策变量，数组c是这些决策变量的目标系数，矩阵A是线性约束矩阵，Z是整数集合。整数规划在现实世界中有着极其广泛的用途，如航空航天、能源网格、制造、交通物流、军事和通信等，发挥着不可替代的基础建模和求解功能。但整数规划也是一个非常困难的问题。从计算机复杂性理论来看，它属于NP-hard问题范畴。这也是美国卡伦宣布的七个数学千年奖问题之一。对于这样的问题，是否存在多项式时间？精确的求解算法尚未确定。
求解整数规划的主要算法组件包括：预求解、分支定界、启发式算法、割平面、冲突分析和线性规划求解器模块。由于DeepMind这次的论文主要涉及分支算法和启发式算法，所以我们将分别关注这两个方向。下面将首先分析DeepMind 的基本结论，然后针对DeepMind 论文中提到的Neural Branching 和Neural Diving 两项成果介绍混合整数规划相关的背景知识，然后比较分析DeepMind 论文中的新思想和传统。纸。算法关系。
文章最后我们还给出了山数科技在求解器内部开发和外部应用过程中对机器学习、强化学习等技术的探索和运用的一些简单例子。我们还想说明，从诞生的第一天起，运筹学和优化技术就注定是一门广泛交叉的科学。各种大数据和人工智能技术的兴起为其注入了新的活力。在智能决策领域，可以预见它将发挥越来越重要的作用。
1
DeepMind论文解题结果分析
DeepMind 的论文引起了广泛关注，不仅因为团队的声誉，还因为论文中报告的惊人的性能提升数据。正如论文摘要中提到的，在测试的5 组问题中，3 组分别取得了1.5 倍、2 倍和10,000 倍的更好Gap。
其实，这里有一个小小的文字游戏。作为MIP求解器开发者，我们一般不会以一定时间内能够获得的Gap作为主要标准。因为这有些误导。想象一下更特殊类型的整数规划问题，例如可行性问题，它没有目标函数，只需要找到一组整数解。那么在找到整数解之前，它的Gap是100%，找到之后，它是0%。如果开启和关闭某种启发式（或割平面）算法，分别可以在1小时和3小时内找到可行解。如果以两个小时为观察点，可以说开启这个算法后，达到的Gap增加了无限倍。但如果以半小时或三小时为观察点，Gap并没有改善。由于DeepMind 尚未公布用于计算这些性能指标的原始数据，因此我们无法使用MIP 行业公认的方法对其进行评估。一般来说，根据目前公认的测试标准，通常是基于MIPLIB问题集，以两个小时为限，并考虑可以解决的问题数量和平均解决时间进行比较。
特定的测试集取得惊人的性能提升并不奇怪，因为这正是机器学习所擅长的：它可以捕捉同类型问题的特征结构并给出优化趋势的判断。正如后面提到的，我们自己在开发过程中也有类似的经历。真正值得关注的是它在MIPLIB 上的表现。 MIPLIB 2017由来自各行各业的1000多个示例组成，MIPLIB2017 Benchmark由从中选出的240个不同结构的问题组成。它在筛选过程中是完全区分的，因此它与电网优化和NN验证等测试集有本质的不同。这也解释了为什么该算法在MIPLIB上的性能提升不如其他数据集那么明显。
为了避嫌，谷歌早前也在论文中表示，训练集使用了完整版MIPLIB 中的1000 多个问题，并删除了这240 个问题中剩余的示例。然而，仍然难以避免训练集和测试集之间的结构相似性。例如，在收集MIPLIB 2017 完整版时，通常会从同一来源收集多个大小略有不同的计算示例。在选择基准集时，为了避免基准集重复，我们会尽量避免使用同一来源的示例。这使得MIPLIB 2017 完整版中的其余示例包含基准集的高级结构。类似的问题。比如MIPLIB 2017 Benchmark中有graph20-20-1rand的问题，有graph-20-80-1rand、graph-40-20-1rand、graph-40-40-1rand、graph-40- MIPLIB2017全套中80-。 1r和四个结构高度相似的问题。因此，在训练集上获得的经验肯定会对解决最终的测试集有帮助。这些帮助是否可以推广到任何一般问题集是非常值得怀疑的。
2
分支算法和神经分支
分支算法是整数规划求解器的核心框架。解决MIP 通常需要解决多个LP（线性规划）问题。第一个LP 问题是没有所有整数约束的原始问题。如果第一个LP问题的最优解恰好满足整数条件，那么这个解也是整数规划的最优解。如果LP松弛问题的解不全部满足整数条件，则可以通过分支算法继续寻找整数解。
分支算法通过选择值不是整数的变量x=x* 并添加xfloor(x*)（即值不大于x* 的最大整数下界）和x 进行分支。分别为ceil(x*)。 （即值不小于x*的最小整数上界）这两个约束将原问题分解为两个子问题。原整数规划问题的最优解必定位于这两个分支之一。接下来继续解决这两个问题，以此类推，直到找到最优整数解或者证明整数解不存在。不难看出，分支算法的本质就是枚举。在具有n个0-1变量的混合整数规划问题中，在最坏的情况下，必须遍历所有2的n次方分支节点。又由于混合整数规划问题是一个NP难问题，目前精确求解的算法基本上都是基于分支算法的框架。在最坏的情况下，复杂度是指数级的时间级别，并且耗时可能会非常长。
在实践中，求解整数规划通常需要更少的所有节点枚举。这是因为分支算法可以以更智能的方式选择要从中分支的变量。在众多分支算法中，最有效的算法是完全强分支算法（Full Strong Branching，简称FSB）。该算法的原理很简单，就是通过对当前LP（线性规划）问题中每个值不是整数的变量进行分支，求解所有分支的LP问题，并根据目标函数值判断选择哪个分支LP。 MIP解决方案可以尽快完成。在实际应用中，FSB所需的计算量非常大，因此对每个LP节点都使用它是不现实的。在MIP 求解过程中，将不时执行有限循环次数的强分支，以获得每个变量分支的最佳估计。
Google提出的Neural Branching的本质是首先通过神经网络离线学习FSB的真实计算结果，然后在实际应用中模拟FSB计算，在追求FSB效果的同时节省计算时间。事实上，在过去的几年里，关于这项工作的类似论文已有很多。 Google的论文在相关工作中还提到了其他8篇相关研究论文，大部分基本思路都比较相似。因此，论文在这一点上的创新具有一定的局限性。正如Google论文中所说：它使用GPU和ADMM来计算原始问题的大量FSB近似值，从而可以生成大量的机器学习数据。不过，这也从另一个侧面反映了FSB的计算量。即使生成了离线学习数据，我们也必须想办法让它更快。
与传统的分支算法相比，神经分支和该领域的其他研究确实是（离线）机器学习和优化算法的有趣组合。然而，值得指出的是，经典分支算法还根据历史数据预测未来的分支。其本质也是一种在线机器学习机制。例如，在冷杉数求解器中，使用强分支只是其中之一。此外，还有伪价格（Pseudocost）、可靠性（Reliability）、推断（Inference）等公开和其他非公开的判断标准。这些算法都是在求解过程中积累信息，并利用这些信息来判断和选择新的分支变量。
3
启发式算法和神经潜水
启发式算法是除主要分支定界算法之外寻找整数解的算法的总称。启发式算法是MIP 研究的热点，相关论文众多。目前，仅SCIP 中就实现了57 种启发式算法。这些启发式算法大致可以分为四类：Rounding、Diving、Sub-MIP，以及上述三类之外的其他算法。
顾名思义，Rounding 启发式算法对不满足的变量进行舍入，以期在LP 松弛解不满足整数约束时得到整数解。潜水启发式算法的本质是深度优先搜索。当LP松弛解不满足整数约束时，从当前节点开始，不断选择最佳分支进行深度优先搜索，直到找到整数解或证明子问题。直到不可行为止。这两类算法的原理虽然简单，但也有多种实现变体，这里不做讨论。
子混合整数规划问题（Sub-MIP）的启发式算法是一个大类，它通过构造和解决子MIP 问题来找到高质量的整数解。构造子问题时，构造方法有很多种，例如固定或收紧变量、添加约束、修改目标函数值等。其中，如固定变量算法，比较著名的是松弛诱导邻域搜索（RINS）。它的工作原理是，当LP松弛解中某个整数变量的值等于当前最佳整数解中的值一致时，该变量就固定为这个整数值。如果可以固定大量的变量，那么固定变量后的子问题就可以作为一个新的MIP来求解，以期找到高质量的整数解。由于大量变量是固定的，子问题的搜索空间会变小，预求解可以进一步减小问题的规模，因此子问题的求解会相对容易一些。
DeepMind提出的Neural Diving算法利用机器学习和神经网络给出问题结构，预测如何固定一些整数变量的值，然后求解子MIP。因此，尽管使用了Diving 这个词，但我们认为它可以归类为解决子问题的启发式算法。可以看出，该算法与上述RINS在原理上有很多相似之处，只是固定变量的方式不同。
尽管其思想与许多现有的启发式算法类似，但Neural Diving 仍然有其独特的功能。 Neural Diving 的最大优点之一是它可以生成多组有区别的部分变量值，并在正式解决原始问题之前启动启发式算法。一方面，这提高了算法寻找高质量整数解的成功率。另一方面也提前了寻找整数解的时间，因此可以更早地得到更小的Gap。我们也认为这是DeepMind论文中最有价值的部分。
4
人工智能与MIP结合的示例应用
山书求解器在开发过程中充分利用了机器学习工具。除了上面提到的本质上是在线学习的分支算法之外，我们还在许多其他不同的方向上使用机器学习工具。
例如，求解子MIP 的启发式算法是一种有效但非常耗时的算法。在开发过程中，我们解决了大量的子问题，提取子问题特征（例如重新预求解结果、变量类型等），并使用机器学习来帮助确定是否值得花费时间从某个子问题开始求解，可以避免耗时，也是提高求解速度的有效方法。
另外，我们线性规划LP求解器的开发也受益于机器学习。例如，我们对一些具有特殊结构的LP使用机器学习方法来预测某个变量是否是最优解的基本解的一部分，并通过对目标函数的小扰动将这种预测结果应用到LP问题中以实现快速求解。
除了上述嵌入求解器的机器学习成果外，过去几年，山书在使用求解器解决多个行业的疑难问题时，也从机器学习、深度学习、强化学习等方面受益匪浅。大的。
国家电网安全约束单位承诺（SCUC）问题就是一个例子。 SCUC问题的特点是规模小，但需要快速求解。我们遇到的实际问题只有几千个整型变量，每15分钟需要解决一次，并且必须在15分钟内尽快解决。我们利用深度神经网络等机器学习方法来预测MIP模型最优解中每个决策变量取1的概率，从而固定一些置信度最高的变量，并对一些中间值的变量添加多变量分支切割面。信心。使最终问题以最高概率可行。这种方法可以有效降低分支定界树的搜索规模。一方面可以实现快速收敛，另一方面可以快速找到高质量的初始解。最终实验表明，使用该方法，达到相同质量解（Gap=0.01%）的速度提高了约5-10倍。很多情况下，原来的问题3分钟无法解决，但结合机器学习算法，只需10秒就可以解决。这种速度的提高对于每15 分钟需要快速计算决策的SCUC 问题非常重要。
电网方面的优化也是DeepMind指出智能MIP可以重点发力的领域。但值得强调的是，电网的另一个特点是对安全性和鲁棒性的极端要求。当新问题的数据结构突然发生巨大变化，历史数据已经无法指导未来，比如战争、自然或人为因素导致发电厂和输电线路发生巨大变化时，机器学习的作用就会被大大削弱。这时，更多的时候，我们仍然依赖于MIP求解器本身的六个模块中与数据无关的经典算法的实现能力。
又如中国邮政的路由网络规划问题。我们在实际中遇到的此类问题通常需要求解数十万个整数变量的MIP 来确定发车时刻表。如果直接扔给求解器，通常需要一到两个小时才能找到第一个整数解（差距在30% 左右，甚至更糟）。通过观察，我们发现虽然不可能预测所有的出发安排，但是我们可以预测一些高概率的车辆安排。我们进一步开发了一套方法，通过历史数据的机器学习，基于线性约束关系为数千个列车时刻表生成部分初始解决方案。在此基础上，我们通过暂时固定这些决策变量来构造子MIP问题，并利用求解器快速计算并完成子问题的求解。由于该子问题的一些关键变量已经确定，预求解模块可以显着减小问题规模，有利于快速求解。虽然这个子问题的最优解并不是原问题的最优解，但在实践中这个解（差距在10%以内）明显优于第一个需要一到两个小时计算的可行解。从预测到子问题的解决，通常需要不到1分钟。因此，可以说机器学习帮助我们以50 倍的速度找到相同质量（实际上更好）的整数解。
另一个具有更广泛意义的例子是，在最近的科研论文和几家自称从事智能决策的公司的声明中，我们可以看到一些交通问题，例如车辆调度和路线规划，由于其事件频率高且数据结构。它相对稳定，因此无论是分支策略、初始解固定，甚至割平面生成，都可以通过机器学习技术获得，从而加速问题的MIP模型求解。确实，很多学者在这个问题上已经取得了比较大的进展。因此，交通领域也是机器学习、智能决策等技术近年来重点关注的领域。
事实上，这不仅仅是路线规划。五年前，杉树与中国最大的出行平台之一合作，考虑为驾驶员和乘客提供智能动态匹配系统。该问题从简单的机器学习计算匹配系数和启发式算法分配，到后来的全城时间分片网络流量匹配，再融合削峰填谷、智慧出行等理念，建立了整个城市的动态规划模型。系统，并在强化学习框架下，逼近未来的趋势和决策，最终得到在时间和空间上都接近全局优化的解决方案。随着数据的完备和算力的可用，整个系统在双方共同建立的强化学习框架下不断演化。从简单的线性函数逼近到神经网络逼近，变得更加智能和准确。 2017年已实现广泛应用，创造了巨大的经济效益和社会效益。
5
结论
最后，我们要强调的是，正如“机器学习之父”迈克尔·乔丹所指出的那样，未来人工智能最重要的突破应该与优化算法紧密结合。这就是运筹学的核心基础。
在今天讨论的例子中，简单地说，神经网络和机器学习技术的进步更像是在MIP 开发的六个模块中的两个探索的武器库中添加一些昂贵的（计算资源需求）。强大的武器丰富了这些模块的加速能力，这远没有打破OR。这些技术所展现出的潜力值得欢呼，但解决现实中的MIP 问题需要极其繁重的数学技能和工程经验。
传统的MIP求解工具具有数十年的理论论证和理论分析基础。相比之下，MIP解决方案中使用的机器学习工具由于模型结构的复杂性，理论论证成果很少。大量相关的机器学习研究依赖于某一类或几类数据集的数值实验结果来验证其有效性。因此，机器学习方法解决现实中普遍问题的可靠性需要进一步论证。另一方面，大多数机器学习算法设计需要将模型转换为经典的整数、线性、凸或非凸数学规划模型，然后对其进行分析。
回到MIP，可以说仅仅利用机器学习在某些点上取得突破是远远不够的。在真正的颠覆性技术突破（例如量子计算机的真正实用化）之前，一般整数规划甚至广泛的NP 难题仍然有望成为未来许多年人类智能的限制之一。
注：在本文的撰写过程中，我得到了香港中文大学（深圳）的王自卓、斯坦福大学的叶印宇、纽约大学的陈曦、约翰斯大学的姜宏毅等多位学者的指导和建议霍普金斯大学。我谨向他们表示感谢。
