{"ID":2851159,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.20499","arxiv_id":"2510.20499","title":"GPU-Accelerated Primal Heuristics for Mixed Integer Programming","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.","short_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 infeasibili...","url_abs":"https://arxiv.org/abs/2510.20499","url_pdf":"https://arxiv.org/pdf/2510.20499v2","authors":"[\"Akif Çördük\",\"Piotr Sielski\",\"Alice Boucher\",\"Kumar Aatish\"]","published":"2025-10-23T12:39:59Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DC\"]","methods":"[\"LoRA\"]","has_code":false}