Don't Waste Population: Post-Anneal Refinement for Combinatorial Optimization

Modern GPU-native solvers for combinatorial optimization exploit parallelism by evolving large populations of relaxed candidates; yet, their post-processing collapses this computational effort into a single, rounded solution. We show that the discarded replicas of Parallel Quasi-Quantum Annealing (PQQA) form an implicit elite archive that contains basin-level information recoverable after annealing. We introduce Iterative Path-Relinking Polish (I-PRP), a deterministic, training-free post-anneal operator that leaves the PQQA inner loop unchanged. I-PRP polishes the top rounded elites, traverses cost-guided relinking paths from the current best elite toward the others, re-polishes intermediate states to cross basin boundaries, and iterates only under strict improvement. The operator never degrades the paired upstream polish, terminates after a finite number of updates, and reduces to the original polish when the population collapses to a single basin. Across QUBO and graph-coloring benchmarks, I-PRP preserves saturated cases while improving PQQA on rugged multi-basin instances, revealing that parallel annealing populations contain reusable search structures beyond their best replicas.