Help Privacy Policy Disclaimer
  Advanced SearchBrowse





FastDOG: Fast Discrete Optimization on GPU


Abbas,  Ahmed
Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society;


Swoboda,  Paul
Computer Vision and Machine Learning, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 775KB

Supplementary Material (public)
There is no public supplementary material available

Abbas, A., & Swoboda, P. (2021). FastDOG: Fast Discrete Optimization on GPU. Retrieved from https://arxiv.org/abs/2111.10270.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B3EA-5
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.