We present a massively parallel Lagrange decomposition method for solving
0--1 integer linear programs occurring in structured prediction. We propose a
new iterative update scheme for solving the Lagrangean dual and a perturbation
technique for decoding primal solutions. For representing subproblems we follow
Lange et al. (2021) and use binary decision diagrams (BDDs). Our primal and
dual algorithms require little synchronization between subproblems and
optimization over BDDs needs only elementary operations without complicated
control flow. This allows us to exploit the parallelism offered by GPUs for all
components of our method. We present experimental results on combinatorial
problems from MAP inference for Markov Random Fields, quadratic assignment and
cell tracking for developmental biology. Our highly parallel GPU implementation
improves upon the running times of the algorithms from Lange et al. (2021) by
up to an order of magnitude. In particular, we come close to or outperform some
state-of-the-art specialized heuristics while being problem agnostic. Our
implementation is available at this https URL

本文提出一种基于广泛并行的拉格朗日分解方法，用于解决出现在结构化预测中的 0-1 整数线性规划问题。通过使用二叉决策图对子问题进行表示，我们的 GPU 实现改进了 Lange 等人 (2021) 算法的运行时间。