GPU-Accelerated Primal Heuristics for Mixed Integer Programming
By: Akif Çördük , Piotr Sielski , Alice Boucher and more
Potential Business Impact:
Makes computers solve hard problems much faster.
We introduce a fusion of GPU accelerated primal heuristics for Mixed Integer Programming. Leveraging GPU acceleration enables exploration of larger search regions and faster iterations. A GPU-accelerated PDLP serves as an approximate LP solver, while a new probing cache facilitates rapid roundings and early infeasibility detection. Several state-of-the-art heuristics, including Feasibility Pump, Feasibility Jump, and Fix-and-Propagate, are further accelerated and enhanced. The combined approach of these GPU-driven algorithms yields significant improvements over existing methods, both in the number of feasible solutions and the quality of objectives by achieving 221 feasible solutions and 22% objective gap in the MIPLIB2017 benchmark on a presolved dataset.
Similar Papers
GPU-Accelerated Primal Heuristics for Mixed Integer Programming
Optimization and Control
Solves hard math problems much faster.
Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP
Optimization and Control
Solves math problems much faster.
GPU-Accelerated Optimization Solver for Unit Commitment in Large-Scale Power Grids
Optimization and Control
Powers up the electric grid faster.