DeepMind 与谷歌又出大招，用神经网络解决 NP-hard 的 MIP 问题

图片地址：https://img.ithome.com/newsuploadfiles/2021/8/2ff05680-2e54-4322-909a-322da7593f89.jpg

近日，DeepMind 与 Google Research 团队共同发布了一项工作，用神经网络与机器学习方法来解决混合整数规划（MIP）问题！论文地址：https://arxiv.org/pdf/2012.13349.pdf在解决现实中遇到的大规模混合整数规划（Mixed Integer Programming, MIP）实例时，MIP 求解器要借助一系列复杂的、经过数十年研究而开发的启发式算法，而机器学习可以使用数据中实例之间的共享结构，从数据中自动构建更好的启发式算法。在这篇工作中，他们将机器学习应用于 MIP 求解器的两个关键子任务，生成了一个高质量的联合变量赋值（joint variable assignment），并缩小了该变量赋值与最优赋值之间的目标值差距。他们构建了两个对应的、基于神经网络的组件，即 Neural Diving 与 Neural Branching，使其可用于基本的 MIP 求解器上，比如 SCIP