NRP4CO: Neural Residual Propagation for Combinatorial Optimization

Partial solutions guide prediction and search in neural combinatorial optimization, where solvers must decide which assignments to retain before completing a solution. Ranking-based completion uses relative score order, while committing assignments at a fixed threshold depends on score magnitudes. We propose NRP4CO, a framework for Neural Residual Propagation that couples learned commitments with deterministic constraint propagation. A Transformer conditioned on a partial solution produces separate edit and residual scores: edit scores guide primary selection and completion, while residual scores receive assignment supervision for thresholded commitment on unresolved variables. Problem-specific propagation rules derive implied assignments, and auxiliary propagation labels train the shared representation to encode these consequences. NRP4CO extends partial solutions and reconstructs incumbents during search. We prove that admissible commitments followed by sound propagation preserve the existence of a feasible completion. We evaluate NRP4CO on the traveling salesman problem (TSP), asymmetric traveling salesman problem (ATSP), capacitated vehicle routing problem (CVRP), maximum independent set (MIS), maximum clique (MCL), and minimum vertex cover (MVC). NRP4CO achieves the lowest optimality gap among the compared neural solvers on all 19 benchmark settings. Across TSP, ATSP, and maximum clique benchmarks, NRP4CO reduces optimality gaps by an average of 24.0%, 69.6%, and 79.0%, respectively, with corresponding average speedups of $11.06\times$, $4.46\times$, and $7.38\times$ over the neural baselines with the best reported gap on each dataset.