Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices
- • Currently, domain propagation in state-of-the-art MIP solvers is single thread only. • The paper presents a novel, efficient GPU algorithm to perform domain propagation. • Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. • The algorithm is capable of running entirely on the GPU with no CPU involvement. • We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.
| Author: | Boro Šofranac, Ambros GleixnerORCiD, Sebastian Pokutta |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Parallel Computing |
| Volume: | 109 |
| First Page: | 102874 |
| Year of first publication: | 2022 |
| DOI: | https://doi.org/10.1016/j.parco.2021.102874 |
