论文解读者：史铭伟，胡明杰，赵田田，陈宇文
编者按：
深度学习近十年的飞速发展带动了各行各业对于数据驱动的研究热潮，运筹学也不例外。本文将展开讨论Deepmind于2020年发表的有关深度学习对混合整数模型加速方法性能的提升。
论文信息：Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols. Solving Mixed Integer Programs Using Neural Networks, arXiv,2020
传统的混合整数规划中通常是基于分支定界法（branch and bound），通过不断求解连续凸松弛问题找出最优解，但是理论上需要求解的松弛问题个数随着整数变量维度上升呈指数倍数增长。因此，实际中我们会添加许多加速方法去减少需要求解的松弛问题数量，其中有很多加速方法的效果取决于混合整数规划的问题结构或是当前分支定界已有的信息，但是很多时候由于模型过于复杂，我们可能无法直接提取出这类信息，而这正好是深度学习方法的优势，它能基于充足的数据通过黑盒优化提供一个预测模型，捕捉我们一些我们难以解释的有效信息。本文介绍了Deepmind于2020年发表的有关深度学习在运筹优化中的运用[1]。论文核心是使用神经网络提升传统混合整数规划中两种常见的启发式方法的性能：下潜（Diving）搜索和分支（branching）选取。其主要思想还是利用神经网络基于数据的预测能力对某一类特定问题求解实现加速。
传统混合整数规划中的下潜和分支方法
结合神经网络的下潜和分支方法
在本篇论文中，作者将学习的方法引入下潜和分支方法选取的优化，我们分别称之为neural diving和neural branching。
1. Neural diving
图1 MIP的二分图表示用于神经网络的输入
接着我们可以将之前混合整数规划的二分图作为输入，将它递交给图卷积神经网络进行分类监督学习。如图二所示。对于图神经网络来说，将约束条件和约束目标对应的节点当成输入，图卷积神经网络对二分图每个节点所连的边进行卷积操作,这样就可以方便抽取特征。最后将抽取特征的矩阵作为输入送入到多层感知机，我们就可以进行分类预测了。因为分类的标签有多个结果，所以每个二分图的节点输出满足伯努利分布。具体实现细节可以参考论文第6部分[1]。
图2 MIP二分图，图神经网络，条件独立模型之间的转化
2. Neural Branching
分支变量的选择是影响分支定界算法效率的关键因素。高质量的分支变量能够有效减少分支定界算法的迭代次数。强分支（FBS）策略在实践中具有较好的性能，相比于其他分支策略，构建的分支搜索树的规模往往更小。每次搜索时，FBS通过模拟所有候选变量的一步分支结果，并选择bound提升效果最好的变量进行分支。然而，实际中FBS每步的计算成本是非常高昂的。我们可以通过神经网络模仿学习（ Imitation Learning）启发式策略（专家策略）。通过将计算成本高昂的专家策略蒸馏至神经网络，我们可以在近似保留解的质量的前提下大幅减少计算时长。更重要的是，在一个给定节点的分支变量决策只需要节点的局部信息，网络只需要输入节点的相关特征，这使得该方法具有很好的可扩展性。计算成本高昂的专家策略被用来在离散状态下一次性生成训练数据。即使如此，由于FBS过高的计算成本，离线数据生成也非常困难 ，论文提出了来加速专家策略，通过在一个批次中同时处理多个LP来加速求解。
对于模仿学习，论文考虑了三种变形：专家策略克隆（expert policy cloning)，随机移动蒸馏（distillation with random moves）以及DAgger。蒸馏是最简单的方式，在每个节点预测专家策略的输出。然而，这种方法对于分布偏移（distribution drift）不够鲁棒。当根节点发生错误时，可能导致后续节点与训练看到的节点完全不同。为了解决上述问题，可以在训练过程中结合随机移动与专家策略，在运行专家策略的同时以10%的概率随机采取一个动作。DAgger将随机移动蒸馏和专家输入相结合，用作学习的目标。这会产生一步DAgger数据，可以利用其重新训练智能体。
在实验中，作者将三种模仿学习变体的选择视为超参，为每个数据集生成数据，使用所有三种变体策略进行训练并根据三小时内在验证集上的表现选出最优策略。具体实现细节可以参考论文第7部分[1]。
数值实验结果
为了验证本文的方法在实例求解中具有一定的优越性，作者团队进行了数值实验。
他们将神经网络在这些数据集上分别进行了训练，然后使用学习增强的SCIP算法求解测试集。对照的标准是调优的SCIP算法（本质是SCIP算法；通过在每个数据集上分别进行网格搜索，来调整算法中的参数）。他们设定一个较大的时间限制，并在该时间范围内分别使用两种算法处理同一组实例，然后比较它们在某一时刻对应求解结果的平均对偶间隙。实验结果如下图所示。
图3. 本文方法和原始SCIP算法：在不同运行时间下的平均对偶间隙
在评估结果中，学习增强的SCIP算法在四个数据集上都有明显的加速效果：在相同的运行时间内，它计算的结果具有更小的间隙；或者说，它需要更少的时间达到相同的间隙。具体地，对于其中三个数据集，它获得了1.5倍, 2倍 和1万倍更好的效果；对于第四个数据集（Google Production Packing），它能够以原始算法5倍的速度让平均对偶间隙下降到0.1。而对于第五个数据集，它取得了和调优SCIP不相上下的结果。
可以看出，对于大规模的现实世界应用数据集和MIPLIB，本文的方法都取得了优于SCIP的结果。在这项工作之前，还没有哪一种方法能够在这些数值实验中取得如此程度的优势。但是，这里有两点值得注意：
• 一个是比较的标准。某一时刻所对应平均对偶间隙的大小，并不是求解器性能的主要衡量标准。根据目前公认的测试标准，一般是给定最大求解时间，考虑求解器在某一个数据集上能按时求解的问题数量，以及它们的平均求解时间。因此，文中的数据结果可能放大了算法的优势。
• 另一个是数据集的选取。实际上，只有MIPLIB包含了来自不同应用场景的例子。而对于其他的四个数据集，它们的实例都分别来自于同一应用背景。对于这四个数据集而言，它们在训练时给算法输送的是大量的同类问题，而机器学习的优势正在于提取同类问题的特征结构，因此算法能在测试集上取得好的结果，我们并不感到意外。MIPLIB也有相同的缺点。尽管例子来自不同背景，但是对于测试集中的问题，我们也总能在训练集中找到结构相似的实例。因此，本文提出的方法未必具有很强的泛化能力。
尽管数值实验的结果并不完美，但我们可以肯定，本文的方法对于特定结构的问题求解有着一定的加速效果。事实上，也有其他一些文章尝试利用深度学习算法加速整数规划的求解。Morabit M et al. (2021) 提出了利用神经网络加速列生成算法。该算法通过学习一个神经网络，在每步迭代时，从一组列集合中预测出最佳的列加入列生成的主问题，从而加速列生成算法的收敛。文章证明该算法在VRP问题实例上使得计算时长提高了30%[3]。
参考文献
[1] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols. Solving Mixed Integer Programs Using Neural Networks, arXiv,2020
[2] “DeepMind 激起千层浪的神经网络求解 MIP 论文，并非无所不能”, https://www.ithome.com/0/569/302.htm
[3] Morabit M, Desaulniers G, Lodi A. Machine-learning–based column selection for column generation. Transportation Science, 2021, 55(4): 815-831.