Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Simulated annealing is a widely-used stochastic optimization approach. The paper presents a general approach for learning the proposal distribution for simulated annealing. The paper formalize simulated annealing as an MDP and consider the problem of learning proposal distribution as leaning a policy. They consider a lightweight policy architecture and compare two training methods, Proximal Policy Optimization (PPO) and Evolution Strategies (ES). They run experiments on four well-known benchmark domains: the Rosenbrock function, the Knapsack problem, The Bin Packing problem, and the Travelling Salesperson problem. Their results show that neural simulated annealing outperforms "vanilla SA" and that training on small problems generalizes well to larger problems.
main_review: Strengths:
- The paper present a simple, lightweight approach for neural simulated annealing that outperforms "vanilla SA". The approach is general and amenable to many problems.
- The approach shows promising results w.r.t generalization to larger problem sizes (a challenging aspect for many approaches to neural-guided combinatorial optimzation).

Weaknesses:
- Limited technical novelty: while the idea of learning a policy for SA using RL is novel, the technical solution follows existing approaches for policy learning using RL.
- While the experimental results are strong for a domain-independent approach, it does not seem to outperforms state-of-the-art for each problem. Further, the experiments are missing some important results. In particular: 
    1) comparisons with "vanilla SA" and not state-of-the-art SA solutions that are tailored to each problem.
    2) In Knapsack, Bin packing, and TSP, the neural approaches that are tailored to the domain outperform neural SA.
    3) Results on larger sizes and additional configurations of the other neural approaches are missing, e.g., it is not clear why the results for Costa use 500 steps and the results for GAT-T use 1000 steps, or why the number of steps is fixed across larger problem sizes (while the neural SA seems to require increasingly more time to solve).
summary_of_the_review: Overall, I think it an interesting and lightweight approach that is general (amenable to many problem) and shows good performance w.r.t generalization to larger problems. However, it has limited technical novelty and the experimental results shows it is not as effective as tailored classical or neural solutions.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduces Neural Simulated Annealing (Neural SA), a heuristic for general combinatorial optimisation (CO) problems.  Considering SA as a two stage process where, (i) given an initial state and new state is proposed and (ii) the new state is probabilistically accepted/rejected depending on the solution quality and current temperature (via a standard Metropolis-Hastings step), Neural SA parameterises the proposal step, (i), with a neural network that outputs a distribution over possible perturbations.  Framing the overall optimisation trajectory as a Markov Decision Process, the proposal policy can be trained using standard RL algorithms (both PPO and evolutionary strategies are used).  Experiments on four tasks — a simple proof-of-concept minimisation and three canonical CO problems — show that the learnt proposal policy significantly outperforms random perturbations (‘Vanilla SA’).  Whilst Neural SA does not surpass SOTA ML algorithms on the CO problems, it still provides strong performance with very small network sizes and the learnt policy can generalise to larger instances than those on which it was trained.
main_review: **Strengths**

- The paper is broadly well written, but I have provided a list of minor typo’s in Errata the author’s may wish to tidy.

- I believe the algorithm is novel and well motivated.  There have been several methods that combine SA and RL, however the authors provide a good review in Sec 2.1 and I agree that directly learning the proposal distribution is, to the best of my knowledge, novel in the context discussed within the paper. (With regards to methods that instead learn a temperature schedule, I feel [1] and [2] are a couple of recent works that may also merit inclusion in the review.)  However, I do feel the authors should avoid claiming that one of their contributions is presenting “simulated annealing as a Markov decision process, bringing it into the realm of reinforcement learning”, as previous works, including [1-2], already frame SA as an MDP and apply RL.

- That Neural SA improves over vanilla SA so significantly, despite the very modest network sizes, is impressive.

**Weakenesses**

- The author’s emphasise the ability of neural SA to generalise to larger problem sizes that those on which it was trained, remarking that “this type of transfer learning is rare in ML4CO” (Sec 4) and that the demonstrated generalisation is “a truly remarkable feat, as transfer learning is notoriously difficult [in RL and CO]” (Sec 5). Generalisation to unseen instances is indeed a highly sought after feature of CO heuristics, however I do not feel these claims are suitably justified.  Many ML heuristics can be applied to larger problems on which they were solved, including many of those referenced in the paper (for example Dai et al., 2017, Kool et al., 2018, Bresson & Laurent, 2021, Gasse et al 2019, Gupta et al 2020, Kool et al., 2021, Fu et al 2021 to select a few from the introduction).  Moreover, as SA can also generalise to larger instances (in the sense that, if we hand-craft a proposal policy and temperature schedule on small instances, it would not immediately fail on larger ones) I would suggest the author’s either (i) justify why Neural SA might naively be expected to not generalise (as to me, I would of been more surprised if it hadn’t) or (ii) demonstrate that the generalisation performance is significantly better than other heuristics or RL baselines.  If neither of these is possible I believe it would be appropriate to soften the discussion of generalisation, as it is not a unique feature of Neural SA, or demonstrated to be particularly exceptional.

- The information presented in the experimental results could be improved.  For the Bin-Packing problem (Table 2), Neural SA is shown to outperform SCIP however SCIP was given a 1 minute time limit and there is not reference to the run time of Neural SA.  If Neural SA was better within a commensurate time-budget, this would strengthen the reported result significantly.  If this is not the case, then the wall-clock time remains important context.  The TSP results in Table 3 are a subset of the full results in Table 11 (found in the appendix), however the strongest baseline (Fu et al) is not reported in the main text.  As such, it feels like the author’s claim to be “neck-and-neck” for TSP100 given Table 3, falsely gives the impression of Neural SA approaching SOTA RL performance.  I would ask the authors to either rectify the omission and update the text accordingly, or justify why Fu et al is not a better choice of baseline than those presented in Table 3.

- I believe the core idea of combining learnt local-improvement operators with a Metropolis-Hasting’s search procedure is very interesting, however experimental results are underwhelming.  Vanilla SA is poor (compared to other baselines) on the CO problems presented, and whilst learning the proposal step improves performance, by the author’s admission it is not state-of-the-art.  It would be interesting to select a problem where SA is already very strong, for example Ising model’s/Max-Cut problems, and see if Neural SA can still improve performance.  Alternatively, investigating wether the addition of a Metropolis-Hastings step to existing strong ML4CO algorithms that learn local improvement operators (e.g. [3]), would help to determine whether Neural SA’s advantage over SA arises from simply learning a better local-improvement step in general, or it the policy is bespoke to SA.

[1] “Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization”, arXiv:2002.04676 (2020)

[2] "Finding the ground state of spin Hamiltonians with reinforcement learning”, Nat Mach Intell 2, 509–517 (2020). 

[3] "Exploratory Combinatorial Optimization with Reinforcement Learning”, arXiv:1909.04063 (2019).

**Errata**

A few minor points that do not require and response from the authors.

- First paragraph of pg. 7: “groundtruth” - I think “ground truth” is more standard.
- First paragraph of pg. 7: “Results in Table 1, show that…” - I do not think there should be a comma after ‘Table 1’.
- First paragraph of pg. 8: “We sample from the policy ancestrally,” - should this be autoregressively?
- First paragraph of pg. 9: “WE use the” - erroneous capitalisation.
summary_of_the_review: Whilst I believe the core idea of Neural SA is interesting and novel, I do not feel that it is sufficiently explored or demonstrates strong enough empirical performance to recommend acceptance at this time.  This is primarily because the algorithm neither achieves SOTA performance on considered problems, or demonstrates unique benefits not found in other systems (I believe the ability to generalise to larger problems was intended to address the second point, however, for the reasons discussed above, I am not convinced by this argument).  In my comments above, I have tried to present a few suggestions for how the paper could be extended to address these concerns - and would of course be open to pushback from the authors - however in it’s current form, my opinion is that this is just below the acceptance threshold.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new Neural Simulated Annealing approach to solve optimization problems. Specifically, reinforcement learning is used to optimize the proposal distribution in Simulated Annealing (SA). The proposed neural SA is empirically shown to be more effective than the classic SA without learning on four optimization problems. Although the neural SA outperforms SA, its performance is still not comparable to  other baselines. 

main_review: Pros:
=

1. The idea is interesting and sound. Simulated annealing can be viewed as Markov decision process naturally, which motivates the use of reinforcement learning.

2. Although there has been some studies for hybridizing SA and learning methods, the authors have distinguished their work from existing studies clearly. 

3. The experiments on four optimization problems demonstrate that the proposed neural SA works better than the SA alone. 


Cons
= 

1. Although the proposed neural SA improves over SA, its performance is still not comparable to other baselines (even a greedy method). I think this is the main weakness of this paper. Further, the authors claim that  "We demonstrate superior performance to off-the-shelf CO tools on the Knapsack, Bin Packing, and Travelling Salesperson problems, in terms of solution quality and wall-clock time." However, this is clearly NOT the case by looking at the experimental results. 

2. There is no runtime comparison in Table 1 (Knapsack problem) and Table 2 (for Bin Packing problem). Hence, there is no way to assess how fast the proposed method compared to other baselines. 

3. OR-Tools should be tested for the traveling salesman problem as well, since it is a general method and has been tested on the other two problems. 
summary_of_the_review: I like the idea of viewing simulated annealing as the Markov decision process, and using reinforcement learning to enhance simulated annealing. My major concern is that the proposed neural simulated annealing is clearly not competitive with other baselines.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a new method called Neural Simulated Annealing, which builds upon traditional Simulated Annealing (SA) by introducing a lightweight neural network as a policy that determines the proposal distribution for SA. The neural network policy is trained by a reinforcement learning (RL) mechanism, which relies on re-formulating the Markov chain of the underlying combinatorial optimization problem as a Markov Decision Process (MDP).  The authors outline how their re-formulation fits into the definitions of SA and MDPs in Section 2 and Section 3, defining the state, action, transition function and reward function (immediate or primal) be aligned to enable RL to train the neural network policy while also being amendable to the general SA optimization structure. The authors then provide an argument for why their method has the same convergence guarantees as traditional SA.

Following the general definition of their method and their algorithm, including the definition of the neural network policy, the authors then show results for 4 tasks: Rosenbrock's function, the Knapsack problem, Bin Packing and the Traveling Salesman problem applying their method, traditional SA and relevant methods from the literature. The results from the authors generally show improvement of their method compared to traditional SA and outperformance compared to other methods in some, but not all, of the cases. The authors also provide an analysis of the results of Neural Simulated Annealing for the Knapsack and Bin Packing problem claiming that the behavior of the policy generally matches an intuitive behavior expected for solving those problems. Finally, the authors provide a discussion of their overall results and some ideas for future work.
main_review: **Strengths** 

I believe the paper has the following strengths:
- A modular and practical improvement on a traditional optimization technique (SA), which demonstrates clear improvement on the optimization benchmarks provided.
- A detailed and thorough description of the method, including how SA can interact with reinforcement learning in a scalable manner. 
- A thorough analysis of the results provided by the Neural Simulated Annealing policy for the Knapsack and Bin Packing problem, which showcase that the policy is behaving as expected. This strengthens the claim that Neural Simulated Annealing is modular, but significant, improvement on SA.

**Weaknesses**

I think that the paper could be improved by:
- Providing a discussion and analysis of the compute cost incurred by Neural Simulated Annealing compared to traditional SA. While it appears that Neural Simulated Annealing provides performance improvements, it would be good to understand the costs of those performance improvements.
- A discussion of whether the proposal distribution can be determined other than using softmax across the entire SA chain. Would good advantages and disadvantages of other methods?
- A discussion on what the authors think would be needed to achieve better results on the benchmarks where SOTA wasn't achieved, such as the TSP. Is it mainly a question of letting the algorithm run longer or are there other things that can be done to arrive at better solutions?
- Stating the size of the combinatorial search space for each experiment that is performed. E.g. Knap200 has a search space of X, which scales to Y in Knap2K because of Z. This will add further clarity to how the method scales to more challenging settings.

While I don't think this is necessary at this moment, I think it would have been nice to have the following as well:
- Results on practical, "real-world" problem where the advantages of Neural Simulated Annealing could be shown. TSP is a good approximation to many COs found in real-world settings, but it would have been nice to see the algorithm applied to other examples as well. 
- An ablation of the state definition to see what information may or may not be critical for NSA to tackle the problem effectively. 
- A discussion on how advances in RL, such as multi-task learning or meta-learning, could be used to potentially generalize NSA across different tasks. 

summary_of_the_review: I think that the paper presents a detailed and thorough framework for improving simulated annealing with a good set of experimental evidence to support the claims. I hope that the feedback provided will help the authors further improve the current draft during the discussion phase, and am open to adjusting my score based on the discussion. 

I am also happy about the reproducibility statement provided by the authors, which outlines that the code will be published upon formal publication of the paper. 

----- Update During Discussion Period -----

The authors addressed many of my questions and reservations in a satisfying manner. Assuming the authors make the changes they outline in their response, I think the paper will be significantly improved and merit acceptance. I am increasing my score to reflect this and will follow up on the technical discussion.
review_title: null

Meta-review: This work presents the Neural Simulated Annealing (NSA) approach as a heuristic for general combinatorial optimization problems. After revising the paper and reading the comments from the reviewers, here are the general comments: 

- In general, the paper is clear enough. The contributions are stated in a proper way.
- The novelty is rather limited, but the key idea of using neural networks in SA, and training it with RL, has merit.
- This approach has merit but the novelty is very limited.
- The NSA improves the vanilla SA, but the benchmark reveals that NSA is not enough competitive with other state-of-the-art methods. 
- The benchmark does not reveal enough information about the NSA against the SOTA methods.
- The work needs technical improvements and validation is required before accepting the work.
Decision: Reject