acceptodds
Withdrawn from ICLR 2027

NRP4CO: Neural Residual Propagation for Combinatorial Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 , , and over the neural baselines with the best reported gap on each dataset.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Neural Residual Propagation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_4gxxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes NRP4CO, a framework that combines learned assignment commitments with deterministic constraint propagation. A Transformer conditioned on a partial solution produces separate edit scores for selection and completion, and residual scores for threshold-based commitments. An auxiliary objective trains the shared representation to predict assignments implied by constraints. The framework is incorporated into a reconstruction-based search procedure, with problem-specific implementations for six combinatorial optimization problems. The paper establishes feasibility preservation under admissible commitments and sound propagation, and evaluates solution quality, runtime, and component contributions across synthetic and public benchmarks.

Critical strengths
  1. The framework provides a coherent separation of learned decisions and deterministic constraint handling. Independent edit and residual outputs serve different decision roles, while propagation preserves the consequences of accepted assignments. The problem-specific implementations and component ablations provide meaningful support for this design.
  2. The experiments demonstrate promising quality–runtime trade-offs on several problems. On ATSP-500, NRP4CO reduces the gap from 1.57% to 0.553% while reducing runtime from 16.48 s to 3.34 s relative to the reported COExpander configuration. Similar improvements on maximum clique, together with cross-scale and public-benchmark evaluations, support the framework’s practical potential.
Critical weaknesses
  1. A direct comparison with a closely related baseline is missing. MaskCO shares the partial-solution conditioning and reconstruction-based search approach and is explicitly discussed in the paper, but no experimental comparison is reported. It is a critical weakness where the novelty is called into question. A comparison on common benchmarks under matched computational budgets would strengthen the evidence for the proposed framework.
  2. The quality–runtime benefit of residual selection remains unclear on MCL RB-LARGE. Tables 6 and 12 show that residual selection reduces the gap from 1.074% to 0.993%, while increasing runtime from 1.075 s to 3.333 s. Although this demonstrates a quality improvement at fixed trajectory and cycle counts, it does not establish an advantage at equal runtime. Allowing the ablated variant additional trajectories or cycles within the same time limit would clarify this trade-off.
Questions for authors
  1. Appendix D.2 states that perturbed ATSP contexts may be incompatible with the original reference solution. How are conflicting reference labels handled during training, and what benefit do these contexts provide over reference-consistent contexts?
  2. In Appendix F.9, disabling residual selection leaves the final gap essentially unchanged on MCL RB-SMALL. Under what instance characteristics or search settings does residual propagation improve solution quality, rather than merely increase the number of resolved assignments?
  3. Proposition 1 establishes that ranking alone does not determine threshold selection. Beyond the shared-head ablation, does a calibrated single-head model offer a competitive alternative to separate edit and residual outputs? I would raise my score if these issues are well-solved.
Reviewer_f2GCOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduced NRP4CO, a neural combinatorial optimization method which combines learned commitments with deterministic constraint propagation. NRP4CO leverages separate edit and residual heads to guide completion and thresholded commitment, supported by assignment and auxiliary propagation supervision. The paper evaluates the framework on various CO problems. The authors claimed that NRP4CO achieves the lowest optimality gap among the compared neural solvers on all 19 benchmark settings.

Critical strengths
  1. The framework clearly separates learned commitments from their deterministic consequences. Its feasibility analysis makes the joint admissibility and sound closure assumptions explicit.
  2. The evaluation is comprehensive, covering multiple problem families, cross-scale generalization, and external benchmarks.
Critical weaknesses
  1. In my view, MaskCO[1] is central to the motivation but absent from the main comparisons, while GenSCO[2] is compared only on TSPLIB. The incremental contribution over closely related reconstruction methods remains insufficiently established.
  2. The TSP ablation shows substantial dependence on 2-opt for final solution quality. Without comparisons against baselines under matched reconstruction and 2-opt budgets, it is difficult to attribute the reported advantage to NRP itself.
  3. Table 12 shows small gap differences between the full model and its ablated variants, while residual selection and constraint propagation add substantial runtime on MCL. The practical benefits of the individual components remain unclear.
  4. Several details remain unclear, such as cost-matrix generation for ATSP, demand and capacity settings for CVRP, and the numerical residual commitment limit for CVRP.
  5. In the main benchmark comparisons, NRP4CO uses target-scale training or fine-tuning, whereas some baselines appear to use zero-shot generalization to larger problem sizes. This raises concerns about fairness.
Questions for authors
  1. How does NRP4CO compare with MaskCO[1] and GenSCO[2] under matched search and experimental settings?
  2. Could you compare NRP4CO with the baselines under matched settings, both with and without 2-opt? Please also report results for both TSPLIB and CVRPLIB settings with and without 2-opt, using a single fixed model trained at a single size per problem.
  3. Can you provide equal-time ablation studies across multiple problem sizes in Table 12?
  4. For the main comparisons, could you specify the training scales and fine-tuning status of each baseline? Could you compare NRP4CO and the baselines using models trained at the same problem size (e.g., 100-node instances), or explain why not?

References:

[1] Chen L, Li Y, Yan J. MaskCO: Masked generation drives effective representation learning and exploiting for combinatorial optimization. ICLR 2026.

[2] Li Y, Chen L, Wang H, et al. Generation as search operator for test-time scaling of diffusion-based combinatorial optimization. NeurIPS 2025.

Reviewer_HjFVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes NRP4CO, a neural combinatorial optimization framework that separates edit scores for selection and completion from residual scores for threshold-based commitments. Accepted commitments are followed by deterministic constraint propagation, and the resulting partial assignments guide feasible completion and iterative search. The model is trained using reference solutions with decision and auxiliary propagation supervision. Experiments cover six combinatorial optimization problems, with additional component ablations and generalization evaluations.

Critical strengths
  1. The motivation for separating ranking-based completion from threshold-based commitments is reasonable.
  2. The experimental coverage is broad, including six problem families and multiple instance sizes. The appendix also includes substantial ablations that help clarify the contributions of individual components.
Critical weaknesses
  1. The technical novelty over closely related methods appears incremental. COExpander already studies adaptive expansion conditioned on partial solutions, while MaskCO uses masked-solution training and iterative reconstruction. The main additional contribution therefore seems to lie primarily in the separate residual prediction and supervision design.
  2. Although the ablations support the proposed components, their benefits are sometimes modest and are not consistently established under equal runtime budgets. For example, on MCL RB-LARGE, adding residual selection reduces the gap from 1.074% to 0.993%, while increasing runtime from 1.075s to 3.333s. These results leave uncertainty about when residual commitments provide a meaningful advantage over spending the same computation on additional search.
  3. MaskCO is discussed as related work but omitted from the experimental comparisons, making it difficult to assess the practical improvement over this closely related baseline.
Questions for authors
  1. On ATSP, how much of the improvement comes from residual propagation, rather than the constrained assignment and cycle-merging completion procedure? Could you provide the corresponding component ablations?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.