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

在实践中，求解整数规划通常远不需要枚举全部的节点。这是因为分支算法可以以一种更聪明的方式选择进行分支的变量。在众多分支算法中，最有效果的算法是完整的强分支算法（Full strong branching简称FSB）。该算法原理非常简单，即通过分别对当前LP（线性规划）问题的各个取值不为整数的变量进行分支，求解全部的分支后的LP问题，并通过LP的目标函数值判断选取哪个分支是可以最快的完成MIP求解。实践中FSB所需要的计算量非常巨大，因此对每个LP节点使用很不现实。在MIP求解过程中，会不定期的做限定循环数的Strongbranching来获取每个变量分支的最佳估计。

Google提出的Neural branching其本质是先通过神经网络离线学习FSB的真实计算结果，再在实际应用中模拟FSB计算，在追求FSB效果的同时，节省计算时间。其实这项工作过去几年间有很多类似的论文。Google的论文在相关工作中也提到了其他8篇相关的研究论文，多数的基本想法是比较类似的。因此论文在这个点上的创新有一定的局限性，正如Google的论文所说：是通过用GPU和ADMM方式大量计算原始问题的FSB近似值，以便可以生成大量的机器学习数据。不过这也从另一个方面反应了FSB的计算量，即使产生离线学习的数据，都不得不设法让它算的更快一些。

和传统的分支算法相比，Neural branching以及其他在这个方面的研究确实是（离线）机器学习和优化算法的一种有趣的结合。但值得指出的是，经典的分支算法，也是基于历史数据对将来分支的预测，它的本质也是一种在线的机器学习机制。例如在杉数求解器里，使用strongbranching只是其中一项，此外还有伪价格(Pseudocost)、可靠性(Reliability)和推断(Inference)等公开和其他不公开的判断标准。这些算法均是通过在求解的过程中积攒信息，并以此来判断、选择新的分支变量等。

启发式算法与Neural Diving

启发式算法，是在主体的分支定界算法之外寻找整数解的算法的总称。启发式算法是MIP研究的一项热点，相关的论文不胜枚举，目前仅在SCIP中实现的启发式算法就有57种之多。这些启发式算法又大致可以分为四类：取整（Rounding）、下潜（Diving）、子问题（Sub-MIP）和上述三类之外的其他算法。

取整（Rounding）启发式算法顾名思义，是在LP松弛解不满足整数约束时，对不满足的变量进行取整，以期望获得整数解。下潜（Diving）启发式算法的本质是深度优先搜索，它在LP松弛解不满足整数约束时，从当前节点出发，不断的选取最佳分支进行深度优先搜索，直到找到整数解或证明子问题为不可行为止。这两类算法虽然原理简单，但是也都有多种实现变种，在这里不展开讨论。

子混合整数规划问题（Sub-MIP）的启发式算法是一个大类，它通过构造并求解子MIP问题来寻找高质量的整数解。在构造子问题的时候，又有多种构造方式，例如：固定或缩紧变量，添加约束以及修改目标函数值。其中如固定变量类的算法，比较有名的有松弛导向邻域搜索（Relaxation induced neighborhood search或简称RINS），它的工作原理是当某个整数变量在LP松弛解中的值与当前最好整数解中的值一致，则将该变量固定在这个整数值。如果大量变量可以被固定，则可以把这个固定变量后的子问题当作一个全新的MIP求解，以期望可以找到高质量的整数解。由于大量的变量被固定了，子问题的搜索空间会变小，且预求解可以进一步的削减问题的规模，因此解子问题会相对容易些。

DeepMind提出的Neural Diving这个算法，是通过机器学习和神经网络，给定一个问题结构，预判如何固定部分整数变量的取值，然后去求解子MIP。因此，尽管用到了Diving这个词，但是我们认为它还是可以归类为求解子问题的启发式算法。可以看出这个算法在原理上和上述的RINS有诸多相似之处，只是固定变量的方式不同。