CHAP: A Hybrid GPU-CPU Heuristic for MIP
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910194733154304 |
|---|---|
| author | Tjusila, Gennesaret Kharistio Hoen, Alexander Kempke, Nils-Christian Mexi, Gioni Berthold, Timo Gleixner, Ambros Koch, Thorsten Pokutta, Sebastian |
| author_facet | Tjusila, Gennesaret Kharistio Hoen, Alexander Kempke, Nils-Christian Mexi, Gioni Berthold, Timo Gleixner, Ambros Koch, Thorsten Pokutta, Sebastian |
| contents | We present CHAP (Coordinating Heuristics Across Platforms) a GPU-CPU-hybrid primal heuristic framework for mixed-integer programming. CHAP adopts a portfolio approach where it coordinates a set of primal heuristics, including Local Search, Fix-and-Propagate, and Feasibility Pump, via a shared solution pool. The solution pool is used to exchange feasible incumbent solutions, LP solutions, along with promising infeasible solution candidates, enabling a more comprehensive exploration of the solution space. On the GPU side, we implement a native tabu search featuring a novel best-shift algorithm built on sort, scan, and reduce primitives, along with specialized kernel designs. We additionally leverage cuPDLPx as an approximate LP solver. On the CPU side, we employ various Fix-and-Propagate strategies, guided by information from the solution pool, complemented by a CPU-based tabu search and a Feasibility Pump. All components operate collaboratively, iteratively repairing and improving candidate solutions maintained in the pool. We evaluate our framework on the 50-instances benchmark from the 2026 Land-Doig MIP Competition under competition constraints, including a five-minute time limit. In these settings, CHAP finds solutions to 47 instances outperforming both Gurobi (44) in default mode and NVIDIA cuOpt (43) in heuristics-only mode. The results demonstrate that coordinated cross-platform portfolios offer a promising direction for the integration of GPU heuristics into modern high-performance MIP solvers. The code will be made available on GitHub. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05086 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | CHAP: A Hybrid GPU-CPU Heuristic for MIP Tjusila, Gennesaret Kharistio Hoen, Alexander Kempke, Nils-Christian Mexi, Gioni Berthold, Timo Gleixner, Ambros Koch, Thorsten Pokutta, Sebastian Optimization and Control 90C59 (Primary) 90C11 (Secondary) We present CHAP (Coordinating Heuristics Across Platforms) a GPU-CPU-hybrid primal heuristic framework for mixed-integer programming. CHAP adopts a portfolio approach where it coordinates a set of primal heuristics, including Local Search, Fix-and-Propagate, and Feasibility Pump, via a shared solution pool. The solution pool is used to exchange feasible incumbent solutions, LP solutions, along with promising infeasible solution candidates, enabling a more comprehensive exploration of the solution space. On the GPU side, we implement a native tabu search featuring a novel best-shift algorithm built on sort, scan, and reduce primitives, along with specialized kernel designs. We additionally leverage cuPDLPx as an approximate LP solver. On the CPU side, we employ various Fix-and-Propagate strategies, guided by information from the solution pool, complemented by a CPU-based tabu search and a Feasibility Pump. All components operate collaboratively, iteratively repairing and improving candidate solutions maintained in the pool. We evaluate our framework on the 50-instances benchmark from the 2026 Land-Doig MIP Competition under competition constraints, including a five-minute time limit. In these settings, CHAP finds solutions to 47 instances outperforming both Gurobi (44) in default mode and NVIDIA cuOpt (43) in heuristics-only mode. The results demonstrate that coordinated cross-platform portfolios offer a promising direction for the integration of GPU heuristics into modern high-performance MIP solvers. The code will be made available on GitHub. |
| title | CHAP: A Hybrid GPU-CPU Heuristic for MIP |
| topic | Optimization and Control 90C59 (Primary) 90C11 (Secondary) |
| url | https://arxiv.org/abs/2605.05086 |