- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The manuscript is motivated by the primal and dual properties in combinatorial optimization problems. It first transforms the instances into equivalent problems, such as by transposing the distance matrix of the asymmetric TSP. The transformed instances are then input to either the training or inference phases. The proposed method is evaluated on asymmetric TSP and five scheduling variants. Results show that applying on inference is helpful, while training with such augmentation deteriorates the performance.
Critical strengths
- The idea of adopting the primal and dual properties in COP is interesting.
- The code is provided.
Critical weaknesses
- The presentation is very poor. It seems to be AI-generated, with so many details and unclear statements. It is difficult to follow despite careful reading.
- A similar idea has been considered in [1]. Careful positioning and differentiation against prior works will strengthen the manuscript.
- It is so straightforward to just use the equivalent transformation as inputs. It would be more interesting to rethink a more suitable use for the duality.
- Why does the use in training deteriorate the performance on scheduling? I expect a more in-depth understanding of it.
- More importantly, why do we need such a transformation for NCO? What special benefits and insights can it bring to the community?
[1] Generalization in deep RL for TSP problems via equivariance and local search.
Questions for authors
See above.
Response to Reviewer FGus: why PDA matters and relation to prior work
Thank you for the careful review. Your questions, why training on the dual can hurt and what duality offers NCO, are the ones our new experiments were designed to answer. We summarize the answers first, then the changes to the paper.
What duality offers NCO. NCO has had two ways to improve a trained model at test time: geometric augmentation, which exists only for Euclidean routing, and search (active search, EAS, SGBS, COMPASS), which needs extra gradient steps or a model trained for it. The dual is a third way that needs neither. It brings two findings we did not expect:
Training does not always hurt, and we now know when it does. PDT helps when the dual adds training signal and not when it splits it (general response, point 2; reply to 2xck):
So the answer to "why does training hurt on scheduling" is that our scheduling backbones learn from their own samples, not that scheduling is special. We also tested tying the two directions more tightly, so that both imitate the best solution of either direction: the PDA gain almost vanishes (0.23 → 0.05 on PFSP), because PDA needs the two directions to differ. The better use of duality in training is therefore as extra labeled data, as in supervised learning; the better use at test time is PDA, which needs no training at all.
Relation to [1]. Ouyang et al. (2021) use the geometric symmetries of Euclidean TSP (rotation, reflection) for equivariant policies and local search. ATSP and scheduling have no such geometry. Our transformations are exact problem duals (time reversal, machine reversal, matrix transposition) that keep the objective value. The revision cites [1] and states this difference.
Soundness. Win counts are replaced by paired Wilcoxon tests with 95% confidence intervals on every problem (general response, point 1). Claims that are not significant are reported as ties, and conclusions that rest on one training run are marked as such.
Presentation. We take this seriously. We used AI assistance and disclose it, as ICLR requires; the experiments, analyses and claims are our own. The revised PDF, which we will upload in this discussion period, is built around these answers, with one table for each, and moves the per-problem details to the appendices. For any further revision, the manuscript will also be edited by a professional editing service.