作者 | 皇甫琦、葛冬冬、杉数科技COPT开发组
Google的DeepMind团队最近官宣了一篇神经网络(Neural Networks)求解MIP论文。一石激起千层浪，在国内外的运筹优化社群引起了讨论。
部分围观吃瓜群众纷纷表示：
"This is suber cool!"
"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难问题类的，也是美国库兰所公布的数学七个千年大奖难题之一，对于此类问题，是否存在多项式时间的精确求解算法，至今仍未有定论。