PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization

Authors: André Hottung, Mridul Mahajan, Kevin Tierney
Primary area: reinforcement learning
Keywords: neural combinatorial optimization, learning to optimize, reinforcement learning, routing problems

Abstract:
Reinforcement learning-based methods for constructing solutions to combinatorial optimization problems are rapidly approaching the performance of human-designed algorithms. To further narrow the gap, learning-based approaches must efficiently explore the solution space during the search process. Recent approaches artificially increase exploration by enforcing diverse solution generation through handcrafted rules, however, these rules can impair solution quality and are difficult to design for more complex problems.  In this paper, we introduce PolyNet, an approach for improving exploration of the solution space by learning complementary solution strategies. In contrast to other works, PolyNet uses only a single-decoder and a training schema that does not enforce diverse solution generation through handcrafted rules. We evaluate PolyNet on four combinatorial optimization problems and observe that the implicit diversity mechanism allows PolyNet to find better solutions than approaches that explicitly enforce diverse solution generation.

Decision: accept (poster)
Reviewer scores: 6, 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1729762830720

thread_type:
official_review

<thread_object>
creator: reviewer_qkcr

<content>
summary:
This paper proposes PolyNet, which aims to reinforce the exploration training and testing of Nueral CO methods. In particular, a representive NCO method POMO is used as the playground in this paper. The idea behind this paper is quite simple: adding a neural network module which contains MLP layers besides the  main structure of POMO, termed PolyNet layer. PolyNet layer  provide exploration ability by letting its input as the node embeddings and a binary context coding. Using different binary context codings, the output of PolyNet layer add different information to the output of POMO hidden layers. By training on moderate instances, PolyNet show state-of-the-art performance on several CO problems (#nodes < 300). Besides, the authors demonstrate the exploration ability of PolyNet during the training and testing is different from the common practice in existing works: forcing diverse first action selection.

strengths:
The idea behind PolyNet is simple yet effective. The methodology part is easy-to-follow. The experimental results for performance comparison on different CO problems are solid and convincing. The ablation studies that explain the solution diversity in PolyNet are with good demonstration.

weaknesses:
There are two major 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. 

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.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730346235702

thread_type:
official_review

<thread_object>
creator: reviewer_bpfa

<content>
summary:
This study, grounded in the POMO framework, introduces a straightforward yet impactful component: PolyNet. The component takes as input the concatenation of a set of binary vectors and the output from the decoder's multi-head attention layers. After processing through a series of linear layers and activation functions, the output is directly added to the output of the decoder's multi-head attention layers, thereby directly influencing the probability distribution of node selection. Analysis from the paper indicates that the newly added module helps to enhance solution diversity without the need for mandatory starting point selection as in POMO. Additionally, the authors assert that PolyNet can be integrated with EAS, and significant performance improvements can be achieved by updating only the newly added modules.

strengths:
1. The authors have clearly articulated the framework and implementation of the method, with smooth writing.
2. The tables and figures are presented clearly, and the experiments are comprehensive.
3. Testing PolyNet on various combinatorial optimization problems (TSP, CVRP, CVRPTW, FFSP) demonstrates the good generality of the method.
4. (As claimed by the authors) their method performs exceptionally well on instances of scale 100, 200, and 300 (Tables 1-3).

weaknesses:
PolyNet can enhance the diversity and optimality of solution sets, but the authors seem to lack an in-depth discussion on the principles behind the additional layers of PolyNet. This leaves me somewhat puzzled. The training process described in the paper adopts a method similar to Poppy, and the added linear layers, activation functions, and residual connections are common components in the Transformer architecture. The motivation for significant improvements by merely concatenating an additional binary array is not very clear.

questions:
1. What is the design motivation behind the additional concatenated binary array $v$? Why can it significantly enhance diversity and optimality? 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?

2. 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. 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.

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

4. 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730384041186

thread_type:
official_review

<thread_object>
creator: reviewer_rgaa

<content>
summary:
To facilitate learning complementary solution strategies, this paper avoids forcing the initial action step. Instead, it enhances exploration by embedding it into the decoder as a bit vector. While experiments demonstrate performance improvements, the approach lacks novelty.

strengths:
1. The paper is well-structured, presenting its content in a clear manner.
2. A wide range of experiments are conducted to assess solution diversity.

weaknesses:
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.
2. The description of bit vectors is minimal, and there is no detailed analysis of how varying vector representations might impact performance.
3. The fairness of comparing COMPASS with PolyNet+EAS in an experimental context is questionable.
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.

[1] Combinatorial optimization with policy adaptation using latent space search. NeurIPS 2023.

questions:
1. The advantages of using bit vectors as supplementary vectors for insertion should be thoroughly analyzed, particularly in comparison to previous continuous potential vectors.
2. In the experimental section, a more comprehensive explanation and analysis of performance concerning runtime are necessary.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730741524366

thread_type:
official_review

<thread_object>
creator: reviewer_rrfp

<content>
summary:
PolyNet introduces a novel approach to enhancing exploration in neural combinatorial optimization (CO). Unlike traditional methods that enforce diversity via handcrafted rules, PolyNet employs a single-decoder model that inherently learns multiple strategies, facilitating more effective search and solution quality. The paper demonstrates PolyNet's superior performance across several benchmark CO problems, such as TSP, CVRP, and CVRPTW, outperforming state-of-the-art methods both in speed and solution quality.

strengths:
- The use of a single-decoder model that can learn multiple strategies simplifies the training pipeline and reduces computational overhead compared to multi-decoder systems.

- The model's training schema, which emphasizes inherent diversity, makes it adaptable to various CO problems beyond simple routing tasks.

- The authors provide useful insights into the impact of their design choices, such as the effectiveness of not forcing diverse first moves.

weaknesses:
- 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.

- 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.

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

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

questions:
1. How would PolyNet perform when extended to non-routing CO problems, such as job scheduling or knapsack problems?

2. Can you elaborate on the potential methods for improving PolyNet’s scalability to handle larger problem instances?

3. What are the specific limitations of PolyNet’s inherent diversity mechanism when applied to problem instances with different statistical properties?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732114653447

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to all reviewers

comment:
Thank you once again for your constructive feedback!

We have uploaded a revised version of the paper that incorporates your suggestions. Specifically, we have restructured the literature review to better emphasize the limitations of prior works and clearly outline the distinctions of our approach. Additionally, we have extended Figure 6 to include results for the original POMO method without additional layers, demonstrating that PolyNet also outperforms the unmodified version of POMO.

If you have any further questions or concerns, we would be happy to address them.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a new policy-based method for combinatorial optimization. The core idea is to form a $\pi(a | s, v)$ where: 
  * $a$ is a possible problem solution (parameterized via the use of standard Pointer Network / Attention mechanisms)
  * $s$ is a representation of the initial problem conditions (e.g. city locations in Travelling Salesman)
  * $v$ is a diversity prompt, meant to ensure that the corresponding $a$ should be diverse and far away from other $a'$ from other $v'$.

Training is done via the Poppy (Grinsztajn et al) method, in which policy gradients are only backpropagated for the best solutions $(a, s, v)$ when varying $v$. Experiments are conducted over standard combinatorial optimization problems e.g. (TSP, CVRP, CVRPTW).

Overall, this paper builds on top of the Poppy regime, with the improvement being that there is now only a single decoder needed, with diversity based on "diversity prompts" $v$ rather than needing multiple separate decoder heads, making it more efficient in practice. While the results and execution are solid, one could argue that this is still fairly incremental work. 

Given that most of the reviewers have voted to accept (see also my analysis of the issues raised by the reviewer who voted to reject), the decision is a poster accept.