np-hDeepMind与谷歌又出大招！用神经网络解决NP-hard的MIP问题( 二 )

1.2 原始启发式
原始启发式是一种尝试找到可行但不一定最佳的变量赋值的方法。任何此类可行的赋值都提供了 MIP 最佳值的保证上限。在 MIP 求解期间的任何点找到的任何此类边界都被称为“原始边界”。
原始启发式可以独立于分支定界运行，但它们也可以在分支定界树中运行，并尝试从搜索树中的给定节点找到不固定变量的可行赋值。生成较低原始边界的、更好的原始启发式方法允许在分支定界过程中修剪更多的树。简单的四舍五入就是原始启发式的一个例子。另一个例子是潜水（diving），试图通过深度优先的方式从给定节点中探索搜索树来找到可行的解决方案。
1.3 原始-对偶间隙
在运行分支定界时，我们会跟踪全局原始边界（任何可行分配的最小目标值）和全局对偶边界（分支定界树所有叶子的最小对偶边界）。我们可以结合这些来定义次优间隙（sub-optimality gap）：
间隙=全局原始边界-全局对偶边界
构造的间隙总是非负的。如果它为零，那么我们已经解决了问题，与原始边界对应的可行点是最优的，而对偶边界是最优性的证明。在实践中，当相对间隙（即以某种方式归一化）低于某个依赖于应用的数量时，我们会终止分支定界，并生成最佳的已寻原始解决方案作为近似最优解决方案。

图注：用作神经网络输入的 MIP 的二部图表示。n 个变量的集合 {x1,...,xn} 和 m 个约束的集合 {δ1,...,δm} 形成了二部图的两组节点。系数被编码为节点和边的特征。

论文介绍
【 np-hDeepMind与谷歌又出大招！用神经网络解决NP-hard的MIP问题】混合整数规划 (MIP) 是 NP-hard 问题中的一类，它的目标是在线性约束下将线性目标最小化，同时使部分或全部变量均为整数值，在容量规划、资源分配与装箱等等现实场景中得到了广泛应用。
该方向的大量研究与工程投入都集中在了开发实用求解器上，比如 SCIP、CPLEX、Gurobi 和 Xpress。这些求解器都是使用复杂的启发式算法来指导求解 MIP 的搜索过程。一个求解器在特定应用上的表现主要是取决于该求解器的启发式算法与该应用的匹配程度。
在这篇工作中，作者团队展示了机器学习可用于从 MIP 实例数据集中自动构建有效的启发式算法。当一个应用需要解决具有不同问题参数的同一高级语义问题中的大量实例时，机器学习便派上了用场。
这篇工作中，此类“同质”数据集的例子包括：1）优化选择电网中的发电厂，以满足需求（O'Neill 2017），其中，电网拓扑保持不变，而需求、可再生能源发电等则因情况而异；2) 解决谷歌生产系统中的包装问题，其中，待打包的“物件”（items）和“箱子”（bins）的语义基本保持不变，但它们的尺寸大小会根据不同的情况而有所变化。
即使是结合了许多语义不同的问题的“异构”数据集，比如 MIPLIB 2017，也可以拥有跨实例的结构，用于学习更好的启发式算法。现成的 MIP 求解器无法自动构建启发式算法来利用这种结构。在具有挑战性的应用场景中，用户可能会依赖专家来手动设计此类启发式算法，或放弃潜在的大幅性能改进。机器学习提供了大幅改进的可能性，且无需使用特定应用场景的专业知识。
这篇工作证明了，机器学习可以构建为特定数据集定制的启发式算法，其性能会明显优于在 MIP 求解器中所使用过的经典方法，包括最先进的非商业求解器 SCIP 7.0.1 。