PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

1.1. Problem Setting

• MIO models real-world decision problems; primal heuristics find high-quality solutions that can help prune branch-and-bound and benefit from restricted subspaces.The problem setting defines a node as a restricted version of the mixed-integer optimization problem.Source: §1 · p. 1, §1.1 · p. 2

1. Introduction

• GPU parallelization for MIO primal heuristics remains an open challenge despite GPU advances for continuous optimization.PaNGEA is presented as a GPU-accelerated primal heuristic tested on 283 instances.Source: §1 · p. 2

1.2. Related Work

• PaNGEA contributes a general-purpose GPU-accelerated primal heuristic, distinctively running local searches on different nodes in parallel.The authors describe it as standalone, without reliance on an MIO solver, and envision future integration into GPU-native branch-and-bound.Source: §1.2 · pp. 3–4

1.3. Contributions

• The two-stage local-search procedure solves a node's linear relaxation before Local-MIP, delaying node bounds until a feasible solution is found.The paper reports a 30% reduction in average optimality gap versus naive Local-MIP and a fivefold gap reduction from linear-relaxation warm-starting.Source: §1.3 · p. 4
• PaNGEA evaluates multiple node-generation strategies in parallel and retains promising nodes, rather than relying on one heuristic rule.Its two-stage local-search implementation also reduces the average optimality gap by 30% versus naive Local-MIP, while linear-relaxation warm-starting reduces the gap by a factor of five.Source: §1.3 · p. 4

2.1. Core Subroutine

• The core subroutine starts local search from the node-relaxation solution, searches over the full original bounds, and imposes node bounds after finding a feasible solution.This is intended to incentivize convergence toward a solution in the node without immediately restricting admissible moves.Source: §2.1 · p. 5

2.2. Overview of PaNGEA

• PaNGEA duplicates the root into W nodes, generates R new nodes per node, explores all W × R in parallel, and retains the best W for the next iteration.A separate CPU thread restarts local search from the best incumbent found by the main loop.Source: §2.2 · p. 6

2.3. Node-Generation Strategies

• Six node-generation strategies run in parallel, including reduced-cost fixings, diving, consensus and elite-pool choices, best-solution neighborhoods, and bound-propagation diving.Deep diving with bound propagation is activated only when root-node analysis finds no feasible solution.Source: §2.3 · p. 7
• Reduced-cost fixings select local-search moves with low objective compromise; consensus and elite strategies use common choices in the solution pool.The Best strategy fixes 90% of coordinates to the incumbent values; deep diving samples binary variables and applies bound propagation.Source: §2.3 · pp. 7–8

2.4. Node Selection

• Node selection discards nodes whose optimal relaxation objective exceeds the incumbent, then selects the W nodes with lowest local-search objective.If too few nodes remain, some discarded nodes may be retained after unfixing 10% of their fixed coordinates; infeasible local searches are ordered by violated constraints.Source: §2.4 · p. 8

2.5. GPU Implementation and Batching

• Shared problem data stays on the GPU while node-specific bounds and search state are stored across the batch, enabling common kernels to process independent nodes.Batched PDLP updates use sparse matrix-matrix products and coordinate-wise projections across the nodes.Source: §2.5 · pp. 8–9

3.1. Local-MIP with Node Pressure

• Across fixed-coordinate fractions, two-stage local search reduces average gap by five percentage points versus direct Local-MIP, which often fails to find feasibility even with 70–90% of coordinates fixed.With node-relaxation initialization, average gap is 12%, versus 55% from a zero vector.Source: §3.1 · p. 10, Figure 2 · p. 10

3.2. Diversifying Node-Generation Strategies

• With W = 1, increasing strategies to R = 6 lowers gap integral by 14%; using W = 5, R = 1 yields no significant improvement over W = R = 1.Deep Diving is beneficial in 1.1% of cases but yields 5.91% improvement when successful; Best and Elite succeed more often, at 35.1% and 21.5%.Source: Figure 3 · p. 11, §3.2 · p. 11

3.3. Parallel Exploration of Multiple Nodes

• With R = 6, average gap integral falls from 124.7 at W = 1 to 118.1 at W = 4, then rises; at W = 16 it exceeds the W = 1 baseline.The adaptive W rule sets W according to instance size and available GPU memory, attaining gap integral 120.2, close to the best W chosen in hindsight.Source: Figure 4 · p. 12, §3.3 · pp. 12–13

3.4. Benchmarking

• PaNGEA ranks best among non-commercial methods on both benchmark sets across all three criteria; versus non-commercial baselines, it achieves 12–30% lower gap integral and 17–45% lower final gap.The 75th-percentile gap integral falls from 268 to 140 on MIPcc26 and from 247 to 146 on MIPLIB relative to Local-MIP.Source: Table 1 · p. 13, Table 2 · p. 13, §3.4 · pp. 13–14
• On MIPcc26, PaNGEA has a smaller final gap than Gurobi without branching (0.27 vs 0.30) and similar gap integral (112.94 vs 111.86); on MIPLIB, Gurobi without branching performs better on both.Gurobi heuristics achieves a smaller final gap on both test sets; PaNGEA’s advantage over Gurobi is more pronounced at higher constraint-to-variable ratios.Source: §3.4 · p. 14
• PaNGEA’s relative performance depends on constraint-to-variable ratio: it beats Gurobi without branching for m/n > 0.5 and Gurobi heuristics for m/n > 3, supporting a complementary role.The authors hypothesize that weaker performance at small m/n may relate to local search changing one coordinate per iteration, making it sensitive to high n.Source: §3.4 · p. 14, Figure 5 · p. 15, §3.5 · p. 15

3.5. Value of a Hybrid GPU-CPU Algorithm

• The hybrid’s CPU and GPU searches both contribute on 67% of instances; only GPU contributes on 11%, only CPU on 22%, and median GPU contribution is 54%.Among instances making further progress after 1 and 2.5 minutes, median GPU contribution rises to 76% and 81%, respectively.Source: §3.5 · pp. 15–16, Figure 6 · p. 16

4. Discussion: Towards a GPU-Native Branch-and-Bound

• PaNGEA resembles branch-and-bound in solving relaxations and seeking feasible solutions at each node, but its unstructured generation quickly produces deep nodes rather than exhaustively evaluating a tree.The approach can find good feasible solutions, but lacks branch-and-bound’s guarantee of exhaustive evaluation.Source: §4 · p. 16
• 63.5% more iterations per second and an increase in node relaxations solved without timeout from 9.8% to 12.1% accompanied 15.6% more pruned nodes under batched processing.Batched processing compares simultaneous PaNGEA and branch-and-bound relaxation solves with sequential solves; each sequential batch receives the same iteration limit and half the batched time limit.Source: §4 · p. 17, Table 3 · p. 17
• Nearly 88% of node relaxations were neither solved to optimality nor proved infeasible, as PDLP was less accurate than simplex or interior-point methods.The resulting weak bounds slow progress; the cited GPU branch-and-bound implementations focus on narrower problem classes with fast GPU relaxation methods.Source: §4 · p. 17

5. Conclusion

• PaNGEA evaluates multiple candidate node-generation strategies simultaneously and continues from the most promising nodes, rather than relying on one rule.The authors report that this design performs strongest among non-commercial methods on MIPcc26 and MIPLIB and gains over non-parallel variants.Source: §5 · p. 18
• The authors frame GPU parallelism as enabling new MIO heuristic architectures, not only faster implementations of existing methods.Their reported GPU gains include both accelerating a single-node heuristic and exploring multiple node-generation rules in parallel.Source: §5 · pp. 17–18

Notes

• Seven instances proved infeasible are excluded; two comparison methods are omitted because their benchmarking code was unavailable at experiment time.The Gurobi “heuristics” and “without branching” modes are also specified through solver parameters.Source: Notes · p. 18
• PaNGEA’s unstructured node generation can make bound propagation inefficient, while deep diving with bound propagation mitigates this issue.The note also identifies integration with branch-and-bound as a way to better leverage preprocessing techniques.Source: Notes · p. 18

Appendix A: Detailed Algorithm Description

• Appendix A introduces implementation details for PaNGEA’s components.The listed implementation includes initialization and the core subroutine.Source: Appendix A · p. 21

A.1. Initialization

• The root relaxation is solved concurrently by PDLP and Gurobi, whose solution can warm-start other relaxations; the two solvers address instance-dependent performance.If initial local search finds no feasible solution, initialization considers six node-generation strategies; otherwise it considers five.Source: §A.1 · p. 21

A.2. Implementation of the core subroutine

• To encourage diverse exploration of the feasible space, node relaxation is capped at 5 seconds in addition to PDLP convergence criteria, while local search stops after 5 seconds, 2,000,000 iterations, or 2 seconds without improvement.Gurobi solves a node relaxation rather than batching it with other node relaxations on the GPU when at least 95% of integral coordinates are fixed and there are fewer than 10,000 effective variables, or when the root relaxation was solved on CPU in less than 5/B seconds. If a Gurobi relaxation times out or is infeasible, PDLP solves it on the GPU to provide local-search initialization.Source: §A.2 · p. 21

A.3. Caching

• After local search, the best node receives a continuous-variable partial optimization with its integer variables fixed, subject to a 0.5-second limit.PaNGEA caches PDLP terminal states to warm-start child nodes and maintains an elite pool of at most 20 solutions, selected with objective quality and diversity in mind.Source: §A.2 · p. 21, §A.3 · pp. 21–22

A.4. Details about node-generation strategies

• Elite-based fixing scores unfixed binary variables using their frequency and their association with variables fixed to 1, then fixes variables with scores farthest from 1/2.Reduced Costs, Diving, and Elite use specified fixing rates; rates with parameter µ receive Gaussian noise to avoid duplicate nodes, and a computational safeguard falls back to the frequency score.Source: §A.4 · pp. 22–23

• Appendix B supplements the numerical experiments reported in Section 3.Source: Appendix B · p. 23

B.1. Diversifying Node-Generation Strategies (Section 3.2)

• 146.2 was the lowest average gap integral among five strategies on 25 odd-numbered MIPcc26 instances, achieved by the reduced-cost strategy.The comparison used PaNGEA with R = 1 and W = 1.Source: §B.1 · p. 23, Figure B.1 · p. 23
• For R > 1, portfolios were built greedily by adding the strategy with the lowest average gap integral on the 25-instance subset.Deep Diving was reserved for R = 6 because it targets instances where root local search fails to find a feasible solution.Source: §B.1 · p. 23, Table B.1 · p. 24
• The figure compares single-strategy performance, with boxplots showing distributions and panel (b) showing mean within-instance differences from the 146.2 baseline.Negative differences indicate improvement; error bars show ±1 standard error across instances.Source: §B.1 · p. 23, Figure B.1 · p. 23

B.2. Parallel Node Exploration and GPU Utilization (Section 3.3)

• No single fixed W dominates across the three instance subsets, and higher GPU SM-active rate is generally associated with better final gap.The subsets are grouped by the number of nonzeros in constraint matrix A.Source: §B.2 · p. 24
• Relaxations may terminate early when solved optimally or proved infeasible, while launched local searches continue until their time or iteration limit.Accordingly, increasing W need not raise relaxation-phase activity, whereas local-search SM-active rate rises monotonically with batch size in the reported subsets.Source: §B.2 · p. 24
• Larger W usually increases GPU activity, especially during local search, but may allocate work to less promising nodes, so final gap is not monotone in activity.The adaptive rule generally achieves higher SM-active rates and better final gaps at the same time.Source: §B.2 · p. 25

B.3. Benchmarking (Section 3.4)

• Figures B.4 and B.5 show gap-integral and final-gap distributions, while Figure B.6 plots average final gap for instances above increasing m/n thresholds.Figure B.6 uses a log-scale threshold axis and 95% confidence intervals.Source: §B.3 · pp. 25–27, Figure B.4 · p. 26, Figure B.5 · p. 26
• PaNGEA’s win rate against Gurobi heuristics and Gurobi without branching rises by around 90% and 50%, respectively, on instances with m/n > 1 versus all instances.Source: §B.3 · p. 26, Table B.2 · p. 27

B.4. GPU-CPU Local Search (Section 3.5)

• Instance examples show GPU batched local search finding the first feasible solution in one case, CPU Local-MIP stalling before GPU-driven improvements in another, and repeated alternation in a third.The examples illustrate that the CPU component contributes more than additional computation, with the interaction varying by instance.Source: §B.4 · pp. 27–28, Figure B.7 · p. 28

Appendix C: Instance-wise Results on the Test Set

• Tables C.1–C.6 present computational results in terms of feasible objective value: C.1 uses the MIPcc26 test set, while C.2–C.6 use the MIPLIB test set.Source: Table C.1 · p. 29, Table C.2 · p. 30, Table C.3 · p. 31

Appendix D: Integration of PaNGEA and Branch-and-Bound

• The prototype maintains a persistent branch-and-bound tree alongside PaNGEA, starting from the root node.Source: Appendix D · p. 34
• The integrated search selects half of its parallel branch-and-bound nodes by smallest lower bound and half by largest, then uses cuPDLP relaxations, branching, propagation, and pruning.Dual lower bounds remain valid even when a relaxation solve stops before its desired accuracy.Source: Appendix D · p. 34

13 end

• PaNGEA supplies bestUB to the branch-and-bound component.Source: §13 · p. 35