PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization

Thank you very much for reviewing our paper and providing helpful feedback! We are happy that you find the performance comparison on different CO problems solid and convincing.

Please let us address your two remaining weaknesses.

a) Related works are not well-organized. As a important part to let readers aware the background, the motivation and the priority of this paper, Neural CO methods should be organized in a way that these points are clearly outlined.

We agree that giving a good overview on the related work is of critical importance. As such we are very motivated to address this weakness and improve the literature review. Could you kindly provide some more details on how we can improve the related work section? Do you think that the related work section does not provide enough details? Are there works that we missed to include? Is the high-level structure of using 3 paragraphs (NCO, Diversity mechanisms in RL, Diversity mechanisms in neural CO) insufficient?

We are confident that we will be able to improve the related work section during the rebuttal based on your feedback!

b) Fow now, the scale of the CO problems PolyNet could address is no more than 300, which makes me curious about the performance of PolyNet on larger instances (#nodes > > 300). From my angle, the exploration ability is especially needed in large scale problems.

The version of PolyNet presented in this paper is not well suited to scale to very large instances without additional modifications, however our approach is nonetheless a significant contribution in its current form despite this limitation for two reasons: 1) A large number of real-world scenarios exit that require solving CVRP(TW) instances with fewer than 500 nodes. In fact, even more recent state-of-the-art, hand-crafted approaches from the operations research literature [1, 2] focus only on problems with 100 to 1000 nodes. On these medium-sized problems, our approach offers state-of-the-art performance and outperforms all other machine learning-based approaches. 2) Going forward, our method can be integrated into divide-and-conquer approaches that divide larger instances into smaller subproblems (see e.g., [3]). For these approaches, our method could function as a powerful subsolver, resulting in improved performance even on very large-scale instances.

[1] Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140, 105643.
[2] Christiaens, J., & Vanden Berghe, G. (2020). Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2), 417-433.
[3] Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., & Li, F. (2024, March). Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 18, pp. 20284-20292).

Thank you for reviewing our paper and providing helpful feedback! We are happy that you like the writing and presentation of the paper and the performance of our proposed method.

Please let us address your remaining questions.

What is the design motivation behind the additional concatenated binary array? Why can it significantly enhance diversity and optimality?

Our key idea is to learn multiple, different construction strategies with a single neural network. To achieve this we condition the output of the network on the additional binary vector and train it so that different binary vectors result in the generation of different solutions. The results shown in Fig. 3 demonstrate that this indeed works. When sampling 100 solutions to a single instance with PolyNet the generated solutions are more diverse than those sampled via POMO, and provide better performance ("useful diversity").

If it were replaced with a column of random numbers, or if random perturbations were directly added to the input of the "added layer," would the same effect be achieved?

This would achieve a similar effect. It is important that the model is given some input additional to the instance representation that it can condition its output on. The form of this additional input and how it is inserted does not seem that important. However, we observe experimentally that the additional layers that process the additional input do lead to significant performance improvements in Figure 6.

In Appendix Figure 6, a comparison is made between "PolyNet w/o Added Layers" and "POMO with Added Layers." It would be better if a "POMO" without additional additions could be included for comparison.

Thank you for the suggestion. We have uploaded a new version of the paper that includes a comparison to POMO without additional layers. POMO without the additional layers performs slightly worse than the modified version with an additional layer.

My question is, why does "PolyNet w/o Added Layers" perform significantly better than "POMO with Added Layers"? Is it due to differences in training methods? If so, it would be best to compare POMO with the new training method.

The added layer only has a small impact on performance. The main performance difference originates from the training method (including the additional input vector) and free first move selection. Note that the input vector is required for the training method to work, so that diverse strategies can be learned. Figure 6 now includes a comparison to the original POMO.

Which contributes more significantly, the training method or the new structure?

As discussed above, the training method (including the additional vector input) is significantly more important. As shown in Figure 6, PolyNet without additional layers only works slightly worse than the PolyNet version with additional layers. Despite their small impact, we use the additional layers because they have an insignificant impact on runtime and are very easy to implement.

In combinatorial optimization, there is a class of problems specifically focused on diversity optimization, where multiple solutions need to be found simultaneously. Relevant papers include “Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study” and “A Niching Memetic Algorithm for Multi-Solution Traveling Salesman Problem.” The work presented in this paper seems particularly suited for such scenarios, and I hope to see more discussion on this topic.

Thank you for bringing this area of research to our attention. We have updated the related work section of our paper to include a discussion on these works. It further confirms the importance of useful diversity for effective search strategies. Please see that updated version of our manuscript.

Thank you for reviewing our paper and providing helpful feedback! We are happy that you like the presentation and the experimental evaluation of our paper.

Please let us address your remaining concerns.

1. The method of inserting additional vectors in the decoder is very similar to the idea of COMPASS [1], lacking sufficient innovation to significantly advance the field.

The COMPASS method is a high-quality contribution to the field, but we emphasize that PolyNet is quite different, even though they both insert a vector into the decoder. PolyNet aims to learn discrete strategies, while COMPASS learns a continuous latent spaces that can be searched by a continuous search method like CMA-ES. Most importantly, PolyNet can generate solutions quickly (e.g., 4 minutes for 10,000 TSP instances) while COMPASS is designed for longer runtimes (e.g., 2 hours for 10,000 instances). While PolyNet can also be combined with EAS for longer search runs, our main focus is on generating solutions quickly.

2. The description of bit vectors is minimal, and there is no detailed analysis of how varying vector representations might impact performance.

We believe that the bit vectors can be replaced with other discrete tokens without a major impact on performance. What matters is that the network has some kind of input that it can condition its output on. We have chosen bit vectors as they are simple to implement and require no extra normalization. In preliminary experiments, we also evaluated one-hot encoding instead of binary encoding for the bit vector (i.e., learning 128 strategies would then require a bit vector of size 128 in contrast to a bit vector of size 7), but we found no major differences. Are there any specific representations that you have in mind? Overall, we are confident that the exact form of the “discrete input token” is not very relevant, simply because the network can learn to transform the bit vector representation into a more beneficial representation on its own.

3. The fairness of comparing COMPASS with PolyNet+EAS in an experimental context is questionable.

Why do you consider this an unfair comparison? COMPASS has been designed with longer runtimes in mind and uses CMA-ES to provide high-level search guidance. PolyNet without EAS lacks such a search component. We could emphasize more strongly in the paper, that EAS increases the runtime due to the needed parameter updates, if this is your main concern.

4. In [1], there is a big difference between COMPASS and EAS runtimes, but in this paper, PolyNet+EAS time is similar to COMPASS, please specify the reason.

Note that the OpenReview version of the COMPASS method contains incorrect runtimes for EAS as described on the Github page of COMPASS. The recent arxiv version contains the corrected values.

There are still some differences to the runtimes reported in our work. We can not provide a definite explanation because we do not have access to all experiment protocols of the COMPASS paper or the same hardware. We can only speculate that the difference originate from differences in the hardware used (we evaluate EAS on an A100 while the COMPASS authors use a TPU), differences in the implementation (we use PyTorch with FlashAttention while the COMPASS authors use JAX). Due to these differences in the experimental settings the runtimes can not easily compared. To ensure a fair comparison we follow earlier work (including the COMPASS paper) and limit the search by the number of generated solution.

The advantages of using bit vectors as supplementary vectors for insertion should be thoroughly analyzed, particularly in comparison to previous continuous potential vectors.

As outlined above, we did not found significant performance differences between different vector representations in preliminary experiments. It should also be possible to use continuous vectors instead of bit vectors without an impact in performance.

In the experimental section, a more comprehensive explanation and analysis of performance concerning runtime are necessary.

The runtime of the methods is highly influenced by the quality of their implementation, the chosen framework, and the hardware used. Therefore, small differences in runtime should not be overinterpreted. We can highlight this more explicitly in the paper and underscore that EAS incurs additional runtime overhead due to the required parameter updates.

Thanks to the authors' efforts in the rebuttal. I am inclined to keep my score, since the methodological contribution of this paper appears to be quite limited, given the following reasons:

1. While the use of discrete vectors is emphasized in this work, the COMPASS paper has already discussed discrete vectors, as noted, "There are several ways to define the latent space, and the simplest approach is to use a set of N one-hot encoded vectors."
2. As stated by the authors in their response, "PolyNet aims to learn discrete strategies, while COMPASS learns a continuous latent spaces that can be searched by a continuous search method like CMA-ES", alongside with the claim that "It should also be possible to use continuous vectors instead of bit vectors without an impact in performance". These two points, when considered together, suggest that the choice of discrete vectors is not particularly significant.
3. The authors emphasize that "our main focus is on generating solutions quickly", which is a limited contribution in my opinion.

Thank you very much for reviewing our paper and providing helpful feedback! We are happy that you point us many of the core components of our work as strengths and find that we provide useful insights into the impact of our design choices.

Please let us address your remaining concerns and your questions.

While starting from pre-trained models boosts training efficiency, this reliance could limit applicability in cases where such pre-training is not feasible or available.

PolyNet can also be trained from scratch, but starting from a pre-trained model indeed boosts training efficiency. The same is true for virtually all deep learning models. We believe that pre-trained models will often already be available in real-world scenarios. If no pre-trained models are available, users can start training from scratch or try self-supervised pre-training methods.

While PolyNet demonstrates strong results in routing tasks, its effectiveness in other CO problem domains (e.g., scheduling or knapsack) has not been deeply explored.

We evaluate PolyNet on a scheduling problem (the flexible flow shop problem (FFSP)) in Appendix A. On this problem, PolyNet shows improvement in line with the improvements observed on the routing problems, demonstrating that it is applicable to a wider range of problems.

The paper does not discuss how PolyNet handles instances where input data is noisy or incomplete, a common occurrence in practical applications.

We agree that noisy input data is a common occurrence in practical applications and that methods that address this (e.g., stochastic optimization methods) deserve more attention. However, almost all NCO paper currently focus on deterministic optimization problems and assume complete information. We intend to evaluate PolyNet on stochastic problems in future work. The evaluation on stochastic problems requires a different experimental setup and a more in-depth discussion that would be beyond the scope of this paper.

The impact of different hyperparameter settings on model performance is not fully analyzed, which could be critical for real-world applications requiring fine-tuning.

One of the benefits of PolyNet is that it does not require hyperparameter tuning for good performance and we also did not conduct any hyperparameter tuning. The impact of the main hyperparameter $K$ (i.e., the number of learned strategies) is shown in Figure 3, with higher-values resulting in better performance. However, the selection of $K$ is effectively limited by the available GPU memory. All other parameters like the batch size and learning rate are selected based on experience with the POMO model to enable stable training. The performance improvements that can be improved by tuning these values are not worth the additional computation costs associated with tuning these values.

If there is any hyperparamter that you are particularly interested in, please let us know!

Thanks for your response. You have addressed my concerns, and I'd like to keep my score.