近日，DeepMind和谷歌研究团队联合发布了一个作品，使用神经网络和机器学习方法解决混合整数规划（MIP）问题！论文地址：https://arxiv.org/pdf/2012.13349.pdf在求解现实世界中遇到的大规模混合整数规划（MIP）实例时，MIP求解器依赖于一组复杂的Heuristics，而机器学习可以自动构建使用数据中实例之间的共享结构，从数据中获得更好的启发式方法。在这项工作中，他们将机器学习应用于MIP求解器的两个关键子任务，生成高质量的联合变量分配并缩小该变量分配与最佳分配之间的差距。目标值差距。他们构建了两个相应的基于神经网络的组件，NeuralDiving和NeuralBranching，可用于SCIP等基本MIP求解器。其中，NeuralDiving学习深度神经网络为其整数变量生成多个部分分配，并使用SCIP求解未分配变量得到的较小MIP，以获得高质量的联合分配。而NeuralBranching学习深度神经网络在分支定界中做出变量选择决策，以缩小目标值与小树的差距。这是通过模仿他们提出的FullStrongBranching的新变体来实现的。作者的团队分别在多个真实数据集（包括两个Google生产数据集和MIPLIB）上训练神经网络以进行评估。在所有数据集中，大多数实例在预求解后都有10^3到10^6个变量和约束，明显大于以前的学习方法。在大时间约束下比较求解器与原始问题和对偶问题在一组holdout实例上的平均差距，在具有最大MIP的3个数据集（总共5个数据集）上学习增强SCIP，达到1.5第4个数据集上的x、2和104倍更好的间隙，更快5倍以在第4个数据集上实现10%的间隙，并在第5个数据集上实现可比的SCIP性能性能。据该团队介绍，据我们所知，他们的方法是第一个在大规模实际应用数据集和MIPLIB上都比SCIP取得更大进步的学习方法。1.概念介绍1.1分支限界MIP的常见解决方案是递归构造搜索树，在每个节点分配一些整数，利用每个节点收集的信息最终收敛到最优（或接近最优）分配。.在每一步，我们都必须选择一个叶节点，从中“分支”。在这个节点上，我们可以解决线性规划(LP)松弛问题，将这个节点上的固定变量的范围约束到它们的指定值。这为我们提供了该节点中所有子节点的真实目标值的有效下限。如果这个界限大于已知的可行分配，那么我们可以安全地修剪搜索树的那部分，因为在该节点的子树中不存在原始问题的最优解。如果我们决定扩展这个节点，那么我们必须从该节点的未固定变量集合中选择一个变量作为分支。一旦选择了一个变量，我们就采取分支步骤，将两个子节点添加到当前节点。节点具有选定变量的域，这些域被约束为大于或等于其父节点的LP松弛值的上限。另一个节点将所选变量的域限制为小于或等于其LP松弛值的下限。树被更新并且进程再次开始。该算法称为“分支定界”算法。线性规划是这个过程的主要工作，既要在每个节点处导出双边界，又要为一些更复杂的分支试探法确定分支变量。从理论上讲，搜索树的大小可以随着问题的输入大小呈指数增长，但在很多情况下搜索树可以很小，建议节点选择和变量选择启发式以保持树尽可能小是个好主意尽可能活跃的研究领域。1.2原始启发式原始启发式是一种试图找到可行但不一定是最优的变量分配的方法。任何此类可行的分配都为MIP的最优值提供了有保证的上限。在MIP解决方案期间的任何点发现的任何此类边界称为“原始边界”。原始启发式算法可以独立于分支定界操作，但它们也可以在分支定界树中操作，并尝试从搜索树中的给定节点找到对不固定变量的可行分配。生成较低原始边界的更好的原始启发式允许在分支定界期间修剪更多树。简单舍入是原始启发式的一个例子。另一个例子是潜水，它试图通过以深度优先的方式从给定节点探索搜索树来找到可行的解决方案。1.3Primitive-DualGap在运行分支定界时，我们跟踪全局原始边界（任何可行分配的最小目标值）和全局对偶边界（分支定界树所有叶子的最小对偶边界）。我们可以结合这些来定义一个次优差距：Gap=GlobalPrimitiveBoundary-GlobalDualBoundary构造的差距总是非负的。如果为零，那么我们已经解决了问题，原始边界对应的可行点是最优的，对偶边界是最优性的证明。在实践中，当相对差距（即以某种方式归一化）低于某个与应用程序相关的数量时，我们终止分支定界并生成找到的最佳原始解决方案作为接近最优的解决方案计划。图例：用作神经网络输入的MIP的二分图表示。n个变量的集合{x1,...,xn}和m个约束的集合{δ1,...,δm}形成二分图的两组节点。系数被编码为节点和边缘特征。2.论文简介混合整数规划（MIP）是一类NP难问题。它的目标是在线性约束下最小化线性目标，同时使某些或所有变量为整数值。在容量规划中，resource已经广泛应用于分发、装箱等现实场景。这个方向的大部分研究和工程工作都集中在开发实用的求解器上，例如SCIP、CPLEX、Gurobi和XPress。这些求解器都使用复杂的启发式方法来指导搜索以求解MIP。求解器在特定应用程序上的执行情况在很大程度上取决于求解器的启发式方法与应用程序的匹配程度。在这项工作中，作者的团队展示了机器学习可用于从MIP实例的数据集自动构建有效的启发式算法。当应用程序需要解决具有不同问题参数的同一高级语义问题中的大量实例时，机器学习会派上用场。这项工作中此类“同质”数据集的示例包括：1)优化选择电网中的发电厂以满足需求（O'Neill2017），其中电网拓扑保持不变，同时需求可再生2）解决Google生产中的包装问题system，其中待打包的“items”和“bins”的语义基本保持不变，但它们的大小会根据不同的情况而有所不同。即使是结合了许多语义不同问题的“异构”数据集，例如MIPLIB2017，也可以具有用于学习更好启发式的跨实例结构。现成的MIP求解器无法自动构建启发式方法来利用此结构。在具有挑战性的应用场景中，用户可能会依赖专家手动设计此类启发式方法，或者放弃潜在的大性能改进。机器学习提供了实质性改进的可能性，而无需特定于应用程序的专业知识。这项工作表明，机器学习可以构建针对特定数据集量身定制的启发式方法，其性能明显优于MIP求解器中使用的经典方法，包括最先进的非商业求解器SCIP7.0.1。他们的方法将机器学习应用于MIP求解器的两个关键子任务：a)输出对满足约束的所有变量的赋值（如果存在此类赋值）；b)证明变量分配和最优分配之间的关系。目标值差距范围。这两项任务决定了该方法的主要组成部分，即神经潜水和神经分支（见图1）。图例：我们的方法构建了MIP求解器中使用的两个基于神经网络的组件，即NeuralDiving和NeuralBranching，并将两者结合以获得为特定MIP数据集神经求解器量身定制的神经解决方案。NeuralDiving：该组件找到高质量的联合变量分配。它是原始启发式(Berthold2006)的一个示例，这是一类对高效MIP求解器至关重要的搜索启发式(Berthold2013)。作者的团队训练了一个深度神经网络，以生成馈入MIP的整数变量的多个部分分配。其余未分配的变量定义较小的“子MIP”，使用现成的MIP求解器（例如SCIP）求解以完成分配。如果计算预算允许，可以并行求解子MIP。该模型使用现成的求解器进行训练，以离线收集训练示例，为具有更好目标值的灵活分配提供更高的概率。该模型基于所有可用的可行分配而不是最佳分配进行学习，并且不一定使用最佳分配（因为收集可能非常昂贵）。NeuralBranching：该组件主要用于缩小最佳分配与最佳分配目标值之间的差距。对于整数变量，MIP求解器使用一种称为“分支定界”的树搜索形式来逐渐收紧边界并帮助找到可行的分配。在给定节点上，分支变量的选择是决定搜索效率的关键因素。他们训练了一个深度神经网络策略来模仿专家策略做出的选择。模仿目标是一种著名的启发式算法，称为“完全强分支”(FSB)，已被证明可以生成小型搜索树。虽然对于实际的MIP求解来说计算量太大，但对于离线生成模拟学习数据来说，它仍然可以被认为是一种缓慢且昂贵的单次计算。经过训练后，该神经网络能够在测试时以一小部分计算成本接近专业性能。即使对于离线数据生成，基于CPU的FSB实现在大型MIP上的成本也可能高得令人望而却步。他们使用交替方向乘数法(ADMM)开发了FSB的变体，可以通过在GPU上批量执行所需的计算来扩展到大型MIP。DeepMind和GoogleResearch团队在多个包含大规模MIP的数据集上评估了该方法，包括来自Google生产系统的两个数据集和MIPLIB（异构数据集和标准基准）。所有数据集中的大多数MIP组合集在预求解后都有10^3-10^6个变量和约束，明显大于早期工作（Gasse等人2019，Ding等人2020）。一旦NeuralDiving和NeuralBranching模型在给定的数据集上得到训练，它们就会被集成到SCIP中以形成特定于该数据集的“神经求解器”。SCIP是基线，关键参数分别在每个数据集上通过网格搜索进行调整，他们称之为“TunedSCIP”。比较NeuralSolver和TunedSCIP在原始问题的对偶问题的一组hold-out实例上的平均差距（如图2所示），在最大的4个数据集（共5个数据集）上在他们评估的MIP中，神经求解器在相同的运行时提供了明显更好的视差，或者在更短的时间内提供了相同的视差，同时在第5个数据集上与TunedSCIP的性能相匹配。他们描述说，据他们所知，这是第一项使用机器学习显示比在大规模实际应用程序数据集和MIPLIB上使用SCIP有更大改进的工作。图2：论文的主要结果：他们的方法（NeuralBranching+NeuralDivin）在原问题和对偶问题的差距上与SCIP相当或优于SCIP，在示例设置方面也相当。TunedSCIP是他们比较的基线，因为他们使用SCIP作为集成学习启发式的基础求解器。作为基础求解器，SCIP提供：a）对集成学习模型内部状态的深度访问；b)允许并行运行大规模求解器实例以进行大规模评估。作者声明他们不能使用具有这些功能的商业求解器，因此它们等同于无法使用。他们在两个数据集上将Gurobi与NeuralDiving进行了部分比较，并将Gurobi作为sub-MIP求解器。比较一组留出实例的平均原始差距，使用并行子MIP求解器的神经潜水在两个数据集上实现平均原始差距的1%，所用时间比Gurobi少3倍和3.6倍。他们还将NeuralDiving的修改版本应用于MIPLIB中“开放”实例的子集，以找到三个新的最知名的任务来击败商业求解器。一些早期的工作侧重于学习原始启发式方法。与它们不同，NeuralDiving将预测变量分配问题视为生成建模问题，提供了一种原则性方法来学习所有可用的可行分配并在测试时生成部分真值。一些工作还着眼于学习分支策略。他们中的许多人，比如DeepMind团队，都专注于学习模仿FSB。与它们不同，NeuralBranching使用更具可扩展性的方法来使用GPU计算目标策略，这使其能够生成更多的模仿数据。这项工作还超越了早期关于学习个体启发式的独立工作，通过在求解器中结合学习的原始启发式和学习的分支策略，在大规模实际数据集和MIPLIB上实现了显着更好的性能。3.论文贡献这项工作的主要贡献如下：提出了NeuralDiving。这是一种基于学习的新颖方法，可为MIP生成高质量的联合变量分配。在可比较的数据集上，NeuralDiving在set-out实例上实现了1%的平均原始差距，比TunedSCIP快3-10倍。在一个数据集上，TunedSCIP未能在时限内达到1%的平均原始差距，而NeuralDiving做到了。提出神经分支，通过模仿基于ADMM的新的可扩展专家策略来学习分支定界算法中使用的分支策略。在用于评估的两个数据集上，FSB由于实例大小（例如，具有超过105个变量）或每次迭代的迭代时间非常长而变慢，ADMMExpert在相同的运行时间内生成了1.4倍和12倍。训练数据加倍。所学习的策略在四个数据集上明显优于SCIP的分支启发式算法，在大时间限制下将设置实例的平均对偶性差距提高了2-20倍，并在其他数据集上取得了可比的结果。表现。将NeuralDiving与NeuralBranching相结合，在具有最大MIP的4个数据集（5个数据集中）的平均原始对偶间隙上实现了明显优于SCIP的性能，同时达到了与SCIP相当的性能。此外，他们开源了一个用于神经网络验证的数据集（第4节，12.6），他们希望这将有助于进一步研究MIP的新学习技术。4.结论这项工作证明了机器学习在显着提高MIP求解器在大规模实际应用程序数据集和MIPLIB上的性能的长期潜力。我们相信随着模型和算法的进一步改进，这种方法将会有更大的改进。未来一些有前途的研究方向是：学习削减：使用机器学习更好地选择和生成削减是另一种提高性能的潜在技术。热启动模型：学习模型在MIPLIB上的强大性能表明它可以学习在不同MIP上运行良好的启发式方法。这可以用来克服应用场景中的“冷启动”问题，在应用场景中，早期可用的训练数据量可能太小，无法训练出好的模型。我们可以从使用在异构数据集上训练的模型开始，并在我们为应用程序收集更多数据时将它们用作通往更专业模型的桥梁。强化学习：使用蒸馏或行为克隆获得的性能由现有最好的专家提供，强化学习(RL)可能会超过它。用于高效探索、长期信用分配和学习的计算可扩展性是将RL应用于大规模MIP的关键挑战。解决这些问题可以带来更大的性能改进。本文转载自雷锋网。如需转载，请在雷锋网官网申请授权。
