Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: ## Summary
The paper proposes an improvement for the Travelling Salesman problem using Transformers to compute positional information. The paper introduces a new architecture to learn separate groups of embeddings for the node and positional features following the encoder-decoder structure; this new architecture is introduced as a Dual Aspect Collaborative Transformer. By separating the node and position embeddings this transformer structure allows for the non deterministic nature of routing tasks. The paper also proposes a cyclic positional encoding method to address the non-linearity of VRPs. The DACT learner is trained using Proximal Policy Optimisation following a curriculum learning strategy in order to address stability issues.
main_review: ## Originality
I would classify the originality presented here here in the mid-range. Because even though using transformers for VRPs has been done in the past, this paper splits the information streams, usually encoded together as a key feature for the original use cases, in order to gain flexibility and therefore improving exploration.

## Quality
* The paper presents clear explanations of any new contributions made; it reads like a complete piece of work but it leaves the reader with a feeling of having expected to see some of the work left for future efforts.
* I would have liked to see more effort on adding clear introductions about the combination of technologies used and the target problem, aiding readers unfamiliar with them to get setup with constructive knowledge.
* The paper does have well supported claims.

## Clarity
* The paper presents the concepts in a clear and well organised manner.
* More reproducibility details would have been well received by the reader; for instance, a repository containing the code and clear steps for running training and inference.
* More information needs to be presented on the implementation and training aspects of the PPO learner.

## Significance
The results and ideas used here are interesting and valuable. The paper presents an interesting line of work where some more ground can be made to create solutions for TSPs. It's difficult to evaluate if the work presented here advances the state of the art, but it does present a very interesting and novel combination of methods to address a well known and difficult problem.

## References
A quick google search provided a couple of papers not listed that seem relevant: 
* https://hanalog.polymtl.ca/wp-content/uploads/2018/11/cpaior-learning-heuristics-6.pdf
* https://arxiv.org/pdf/2010.02068.pdf \
It may be worth scanning for more. \
Please provide details of how this paper relates to those.
limitations_and_societal_impact: ## Limitations
The work is clearly focused on a very particular problem. Whether that focus is enough to establish an assertion of its limitations is perhaps a bit subjective.

## Societal impact
I do not foresee any negative societal impact sourced from this work. It addresses a pretty fundamental problem already present in our daily lives.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses the vehicle routing problem. It proposes to learn the embeddings for the nodes and the positional encodings separately, where the positional encoding is learned in a novel cyclic manner. The results show that the proposed dual transformers outperform previous works.
main_review: I do not see apparent flaws in this paper. The paper presentation is detailed, the figures are nice, and the results are promising. The ablation studies properly evaluate the contribution of each component.

Building on top of [10], this paper makes several solid contributions, yet none of them can be considered groundbreaking.

There are some minor details not clear to me.
How does the proposed model compare to baseline methods in terms of parameters?
How does this model generalize to random initial solutions?
What if testing the model with L > 3?
I believe the g_n^(l) in Figure 2 should be g_N^(l)

limitations_and_societal_impact: I do not see the potential negative societal impact.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes a few variants to the Transformer model to learn to find solutions for routing problems. There are two main architectural changes: (1) using cyclic Gray codes instead of sinusoidal positional embeddings, and (2) using a two-stream attention function (named Dual-Aspect Collaborative Attention (DAC-Att)) instead of the multihead QKV attention.

The resulting model is trained with Proximal Policy Optimization (PPO), and is shown to find good solutions to the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).

main_review: I have two main concerns with this paper.

First, the contributions seem overly complicated and whether it is necessary to go for such complexity is questionable. For instance, the use of cyclic Gray codes is motivated by the hypothesis that it better encodes the cyclical similarity which is needed when searching for tours, in the case of TSP and CVRP. However, these insights are very specific for these problems. Also, learnable positional embeddings (which is done in many modern Transformer language models), is capable of learning this cyclic behavior as well. If the authors just use learnable positional embeddings, they would not need to introduce the Gray codes. If the authors train with learnable embeddings, and the resulting learned embeddings do not exhibit the cyclic behavior, then maybe the cyclical behavior is not favored in the Transformer. Either way, I feel like the use of Gray codes is not justified.

Second, while the Dual-aspect Attention (DAC-Att) mechanism is somewhat more justified than the Gray code embeddings, DAC-Att would significantly increase the computational complexity. Perhaps this is the reason why the time stamps in Table 1 for DACT are bad. Other than a slower training and inference time, I think that DACT should compare against methods that have the same computational complexity. If no such method exists (they do), then DACT should still compare to heuristic methods that are allowed to run for more randomized trials in order to account for the complexity differences. Under such circumstances, it is unlikely that DACT will deliver any benefits, which leads to my next point.

Third, the experimental results in the paper are not convincing. In Table 1, DACT lost to many other baselines *under the same time constraint*. Understandably, the authors focus on the gap to optimal solutions, which fafor their method DACT, but the tradeoff for the smallest gaps in DACT is the much longer operating time. Furthermore, all the instances considered in the experiments are relatively small (i.e., with 20, 50, and 100 instances). More convincing experiments on larger situations, preferably the situations where previous methods fail to solve, are needed in order to prove the effectiveness of DACT.

Therefore, while the paper has no obvious flaw, I think the authors will need more work in order to justify the effectiveness of DACT. I recommend rejecting the paper.

limitations_and_societal_impact: Very limited or none.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes an improved Transformer-like architecture to learn an improvement heuristic for the Travelling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). It proposes a special form of positional encoding that represents the cyclic structure of a current solution and proposes to learn separate embeddings for 'node' and 'positional' features (in each layer) which only exchange information through an attention matrix. It uses a PPO algorithm with a curriculum learning strategy. Experiments on TSP and VRP with up to 100 nodes show reasonable performance compared to existing alternatives.

While the paper presents an improvement to the results for TSP and VRP, in my opinion it is too incremental to be accepted in its current form, as it largely reuses existing architecture and experimental setup, but with improved positional encodings/embeddings and a simple curriculum learning strategy. It is unclear how the proposed improvements (which share some similarity with United Positional Encoding) can generalize to other problems or how this will affect the ability to solve larger instances, which I think should be the main goal of this line of research, as the current SOTA is not yet competitive with alternative methods. Given the quality of the work I encourage the authors to continue but I think the paper should be improved to show this potential before it can be accepted.
main_review: Originality

The paper is somewhat incremental as it can be seen as making certain specific improvements to an existing setup (learning to solve routing problems by an improvement heuristic using transformers). Specifically, the improvements made are the 1) using cyclic positional features, 2) separate embeddings for positional and node features (somewhat related to United Positional Encoding) and 3) using PPO with a simple curriculum learning strategy.

Clarity

The paper is quite clear and well written in general, although I find that it should balance the amount of space dedicated to different topics. Much space is used to describe the cyclic positional encoding and equations relating to the 'standard parts' of the transformer architecture (multi-head attention and feed forward layers), whereas to understand the proposed method I would find it much more helpful if the pseudocode in the appendix D was included in the main paper, as well as the description of the '2-opt' operator (reversing the segment between selected nodes i and j), which are crucial details of the used methods.

The Figures are a bit scary to look at at first sight and could be simplified possibly, but are very helpful in understanding the architecture, positional encoding, etc.

Quality

The work is technically correct and well-motivated. The experiments are well-conducted and carefully reported to deal reasonably with differences between evaluations of different methods. They support the claim that the architecture outperforms existing improvement models, although this should not be mistaken for 'outperforming VRP' or neural VRP, in which case POMO is a reasonably simple and strong baseline. To give a better picture of where it stands, it would be good to report full performance vs time curves against some of the strongest baselines, which can be easily obtained by running with a different number of iterations.

Significance

The results push the boundary for learning improvement based heuristics for VRP which is promising. However, I consider the main contribution the architectural improvement as using PPO with a curriculum learning strategy is rather straightforward. While promising, it is unclear how these generalize to other problems (e.g. when adding time windows, the cyclic property seems to break) or larger instances, which would ultimately be the goal as the method is not yet competitive to VRP. DACT mainly exploits the fact that the input is a (circular) sequence, so I do think it would be good to at least hint at how this could extend to construction heuristics or other problems where solutions are not naturally represented as ordered sequences (e.g. knapsacks).

Minor comments/questions

- Please check spelling (e.g. matmal -> matmul Fig 2.)?
- Line 288 -> multiple GPU in (.) and single GPU in {.}, I think this should be other way around?
- Which attention exactly is shown in Fig. 5? Is it averaged over layers?
- Scrolling past Fig. 5 lags on my PC. If others experience this as well it may be worth saving the images differently for convenience of your e-readers.
limitations_and_societal_impact: Limitations are discussed in the discussion. I do not see any direct negative societal impact.
review_title: null

Meta-review: Based on reviews, rebuttal and discussion, I recommend acceptance of this paper. Based on reviews:

* There is no fundamental flaws
* The overall paper is clear
* The experiments are well conducted
* The rebuttal addresses the main concerns

While the significance of the contributions are borderline, it is sufficient to inspire new works in the same direction and is likely to have positive impact on the sub-community.
Decision: Accept (Poster)