pith. machine review for the scientific record. sign in

arxiv: 2605.05086 · v1 · submitted 2026-05-06 · 🧮 math.OC

Recognition: unknown

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
Authors on Pith no claims yet

Pith reviewed 2026-05-08 17:06 UTC · model grok-4.3

classification 🧮 math.OC
keywords mixed-integer programmingprimal heuristicsGPU-CPU hybridsolution pooltabu searchfix-and-propagatefeasibility pump
0
0 comments X

The pith

CHAP coordinates GPU and CPU heuristics via a shared solution pool to find feasible solutions for 47 of 50 MIP instances in five minutes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents CHAP as a portfolio framework that runs primal heuristics on both GPU and CPU platforms while exchanging information through one common pool of solutions. This pool passes feasible incumbents, LP solutions, and promising infeasible candidates among Local Search, Fix-and-Propagate, Feasibility Pump, and tabu search components so that each can repair or improve what the others have found. On the GPU side the framework adds a native tabu search built from sort-scan-reduce primitives and an approximate LP solver; on the CPU side it adds multiple Fix-and-Propagate variants and a Feasibility Pump. The authors evaluate the system on the 50-instance 2026 Land-Doig benchmark under a strict five-minute limit and report 47 solved instances, exceeding both Gurobi in default mode and cuOpt in heuristics-only mode. A sympathetic reader cares because finding any feasible solution quickly remains a bottleneck in large-scale mixed-integer optimization, and the result suggests that cross-platform coordination can enlarge the set of instances that become tractable within tight time bounds.

Core claim

CHAP adopts a portfolio approach where a set of primal heuristics, including Local Search, Fix-and-Propagate, and Feasibility Pump, are coordinated via a shared solution pool that exchanges feasible incumbent solutions, LP solutions, and promising infeasible candidates. On the GPU it implements a native tabu search with a best-shift algorithm using sort, scan, and reduce primitives together with specialized kernels and cuPDLPx as an approximate LP solver; on the CPU it runs Fix-and-Propagate strategies guided by pool information, a CPU tabu search, and a Feasibility Pump. All components operate collaboratively and iteratively repair and improve candidate solutions. On the 50-instance 2026-LD

What carries the argument

The shared solution pool that exchanges feasible incumbents, LP solutions, and infeasible candidates among GPU and CPU heuristics so each can build on the others' progress.

If this is right

  • Coordinated cross-platform portfolios provide a practical route for integrating GPU-based heuristics into existing high-performance MIP solvers.
  • Iterative exchange of candidate solutions between platforms enlarges the portion of the search space that can be explored within a fixed time budget.
  • Specialized GPU kernels for tabu search and approximate LP solving can be combined with established CPU heuristics without requiring a complete rewrite of the solver.
  • The portfolio design allows new GPU or CPU heuristics to be added by connecting them to the same solution pool.
  • Under competition-style five-minute limits the hybrid approach solves more instances than either a commercial MIP solver in default mode or a GPU heuristic set running alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the coordination mechanism proves robust, similar shared pools could be tested on other combinatorial problems that already have separate CPU and GPU solvers.
  • The framework leaves open the possibility of replacing the approximate LP solver with an exact one or adding branching decisions that use pool information.
  • Performance on the Land-Doig set does not yet indicate how the method scales when instance size or number of constraints grows by an order of magnitude.
  • A direct ablation that disables only the pool while keeping all heuristics running would isolate the coordination benefit more cleanly than the current comparison.

Load-bearing premise

The observed performance gain arises from genuine synergy produced by the shared pool and cross-platform coordination rather than from simply executing several independent heuristics whose separate coverage happens to be larger on this benchmark.

What would settle it

Measure the number of instances solved when each GPU and CPU heuristic runs in isolation without the shared pool and compare that total coverage directly against the 47 instances solved by the coordinated CHAP system on the same 50-instance benchmark and time limit.

Figures

Figures reproduced from arXiv: 2605.05086 by Alexander Hoen, Ambros Gleixner, Gennesaret Kharistio Tjusila, Gioni Mexi, Nils-Christian Kempke, Sebastian Pokutta, Thorsten Koch, Timo Berthold.

Figure 1
Figure 1. Figure 1: Architecture of CHAP. CPU workers (left) and GPU workers (right) communi￾cate through a shared solution pool (center). The solution pool stores feasible solutions, partial (infeasible) solutions, and LP solutions. On the GPU, cuPDLPx solves the LP relaxation at increasing iteration checkpoints, while the tabu search runs multiple in￾dependent instances in parallel. 3.1 GPU Tabu Search Tabu search on GPU ha… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces CHAP, a hybrid GPU-CPU primal heuristic framework for mixed-integer programming that coordinates a portfolio of heuristics (Local Search, Fix-and-Propagate, Feasibility Pump, tabu search) through a shared solution pool for exchanging incumbents, LP solutions, and infeasible candidates. GPU components include a native tabu search with best-shift algorithm using sort/scan/reduce primitives and cuPDLPx as an approximate LP solver; CPU components include Fix-and-Propagate strategies and Feasibility Pump. All elements operate collaboratively under a five-minute time limit. On the 50-instance 2026 Land-Doig MIP Competition benchmark, CHAP solves 47 instances, outperforming default Gurobi (44) and heuristics-only cuOpt (43). The code is promised to be released on GitHub.

Significance. If the reported performance holds under stronger validation, the work provides a concrete demonstration that cross-platform coordinated portfolios can improve primal heuristic coverage in MIP, offering a practical path for incorporating GPU-accelerated components into existing solvers. The explicit use of a shared pool for iterative repair and the native GPU tabu-search implementation are positive contributions to the empirical literature on hybrid MIP heuristics.

major comments (2)
  1. [Evaluation / benchmark results] Evaluation section (results on the 50-instance benchmark): the headline claim that CHAP solves 47 instances (vs. Gurobi 44 and cuOpt 43) under a fixed five-minute limit is presented without statistical significance tests, without reporting variance across multiple runs, and without details on how ties or solution-quality cutoffs were handled. This leaves the outperformance claim plausible but not fully substantiated.
  2. [Framework description and Evaluation] Framework description and evaluation: the central narrative attributes the coverage gain to 'collaborative' exchange via the shared solution pool, yet the manuscript contains no ablation experiments (e.g., pool-disabled baseline, uncoordinated ensemble of the same Local Search / Fix-and-Propagate / Feasibility Pump / tabu-search routines, or component-wise removal of the coordination layer). Without these controls it is impossible to distinguish genuine synergy from the simple union of independent search trajectories on this particular benchmark set.
minor comments (2)
  1. [Abstract / Implementation details] The abstract and introduction mention 'tabu tenure and pool-size parameters' but provide no concrete values, ranges, or sensitivity analysis used in the reported runs.
  2. [Abstract] The manuscript states that code will be made available on GitHub but does not include a repository link or commit hash in the current version.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the constructive feedback on our manuscript. The comments highlight important aspects of the evaluation that we will address in the revision to strengthen the substantiation of our claims. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Evaluation / benchmark results] Evaluation section (results on the 50-instance benchmark): the headline claim that CHAP solves 47 instances (vs. Gurobi 44 and cuOpt 43) under a fixed five-minute limit is presented without statistical significance tests, without reporting variance across multiple runs, and without details on how ties or solution-quality cutoffs were handled. This leaves the outperformance claim plausible but not fully substantiated.

    Authors: We agree that the evaluation section would benefit from additional details on the experimental protocol. The reported results were obtained from single runs using fixed random seeds for reproducibility, which is standard practice for MIP heuristic comparisons under strict competition time limits. We will revise the manuscript to explicitly document this setup, clarify that success is defined by finding any feasible solution (no additional quality cutoff), and specify that ties are resolved by the first solution discovered within the time limit. While multiple runs for variance estimation were not performed due to the computational cost of the 5-minute limit across 50 instances, we will add a discussion of this limitation and note that the components with stochastic elements (e.g., tabu search) use deterministic tie-breaking where possible. revision: partial

  2. Referee: [Framework description and Evaluation] Framework description and evaluation: the central narrative attributes the coverage gain to 'collaborative' exchange via the shared solution pool, yet the manuscript contains no ablation experiments (e.g., pool-disabled baseline, uncoordinated ensemble of the same Local Search / Fix-and-Propagate / Feasibility Pump / tabu-search routines, or component-wise removal of the coordination layer). Without these controls it is impossible to distinguish genuine synergy from the simple union of independent search trajectories on this particular benchmark set.

    Authors: We acknowledge that the absence of ablation studies makes it difficult to isolate the precise contribution of the coordination mechanism. The shared pool is not merely a passive repository; several components are explicitly designed to use it (e.g., Fix-and-Propagate strategies are guided by incumbents and LP solutions from the pool, and the GPU tabu search exchanges candidates iteratively). We will add a dedicated paragraph in the framework description and evaluation sections that explains these design choices and provides qualitative evidence from the implementation showing how information flows through the pool. However, conducting controlled ablation experiments (such as disabling the pool or running uncoordinated versions) would require a substantial new set of computational runs and is beyond the scope of the current revision. revision: partial

standing simulated objections not resolved
  • Full ablation experiments isolating the effect of the shared solution pool versus independent execution of the same heuristics

Circularity Check

0 steps flagged

Empirical algorithmic framework with no internal derivations or self-referential claims.

full rationale

The manuscript presents CHAP as a portfolio of existing primal heuristics (Local Search, Fix-and-Propagate, Feasibility Pump, tabu search) coordinated via a shared solution pool, with GPU and CPU implementations described at the level of algorithmic primitives and kernel designs. All central claims are empirical performance numbers obtained by executing the framework on the external 50-instance Land-Doig benchmark under a fixed five-minute limit. No equations, fitted parameters, uniqueness theorems, or ansatzes are invoked whose outputs are then re-labeled as predictions or first-principles results. The reported 47/50 solved instances is therefore a direct measurement, not a quantity that reduces by construction to any internal fit or self-citation chain. Self-citations, if present, are incidental and do not carry the load of the performance claims.

Axiom & Free-Parameter Ledger

1 free parameters · 0 axioms · 0 invented entities

The framework builds on well-known MIP primal heuristics and standard GPU primitives; no new mathematical axioms or invented physical entities are introduced. A small number of implementation parameters (tabu tenure, pool size, repair thresholds) are necessarily chosen but are not presented as fitted constants in the abstract.

free parameters (1)
  • tabu tenure and pool-size parameters
    Typical tunable constants in heuristic design whose concrete values are not reported in the abstract.

pith-pipeline@v0.9.0 · 5595 in / 1323 out tokens · 30096 ms · 2026-05-08T17:06:14.429855+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

52 extracted references · 39 canonical work pages

  1. [1]

    https: //doi.org/10.48550/ARXIV.2111.10270

    Abbas, A., Swoboda, P.: Fastdog: Fast discrete optimization on gpu (2021). https: //doi.org/10.48550/ARXIV.2111.10270

    work page doi:10.48550/arxiv.2111.10270 2021

  2. [2]

    In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

    Abdelatti, M.F., Sodhi, M.S.: An improved GPU-accelerated heuristic technique applied to the capacitated vehicle routing problem. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference. p. 663–671. GECCO ’20, ACM (Jun 2020). https://doi.org/10.1145/3377930.3390159

    work page doi:10.1145/3377930.3390159 2020

  3. [3]

    In: 2019 IEEE Congress on Evolutionary Computation (CEC)

    Abdelkafi, O., Derbel, B., Liefooghe, A.: A Parallel Tabu Search for the Large- scale Quadratic Assignment Problem. In: 2019 IEEE Congress on Evolutionary Computation (CEC). p. 3070–3077. IEEE (Jun 2019). https://doi.org/10.1109/ cec.2019.8790152

    work page arXiv 2019

  4. [4]

    Achterberg, T.: Constraint Integer Programming. Ph.D. thesis (01 2007). https: //doi.org/10.14279/depositonce-1634

    work page doi:10.14279/depositonce-1634 2007

  5. [5]

    https://doi.org/10.3217/JUCS-014-14-2416

    Adam Janiak, Maciej Lichtenstein, Wladyslaw Janiak: Tabu Search on GPU (2008). https://doi.org/10.3217/JUCS-014-14-2416

    work page doi:10.3217/jucs-014-14-2416 2008

  6. [6]

    Advances in Neural Information Processing Systems34, 20243–20257 (2021)

    Applegate, D., D´ ıaz, M., Hinder, O., Lu, H., Lubin, M., O’Donoghue, B., Schudy, W.: Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems34, 20243–20257 (2021)

    2021

  7. [7]

    In: Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W

    Applegate, D., Diaz, M.D., Hinder, O., Lu, H., Lubin, M., O’Donoghue, B., Schudy, W.: Practical large-scale linear programming using primal-dual hybrid gradient. In: Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W. (eds.) Advances in Neural Information Processing Systems (2021), https://openreview.net/forum?id= eXwwWOyqT

    2021

  8. [8]

    Computers & Chemical Engineering184, 108627 (May 2024)

    Bernal Neira, D.E., Laird, C.D., Lueg, L.R., Harwood, S.M., Trenev, D., Venturelli, D.: Utilizing modern computer architectures to solve mathematical optimization problems: A survey. Computers & Chemical Engineering184, 108627 (May 2024). https://doi.org/10.1016/j.compchemeng.2024.108627

    work page doi:10.1016/j.compchemeng.2024.108627 2024

  9. [9]

    Operations Research Let- ters41(6), 611–614 (Nov 2013)

    Berthold, T.: Measuring the impact of primal heuristics. Operations Research Let- ters41(6), 611–614 (Nov 2013). https://doi.org/10.1016/j.orl.2013.08.007

    work page doi:10.1016/j.orl.2013.08.007 2013

  10. [10]

    EURO Journal on Computational Optimization7(1), 1–14 (2019)

    Berthold, T., Lodi, A., Salvagnin, D.: Ten years of feasibility pump, and counting. EURO Journal on Computational Optimization7(1), 1–14 (2019). https://doi. org/10.1007/s13675-018-0109-7

    work page doi:10.1007/s13675-018-0109-7 2019

  11. [11]

    Boyer, V., El Baz, D., Salazar-Aguilar, M.: GPU computing applied to linear and mixed-integer programming, p. 247–271. Elsevier (2017). https://doi.org/10.1016/ b978-0-12-803738-6.00010-0

    2017

  12. [12]

    In: 2013 IEEE International Symposium on Parallel & Distributed Pro- cessing, Workshops and Phd Forum

    Boyer, V., El Baz, D.: Recent Advances on GPU Computing in Operations Re- search. In: 2013 IEEE International Symposium on Parallel & Distributed Pro- cessing, Workshops and Phd Forum. p. 1778–1787. IEEE (May 2013). https: //doi.org/10.1109/ipdpsw.2013.45

    work page doi:10.1109/ipdpsw.2013.45 2013

  13. [13]

    In: 2013 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing

    Bukata, L., Sucha, P.: A GPU Algorithm Design for Resource Constrained Project Scheduling Problem. In: 2013 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. p. 367–374. IEEE (Feb 2013). https: //doi.org/10.1109/pdp.2013.59

    work page doi:10.1109/pdp.2013.59 2013

  14. [14]

    Computers & Industrial Engineering128, 514–525 (Feb 2019)

    Cheng, J.R., Gen, M.: Accelerating genetic algorithms with GPU computing: A selective overview. Computers & Industrial Engineering128, 514–525 (Feb 2019). https://doi.org/10.1016/j.cie.2018.12.067

    work page doi:10.1016/j.cie.2018.12.067 2019

  15. [15]

    Journal of Parallel and Distributed Computing 71(6), 802–811 (Jun 2011)

    Czapi´ nski, M., Barnes, S.: Tabu Search with two approaches to parallel flowshop evaluation on CUDA platform. Journal of Parallel and Distributed Computing 71(6), 802–811 (Jun 2011). https://doi.org/10.1016/j.jpdc.2011.02.006 14 Tjusila et al

    work page doi:10.1016/j.jpdc.2011.02.006 2011

  16. [16]

    Procedia Computer Science60, 1070–1080 (2015)

    Dali, N., Bouamama, S.: GPU-PSO: Parallel Particle Swarm Optimization Ap- proaches on Graphical Processing Unit for Constraint Reasoning: Case of Max- CSPs. Procedia Computer Science60, 1070–1080 (2015). https://doi.org/10.1016/ j.procs.2015.08.152

    2015

  17. [17]

    International Journal of Parallel, Emer- gent and Distributed Systems34(5), 497–522 (Jan 2018)

    Essaid, M., Idoumghar, L., Lepagnot, J., Br´ evilliers, M.: GPU parallelization strategies for metaheuristics: a survey. International Journal of Parallel, Emer- gent and Distributed Systems34(5), 497–522 (Jan 2018). https://doi.org/10.1080/ 17445760.2018.1428969

    work page arXiv 2018

  18. [18]

    Pro- cedia Computer Science29, 84–94 (2014)

    Fingler, H., C´ aceres, E.N., Mongelli, H., Song, S.W.: A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Pro- cedia Computer Science29, 84–94 (2014). https://doi.org/10.1016/j.procs.2014.05. 008

    work page doi:10.1016/j.procs.2014.05 2014

  19. [19]

    Mathematical Program- ming104(1), 91–104 (2005)

    Fischetti, M., Glover, F., Lodi, A.: The Feasibility Pump. Mathematical Program- ming104(1), 91–104 (2005). https://doi.org/10.1007/s10107-004-0570-3

    work page doi:10.1007/s10107-004-0570-3 2005

  20. [20]

    Mathematical Programming Computation1(2-3), 201–222 (2009)

    Fischetti, M., Salvagnin, D.: Feasibility Pump 2.0. Mathematical Programming Computation1(2-3), 201–222 (2009). https://doi.org/10.1007/s12532-009-0017-6

    work page doi:10.1007/s12532-009-0017-6 2009

  21. [21]

    doi:10.1287/ijoc.1.3.190 Fred Glover

    Glover, F.: Tabu Search—Part I. ORSA Journal on Computing1(3), 190–206 (Aug 1989). https://doi.org/10.1287/ijoc.1.3.190

    work page doi:10.1287/ijoc.1.3.190 1989

  22. [22]

    doi:10.1287/ijoc.2.1.4 David E

    Glover, F.: Tabu Search—Part II. ORSA Journal on Computing2(1), 4–32 (Feb 1990). https://doi.org/10.1287/ijoc.2.1.4

    work page doi:10.1287/ijoc.2.1.4 1990

  23. [23]

    Algorithms14(1), 21 (2021)

    Hansknecht, C., Joormann, I., Stiller, S.: Dynamic shortest paths methods for the time-dependent tsp. Algorithms14(1), 21 (2021). https://doi.org/10.3390/ a14010021, https://doi.org/10.3390/a14010021

    work page doi:10.3390/a14010021 2021

  24. [24]

    Low-precision first-order me thod-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization

    Kempke, N.C., Koch, T.: Fix-and-Propagate Heuristics Using Low-Precision First- Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization (2026). https://doi.org/10.48550/arXiv.2503.10344

    work page doi:10.48550/arxiv.2503.10344 2026

  25. [25]

    GPU gems2, 733–746 (2005)

    Kipfer, P., Westermann, R.: Improved GPU sorting. GPU gems2, 733–746 (2005)

    2005

  26. [26]

    Morgan kaufmann (2016)

    Kirk, D.B., Wen-Mei, W.H.: Programming massively parallel processors: a hands- on approach. Morgan kaufmann (2016)

    2016

  27. [27]

    International Journal of Parallel Programming42(5), 681–709 (Nov 2013)

    Kr¨ omer, P., Platoˇ s, J., Sn´ aˇ sel, V.: Nature-Inspired Meta-Heuristics on Modern GPUs: State of the Art and Brief Survey of Selected Algorithms. International Journal of Parallel Programming42(5), 681–709 (Nov 2013). https://doi.org/10. 1007/s10766-013-0292-3

    2013

  28. [28]

    Artificial Intelligence348, 104405 (2025)

    Lin, P., Cai, S., Zou, M., Lin, J.: Local-MIP: Efficient local search for mixed integer programming. Artificial Intelligence348, 104405 (2025). https://doi.org/10.1016/ j.artint.2025.104405

    work page arXiv 2025

  29. [29]

    https://developer.nvidia

    Lin, Y., Grover, V.: Using CUDA Warp-Level Primitives. https://developer.nvidia. com/blog/using-cuda-warp-level-primitives/ (2018)

    2018

  30. [30]

    arXiv preprint (2025)

    Lu, H., Peng, Z., Yang, J.: cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming. arXiv preprint (2025). https://doi.org/10.48550/ arXiv.2507.14051

    work page arXiv 2025

  31. [31]

    Lu and J

    Lu, H., Yang, J.: Restarted Halpern PDHG for linear programming. arXiv preprint (2024). https://doi.org/10.48550/arXiv.2407.16144

    work page doi:10.48550/arxiv.2407.16144 2024

  32. [32]

    Mathematical Programming212(1), 349–387 (2025)

    Lu, H., Yang, J.: On the geometry and refined rate of primal–dual hybrid gradi- ent for linear programming. Mathematical Programming212(1), 349–387 (2025). https://doi.org/10.1007/s10107-024-02109-9

    work page doi:10.1007/s10107-024-02109-9 2025

  33. [33]

    Mathematical Programming Computation15(2), 365–388 (Mar 2023)

    Luteberget, B., Sartor, G.: Feasibility Jump: an LP-free Lagrangian MIP heuristic. Mathematical Programming Computation15(2), 365–388 (Mar 2023). https://doi. org/10.1007/s12532-023-00234-8

    work page doi:10.1007/s12532-023-00234-8 2023

  34. [34]

    https://nvlabs.github.io/cub/ (2024) CHAP: A Hybrid GPU-CPU Heuristic for MIP 15

    Merrill, D.: CUB: CUDA Unbound. https://nvlabs.github.io/cub/ (2024) CHAP: A Hybrid GPU-CPU Heuristic for MIP 15

    2024

  35. [35]

    In: International Conference on Operations Research

    Mexi, G., Besan¸ con, M., Bolusani, S., Chmiela, A., Hoen, A., Gleixner, A.: Scylla: A matrix-free fix-propagate-and-project heuristic for mixed-integer optimization. In: International Conference on Operations Research. pp. 65–72. Springer (2023). https://doi.org/10.1007/978-3-031-58405-3 9

    work page doi:10.1007/978-3-031-58405-3 2023

  36. [36]

    https://www

    MIP Workshop 2026: 2026 Land–Doig MIP Competition. https://www. mixedinteger.org/2026/competition/ (2026), accessed: 2026-03-13

    2026

  37. [37]

    https://docs

    NVIDIA Corporation & affiliates: CUDA Programming Guide. https://docs. nvidia.com/cuda/cuda-programming-guide/index.html, accessed: 2026-03-13

    2026

  38. [38]

    Journal of Parallel and Distributed Computing73(1), 101–110 (Jan 2013)

    Pinel, F., Dorronsoro, B., Bouvry, P.: Solving very large instances of the scheduling of independent tasks problem on the gpu. Journal of Parallel and Distributed Computing73(1), 101–110 (Jan 2013). https://doi.org/10.1016/j.jpdc.2012.02.018

    work page doi:10.1016/j.jpdc.2012.02.018 2013

  39. [39]

    Rothberg, E.: Concurrent crossover for pdhg (2025), https://arxiv.org/abs/2510. 24429

    2025

  40. [40]

    Mathematical Programming Computation17(1), 111–139 (Oct 2024)

    Salvagnin, D., Roberti, R., Fischetti, M.: A fix-propagate-repair heuristic for mixed integer programming. Mathematical Programming Computation17(1), 111–139 (Oct 2024). https://doi.org/10.1007/s12532-024-00269-5

    work page doi:10.1007/s12532-024-00269-5 2024

  41. [41]

    Journal of Parallel and Distributed Computing73(1), 14–31 (Jan 2013)

    Schulz, C.: Efficient local search on the GPU—Investigations on the vehicle routing problem. Journal of Parallel and Distributed Computing73(1), 14–31 (Jan 2013). https://doi.org/10.1016/j.jpdc.2012.02.020

    work page doi:10.1016/j.jpdc.2012.02.020 2013

  42. [42]

    Journal of Parallel and Distributed Computing98, 48–60 (Dec 2016)

    Skinderowicz, R.: The GPU-based parallel Ant Colony System. Journal of Parallel and Distributed Computing98, 48–60 (Dec 2016). https://doi.org/10.1016/j.jpdc. 2016.04.014

    work page doi:10.1016/j.jpdc 2016

  43. [43]

    In: IEEE Congress on Evolutionary Com- putation

    Soca, N., Blengio, J.L., Pedemonte, M., Ezzatti, P.: PUGACE, a cellular Evolu- tionary Algorithm framework on GPUs. In: IEEE Congress on Evolutionary Com- putation. p. 1–8. IEEE (Jul 2010). https://doi.org/10.1109/cec.2010.5586286

    work page doi:10.1109/cec.2010.5586286 2010

  44. [44]

    Procedia Computer Science108, 1404–1413 (2017)

    Souza, D.S., Santos, H.G., Coelho, I.M.: A Hybrid Heuristic in GPU-CPU Based on Scatter Search for the Generalized Assignment Problem. Procedia Computer Science108, 1404–1413 (2017). https://doi.org/10.1016/j.procs.2017.05.188

    work page doi:10.1016/j.procs.2017.05.188 2017

  45. [45]

    Procedia Computer Science18, 2529–2532 (2013)

    Szymon, J., Dominik, Z.: Solving Multi-criteria Vehicle Routing Problem by Par- allel Tabu Search on GPU. Procedia Computer Science18, 2529–2532 (2013). https://doi.org/10.1016/j.procs.2013.05.434

    work page doi:10.1016/j.procs.2013.05.434 2013

  46. [46]

    IEEE Transactions on Cybernetics46(9), 2028–2041 (Sep 2016)

    Tan, Y., Ding, K.: A Survey on GPU-Based Implementation of Swarm Intelligence Algorithms. IEEE Transactions on Cybernetics46(9), 2028–2041 (Sep 2016). https: //doi.org/10.1109/tcyb.2015.2460261

    work page doi:10.1109/tcyb.2015.2460261 2028

  47. [47]

    In: 2012 Third International Conference on Networking and Computing

    Uchida, A., Ito, Y., Nakano, K.: An Efficient GPU Implementation of Ant Colony Optimization for the Traveling Salesman Problem. In: 2012 Third International Conference on Networking and Computing. p. 94–102. IEEE (Dec 2012). https: //doi.org/10.1109/icnc.2012.22

    work page doi:10.1109/icnc.2012.22 2012

  48. [48]

    A Case Study: The Flowshop Scheduling Prob- lem, p

    Van Luong, T., Melab, N., Talbi, E.G.: GPU-Based Approaches for Multiobjec- tive Local Search Algorithms. A Case Study: The Flowshop Scheduling Prob- lem, p. 155–166. Springer Berlin Heidelberg (2011). https://doi.org/10.1007/ 978-3-642-20364-0 14

    2011

  49. [49]

    https://doi.org/10.48550/ ARXIV.2510.27117

    Wei, N., Liang, J.: GFORS: GPU-Accelerated First-Order Method with Ran- domized Sampling for Binary Integer Programs (2025). https://doi.org/10.48550/ ARXIV.2510.27117

    work page arXiv 2025

  50. [50]

    Weiss, R.M.: GPU-Accelerated Ant Colony Optimization, p. 325–340. Elsevier (2011). https://doi.org/10.1016/b978-0-12-384988-5.00022-x

    work page doi:10.1016/b978-0-12-384988-5.00022-x 2011

  51. [51]

    In: 2014 IEEE Congress on Evolutionary Computation (CEC)

    Zan, D., Jaros, J.: Solving the Multidimensional Knapsack Problem using a CUDA accelerated PSO. In: 2014 IEEE Congress on Evolutionary Computation (CEC). p. 2933–2939. IEEE (Jul 2014). https://doi.org/10.1109/cec.2014.6900534 16 Tjusila et al

    work page doi:10.1109/cec.2014.6900534 2014

  52. [52]

    (2025) Integrated Information Theory: A Consciousness-First Approach to What Exists.https://doi.org/10.48550/arXiv.2510

    C ¸ ¨ ord¨ uk, A., Sielski, P., Boucher, A., Aatish, K.: GPU-Accelerated Primal Heuris- tics for Mixed Integer Programming (2025). https://doi.org/10.48550/arXiv.2510. 20499

    work page doi:10.48550/arxiv.2510 2025