Accelerating domain propagation: An efficient GPU-parallel algorithm over sparse matrices

center dot Currently, domain propagation in state-of-the-art MIP solvers is single thread only. center dot The paper presents a novel, efficient GPU algorithm to perform domain propagation. center dot Challenges are dynamic algorithmic behavior, dependency structures, sparsity patterns. center dot The algorithm is capable of running entirely on the GPU with no CPU involvement. center dot We achieve speed-ups of around 10x to 20x, up to 180x on favorably-large instances.

Automated summary

The paper presents a novel, efficient GPU algorithm for domain propagation in state-of-the-art MIP solvers, achieving speed-ups of around 10x to 20x, up to 180x on favorably-large instances. Challenges include dynamic algorithmic behavior, dependency structures, and sparsity patterns. The algorithm can run entirely on the GPU with no CPU involvement.