BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization

Summary

Based on Bisimulation Quotienting (BQ), this paper proposed a new MDP formulation named BQ-MDP, to better formalise the process of solution construction in neural constructive solvers for CO problems. The proposed BQ-MDP reduces the state space and is designed to better reflect the symmetry of sub-problems encountered during solution construction. A new deep model named BQ-Transformer (based on Transformer) is designed according to the BQ-MDP, which is leveraged to solve CO problems including TSP, CVRP, and KP. The deep model is trained via supervised learning and the results showed better generalization performance of the learned model across problem sizes and distributions compared to several baselines.

Strengths

- The introduction of BQ into MDP formulations for neural constructive solvers is novel and interesting. - While several works like POMO (NeurIPS-20) [1], Sym-NCO (NeurIPS-22) [2] and Pointformer (AAAI-23) [3] have tried to explore the symmetries of CO problems, the idea of exploiting the symmetries during the recursive construction process is novel. - The proposed model showed impressive generalization performance across size and distribution, outperforming several baselines. - The exploration of BQ-PerceiverG to reduce computational complexity.

Weaknesses

- The clarity of the paper, particularly the mathematical formulations in Section 2.1 and Section 3.1, is limited. Examples include but are not limited to: the concept of the "step set Z" being “a set of partial solutions obtained by one construction step” is unclear, as it is not explicitly stated whether this step is based on an empty solution or an existing partial solution; It is said that “if x, y are partial solutions, x◦y denotes the result of applying the sequence of construction steps yielding x followed by that yielding y”, but I did not follow this definition. If x = z_1◦ · · · ◦ z_n, does it means that z_i are partial solutions? - The novelty (about the model architecture) may be limited. The proposed architecture seems to share similarities to an earlier exploration in [4] which also suggests re-encoding the sub-problems during solution construction. Furthermore, in the model designs, the claim about the elimination of the autoregressive decoder may not be compelling. Essentially, the proposed model, similar to AM and POMO, also requires multiple calls to select nodes for solution construction. And the proposed model still follows the encoder-decoder structure, as the last linear layer (used for generating the probability of selecting nodes via softmax) is the decoder. - The model is trained using imitation learning, which necessitates labeled data and pre-existing solvers to generate high-quality solutions. It is thus not clear if the credits for better performance should be given to the imitation learning/labeled data, or the proposed new architecture. - The experimental comparisons raise several concerns which make the advantages of the proposed method unclear: 1. On TSP-100 and CVRP-100 (without generalization), the BQ-Transformer performs worse than POMO despite using a longer runtime, particularly on CVRP. The BQ-Transformer seems to struggle with handling VRP constraints effectively. 2. Furthermore, when BQ-Transformer is equipped with beam search, there is no comparison made with POMO under similar settings, e.g., the POMO + beam search as proposed in the SGBS paper (NeurIPS2022) [5]. 3. Are the test datasets the same as DIEMS and DIFUSCO? How many instances are in the test datasets? The reported performance gaps of DIMES and DIFUSCO may be inaccurate, as I could not locate the reported gaps in their papers. 4. Since the models are trained on size 100, in Table 1, it would be clearer to label TSP200, TSP500, and TSP1000 as performance under generalization, rather than mixing them up, which could lead to confusion. 5. While the proposed model exhibits better generalization on larger-scale instances, it is unclear whether the model has the ability to further reduce the objective values (gaps) given a longer time budget, and how good the performance would be when compared to baselines with longer run time. References: [1] Kwon, Yeong-Dae, et al. "Pomo: Policy optimization with multiple optima for reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 21188-21198. [2] Kim, Minsu, Junyoung Park, and Jinkyoo Park. "Sym-nco: Leveraging symmetricity for neural combinatorial optimization." Advances in Neural Information Processing Systems 35 (2022): 1936-1949. [3] Jin, Yan, et al. "Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem." arXiv preprint arXiv:2304.09407 (2023). [4] Xin, Liang, et al. "Step-wise deep learning models for solving routing problems." IEEE Transactions on Industrial Informatics 17.7 (2020): 4861-4871. [5] Choo, Jinho, et al. "Simulation-guided beam search for neural combinatorial optimization." Advances in Neural Information Processing Systems 35 (2022): 8760-8772.

Questions

- Are the test datasets the same as DIEMS and DIFUSCO? How many instances are in the test datasets? Why have the objective values, in addition to the gaps, not been reported in Table 1? - What are the principal differences between the proposed model architecture and the one in reference [4]? Can we apply [4] to reflect the features of BQ-MDP? - The claim about the generality of BQ-MDP seems to be overstated. Are there certain Combinatorial Optimization Problems (COPs) that the MDP might struggle to handle? For instance, how would the MDP manage problems where the feasibility of the solution can only be determined when the solution is complete, as in some Simulation Optimization tasks? - Can the authors clarify the mathematical notations mentioned above? It may be beneficial to include examples (for instance, toy TSP-5 instances) to illustrate the new concepts introduced. - I could not find the correct Appendix; the current zip file contains the submitted manuscript for ICLR23, not the NeurIPS appendix.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The limitation mentioned in the weakness above should be discussed in the revised paper.

Summary

The paper proposes to use the notion of bisimulation quotienting (BQ) to define state spaces with the minimal information that is required to solve a combinatorial optimization (sub)problem. This results in a simpler architecture for the model used in training. Empirically, the methods advance state-of-the-art performance on a couple of routing problems.

Strengths

The paper rigorously formulates BQ-MDP for CO problems. I find this method applicable to a wide range of CO problems whenever it could be formulated as dynamic programming. The empirical results show that the method can generalize to larger instances than training. The paper includes many baselines, including some recent ones e.g. DIFFUSCO. I also like the idea of testing the method with a lightweight version of transformers.

Weaknesses

This method is limited to problems where finding feasible solutions are easy since it is mainly a construction heuristic. Other problems like 3-SAT (decision version of the Satisfiability problem, as opposed to MAX-SAT) that have a much constrained solution space might not be suitable for this method, though the BQ-MDP formulation is still applicable. For people who are familiar with dynamic programming (DP), the idea behind the approach is pretty straightforward — In DP, it is crucial to identify the minimal state representation to solve a subproblem to reduce complexity. This paper formulates this idea in a more mathematical fashion. I find this method applicable to a wide range of CO problems whenever it could be formulated as dynamic programming. But the authors didn’t emphasize this enough — it simply states it as a generic framework for COP. It is not obvious to readers how widely this method is applicable to COP. In experiments, it would be nice to also report variances. The benchmarks used are mostly in euclidean space, which gives the readers an impression that this might only work for this case. Are there non-euclidean routing problem benchmark that you could test your approach on? It seems that the method is not restricted to a particular learning algorithm or architecture. Imitation learning is just a way to go, but it wasn’t clear in the paper. In other words, would other learning methods like RL also be applicable?

Questions

See the weaknesses section. This paper seems relevant to this work: https://arxiv.org/pdf/2006.01610.pdf Might be good to discuss its relevance in the paper. Is the method more sample efficient that the other works? Intuitively, this should be one of the benefits because you are reducing states that are essentially the same but with different representations of partial solutions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I don't see any limitations other than those pointed out already.

Summary

The paper presents a generic framework for deriving direct MDPs for a given combinatorial optimization problem (COP) and propose a method for reducing the MDP using symmetry-focused bisimulation quotienting. Specifically, the paper presents a generic bisimulation that can be applied to a wide range of recursive problems. The paper presents an instantiation of the approach to three well known problems: TSP, CVRP, and Knapsack using a simple Transformer-based architecture with minor adaptation per application. The experiments show that the proposed approach obtains significantly better performance in generalizing to larger problems.

Strengths

- Novel and interesting approach to enhance neural combinatorial optimization problem by exploiting the recursive nature of many COPs. - The proposed technical approach seems to be relatively generic and can potentially be applied to a range of combinatorial optimization problems. - Experiments show significant improvement in generalizing to larger problems compared to the baselines.

Weaknesses

- Experiments in the paper are limited to three benchmarks domains. While these are important and somewhat diverse domains, previous work has also considered combinatorial optimization problems like maximum cut, maximum independent set, etc. Further, as TSP and CVRP are highly related and the results for KP show somewhat different performance patterns, it is not clear how well this approach works beyond the limited set of benchmarks. Specifically, the results on KP that are only presented in the appendix show more limited improvement over POMO compared to TSP and CVRP (no other baselines). Taking into account that POMO is a relatively poor baseline on TSP/CVRP in terms of generalizing to larger instances, this raises the concern that the proposed method may not perform as well on domains beyond TSP/CVRP. - Comparison with previous symmetry-related enhancements such as Sym-NCO is missing. While the authors note that such approaches are "orthogonal to our approach", it is still important to evaluate the benefit of the proposed approach in presence of these augmentations. - The approach still requires optimal solutions for training. Such optimal solutions are typically intractable to compute beyond certain problem size. While the proposed approach shows very good performance in generalizing to larger problems, there may be a limit to the scalability (the paper presents results for up to one order of magnitude larger test problems). It is interesting to see if this can be paired with RL fine-tuning to further improve performance on larger instances.

Questions

I would appreciate the authors' response to my main concerns listed above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

There is no explicit discussion of limitation, however I have no concerns about the work.

Summary

This paper first present a formulation of Combinatorial Optimization Problems (COPs) as Markov Decision Processes (MDPs) that can leverage symmetries of COPs to improve out-of-distribution robustness. Based on the MDP formulation, the authors then introduce the Bisimulation Quotienting to the MDP, namely BQ-MDP, which can reduce the state space. Finally, the authors introduce a simple attention-based policy network to learn policies in the BQ-MDP. Experiments demonstrate that the proposed method achieves the state-of-the-art performance on both synthetic and realistic benchmarks.

Strengths

1. To the best of my knowledge, the idea of introducing the Bisimulation Quotienting (BQ) to exploit symmetries of COPs is novel. 2. Experiments demonstrate that the proposed method achieves the state-of-the-art performance on both synthetic and realistic benchmarks. Moreover, the method achieves impressive generalization performance to much larger instances than seen during training.

Weaknesses

The presentation could be improved. 1. The authors claim that their formulation is generic for any CO problems. However, the formulation seems specific for the binary integer linear programming problems. Thus, it would be more convincing if the authors could explain how the proposed formulation applies to production planning problems with both continuous and discrete variables. 2. The details about the proposed method are unclear to me. For example, the authors may want to explain why and how introducing Bisimulation Quotiented can exploit the symmetries of COPs. Moreover, the details about the impact of the BQ-MDP on model architecture is unclear.

Questions

Please refer to Weaknesses for my questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Thanks for the response

I want to thank the author for the detailed responses. They have mostly resolved my concerns. I encourage the authors to include the details clarified during the rebuttal in the main paper. I have also read the other reviews and remain supportive of acceptance.

Thanks for the response

I appreciate the authors' detailed response which addressed some of my concerns, and I am now able to access the correct Appendix. I will increase my score, however, I still have some concerns. 1. Performance Concerns: * 1.1 While achieving better cross-size generalization performance (train on size 100 and test on larger size), the in-size performance (train and test on size 100) of the approach is limited (even worse than POMO on TSP and CVRP). * 1.2 The added results in PDF compare with a basic version of SGBS (4,4), overlooking the superior EAS+SGBS variant where the efficient active search (EAS) is the design that aims to boost the generalization of POMO on larger scales. * 1.3 Following the above, it is thus interesting to evaluable how good the performance of the BQ-MDP is when compared to other recently developed frameworks that aim to boost the cross size/distribution performance of a neural solver (shall be discussed and compared). In other words, it is hard to conclude that BQ-MDP is the SOTA framework for generalization enhancement (no comparison in the paper). 2. Use of Imitation Learning: * 2.1 The approach relies on imitation learning and labeled data, diverging from the original motivation of constructive NCO solvers like AM and POMO which aim to learn solvers without much human knowledge. * 2.2 While the proposed approach used imitation learning, key baselines like POMO and reference [4] were RL-based. It is unclear if the improved generalization performance is attributed to imitation learning or the BQ-MDP framework. What if we train the baselines (e.g. the architecture in ref[4] or POMO) using high-quality solutions generated in this paper instead of RL? 3. Presentation: More clarity is needed around the BQ-MDP framework's details, what steps are needed to adapt it to various architectures/existing approaches (as a framework), and the details of mathematical formulations.

Thanks for the response

Thanks for the response to address most of my concerns. I will keep my supportive score for this paper unchanged.

Thank you for your response

I thank the authors for their response and the additional results. My main concerns have been addressed. I remain supportive of accepting the paper.