Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: A step-wise neural CO algorithm is proposed, where the idea of bisimulation quotienting is used to define a state with the minimal but sufficient information. Authors mathematically formalize the solution-construction approach in CO problems and its MDP perspective (in Section 2). Then, the idea of bisimulation quotienting is introduced and how it is used to map TSP-MDP into path-TSP-MDP is discussed (in Section 3, with CVRP). With such formulation, a simple policy network that uses a Transformer (with slight modifications, e.g., removing PE) and is suitable for path-TSP-MDP (and its CVRP version) is proposed (Section 4), where the scalability of the model was empirically proven in a variety of experiments (Section 6). 
strength_and_weaknesses: ### Strength
- Constructive approach in CO and its relation to MDP are rigorously defined. 
- Explanation on generalization based on bisimulation and bisimilarity is clearly stated. 
- Strong generalization performance is shown through multiple experiments across two different CO problem instances (TSP, CVRP).
### Weaknesses
- Problems are restricted into the Euclidean settings. The algorithm’s applicability to non-Euclidean, non-symmetric COs is unclear.
- High computational complexity since pure Transformer is used. It was shown that using efficient Transformer techniques makes generalization performance poor.

clarity,_quality,_novelty_and_reproducibility: ### Clarity
- Maths and notations seem correct, but more detailed descriptions will make readers understand better. Since I was not familiar with bisimulation and bisimilarity, I had to spend a lot of time to understand those concepts although I believe authors try their best to describe those concepts.
  - e.g., in Section 3, it is mentioned that “bisimilarity is equivalently defined as the largest bisimulation (the union of all bisimulations)” but I couldn’t fully understand what this means. 
  - In Figure 1, $\equiv_{\Phi}$ is used without definition.
  - When the step space is defined in Section 2, $\mathcal{T}^*$ is mentioned without definition.
- In Section 4, “hence removing the need for a separate decoder”; I guess this was stated since there’s no need to use autogressive decoder, but I believe FF network after Transformer encoding can be regarded as a decoder. The same question for Section 4, Summary; authors state “our model does not have a decoder”.
- In Section 4, “Note that (optimal) solutions are not directly in the form of trajectories”: can you please elaborate what it means?
- In Section 4, Complexity, it would be better to describe how O(N^3) was derived, why standard encoder-decoder spend O(t^2) in more detail. 
### Quality
- I think most of contents are well-written. 
- The results show the impressive empirical performance.
- In Section C, authors use efficient Transformer (HyperMixer) to reduce the complexity but show that this harms the generalizability. Can you please elaborate why HyperMixer results in poor generalization? If this is simply because of using Layer Norm and not using ReZero, are there any alternatives other than HyperMixer? 
- At some point, it was unclear to me why training on small instances generalizes well to larger instances. For example, let’s consider generalization for TSP 1000 when we have a trained model on TSP 100. From the very beginning of evaluation to the point where less than 100 nodes remain, I believe it’s not possible to see any path-TSP states which were used to train the model. Then, what makes the model generalize well for larger instances?
### Novelty
- The formulation using bisimulation seems interesting and novel. 
### Reproducibility
- The idea seems easily reproducible. 

summary_of_the_review: The submission proposes an interesting symmetry perspective for constructive CO problems and shows impressive performance, which makes me vote for the acceptance of this work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: To improve the out-of-distribution generalization in solving combinatorial optimization (CO) problems, this paper proposes a transformed MDP to formulate constructive heuristics. Specifically, the transformation is based on bisimulation quotienting (BQ), which reduces the state space by leveraging the symmetries of the state space. Experiments on the Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP) demonstrate that the proposed method achieves the state-of-the-art generalization performance.

strength_and_weaknesses: Strengths:
* Introducing bisimulation quotienting to reduce the state space of CO problems is an interesting idea.
* The proposed method significantly improves the generalization performance in solving the TSP and CVRP, especially on the problems with large-scale graphs.

Weaknesses:
* The authors claim that their formulation is generic for arbitrary CO problems. However, the formulation seems specific for the TSP and CVRP. Thus, it would be more convincing if the authors could explain how the proposed formulation applies to other CO problems, such as mixed-integer linear programs. 
* The details about introducing the bisimulation quotienting into their proposed transformer-based model are unclear. For example, please illustrate the proposed model architecture and hyperparameters. Moreover, how does the proposed method learn two special embedding vectors for the origin and destination nodes?
* The ablation studies are insufficient. The authors may want to provide more experiments to show the effectiveness of the proposed BQ-based formulation. 
clarity,_quality,_novelty_and_reproducibility: Clarity and Reproducibility: Some description of the method is unclear.

Quality and Novelty: The idea of reducing the state space based on BQ is interesting.

summary_of_the_review: The idea of improving the generalization performance based on BQ is interesting. However, some claims are not well-supported, and some description of the method is unclear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents a framework for defining construction heuristic MDPs for combinatorial optimization problems and proposes a technique for exploiting symmetries in state representation in such MDPs based on a mapping to a different state representation. They design a transformer-based architecture for solving TSP and CVRP that utilizes such mapping and show that they significantly improve over the baseline in terms of generalization to larger problems.
strength_and_weaknesses: Strengths:
* Novel and simple approach to enhance neural combinatorial optimization problem by exploiting symmetry
* Results on generalization to larger instances than the training set instances show impressive improvement over the baselines


Weaknesses:
* While the approach is presented as a generic and flexible framework for combinatorial optimization, it seems to require a domain-specific mapping (Phi). The paper only considers such mapping for two routing problems and it is not clear if such mappings would naturally exist for many other (particularly non-routing) combinatorial problems and whether they will prove useful in such problems.
* The long theoretical discussion on general combinatorial optimization using MDP and bisimulation-quotienting seems somewhat disconnected from the actual neural approach. While it does seem to inspire such approach, the proposed neural approach could stand on its own as a new way of handling symmetries in routing problems. In particular, unlike the MDP framework built around rewards, the neural approach is trained using imitation.
* The approach requires optimal solutions for training. Such optimal solutions are typically intractable to compute beyond certain problem size. This is an important difference from approaches like Kool et al. (2021) based on reinforcement learning that do not rely on ground-truth optimal solutions.

Minor question: does "AM bs1024" indicate a beam search with beam width of 1024?
clarity,_quality,_novelty_and_reproducibility: - The paper is mostly clear, however as I noted before the theoretical part seems somewhat disconnected from the actual neural approach used.

- The approach provide a novel mechanism for exploiting symmetry in neural combinatorial optimization

- Reproducibility: the paper and the appendix seem to provide sufficient details for reproducing the results. The code is not attached however authors state they plan to make the code public upon acceptance.

summary_of_the_review: The paper seems to propose a nice enhancement to neural combinatorial optimization by exploiting symmetries in states. The experimental results show impressive improvement over baselines on problems of larger size compared to training set. The main weaknesses are: (1) it is not entirely clear how much the experimental results benefit from the theory presented in the paper; (2) the existing experimental results are limited to two routing problems and it is not clear that this technique would easily extend to non-routing combinatorial problems despite being presented as a general approach for combinatorial problems.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of solving combinatorial optimization problems using reinforcement learning enhanced with bisimulation quotients, where the main idea is to reduce the search space by identifying states with identical paths in MDP. In particular, new models are designed for TSP and CVRP. The proposed methods are supplemented with experimental studies

strength_and_weaknesses: Strength:

The overall idea is reasonable: capturing symmetries in the system is expected to reduce the required training efforts and thereby facilitate good generalization. Most of the sections are well-written (module the technical part), and the studied problem is well-motivated. The presented experimental results suggest that the proposed method is promising.


Weaknesses:

- W1: The presentation of this paper lacks mathematical rigor, which makes its technical contribution less clear. 
  - Is $T$ a set of steps or a set of sequences of steps? Is $T^*$ a closure of $T$? Some notations on pages 2 and 3 are inconsistent.
  - It would be better to formally define the concepts of being finalized, the new space $\hat{S}$.
  - Since the process is deterministic, should there be only one expansion?
  - I am a little confused by the context around Proposition 1, especially by the claim that MDP is equivalent to solving the CO problem. The proof seems to show that MDP can simulate general Turing machines subsuming CO algorithms, which is well-known.
  - The mapping $\Theta$ introduced in Section 3 is desired but computationally hard to obtain in general. In addition, its role in the proposed model (Sec 4) is not very clear.

- W2: Another major concern is that the designed model, as the main contribution, was described in a very abstract manner, and it is not clear how the ideas in the previous sections can be realized. Therefore, the novelty of this paper is not clear. The concrete contribution of this paper is entirely in the first paragraph of Section 4, but there are almost no technical details. As such, it seems that the proposed method can be obtained from the existing methods with very slight modifications. 

- W3: The paper could support reproducibility by including the source code. 

clarity,_quality,_novelty_and_reproducibility: The clarity could be improved by providing more formal definitions of the involved terms.

The quality and novelty are less satisfactory due to the lack of details.

The reproducibility could be better supported by providing course codes.

summary_of_the_review: The paper presents an interesting idea but could do better in explaining its novelty by having more details. The overall contribution seems limited.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a very interesting approach to leverage symmetries in combinatorial optimization (CO) problems.  While the approach advances the state of the art for solving CO by MDPs, the reviewers expressed concerns about the generality of the approach and the clarity of the technical details.  The rebuttal and the new experiments helped, but the concerns remain.  At the end of the day, the class of CO problems for which the approach is applicable should be clearly stated instead of broadly claiming that it applies to all CO problems.  In addition, the approach relies on a user defined mapping $\Phi$ and it is not clear how to obtain this mapping in general.  Finally, as pointed out by the reviewers, the technical details of the approach were not clear and the absence of code did not help.  Since the core of the work is good and worth publishing eventually, the authors are encouraged to pursue this work and to re-submit at a future venue while taking into account the reviewers' feedback. 

Strengths: 
* New MDP formulation that leverages symmetries induced by bisimilarity
* The proposed approach advances the state of the art

Weaknesses:
* Not clear what class of combinatorial optimization problems this approach is suitable for
* Users must provide a mapping $\Phi$, but it is not clear how to define it beyond the examples provided in the paper
* Lack of technical details regarding the implementation of the approach (this was not helped by the absence of code)
justification_for_why_not_higher_score: There was concensus among the reviewers in the written discussion for rejection.
Decision: Reject