机器学习|并非无所不能—评DeepMind近期神经网络求解MIP的论文( 四 )

虽然思路和很多既有启发式算法形式类似，但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倍的速度提升找到了同等质量（其实是更好）的整数解。