Symmetry-preserving graph attention network to solve routing problems at multiple resolutions

1- While the idea of leveraging symmetry seems interesting, it is not novel. In fact, POMO and Sym-NCO also exploit them, but in different ways; 2- The baselines such as AM, POMO, AMDM, Sym-NCO are classic, but not the SOTA. Actually, quite a number of works on learning to solve VRPs have been published in ICML, ICLR, AAAI this year and last year. Especially, many of them also test their performance on the benchmark instances. Without comparing with them, I am not full convinced by the results and conclusions drawn in this paper; 3- The studied problem sizes are quite small; 4- Overall, this work contributes little to the community of learning to solve VRPs.

• The related work section is not sufficient. A lot of literature on deep learning approaches for vehicle routing is not mentioned. Despite the cited papers, many of which were published before 2021, the authors should cite the latest literature. Given the fast development of the research on vehicle routing with deep learning, the related work is so simplified to me.

• The training problem size is too small for the current literature. You are using A100 GPUs, so why not train on larger problems? It raises concerns about the training efficiency and scalability of the proposed method. Could you report the training complexity of mEGAT compared with baselines?

• In Table 1, the authors directly copy the results from Sym-NCO [3]. Are their training settings the same as yours? If different, please retrain it following their open-source code. Moreover, the results of Sym-NCO on 20 and 50, and that of HGS [4] should be reported.

• For the variable-size generalization, the authors should test on larger sizes (e.g., TSP100+). It is expected that your model (trained on TSP100) performs well on TSP20 and TSP50 due to the (multiresolution) training on low-level graphs. But what if the problem sizes scale up?

• The authors should carefully proofread the submission since some minor issues exist:

  • On page 6, "$\pi_{\ell}^{sub}$ denotes the $\ell$-th resolution's solution on the high-level instance" -> $\pi_{\ell}^{high}$
  • In Algorithm 2, "Multisolution graph Training" -> "Multiresolution"
  • The caption of Table 3: "AM" -> "POMO". The best result is not in bold.

[1] Attention, learn to solve routing problems! In ICLR 2019.
[2] POMO: Policy optimization with multiple optima for reinforcement learning. In NeurIPS 2020.
[3] Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In NeurIPS 2022.
[4] https://github.com/vidalt/HGS-CVRP
[5] http://vrp.galgos.inf.puc-rio.br/index.php

Given all, I vote for rejection. This submission needs a bit more work on the empirical evaluation before meeting the bar of ICLR.

• The method does perform better than baselines, but the gap is not that extensive.
• Handcrafted solvers still remain clearly superior to all neural approaches, meaning that any real impact or the field of Operations Research is still only potential.
• Relatively small (up to n=100 cities) problem instances are considered, in line with previous ML efforts. Handcrafted solvers can comfortably handle problem instances several orders of magnitude larger.
• When it comes to the multi-scale training component of the method, it is not proven beyond doubt that the observed performance improvements are due to the leveraging of multi-scale information as the authors suggest; the improvement could just be the consequence of effectively training on more problem instances (the original one, and the sub-instances, and the high-level instances) compared to not using multi-scale training.
• Usually, equivariance (or any inductive bias in general) is mostly useful for improving data efficiency. Since TSP instances can be easily generated synthetically (which the authors themselves do), it does not appear that this use-case is one in which data are scarce, and therefore data-efficiency is an important consideration.

A lot of paradigms on deep learning for routing problems are in literature. But the paper only covers much less and neglects recent ones. Even the highly related ones are not included. As an example, Revisiting Transformation Invariant Geometric Deep Learning: Are Initial Representations All You Need solves TSP by symmetry-preserving approaches.

The compared methods are not new and most published before 2021. Therefore the results are not convincing. Moreover, the compared methods are supposed to be trained by multiple sizes of instance for fairness. The tested sizes are relatively small and no hints are described to raise the generalization scales.