本文经AI新媒体量子位授权转载,转载请联系出处。
本文对DeepMind近期的神经网络求解MIP的论文进行了一些初步解读。相较于此领域近期的类似工作,DeepMind的工作在MIP的求解开发某些环节,如分支定界,启发式算法上所做的利用神经网络的尝试,更加的精细化和高度工程化,并且与开源求解器的耦合程度明显更高,也取得了相对良好的进展,但是并未看到太多有突破性和颠覆性的思想。
Google的DeepMind团队最近官宣了一篇神经网络求解MIP论文。
一石激起千层浪,在国内外的运筹优化社群引起了讨论。
部分围观吃瓜群众纷纷表示:
部分围观吃瓜群众纷纷表示:
攻破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的每次出手都是风口浪尖上的大动作,也确实在某些领域带来过突破性的进展。
但这篇论文是否有颠覆性的研究成果,以至于可以
DeepMind并没有回应开源这部分代码的要求,因此想要看看他们的工作只能读论文。
杉数科技的COPT求解器开发团队详细地学习、研究了这篇论文。
在此我们把团队的分析讨论奉上,以资对机器学习和优化算法结合做进一步探讨。
MIP一般特指混合整数线性规划,它在满足线性约束条件Ax≤b和整数约束条件x∈Z的前提下,求解目标函数f(x) = c·x的最小值。
其中数组x叫做决策变量,数组c是这些决策变量的目标系数,矩阵A是线性约束矩阵,Z是整数集合。
整数规划在现实世界中的用途极为广阔,例如在航空航天,能源电网,生产制造,交通物流,军事与通讯等领域都起着不可替代的基础建模与求解功能。
但是整数规划也是非常困难的问题,在计算机的复杂性理论上,是属于NP难问题类的,也是美国库兰所公布的数学七个千年大奖难题之一,对于此类问题,是否存在多项式时间的精确求解算法,至今仍未有定论。
求解整数规划的主要算法部件有:预求解、分支定界、启发式算法、割平面、冲突分析和线性规划求解器等模块。
鉴于DeepMind此次的论文主要涉及分支算法和启发式算法,我们分别重点从这两个方向进行探讨。