算法|并非无所不能—评DeepMind近期神经网络求解MIP的论文

本文对DeepMind近期的神经网络求解MIP（混合整数规划）的论文进行了一些初步解读。事实上，相较于此领域近期的类似工作，DeepMind的工作在MIP的求解开发某些环节，如分支定界，启发式算法上所做的利用神经网络的尝试，更加的精细化和高度工程化，并且与开源求解器的耦合程度明显更高，也取得了相对良好的进展，但是并未看到太多有突破性和颠覆性的思想。

Google的DeepMind团队最近官宣了一篇神经网络(Neural Networks)求解MIP论文。一石激起千层浪，在国内外的运筹优化社群引起了讨论。
部分围观吃瓜群众纷纷表示：

"This is uber cool"
【算法|并非无所不能—评DeepMind近期神经网络求解MIP的论文】"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。