FastDOG: Fast Discrete Optimization on GPU
This work addresses the need for faster discrete optimization in fields like computer vision and biology, though it is incremental as it builds on existing methods like binary decision diagrams.
The authors tackled the problem of solving 0-1 integer linear programs in structured prediction by developing a massively parallel Lagrange decomposition method with a new iterative update scheme and perturbation technique, resulting in a GPU implementation that improves running times by up to an order of magnitude compared to prior work and competes with specialized heuristics.
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 https://github.com/LPMP/BDD.