近日，顶级国际会议 NeurIPS 的 The Machine Learning for Combinatorial Optimization（以下简称：ML4CO） 组合优化比赛结果揭幕，来自旷视研究院的代表队荣获 Dual Task 赛道冠军。
ML4CO 全称基于机器学习的组合优化，本次比赛由加拿大蒙特利尔理工大学和蒙特利尔大学机器学习研究所 (Mila) 主办。Mila是全球领先的深度学习研究中心，由蒙特利尔大学约书亚·本希奥（Yoshua Bengio）教授创立。约书亚·本希奥也是“深度学习三巨头”之一，曾在2018年夺得ACM图灵奖（又称“计算机领域的诺贝尔奖”）。
组合优化问题介绍
假如我们周末要去跳蚤市场摆摊，最多可以带 15 千克的商品，每个商品有对应的重量和价值，我们该如何选择商品组合，才能使包里的东西总价值最大呢？
因为有 5 件物品，每件物品带还是不带，合起来有 2 的 5 次方，即 32 种选择。从这些选择中找到最优的解，这样的“背包问题”就是一个组合优化问题的典型例子。
一般的情况，把 n 个物品的重量和价值分别记为 W=(w1,w2,...,wn) 和 V=(v1,v2,...,vn)，记背包中放置物品的总重量最大为 wmax。
从组合优化的角度求解这个问题，就是将这个问题转化为求解 X=(x1,x2,...,xi,...,xn)，其中 xi 是一个只能取 0 或 1 的离散变量，代表第 i 个物品取或者不取。
我们希望得到的 X 能满足背包重量 WXT≤Wmax的限制，并最大化背包中物品的总价值 VXT。
得到“背包问题”的数学表达形式后，我们可以使用专业的组合优化问题求解器（例如开源求解器 SCIP）求解上述问题。
组合优化问题的求解在现实生活中同样存在广泛的应用，例如上图中的货物运输问题，我们需要调度货车从中央仓库运输货物到门店，在满足门店需求的限制下使得总运输成本最小。
实际中的组合问题具有搜索空间大（也意味着优化空间大）、混合离散与连续变量等特点。
赛题介绍
（基于深度学习的组合优化）
有很多组合优化是 NP-hard 的，因此使用的一般是一些启发式算法。近年来，伴随着深度学习在多个领域的成功应用，使用深度学习技术，从大量的数据中自主学习启发式算法，辅助甚至替代求解器求解组合优化问题，成为学界研究的一个新的热点。
本次挑战赛的重点是通过机器学习方法替代现有组合优化求解器中的启发式组件，来达到提升现有的组合优化求解器求解性能的目的。
基于开源求解器 SCIP 和它的Python封装 Ecole，本次比赛专门针对组合优化问题中的混合整数线性规划问题 (MILP)进行优化；
主办方提供了三个 MILP 数据集，它们来自完全不同的现实问题，参赛者可以针对这三个数据集提交不同的模型。
其中 Dual Task 赛道研究如何更快收紧 MILP 问题的约束边界，参赛者需要最小化 Dual Integral（如下图所示，最小化积分区域面积），模型效果最后转化为一个累计的奖励函数。
旷视夺冠算法介绍
旷视研究院参赛队针对三个数据集的不同特点，在数据收集，模型结构和训练策略等方面进行改进，最终取得综合排名第一（表中 Nuri 队）。
比赛官方提供的基准算法使用了"Exact combinatorial optimization with graph convolutional neural networks"[1] 中的方法。
在该篇文献中，作者将经典的启发式搜索算法"Strong Branching"[2] 作为专家知识，使用图神经网络模仿专家行为，训练后的神经网络可以替换组合优化求解器中的部分组件，并提升求解器的最终求解性能。
Nuri 队最终提交的模型表现与Baseline在验证集上的对比如下表所示。
"Anonymous" Benchmark
针对基准方法中收集的训练数据和实际与求解器交互得到的测试数据分布不一致的问题，我们使用了数据聚合 (DA) 方法：
数据聚合从一个随机初始化的模型开始，不断让新训练的模型与求解器交互，获得新的训练数据，并对数据进行专家知识标注，通过对模型和数据的不断迭代，最终缩小训练数据和测试数据差异。
我们还修改了基准中图神经网络的卷积方式（CM），并通过添加 Dropout 层的方式避免数据过拟合，最终验证集的提升效果参考下图 (DA 后数字代表模型和数据的交替迭代轮次)。
"Item Placement" Benchmark
对于 Item Placement 数据集，我们同样使用数据聚合的方法，相较于基准算法，表现有一定的提升。
我们进一步对数据聚合训练出的多个模型集成，最终将模型在验证集的表现从 4992 提升至 7562。
如下图所示，我们从验证集中取出一个问题作为示例，在 15 分钟的时间限制内，集成后的模型奖励曲线要比基准模型的奖励曲线上升更快。
更多方法细节将在 NeurIPS 后续活动中公布。
参考文献：
[1] Exact combinatorial optimization with graph convolutional neural networks (NIPS 2019)
[2] Branching rules revisited (Operations Research Letters, 2005)
首发：旷视研究院
专栏文章推荐
欢迎关注旷视研究院极术社区专栏，定期更新最新旷视研究院成果
加入旷视：career@megvii.com
