- 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
- 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.
- 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
- 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.
- 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
- 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?
- 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?
- 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.