Skip to main content

Design Considerations for GPU-based Mixed Integer Programming on Parallel Computing Platforms...

by Kalyan S Perumalla, Md Maksudul Alam
Publication Type
Conference Paper
Book Title
Proceedings of the 50th International Conference on Parallel Processing
Publication Date
Conference Name
International Conference on Parallel Processing (ICPP)
Conference Location
Chicago, Illinois, United States of America
Conference Sponsor
Association for Computing Machinery
Conference Date

Mixed Integer Programming (MIP) is a powerful abstraction in combinatorial optimization that finds real-life application across many significant sectors. The recent proliferation of graphical processing unit (GPU)-based accelerated computing architectures in large-scale parallel computing or supercomputing presents new opportunities as well as challenges in the advancement of MIP solver technology to effectively use the new accelerated computing platforms and scale to large parallel systems. Here, we recount the conventional processor-based strategies and focus on configurations where the most promising intersection lies between parallel MIP solver approaches and the specific strengths of accelerated parallel platforms. We note that the best potential lies in solving problems whose individual matrix sizes (of the linear program relaxation) fit entirely within one accelerator's memory and whose branch-and-bound (or branch-and-cut) trees cannot be fully contained within a small number of computational nodes. Additionally, we identify ideal features of computational linear algebra support on GPU accelerators that would help advance this direction of scalable parallel solution of MIP problems on GPU-based accelerated computing architectures.