论文标题
Doge-Train：通过端到端培训对GPU进行离散优化
DOGE-Train: Discrete Optimization on GPU with End-to-end Training
论文作者
论文摘要
我们提出了一种快速，可扩展，数据驱动的方法，用于解决0-1整数线性程序的放松。我们使用图形神经网络（GNN）和基于拉格朗日分解的算法快速狗（Abbas和Swoboda 2022b）的组合。我们可以使后者进行端到端培训，并使用GNN来预测其算法参数。这允许保留该算法的理论属性，包括双重可行性和通过训练改进下限的下限中的非折扣。我们通过维持双重可行性的其他非参数GNN更新步骤来克服基本求解器的次优固定点。对于培训，我们使用无监督的损失。我们对较小的问题进行训练，并对较大的问题进行测试，显示出强大的概括性能，而GNN仅包含$ 100K $的参数。我们的求解器的性能要比其非学习版本要快得多，并且双重目标更高，这几乎接近了非常大的结构化预测问题和选定组合的LP松弛的最佳目标值。特别是，在保留其效率的同时，我们比专门的近似求解器获得更好的客观值。与商业求解器相比，我们的求解器在较大时间内的任何时间都更好。代码可在https://github.com/lpmp/bdd上找到
We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG (Abbas and Swoboda 2022b). We make the latter differentiable for end-to-end training and use GNNs to predict its algorithmic parameters. This allows to retain the algorithm's theoretical properties including dual feasibility and guaranteed non-decrease in the lower bound while improving it via training. We overcome suboptimal fixed points of the basic solver by additional non-parametric GNN update steps maintaining dual feasibility. For training we use an unsupervised loss. We train on smaller problems and test on larger ones showing strong generalization performance with a GNN comprising only around $10k$ parameters. Our solver achieves significantly faster performance and better dual objectives than its non-learned version, achieving close to optimal objective values of LP relaxations of very large structured prediction problems and on selected combinatorial ones. In particular, we achieve better objective values than specialized approximate solvers for specific problem classes while retaining their efficiency. Our solver has better any-time performance over a large time period compared to a commercial solver. Code available at https://github.com/LPMP/BDD
