# FastDOG: Fast Discrete Optimization on GPU

arXiv: https://arxiv.org/abs/2111.10270 · HTML: https://mlsanity.com/paper/2111.10270/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 64 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 19 of 19)

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching](https://mlsanity.com/paper/1612.05476/) (2016)
- [Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths](https://mlsanity.com/paper/2108.10606/) (2021)
- [A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems](https://mlsanity.com/paper/1404.0533/) (2014)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Message Passing Algorithm for the Minimum Cost Multicut Problem](https://mlsanity.com/paper/1612.05441/) (2016)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [A New Look at BDDs for Pseudo-Boolean Constraints](https://mlsanity.com/paper/1401.5860/) (2014)
- [Taxonomy of Dual Block-Coordinate Ascent Methods for Discrete Energy Minimization](https://mlsanity.com/paper/2004.07715/) (2020)
- [Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams](https://mlsanity.com/paper/2009.00481/) (2020)
- [Solving Dense Image Matching in Real-Time using Discrete-Continuous Optimization](https://mlsanity.com/paper/1601.06274/) (2016)
- [A Primal-Dual Solver for Large-Scale Tracking-by-Assignment](https://mlsanity.com/paper/2004.06375/) (2020)
- [Improved Job sequencing Bounds from Decision Diagrams](https://mlsanity.com/paper/1908.07076/) (2019)
- [Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices](https://mlsanity.com/paper/2009.07785/) (2020)

## Built on by (most cited first, 8 of 8)

- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [DiscoMatch: Fast Discrete Optimisation for Geometrically Consistent 3D Shape Matching](https://mlsanity.com/paper/2310.08230/) (2023)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [Structured Prediction Problem Archive](https://mlsanity.com/paper/2202.03574/) (2022)
- [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023)
- [Convergence of Some Convex Message Passing Algorithms to a Fixed Point](https://mlsanity.com/paper/2403.07004/) (2024)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [MesonGS++: Post-training Compression of 3D Gaussian Splatting with Hyperparameter Searching](https://mlsanity.com/paper/2604.26799/) (2026)

## Abstract (arXiv)

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.