用神经网络解决NP-hard的MIP问题
近日，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。
其中，Neural Diving 学习一个深度神经网络，为其整数变量生成多个部分赋值，并用 SCIP 来解决由此产生的未赋值变量的较小 MIP，以得到高质量的联合赋值。而 Neural Branching 学习一个深度神经网络，在分支定界中进行变量选择决策，以用一棵小树来缩小目标值的差距。这是通过模仿他们所提出的 Full Strong Branching（全强分支）的新变量来实现。
作者团队将神经网络在多个真实世界的数据集（包括两个谷歌生产数据集和 MIPLIB）上分别进行了训练，以进行评估。在所有数据集中，大多数实例在预求解后都有 10^3 至 10^6 个变量和约束，明显大于以前的学习方法。
对比求解器与大时间限制下原问题与对偶问题在一组留出（hold-out）实例上的差距平均值，学习增强的 SCIP 在3个具有最大 MIP 的数据集（一共有5个数据集）上实现了 1.5x、2x 和 104x 的更好差距，在第4个数据集上以5x的速度更快实现 10% 的差距，并在第5个数据集上取得了与 SCIP 不相上下的表现。
该团队介绍，据了解，他们的方法是第一个在大规模现实世界应用数据集和 MIPLIB 上都展示了比 SCIP 有更大进步的学习方法。
概念简介
1.1 分支定界
常见的解决 MIP 过程是递归地构建搜索树，在每个节点处分配部分整数，并使用每个节点所收集的信息最终收敛于最佳（或接近最佳）分配。在每一步，我们都必须选择一个叶子节点，从中“分支”。在这个节点上，我们可以解决线性规划（LP）松弛问题，将在该节点上的固定变量的范围限制为它们的指定值。这为我们提供了该节点中所有子节点的真实目标值的有效下限。
如果这个界限大于已知的可行分配，那么我们就可以安全地修剪搜索树的这一部分，因为该节点的子树中不存在原问题的最优解。如果我们决定扩展这个节点，那么我们必须从该节点的一组未固定变量中选择一个变量作为分支。一旦选择了一个变量，我们就采取分支步骤，将两个子节点添加到当前节点。一个节点有选定变量的域，该域会被约束为大于或等于其父节点处的 LP 松弛值的上限。另一个节点将所选变量的域约束为小于或等于其 LP 松弛值的下限。树被更新，过程再次开始。
这个算法被称为“分支定界”（branch-and-bound）算法。线性规划是这个过程的主要工作，既可以在每个节点上导出对偶边界，又可以为一些更复杂的分支启发式算法确定分支变量。理论上，搜索树的大小可以随着问题的输入大小呈指数增长，但在许多情况下，搜索树可能很小，并且是一个提出节点选择和变量选择启发式算法来使树尽可能保持小的活跃研究领域。
1.2 原始启发式
原始启发式是一种尝试找到可行但不一定最佳的变量赋值的方法。任何此类可行的赋值都提供了 MIP 最佳值的保证上限。在 MIP 求解期间的任何点找到的任何此类边界都被称为“原始边界”。
原始启发式可以独立于分支定界运行，但它们也可以在分支定界树中运行，并尝试从搜索树中的给定节点找到不固定变量的可行赋值。生成较低原始边界的、更好的原始启发式方法允许在分支定界过程中修剪更多的树。简单的四舍五入就是原始启发式的一个例子。另一个例子是潜水（diving），试图通过深度优先的方式从给定节点中探索搜索树来找到可行的解决方案。
1.3 原始-对偶间隙
在运行分支定界时，我们会跟踪全局原始边界（任何可行分配的最小目标值）和全局对偶边界（分支定界树所有叶子的最小对偶边界）。我们可以结合这些来定义次优间隙（sub-optimality gap）：
间隙=全局原始边界-全局对偶边界
构造的间隙总是非负的。如果它为零，那么我们已经解决了问题，与原始边界对应的可行点是最优的，而对偶边界是最优性的证明。在实践中，当相对间隙（即以某种方式归一化）低于某个依赖于应用的数量时，我们会终止分支定界，并生成最佳的已寻原始解决方案作为近似最优解决方案。
图注：用作神经网络输入的 MIP 的二部图表示。n 个变量的集合 {x1,...,xn} 和 m 个约束的集合 {δ1,...,δm} 形成了二部图的两组节点。系数被编码为节点和边的特征。
论文介绍
混合整数规划 (MIP) 是 NP-hard 问题中的一类，它的目标是在线性约束下将线性目标最小化，同时使部分或全部变量均为整数值，在容量规划、资源分配与装箱等等现实场景中得到了广泛应用。
该方向的大量研究与工程投入都集中在了开发实用求解器上，比如 SCIP、CPLEX、Gurobi 和 Xpress。这些求解器都是使用复杂的启发式算法来指导求解 MIP 的搜索过程。一个求解器在特定应用上的表现主要是取决于该求解器的启发式算法与该应用的匹配程度。
在这篇工作中，作者团队展示了机器学习可用于从 MIP 实例数据集中自动构建有效的启发式算法。当一个应用需要解决具有不同问题参数的同一高级语义问题中的大量实例时，机器学习便派上了用场。
这篇工作中，此类“同质”数据集的例子包括：1）优化选择电网中的发电厂，以满足需求（O'Neill 2017），其中，电网拓扑保持不变，而需求、可再生能源发电等则因情况而异；2) 解决谷歌生产系统中的包装问题，其中，待打包的“物件”（items）和“箱子”（bins）的语义基本保持不变，但它们的尺寸大小会根据不同的情况而有所变化。
即使是结合了许多语义不同的问题的“异构”数据集，比如 MIPLIB 2017，也可以拥有跨实例的结构，用于学习更好的启发式算法。现成的 MIP 求解器无法自动构建启发式算法来利用这种结构。在具有挑战性的应用场景中，用户可能会依赖专家来手动设计此类启发式算法，或放弃潜在的大幅性能改进。机器学习提供了大幅改进的可能性，且无需使用特定应用场景的专业知识。
这篇工作证明了，机器学习可以构建为特定数据集定制的启发式算法，其性能会明显优于在 MIP 求解器中所使用过的经典方法，包括最先进的非商业求解器 SCIP 7.0.1 。
他们的方法将机器学习应用于 MIP 求解器的两个关键子任务：a) 输出能满足约束条件的所有变量的赋值（如果存在这样的赋值）；b）证明变量赋值与最优赋值之间的目标值差距范围。这两个任务决定了该方法的主要组件，即 Neural Diving 与 Neural Branching（见图1）。
图注：我们的方法构建了两个在 MIP 求解器中使用、基于神经网络的组件，即 Neural Diving 与 Neural Branching，并将两者结合，得到了一个为特定 MIP 数据集量身定做的神经求解器（Neural Solver）。
Neural Diving：该组件可找到高质量的联合变量赋值。它是原始启发式算法 (Berthold 2006) 的一个示例，而原始启发式是一类对有效 MIP 求解器十分关键的搜索启发式算法 (Berthold 2013)。
作者团队训练一个深度神经网络来生成输入 MIP 的整数变量的多个部分真值（partial assignments）。其余未赋值的变量定义了较小的“sub-MIPs”，它们是用现成的 MIP 求解器（例如 SCIP）求解来完成赋值。如果计算预算允许，sub-MIPs 可以并行求解。模型经过训练，使用现成求解器离线收集的训练示例，为灵活的、拥有更优目标值的赋值提供更高的概率。模型是基于所有可用的可行赋值而不是最优赋值来进行学习，且不一定要用到最优赋值（因为收集的成本可能非常昂贵）。
Neural Branching：该组件主要用于缩小最好赋值与最优赋值的目标值之间的差距。
在整数变量上，MIP 求解器使用了一种树搜索的形式，即“分支定界”，逐渐收紧边界并帮助寻找可行的赋值。在给定节点上，分支变量的选择是决定搜索效率的关键因素。
他们训练了一个深度神经网络策略来模仿专家策略所做出的选择。模仿目标是一个著名的启发式算法，称为“全强分支”（FSB），实践已证明，FSB 可以生成小型搜索树。虽然对实际的 MIP 求解来说，它的计算成本往往过高，但它仍可以被当成一种缓慢且昂贵的一次性计算，用于离线生成模仿学习数据。一旦经过训练，这个神经网络就能够在测试时以一小部分计算成本来接近专业表现。即使是在离线数据的生成上，基于 CPU 的 FSB 实现在大规模 MIP 上也可能过于昂贵。他们用交替方向乘子法 (ADMM) 开发了 FSB 的变体，可以通过在 GPU 上以批处理方式执行所需的计算来扩展到大规模 MIP。
DeepMind与Google Research的团队在许多包含大规模 MIP 的数据集上对这个方法进行了评估，包括来自 Google 生产系统的两个数据集，以及 MIPLIB（一个异构数据集和标准基准）。
来自所有数据集的大多数 MIP 组合集在预求解后都有 10^3-10^6 个变量和约束，明显大于早期工作（Gasse et al. 2019, Ding et al. 2020）。一旦 Neural Diving 与 Neural Branching 模型在给定数据集上进行了训练，它们会被整合到 SCIP 中，形成专门针对该数据集的“神经求解器”（Neural Solver）。SCIP是基线，重点参数分别在每个数据集上经过网格搜索进行调整，他们将其称为“Tuned SCIP”。
比较 Neural Solver 和 Tuned SCIP 在一组hold-out实例上原问题对偶问题的差距平均值 (如图2)，在他们所评估的、具有最大 MIP 的4个数据集（一共有5个数据集）上，神经求解器（Neural Solver）在相同的运行时间内提供了明显更好的差距，或在更少时间内提供了相同的差距，同时在第5个数据集上媲美 Tuned SCIP 的表现。他们介绍，据他们所知，这是第一项在大规模现实世界应用数据集和 MIPLIB 上，使用机器学习比使用 SCIP 具有更大改进的工作。
图 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 求解器性能的长期潜力。我们相信，随着模型和算法的进一步改善，这个方法会有更大的改进。
一些在未来有前景的研究方向是：
· 学习切割：使用机器学习更好地选择和生成切割是性能改进的另一个潜在技术。
· 热启动模型：学习模型在 MIPLIB 上的强劲表现表明，它可以学习在不同 MIP 中都能很好地工作的启发式方法。这可用于克服应用场景中的“冷启动”问题，即应用中早期可用的训练数据量可能太少而无法训练好的模型。我们可以从使用在异构数据集上训练的模型开始，并在为应用收集更多数据时，将它们用作通往更专业模型的桥梁。
· 强化学习：使用蒸馏或行为克隆获得的性能是由现有的最佳专家提供，而强化学习 (RL) 可能会超过它。高效探索、长期信用分配和学习的计算可扩展性是将 RL 应用于大规模 MIP 的关键挑战。解决这些问题可以带来更大的性能改进。
参考链接：
https://twitter.com/DeepMind/status/1419642398553120772