DeepMind的这篇论文并不是万能的。本文对DeepMind近期关于神经网络解决方案MIP（MixedIntegerProgramming）的论文做一些初步解读。事实上，与该领域最近的类似工作相比，DeepMind的工作在MIP解决方案开发的某些方面更加精细和高度工程化，例如分支定界、启发式算法以及使用神经网络的尝试。也取得了比较不错的进展，但是并没有看到太多突破和颠覆的想法。谷歌的DeepMind团队最近正式公布了解决MIP论文的神经网络（NeuralNetworks）。一石激起千层浪，引起了国内外优化界的讨论。有围观者表示：这太酷了。很高兴看到ML和组合优化的合并终于发生了。OR（运筹学）被打破只是时间问题。并且已经有从业者在求代码：代码开源了吗？很乐意在一些标准的难题上对其进行测试。需要在这里查看一些代码。测试这个会很有趣。其实，把机器学习和整数规划结合起来并不是什么新鲜话题。为什么谷歌的论文会引起如此多的关注？谷歌和DeepMind团队的声誉当然是最大的因素。从围棋的AlphaGo到最近蛋白质结构预测的AlphaFold2，DeepMind的一举一动都是风口浪尖上的大动作，也确实在某些领域带来了突破。进步。但这篇论文有没有可以“打破OR（运筹学）”的颠覆性研究成果呢？DeepMind没有回应开源这部分代码的请求，所以要想看到他们的工作，唯一的办法就是阅读论文。杉树科技的COPT求解器开发团队对这篇论文进行了详细的学习和研究。在这里我们呈现团队的分析和讨论，进一步探索机器学习和优化算法的结合。MIP（mixedintegerprogramming）一般指混合整数线性规划。它在满足线性约束条件Ax≤b和整数约束条件x∈Z的前提下求解目标函数f(x)=cx的最小值。其中，数组x称为决策变量，数组c为这些决策变量的目标系数，矩阵A为线性约束矩阵，Z为整数集。整数规划在现实世界中有着广泛的用途，如航空航天、能源电网、制造、交通物流、军事通信等领域。起着不可替代的基础建模和求解功能。但是整数规划也是一个非常困难的问题。在计算机的复杂性理论中，属于NP-hard问题范畴。它也是美国库兰宣布的七大数学千年奖难题之一。对于这样的问题，有多项式时间吗？精确解算法尚未确定。求解整数规划的主要算法组件包括预求解器、分支定界、启发式算法、割平面、冲突分析和线性规划求解器等模块。鉴于DeepMind的论文主要涉及分支算法和启发式算法，我们将重点关注这两个方向。下一节将首先分析DeepMind的基本结论，然后在DeepMind论文中提到的NeuralBranching和NeuralDiving这两个成果上介绍混合整数规划相关的背景知识，然后对新思想和传统思想进行比较分析在论文中。算法关系。DeepMind论文解题结果分析DeepMind的论文之所以受到广泛关注，不仅是因为团队的声誉，更在于论文中报告的惊人的性能提升数据。论文摘要中提到，测试的5组问题中，有3组实现了1.5倍、2倍、10000倍更好的差距。事实上，这里有一个小小的文字游戏。作为MIP求解器开发者，一般不会以一定时间内能够得到的Gap作为主要衡量标准。因为有点误导。想象一类特殊的整数规划问题，比如可行性问题，没有目标函数，只需要找到一组整数解就可以完成。那么Gap在找到整数解之前是100%，找到之后是0%。如果开启和关闭启发式（或切割平面）算法，可以分别在1小时和3小时内找到可行的解决方案。那么，如果以两个小时为观察点，可以说在启用这个算法的前提下，实现的Gap增长是无穷多倍，而如果以半小时或者三个小时为观察点，则差距没有改善。由于DeepMind没有公布计算这些性能指标的原始数据，我们无法以MIP行业公认的方式对其进行评估。一般来说，按照目前公认的考试标准，在MIPLIB的题集上一般限制在两个小时以内，考虑到可以解题的数量和平均解题时间进行比较。一个特定的测试集取得惊人的性能提升并不奇怪，因为这正是机器学习所擅长的：它可以捕捉到同类问题的特征结构，并给出优化趋势的判断。后面会提到，我们自己在开发过程中也有过类似的经历。真正值得关注的是它在MIPLIB上的表现。MIPLIB2017由1000多个来自各个行业的例子组成，而MIPLIB2017Benchmark由240个不同结构的精选问题组成，在筛选时充分区分，因此与电网优化和NN测试集有本质区别比如验证。这也解释了为什么算法对MIPLIB的性能提升效果不如其他数据集明显。为了避嫌，谷歌早前也在论文中表示，训练集使用了完整版MIPLIB中的1000多道题，并去掉了这240道题中剩余的例子。然而，仍然难以避免训练集和测试集之间的结构相似性。例如收集MIPLIB2017完整版时，往往会从同一来源收集多个大小略有不同的计算实例。在选择基准集时，为了避免基准集的重复，我们会尽量避免使用同源的例子，这使得MIPLIB2017完整版中剩余的例子都包含了基准的高度结构化设置类似的问题。例如MIPLIB2017Benchmark中有graph20-20-1rand，MIPLIB2017中有graph-20-80-1rand、graph-40-20-1rand、graph-40-40-1rand、graph-40-80完整的集合-1rand四个结构高度相似的问题。因此，在训练集上获得的经验一定会有助于解决最终的测试集。这些辅助工具是否可以推广到任何一般问题集，这是非常值得怀疑的。分支算法和神经分支分支（Branching）算法是整数规划求解器的核心框架。解决MIP通常需要解决多个LP（线性规划）问题才能完成。第一个LP问题是通过从原始问题中删除所有整数约束得到的。如果第一个LP问题的最优解恰好满足整数条件，那么这个解也是整数规划的最优解。如果LP松弛问题的解不都满足整数条件，分支算法可以继续搜索整数解。分支算法通过选择一个值不是整数的变量x=x，加上x≤floor(x)（即值不大于x的最大整数的下界）和x≥ceil(x)（即值不小于x的最小整数上界）*这两个约束将原问题分解为两个子问题。原始整数规划问题的最优解必须在这两个分支之一中。然后继续求解这两个新问题，以此类推，直到找到最优整数解或者整数解不存在。不难看出，分支算法的本质是枚举。在n个0-1变量的混合整数规划问题中，在最坏情况下，需要遍历所有2的n次方分支节点。也因为混合整数规划问题是NP-hard问题，目前的精确求解算法基本都是基于分支算法的框架。在最坏的情况下，复杂度在指数时间级别，耗时可能会非常长。在实践中，求解整数规划通常远非枚举所有节点。这是因为分支算法可以更智能地选择要分支的变量。在众多分支算法中，最有效的算法是全强分支算法（Fullstrongbranching简称FSB）。算法原理很简单，就是对当前LP（线性规划）问题中每一个取值为非整数的变量进行分支，求解分支后的所有LP问题，通过取值判断选择哪个分支LP的目标函数。能最快完成MIP解。在实践中，FSB需要的计算量非常大，所以对每个LP节点都使用它是不现实的。在MIP求解过程中，会时不时地进行有限循环次数的强分支，以获得每个变量分支的最佳估计。Google提出的Neuralbranching本质是先通过神经网络离线学习FSB的真实计算结果，然后在实际应用中模拟FSB计算，从而在追求FSB效果的同时节省计算时间。事实上，在过去的几年里，关于这项工作的类似论文已经有很多了。谷歌的论文在相关工作中还提到了其他8篇相关研究论文，大部分基本思路都是相似的。因此，论文在这一点上的创新具有一定的局限性，正如谷歌的论文所说：通过使用GPU和ADMM对原问题进行大量的FSB近似计算，从而产生大量的机器学习数据。不过这也从另一个方面反映了FSB的计算量。即使离线学习的数据产生了，我们也得想办法让它更快。与传统的分支算法相比，Neuralbranching等这方面的研究确实是（离线）机器学习和优化算法的有趣结合。但值得指出的是，经典的分支算法也是根据历史数据来预测未来的分支，其本质也是一种在线机器学习机制。例如，在冷杉数求解器中，强分支的使用只是其中之一。此外，还有Pseudocost、Reliability和Inference等公开和非公开的判断标准。这些算法都是基于在求解过程中积累信息，并以此来判断和选择新的分支变量。启发式算法和神经潜水启发式算法是在主要分支定界算法之外寻找整数解的算法的总称。启发式算法是MIP研究的热点，相关论文太多。目前，在SCIP中实现的启发式算法多达57种。这些启发式算法大致可以分为四类：Rounding、Diving、Sub-MIP以及除上述三类之外的其他算法。顾名思义，Rounding启发式算法在LP松弛解不满足整数约束时，对不满足的变量进行舍入，以期望得到整数解。潜水（Diving）启发式算法的本质是深度优先搜索。当LP松弛解不满足整数约束时，从当前节点开始，不断选择最佳分支进行深度优先搜索，直到找到整数解或证明子问题。直到不可行为止。这两类算法虽然原理简单，但也有很多实现变体，这里不再赘述。子混合整数规划问题（Sub-MIP）启发式算法是一大类，它通过构造和求解子MIP问题来寻找高质量的整数解。在构造子问题时，有多种构造方法，例如：固定或收紧变量、添加约束、修改目标函数的值等。其中，如固定变量算法，著名的松弛诱导邻域搜索（Relaxationinducedneighborhoodsearch，简称RINS），其工作原理是当LP松弛解中的一个整数变量的值与当前最佳整数解中的值相同，则变量固定为这个整数值。如果可以固定大量的变量，则固定变量后的子问题可以看作是一个全新的MIP解，希望能找到高质量的整数解。由于大量变量是固定的，子问题的搜索空间会更小，预求解可以进一步缩小问题的规模，因此求解子问题会相对容易。DeepMind提出的NeuralDiving算法利用机器学习和神经网络给出一个问题结构，预测如何固定一些整数变量的值，然后求解子MIP。因此，尽管使用了潜水这个词，我们认为它可以归类为解决子问题的启发式算法。可以看出，该算法在原理上与上述RINS有很多相似之处，只是固定变量的方式不同。虽然这个想法与许多现有的启发式算法相似，但NeuralDiving仍然有其独特之处。NeuralDiving最大的优势之一是可以生成多组差异化的偏变量值，并在正式求解原问题之前启动启发式算法。这一方面提高了算法寻找高质量整数解的成功率，另一方面也提前了寻找整数解的时间，所以可以更早的得到更小的Gap。我们也认为这是这篇DeepMind论文中最有价值的部分。人工智能与MIP结合的实例应用firnumbersolver在开发过程中充分利用了机器学习工具。除了上面提到的本质上是在线学习的分支算法之外，我们还在很多其他不同的方向上使用了机器学习工具。例如，求解子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年获得广泛应用，创造了巨大的经济效益和社会效益。结语最后，我们要强调的是，正如“机器学习之父”迈克尔·乔丹所指出的，未来人工智能最重要的突破应该与优化算法紧密结合。而这就是运筹学的核心基础。在今天讨论的例子中，简单来说，神经网络和机器学习技术的进步更像是在MIP开发的六个模块中的两个探索的武器库中添加一些昂贵的（计算资源需求）。强大的武器丰富了这些模块的加速能力，远非破坏OR。这些技术所展现的潜力值得欢呼，但解决现实中的MIP问题需要极其繁重的数学技能和工程经验。传统的MIP求解工具有几十年的理论论证和理论分析基础。相比之下，由于模型结构的复杂性，机器学习工具在MIP求解方面的理论论证成果较少。大量相关的机器学习研究依赖于某一类或几类数据集的数值实验结果来验证其有效性。因此，机器学习方法解决现实中一般问题的可靠性需要进一步论证。另一方面，大多数机器学习的算法设计需要将模型转化为经典的整数、线性、凸或非凸数学规划模型，然后对其进行分析。回到MIP，可以说利用机器学习在某些点上取得突破是远远不够的。一般整数规划甚至广义的NP-hard问题，在真正具有颠覆性的技术突破之前（比如量子计算机的真正实际应用），在未来许多年内仍有望成为人类智能的极限之一。说明：在写这篇文章的过程中，得到了香港中文大学（深圳）汪子卓、斯坦福大学叶寅宇、纽约大学陈曦、约翰斯江宏义等多位学者的指导和建议霍普金斯大学。在此表示感谢。作者简介黄福奇，闪数科技副总裁，毕业于英国爱丁堡大学，博士。优化算法方向。从事XPRESS求解器多年，是数学规划求解器开发领域的资深专家。曾获得国际著名优化期刊《数学规划计算》年度最佳论文奖（2018），《计算优化与应用》年度最佳论文奖（2015）。.葛东东，闪数科技联合创始人兼首席科学官，上海财经大学交叉科学研究所院长、教授。博士斯坦福大学运筹学博士。开源求解器项目LEAVES和商业求解器项目COPT的负责人。在人工智能、理论计算、运筹学NeurIPS、ICML、FOCS、SODA、OperationsResearch、MathematicalProgramming等期刊和会议上发表多篇论文。论文地址：https://arxiv.org/abs/2012.13349
