GPU-Accelerated Primal Heuristics for Mixed Integer Programming

2025/10/23 by Çördük, Akif, Sielski, Piotr, Boucher, Alice +1 · 1 citation
#Distributed #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2510.20499

Abstract

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.

Citations

• Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization
• Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient
• Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices
• Improving the Randomization Step in Feasibility Pump
• Parallelizing the dual revised simplex method

Cited by

• Activate the Dual Cones: A Tight Reformulation of Conic ACOPF Constraints

Related

• Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization
• Learning Primal Heuristics for Mixed Integer Programs
• GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
• Efficient primal heuristics for mixed-integer linear programs