np-hDeepMind与谷歌又出大招！用神经网络解决NP-hard的MIP问题( 四 )

图 2：论文的主要结果：他们的方法（Neural Branching + Neural Divin）在原问题与对偶问题的差距上与 SCIP 媲美，或优于 SCIP，在留出实例上不相上下。
Tuned SCIP 是他们比较的基线，因为他们使用 SCIP 作为整合学习启发式算法的基础求解器。
作为基础求解器，SCIP 提供了：a) 用于集成学习模型的内部状态的深入访问权限；b) 并行运行大规模求解实例来进行大规模评估的许可授权。
作者表示，他们无法使用具有这些功能的商业求解器，所以它们相当于不可用。他们已经在两个数据集上对 Gurobi 与 Neural Diving 进行了部分比较，其中 Gurobi 作为 sub-MIP 的求解器。对比原始差距在一组保留实例上的平均值，具有并行 sub-MIP 求解的 Neural Diving 在两个数据集上达到 1% 的平均原始间隔比 Gurobi 的时间少 3 倍和 3.6 倍。
他们还将 Neural Diving 的修改版本应用于 MIPLIB 中“开放”实例的子集，以找到三个新的最著名任务来击败商业求解器。一些早期的工作专注于学习原始启发式算法。与它们不同的是，Neural Diving 将预测变量赋值的问题看作生成建模问题提出，提供了一种原则性方法来学习所有可用的可行赋值，并在测试时间内生成部分真值。
一些工作也着眼于学习分支策略。其中，许多都像DeepMind这个团队一样专注于学习模仿 FSB。与它们不同的是，Neural Branching 使用了更可扩展的方法来计算使用 GPU 的目标策略，与基于 CPU 的 FSB 实现相比，这允许它在相同的时间限制内从更大的实例中生成更多的模仿数据。这个工作还超越了早期独立研究学习个体启发式的工作，通过在求解器中结合学习的原始启发式和学习的分支策略，在大规模实际应用数据集和 MIPLIB 上实现了明显更优的性能。

论文贡献
这个工作的主要贡献如下：
1、提出了Neural Diving。这是一种基于学习的新方法，可以为 MIP 生成高质量的联合变量赋值。在同类数据集上，Neural Diving 在留出实例上实现了 1% 的平均原始差距，比 Tuned SCIP 快了 3-10 倍。在一个数据集上，Tuned SCIP 在时限内没能达到 1% 的平均原始差距，而 Neural Diving 做到了。
2、提出了Neural Branching，通过模仿基于 ADMM 的新可扩展专家策略来学习在分支定界算法中使用的分支策略。在评估时所使用的两个数据集上，由于实例规模（如有大于105个变量）或每次的迭代时间很长，FSB很慢，ADMM 专家在相同的运行时间内生成了 1.4 倍和 12 倍训练数据。学习策略在四个数据集上显着优于 SCIP 的分支启发式算法，在大时间限制下的留出实例上平均对偶差距提高了 2-20 倍，并在其他数据集上取得了可媲美的性能。
3、将 Neural Diving 与 Neural Branching 结合起来，在具有最大 MIP 的4个数据集（共有5个数据集）中的平均原始对偶差距上获得了明显比 SCIP 更好的性能，同时在第5个数据集中达到与 SCIP 不相上下的性能。
此外，他们还开源了一个用于神经网络验证的数据集（第 4、12.6 节），希望有助于进一步研究 MIP 的新学习技术。

结论
这项工作证明了机器学习在大规模现实世界应用数据集和 MIPLIB 上能够显着提高 MIP 求解器性能的长期潜力。我们相信，随着模型和算法的进一步改善，这个方法会有更大的改进。
一些在未来有前景的研究方向是：
? 学习切割：使用机器学习更好地选择和生成切割是性能改进的另一个潜在技术。