论文标题
用于求解合并优化问题的线性编程松弛的梯度下降程序在大规模上并行模式下
Gradient descent procedure for solving linear programming relaxations of combinatorial optimization problems in parallel mode on extra large scale
论文作者
论文摘要
线性编程（LP）松弛是解决硬组合优化（CO）问题的标准技术。在这里，我们提出了一种梯度下降算法，该算法利用了由CO问题引起的某些LP松弛的特殊结构。该算法可以在并行模式下运行，并作为将在GPU上执行的CUDA C/C ++程序实现。我们通过解决分数2匹配问题来体现算法的效率。我们的结果表明，我们的算法在现代GPU上以一秒钟的比例解决了100,000个节点的分数2匹配问题，而使用单纯形方法解决该问题可能需要一个多小时。可以修改该算法，以解决来自CO问题的更复杂的LP松弛。
Linear programming (LP) relaxation is a standard technique for solving hard combinatorial optimization (CO) problems. Here we present a gradient descent algorithm which exploits the special structure of some LP relaxations induced by CO problems. The algorithm can be run in parallel mode and was implemented as CUDA C/C++ program to be executed on GPU. We exemplify efficiency of the algorithm by solving a fractional 2-matching problem. Our results demonstrate that a fractional 2-matching problem with 100,000 nodes is solved by our algorithm on a modern GPU on a scale of a second while solving the problem with simplex method would take more than an hour. The algorithm can be modified to solve more complicated LP relaxations derived from CO problems.
