『』组合求解器 + 深度学习 =？这篇ICLR 2020论文告诉你答案( 三 )

求解器输出匹配中所选边的指示向量。右侧的匹配损失为 348（水平为 46 + 12 ，垂直为 27 + 45 + 40 + 67 + 78 + 33）。
同样，在以下性能对比图中，我们注意到在神经网络中嵌入真正的完美匹配求解器带来了明显的优势。
我们还研究了一个旅行商问题，其中网络应该输出各个国家首都的最佳 TSP 旅行线路。对于该问题，重要的是学习正确的首都位置隐表示。我们的数据集由国旗（即原始表示）和对应首都的最优旅行线路组成。一个训练示例包含 k 个国家。在这种情况下，将各个国家的国旗输入卷积神经网络，然后网络输出最优旅行线路。
在下面的动画中，我们可以看到训练期间学习到的各个国家首都在地球上的位置。最初，位置是随机分散的，但是在训练后，神经网络不仅学习输出了正确的 TSP 线路，还学习到了正确的表示，即各个首都正确的三维坐标。值得注意的是，这仅仅是通过在监督训练过程中使用 Hamming 距离损失，以及对网络输出使用 Gurobi 中的 MIP 实现的。
总结
实验证明，事实上，在某些关于求解器损失函数的假设下，可以通过黑盒组合求解器传播梯度。这使得我们获得基于传统有监督方法的标准神经网络架构无法实现的组合泛化能力。
我们正在尝试说明，该方法在解决需要组合推理能力的现实问题中有着广泛的应用。我们已经给出了一种针对排名度量优化的应用 [2] 。然而，问题在于（无论从理论还是实践上）我们可以沿着求解器损失的线性假设这一方向走多远。未来工作的另一个问题是，我们能否学习到组合问题的底层约束，例如 MIP 组合问题。
参考文献
[1] Vlastelica, Marin, et al.「Differentiation of Blackbox Combinatorial Solvers arXiv preprint arXiv:1912.02175 (2019).
[2]Rolínek, Michal, et al.「Optimizing Rank-based Metrics with Blackbox Differentiation.」arXiv preprint arXiv:1912.03500 (2019).
https://towardsdatascience.com/the-fusion-of-deep-learning-and-combinatorics-4d0112a74fa7