Venue: ICLR 2022 Conference

Reviews:

final_score: rating: null
review_content: Dear all,

Recently I come up with the concern about whether the measurement of time is proper in a line of MLCO papers (Kool2019, Kwon2020) including this paper. In these papers, the MLCO algorithms are run in parallel on GPU, and the time reported is the time it takes to solve a single problem if batch=1, divided by the batch size. However, their compared baselines that run on CPU, are not run in parallel batches. I believe this is not a fair comparison because the number of parallel batches is different, and in practice, it is easy to solve multiple problems in parallel batches with multiple CPU nodes. In contrast, what we should care about is the time it takes to solve a single problem with batch=1 because it corresponds to how long we will keep the user waiting for the optimization result. 

Though the discussion period is scheduled to have been ended, I am writing this comment to raise the concern because this seems to be an issue even in some highly-cited papers. The authors of this paper may have simply followed the open-source code from others and did not think carefully about the timing results. However, it does not mean that the authors should not be criticized for conducting an unfair comparison among different methods, and it is the responsibility of we researchers to stop delivering misleading information to our future readers.

[Kool2019] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019. 

[Kwon2020] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33, 2020.
review_title: The time measurement may be unfair in (Kool2019, Kwon2020) and this paper

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work presents GANCO, a framework that extends the training of RL heuristics for combinatorial optimisation problems (COPs) to include an adversarial agent that aims to generate hard-to-solve problem instances.  The RL heuristic and adversarial instance generation are alternately trained, with the intuition that the adaptive problem distribution encourages the solving agent to learn policies with better generalisation performance to unseen instances compared to those trained on a single static distribution.  Experiments train the Attention Model of Kool et al (and a subsequent extension, POMO) within the GANCO framework and show that across multiple well-studied COPs (including the travelling salesman problem), GANCO augmented training does result in policies that generalise better to unseen distributions at test time.
main_review: **Strengths**

- The paper is well written, the framework is presented clearly and (along with the supporting code promised to be released) with sufficient information to reproduce the key elements if the work.

-  I find the task itself, improving generalisation in RL COP solvers, to be well motivated and prescient.  Indeed, most works learning solvers for combinatorial problems seek to test how they perform when the test-time distribution is different from that on which the solver was trained and I find the idea of dynamically controlling the training distribution to challenge the learnt heuristic to be an interesting approach.  To the best of my knowledge, the proposed framework is novel.

- The experimental results are impressive, with the improved generalisation of agents trained within the GANCO framework clearly demonstrated with respect to those trained on only a single base distribution.  By considering multiple COP instances and using established methodologies, the empirical performance improvements are clear, however it there remains scope to further improve the analysis of GANCO itself as discussed below.

**Weaknesses**

- Whilst the broader distribution of training tasks provided by GANCO is clearly demonstrated to improve generalisation, the necessity of the adversarial entity (GANCO’s core contribution) is not demonstrated clearly enough to unequivocally endorse GANCO as an optimal (or very good) approach to generating additional instances.  To be precise, the RL baselines to which GANCO is compared are trained on strictly fewer instances sampled from a narrower distribution and for fewer steps overall, therefore it is unsurprising that GANCO performs better across different distributions at test time.  Whilst the authors do compare GANCO to a genetic based (GB) method for generating data, they also highlight that it is unsuitable for the task at hand: "The resulting distribution [from GB] still approximately follows the base training distribution. It would be extremely hard for the genetic operators to attain instances following a significantly different distribution.”.  Given GANCO requires training a second adversarial agent (which comes with a significant overhead),  I believe justifying this additional training as necessary is important.  At the least, I would like to see comparisons to:

 	1. The performance on an RL agent trained on multiple/all target distributions.  GANCO would, of course, not be expected to beat this, however it is unclear from the current results if GANCO is achieving most of the benefits of training on in-distribution data, or only providing fractional improvement compared to what could be achieved.

	2. The performance of an agent trained on the curriculum of instances generated by GANCO *from a different training run*.  It would be highly insightful to know whether it is the ability of GANCO to tailor instances bespoke to the current agent, or it is simply the ability to generate many significantly different distributions from the base distribution, that provides the bulk of the performance improvement.  If it was demonstrated that the adaptive nature of GANCO is key, this would, in my opinion, significantly strengthen the paper and further justify the design choices of the framework.

- I do not believe Figure 2 is suitable as it is a set of ‘plots’ denoting how the authors hope GANCO will change the performance across a distribution (e.g. performance is strictly improved for all instances and all stages of the pipeline), and does not present any data or additional insight.  The intuition that providing additional data from distributions on which the agent performed poorly and help to learn more general policies is clear and suitably presented in the rest of the paper without the need for Figure 2, therefore I would suggest removing it.

**Additional comments, question and errata**

- The authors state that both the inputs to the generating network are sampled noise, and that the outputs are also per-node distributions from which node attributes are sampled.  What is the purpose of have two sources of stochasticity?  Initially I interpreted the input noise as sampling the specific problem instances distribution, and the output as sampling a value from this distribution.  However as the attributes for each node are sampled sequentially, presumably the input noise is resampled at each state too?  Of course it is not a major issue, but I would appreciate clarity for my own insight!

- The authors claim that the challenge of generalising to out-of-distribution (OOD) test-time instances is “particularly severe for neural combinatorial optimization (NCO) models because the solution quality intricately depends on the instance distributions”.  Whilst I would agree that OOD generalisation is challenging and important, it is not clear to be that NCO models find it especially difficult compared to the multitude of other ML/RL applications.  Indeed, as solving COPs is often extremely (NP-)hard, an alternative stance would be that ML4CO models will never learn to analytically solve even in-distribution tasks of meaningful size, an so will instead naturally rely on sub-optimal heuristics that may in fact generalise quite well (e.g. a greedy algorithm is simple to learn, sub-optimal, but often shows good generalisation).  Could the authors clarify their meaning, or alternatively simply acknowledge that generalisation is difficult and important in general, with COPs being no exception?

- Is there a particular reason the authors settled on alternately training the solver and generator, as a naive implementation might train both jointly (or indeed train exclusively on the generated instances)?

- Typo in the caption of Fig 3c: (c) “CANCO-POMO on CVRP100”.

summary_of_the_review: Whilst the GANCO framework is novel as a whole, it is the combination of existing ideas and methodologies (e.g, learning construction heuristics for CO problem and adversarial training).  The field of ML4CO is active the particular problem considered in the is work, generalising to OOD test-time data, is ubiquitous - therefore, in my opinion, the paper comfortably reaches the required standard in terms of novelty and potential interest.  Ultimately then, I believe it comes down to whether the demonstrated empirical performance is sufficiently strong, or if the core idea of adversarial instance generation is sufficiently well justified and investigated.  My feeling is that it is not clear cut, with the experimental results impressive, but to me only unequivocally demonstrating that training on a broader distribution of tasks results in a more general agent.  Overall, however, there is enough justification of the GANCO framework in the latter sections, for me to lean towards acceptance (ultimately, I find the ideas and results in the paper interesting, and therefore feel the same can be said for others working in the field).  With that said, I would be more confident and comfortable in my recommendation if the adaptive nature of the adversarial instance generation that is core to GANCO could be demonstrated as a key element in the frameworks empirical success (as discussed in detail in my main review).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Over the last few years, several machine learning based approaches have been proposed to solve common combinatorial optimization problems, such as the traveling salesman problem. However, it's never been entirely clear how well the previous work generalized to out of distribution instances. This paper proposes to improve generalization through dataset augmentation.
Specifically, the paper proposes to train a model (aka the generator) that is used to drive the creation of training instances on which the neural network used to solve the combinatorial problem (aka the optimizer) does poorly. The authors then show that training the optimizer model on a set of examples taken from the original dataset as well as created under the guidance of the generator model results in better performance than training the optimizer model on the original dataset only. 
main_review: The paper is reasonably well written, though section 3.1 would be easier to follow if the architecture of the generator model was described using a figure instead of just text. Moreover, since the authors evaluate their approach on optimizer models trained through reinforcement learning (according to section 2), I would have liked to see a discussion of other approaches that have been taken to improve the robustness of RL techniques in the related work section.

The evaluation section demonstrates empirically that data augmentation helps improve the performance of ML based combinatorial optimization techniques: it covers several enough combinatorial optimization problems (e.g TSP, CVRP, OP, PCTSP, KP) to give confidence to the reader that it is very likely to succeed on any combinatorial optimization problem. Furthermore, it evaluates the effectiveness of data augmentation in conjunction with 2 common optimizer models, AM and POMO, which indicates that data augmentation can be leveraged to improve the effectiveness of several prior work in this area.

However, it is widely known that data augmentation helps the performance of neural networks, and the authors fail to demonstrate the effectiveness of their particular flavor of data augmentation. At the very least, they should have compared their approach against random data augmentation as well as against a simple policy that generates n examples, and keeps the k% of these n examples on which the optimizer model performs the worst. In other words, the paper needs to demonstrate that the generator model truly learns how to improve the quality of the dataset on which the optimizer model is trained. Put another way, the authors explain very well what they set out to accomplish in figure 2. They need to demonstrate in their evaluation that they accomplished this. 

summary_of_the_review: This paper attempted to tackle an important problem which hasn't received the attention it deserved, namely ensuring that neural networks trained to solve combinatorial optimization problems generalize well. They proposed a theoretically sound approach to augment the original dataset with additional training examples created under the guidance of an auxiliary 'generator' model to cover the gaps in the original dataset. However, they failed to demonstrate that the effectiveness of this 'generator' based approach.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a way to generate training examples for neural combinatorial optimisation  (NCO) methods (specifically evaluated on POMO and AM) that leverages an adversarial RL policy trained in stages to generate instances that maximise the performance advantage of a baseline CO method over the NCO method. The method is tested on a variety of CO problems and shows improved OOD generalization especially for larger problem instances.
main_review: Strengths:

- paper is well written
- good evaluation
- intuitively understandable method with good results, both in terms of generalisation and speeding up training (which is expected due to other works establishing selecting tough training instances helping convergence)

Weaknesses
- the concept reminds me strongly of https://ai.googleblog.com/2021/03/paired-new-multi-agent-approach-for.html which should be cited 
- I wonder how much of the improvement is due to simply training on more examples? did you try generating random problem instances of multiple distributions and training AM for the same number of episodes? I'd still expect the adversarial method to be more universal, but if the distributions we might expect are somewhat known, domain randomisation can be computationally cheaper and simpler than this setup. Especially if a small subset of distributions can capture most of the expected variation across test distributions.

Other comments:

- instead of training in stages, did you attempt alternating the optimizer and the adversary on a per step basis?
summary_of_the_review: The paper presents an intuitive approach to generating training examples, makes it work and does a good evaluation. However, similar work has been done in the RL domain and other supervised training domains before (e.g. using GANs for data augmentations) so giving a marginal accept for now.  If the missing citation is added, my questions are answered and the edge the *adversarial* augmentation has over *random* augmentations (or simply perturbing the network slightly and training for longer) I'm willing to update my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a generative adversarial training pipeline for general combinatorial optimization problems, aiming to improve the generalization ability of learned neural network solvers on unseen data distributions. In experiments, the authors select the attention model as the neural network solver, and REINFORCE, POMO as the RL algorithms. The experiment results are comprehensive on various routing problems, and on the knapsack problem.
main_review: ## Strengths
1. The idea of generative adversarial training for combinatorial optimization is new.
1. The experiment results are comprehensive and detailed, mainly on various settings of routing problems.
1. Figure 1 presents a clear and straightforward overview of the proposed framework.

## Weaknesses
1. My first concern about this paper is the motivation and necessity for developing generative adversarial training methods for combinatorial optimization problems. Since we are handling a reinforcement learning problem without any supervision labels, it seems not very difficult to obtain a batch of problem instances that lie within the distribution of test instances (for example, loading the business data from last month and using them for training, and predicting on the next month). More aggressively, you may also train (or more properly, finetune) a neural network on the test instance if the time budget is acceptable. Besides, the results on the "base" distribution entry show that the performance of the model will probably degenerate after generative adversarial learning, but such property seems undesirable, especially we can easily obtain a batch of test instances in real-world applications.
1. An assumption made in this paper is that the neural network has enough capacity to learn the input-to-optimal mapping of combinatorial problems from various distributions. If the network does not have enough capacity, the expressiveness of the neural network should be our major concern instead of the generalization ability. However, the results of neural networks, whether aided with adversarial learning or not, are all inferior to the traditional solvers. It makes me doubt the capacity of the current neural network models.
2. Besides, is there any special design to prevent the neural network from "forgetting" the original distribution? The results on the "base" distribution entry show that the performance of the model will probably degenerate after generative adversarial learning, suggesting that the model seems incapable to learn the input-to-optimal mapping under the current pipeline and is likely to forget some information from the original distribution.
1. Concerning the experiment part, it will be very interesting to see the result of traditional algorithms that are configured to run comparatively faster with learning-based methods. For example, the number of trials of LKH-3 is configurable to control the runtime of the heuristic and the current configuration (10000 trials as written in the appendix) seems too time-consuming. On page 7 the authors mentioned that "Generally, their (the neural network's) run time is much shorter than the traditional algorithm as indicated in the table(s), which is a core strength of deep models." I doubt whether such a conclusion still holds if you replace your current solvers with a well-configured LKH-3 solver. It will make much more sense if you do not set a large number of trials for LKH-3 to force it to run super slow.
1. The authors make an effort on including the knapsack problem. However, there is still room for further improvement if the authors can include more problems beyond routing problems because the title of this paper is claimed for general combinatorial optimization problems.
1. The writing and formatting of this paper need to be improved to meet the quality of ICLR papers. See some examples in "detailed comments" below.

## Other detailed comments:
1. It seems unclear whether the objective function $O_\Phi(x)$ is to be maximized or minimized. Maximizing or minimizing $O_\Phi(x)$ will correspond to different formulations of $G(x,\Phi, B)$.
1. In Table 1, the inference times of AM and GANCO-AM are regarded as the same, which is reasonable because they share the same model architecture. And in Table 2 and 3, the inference times of AM/GANCO-AM and POMO/GANCO-POMO are different, which is also reasonable due to random noises in experiments. Although both of the writings may be reasonable, I think it will be better to maintain a consistent style of tables in one paper. 
2. In Table 2, the inference time of HGS (~0.5 hours for the smallest sized problem) seems unacceptable as an intermediate step when computing the reward signal in reinforcement learning. 
1. What is the time cost for the pertaining stage and the proposed adversarial training steps?

summary_of_the_review: The generative adversarial training for combinatorial optimization in this paper is novel, the experiment results are detailed and comprehensive. However, the motivation, writing, and the experiment part of this paper seem to have room for further improvement, and I am suggesting a rejection for this time and I am wishing to see an improved version in the future.
review_title: null

Meta-review: ## A Brief Summary
Recent works in deep learning have shown that it is possible to solve [[combinatorial optimization]] problems (COP) with neural networks.  However, generalization beyond the examples seen in the training set is still challenging, e.g., generalizing to TSP with more cities than the ones seen in the training set. This paper proposes the GANCO approach, where a separate generative neural network based on GAN generates new hard-to-solve training instances for the optimizer. The optimizer and the generative network are trained in an alternating fashion. The authors have run experiments with the attention model (AM) and POMO with their GAN-based data augmentation approach. The authors provide experimental results on several well-known COPs, such as the traveling salesman problem.

## Reviewers' Feedback

Below, I will summarize some reviewers' feedback and would like the authors to address the cons noted below.
### Reviewer sEuD

*Pros:*
- Paper is well-written.
- Task is important and well-motivated.
- Good experimental results.
*Cons:*
- The paper's core contribution on the necessity of adversarial entities is not well-motivated.
- Missing baselines:
- RL agent trained on all target distributions. To figure out how far GANCO is from the optimal policy.
- The performance of an agent trained on a curriculum.
- Figure 2 is unnecessary/redundant in the paper.



### Reviewer tjCH
*Cons:*
- The paper is reasonably written. However, it would be much easier to follow with a few changes. For example, section 3.1 explains the architecture and, in related works, a more comprehensive overview of the methods to improve the robustness of RL methods.
- It is widely known that data augmentation helps in deep learning. The paper's claims would be more convincing if it provided some crucial baselines, such as comparing different data augmentations methods and carefully ablating them.
  
### Reviewer N945
*Pros:*
- Well-written
- Good evaluation
- Simple model with good results
*Cons:*
- Missing citation to the PAIRED paper.
- How important are the adversarial entities generated? Is it possible to achieve similar results by just training on more samples?
- Missing baselines: Instead of training in stages, alternate optimizer and generator network per step basis.

### Reviewer mumN
*Pros:*
- The proposed approach is novel.
- Comprehensive and extensive experiments.
- Figure 1 provides a good summary of the approach.

*Cons:*
- Motivation is for the GANCO is not very convincing.
- Concerns about the capacity of the neural nets used in the paper.
- Concerns on forgetting the original distribution.
- Concerns about experimental evaluation protocol.
- Including experiments on routing problems to show the generality of the proposed approach.
- Request for improvements in the writing and the formatting of the paper.

## Key Takeaways and Thoughts
I think this paper attacks an interesting problem. As far as I am aware of the approach is novel. However, generative adversarial networks have been used in the machine learning literature for data augmentation and RL for augmenting the environment (see the PAIRED paper.) GAN type of approaches hasn't been used to improve the generalization of the deep learning approaches for COP. The results look promising. However, as pointed out by Reviewer mumN and tjCH, this paper would benefit more from further ablations, particularly the necessity of adversarial generation part to make the arguments more convincing. As it stands now, it is not clear where exactly the improvements are coming from. Reviewer mumN also raised some concerns about the poorly configured LHK3 baseline in the discussion period. Furthermore, I agree with the reviewer mumN and tjcH that this paper would benefit from restructuring to make it flow better. I do think that this paper needs another round of reviews. I would recommend the authors go over the feedback provided here and address them for future submission.## References
Decision: Reject