@online{Abbas_2111.10270,
TITLE = {{FastDOG}: {F}ast Discrete Optimization on {GPU}},
AUTHOR = {Abbas, Ahmed and Swoboda, Paul},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2111.10270},
EPRINT = {2111.10270},
EPRINTTYPE = {arXiv},
YEAR = {2021},
ABSTRACT = {We present a massively parallel Lagrange decomposition method for solving 0-1<br>integer linear programs occurring in structured prediction. We propose a new<br>iterative update scheme for solving the Lagrangean dual and a perturbation<br>technique for decoding primal solutions. For representing subproblems we follow<br>Lange et al. (2021) and use binary decision diagrams (BDDs). Our primal and<br>dual algorithms require little synchronization between subproblems and<br>optimization over BDDs needs only elementary operations without complicated<br>control flow. This allows us to exploit the parallelism offered by GPUs for all<br>components of our method. We present experimental results on combinatorial<br>problems from MAP inference for Markov Random Fields, quadratic assignment and<br>cell tracking for developmental biology. Our highly parallel GPU implementation<br>improves upon the running times of the algorithms from Lange et al. (2021) by<br>up to an order of magnitude. In particular, we come close to or outperform some<br>state-of-the-art specialized heuristics while being problem agnostic.<br>},
}