本文对DeepMind近期的神经网络求解MIP（混合整数规划）的论文进行了一些初步解读。
事实上，相较于此领域近期的类似工作，DeepMind的工作在MIP的求解开发某些环节，如分支定界，启发式算法上所做的利用神经网络的尝试，更加的精细化和高度工程化。
其中数组x叫做决策变量，数组c是这些决策变量的目标系数，矩阵A是线性约束矩阵，Z是整数集合。整数规划在现实世界中的用途极为广阔。
例如在航空航天、能源电网、生产制造、交通物流、军事与通讯等领域都起着不可替代的基础建模与求解功能。
鉴于DeepMind此次的论文主要涉及分支算法和启发式算法，我们分别重点从这两个方向进行探讨。
设想一类较特殊的整数规划问题，如可行性问题，它没有目标函数，只需要找到一组整数解即可完成。那么在找到整数解之前，其Gap就是100%，找到之后就是0%。
如果某个启发式（或者割平面）算法，在开启和关闭的的情况下，分别可以于1小时和3小时找到可行解。
则如果以两小时为观察点，则可以说在开启这项算法的前提下，实现的Gap提升就是无穷多倍，而若以半小时或者三个小时作为观察点，则Gap没有提升。
因此在训练集上获得的经验，必然会对求解最后的测试集有帮助。而这些帮助能否泛化推广到任何通用问题集上，高度存疑。分支算法与NeuralBranching分支（Branching)算法是整数规划求解器的核心框架。求解MIP通常需要求解多个LP（线性规划）问题完成。其中第一个LP问题是原始问题去掉全部的整数约束得来。
如果第一个LP问题的最优解碰巧满足整数条件，则这个解也是整数规划的最优解。如果LP松弛问题的解不都满足整数条件，则可以通过分支算法继续寻找整数解。分支算法通过选择一个取值不为整数的变量x=x*进行分支，通过分别添加x≤floor(x*)（即取值不大于x*的最大整数下界）和x≥ceil(x*)（即取值不小于x*的最小整数上界）这两个约束来把原始问题分解为两个子问题。
原整数规划问题的最优解一定在这两个分支之一。接下来继续求解这两个新的问题，并以此类推，直到找到最优的整数解或者证明整数解不存在为止。
不难看出，分支算法的本质是枚举，在有n个0-1变量的混合整数规划问题里，最坏情况要遍历所有2的n次方个分支节点。
该算法原理非常简单，即通过分别对当前LP（线性规划）问题的各个取值不为整数的变量进行分支，求解全部的分支后的LP问题，并通过LP的目标函数值判断选取哪个分支是可以最快的完成MIP求解。
这些启发式算法又大致可以分为四类：取整（Rounding）、下潜（Diving）、子问题（Sub-MIP）和上述三类之外的其他算法。
取整（Rounding）启发式算法顾名思义，是在LP松弛解不满足整数约束时，对不满足的变量进行取整，以期望获得整数解。
下潜（Diving）启发式算法的本质是深度优先搜索，它在LP松弛解不满足整数约束时，从当前节点出发，不断的选取最佳分支进行深度优先搜索，直到找到整数解或证明子问题为不可行为止。这两类算法虽然原理简单，但是也都有多种实现变种，在这里不展开讨论。子混合整数规划问题（Sub-MIP）的启发式算法是一个大类，它通过构造并求解子MIP问题来寻找高质量的整数解。在构造子问题的时候，又有多种构造方式，例如：固定或缩紧变量，添加约束以及修改目标函数值。
其中如固定变量类的算法，比较有名的有松弛导向邻域搜索（Relaxationinducedneighborhoodsearch或简称RINS），它的工作原理是当某个整数变量在LP松弛解中的值与当前最好整数解中的值一致，则将该变量固定在这个整数值。
如果大量变量可以被固定，则可以把这个固定变量后的子问题当作一个全新的MIP求解，以期望可以找到高质量的整数解。由于大量的变量被固定了，子问题的搜索空间会变小，且预求解可以进一步的削减问题的规模，因此解子问题会相对容易些。DeepMind提出的NeuralDiving这个算法，是通过机器学习和神经网络，给定一个问题结构，预判如何固定部分整数变量的取值，然后去求解子MIP。
因此，尽管用到了Diving这个词，但是我们认为它还是可以归类为求解子问题的启发式算法。可以看出这个算法在原理上和上述的RINS有诸多相似之处，只是固定变量的方式不同。虽然思路和很多既有启发式算法形式类似，但NeuralDiving还是有它的独特之处。NeuralDiving最大的优势之一，是它可以在正式求解原始问题之前，即生成多组差异化的部分变量取值，启动启发式算法。
我们遇到的实际问题只有数千个整数变量，需要求每隔15分钟求解一次，并且要在15分钟内尽快解完。我们通过深度神经网络等机器学习的方法去预测MIP模型最优解中每个决策变量取1的概率。
从而固定部分置信度最高的变量和对中间置信度的部分变量添加多变量分支的割平面，使得最后的问题可行的概率最高。
这样的方法能够有效减少分支定界树的搜索规模，一方面能够实现快速收敛，另一方面能够快速寻找到高质量的初始解。最后的实验显示，借助该方法在达到相同质量解(Gap=0.01%)的速度提升为5-10倍左右。
其中不乏有原始问题3分钟无法完成求解，而结合使用机器学习算法仅需10秒就能完成求解的时候。这种速度的提升对需要每15分钟都需要快速计算决策的SCUC问题非常重要。电网中的优化也是DeepMind指出的智能化MIP可以重点发力的领域。但是，值得着重指出的是，电网另一个特性就是对于安全性和鲁棒性的极端要求。
而在新问题的数据结构突发巨变，历史数据已经不能指导未来的时候，例如战争，自然或者人为因素导致的发电厂和输电线路的极大变化，机器学习能起到的作用会弱化很多。
这个时候，更多的时候还是依靠MIP求解器自身六个模块那些独立于数据之外的经典算法的实现能力。另一个例子是中国邮政的路由网络规划问题。我们在实践中遇到的此类问题通常需要求解数十万整数变量的MIP来决定发车安排。
如果直接抛给求解器，则往往需要花费一至两个小时才能找到第一个整数解（Gap在30%左右甚至更差）。通过观察，我们发现尽管无法预测全部的发车安排，但是可以预测部分高概率的车辆安排。
我们进而通过机器学习历史数据，形成了一套根据线性约束关系生成数千发车安排的部分初始解的方法。在此基础上，我们通过临时固定这些决策变量，构造子MIP问题，用求解器快速的计算、补全子问题的解。
这个子问题由于部分关键变量确定，使得预求解模块可以对问题规模进行大幅度的削减，促成快速求解。尽管这个子问题的最优解不是原始问题的最优解，但在实践中这个解（Gap在10%之内）明显优于花费一至两小时算出的第一个可行解。
所以无论是分支策略，初始解固定，甚至割平面产生，都可以通过机器学习技术获得，从而加速问题的MIP模型求解。而且也确实有很多学者在这个问题上取得了相对多的进展。
这些技术展示出来的潜力是值得欢呼的，但是在现实中求解MIP问题，需要的数学技巧和工程经验是极其厚重的。传统的MIP求解工具有数十年的理论论证和理论分析基础。