Journal
PARALLEL COMPUTING
Volume 109, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.parco.2021.102874
Keywords
Mixed integer linear programming; MIP; GPU; Domain propagation; Bound tightening; Parallel algorithms
Categories
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available