论文标题
使用神经网络解决混合整数程序
Solving Mixed Integer Programs Using Neural Networks
论文作者
论文摘要
混合整数编程（MIP）求解器依赖于数十年研究的一系列复杂的启发式方法来解决实践中遇到的大规模MIP实例。机器学习提供了通过在数据中的实例中利用共享结构来自动从数据中自动构建启发式方法。本文将学习应用于MIP求解器的两个关键子任务，生成高质量的关节变量分配，并在该分配和最佳距离之间界定客观值的差距。我们的方法构建了两个相应的基于神经网络的组件，即神经潜水和神经分支，用于用于基本MIP求解器（例如SCIP）。神经潜水学会了深层神经网络，以生成其整数变量的多个部分分配，并且使用SCIP求解了未分配变量的较小MIP，以构建高质量的关节分配。神经分支学习了一个深层神经网络，以在分支和结合的情况下做出可变的选择决策，以将客观值差距与一棵小树联系起来。这是通过模仿完整强大分支的新变体来完成的，我们建议使用GPU缩放到大型实例。我们通过训练每个神经网络的单独的神经网络，评估六个不同的现实世界数据集（包括两个Google生产数据集和Miplib）的方法。所有数据集中的大多数实例总和都具有$ 10^3-10^6 $变量和限制，这比以前的学习方法大得多。将求解器相对于一组持有的实例进行比较，在所有数据集上，学习效果的SCIP在所有数据集上都更好2倍至10倍，除了一个$ 10^5 $ x更好的时间限制。据我们所知，我们的第一种学习方法是在大型现实世界应用程序数据集和Miplib上证明对SCIP进行如此大的改进。
Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among instances in the data. This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. Neural Diving learns a deep neural network to generate multiple partial assignments for its integer variables, and the resulting smaller MIPs for un-assigned variables are solved with SCIP to construct high quality joint assignments. Neural Branching learns a deep neural network to make variable selection decisions in branch-and-bound to bound the objective value gap with a small tree. This is done by imitating a new variant of Full Strong Branching we propose that scales to large instances using GPUs. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each. Most instances in all the datasets combined have $10^3-10^6$ variables and constraints after presolve, which is significantly larger than previous learning approaches. Comparing solvers with respect to primal-dual gap averaged over a held-out set of instances, the learning-augmented SCIP is 2x to 10x better on all datasets except one on which it is $10^5$x better, at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.
