CHAP: A Hybrid GPU-CPU Heuristic for MIP

Gennesaret Kharistio Tjusila, Alexander Hoen, Nils-Christian Kempke, Gioni Mexi, Timo Berthold, Ambros Gleixner, Thorsten Koch, Sebastian Pokutta

arXivarxiv/2605.05086May 6, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.05086
curl -X POST /api/v1/records/arxiv/2605.05086/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.05086/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'