Neural Simulated Annealing
Authors: Alvaro Correia
Daniel E. Worrall
Roberto Bondesan
Venue: ICLR 2022 Submitted (2022)
Keywords: Combinatorial Optimization
Reinforcement Learning
Evolution Strategies
Simulated Annealing

Abstract: Simulated annealing (SA) is a stochastic global optimisation technique applicable to a wide range of discrete and continuous variable problems. Despite its simplicity, the development of an effective SA optimiser for a given problem hinges on a handful of carefully handpicked components; namely, neighbour proposal distribution and temperature annealing schedule. In this work, we view SA from a reinforcement learning perspective and frame the proposal distribution as a policy, which can be optimised for higher solution quality given a fixed computational budget. We demonstrate that this Neural SA with such a learnt proposal distribution outperforms SA baselines with hand-selected parameters on a number of problems: Rosenbrock's function, the Knapsack problem, the Bin Packing problem, and the Travelling Salesperson problem. We also show that Neural SA scales well to large problems while again outperforming popular off-the-shelf solvers in terms of solution quality and wall clock time.

Under review as a conference paper at ICLR 2022
NEURAL SIMULATED ANNEALING
Anonymous authors Paper under double-blind review
ABSTRACT
Simulated annealing (SA) is a stochastic global optimisation technique applicable to a wide range of discrete and continuous variable problems. Despite its simplic- ity. the development of an effective SA optimiser for a given problem hinges on a handful of carefully handpicked components; namely. neighbour proposal dis- tribution and temperature annealing schedule. In this work, we view SA from a reinforcement learning perspective and frame the proposal distribution as policy, which can be optimised for higher solution quality given a fixed computational budget. We demonstrate that this Neural SA with such learnt proposal distri- bution outperforms SA baselines with hand-selected parameters on a number of problems: Rosenbrock's 's function, the Knapsack problem, the Bin Packing prob- lem, and the Travelling Salesperson problem. We also show that Neural SA scales well large problems while again outperforming popular off-the-shelf solvers in terms of solution quality and wall clock time.
INTRODUCTION
There are many different kinds of combinatorial optimisation (CO) problem, spanning bin packing, routing, assignment, scheduling, constraint satisfaction, and more. Solving these problems while sidestepping their inherent computational intractability has great importance and impact for the real world, where poor bin packing or routing lead to wasted profit or excess greenhouse emissions (Salimifard et al. 2012). General solving frameworks or metaheuristics for all these problems are desirable, due to their conceptual simplicity and ease-of -feee-ff--plooeen, but require manual tailoring to each individual problem. One such metaheuristic is Simulated Annealing (SA) (Kirkpatrick al., 1987), simple, and equally very popular, iterative global optimisation technique for numerically ap- proximating the global minimum of both continuous- and disccreee-vrrihle problems. While SA has wide applicability, this is also its Achilles' Heel, leaving many design choices to the user. Namely, user has to design 1) neighbourhood proposal distributions, which define the space of possible tran- sitions from solution X2 at time & to solutions X at time & + 1, and 2) temperature schedule, which determines the balance of exploration to exploitation. In this work, we mitigate the need for extensive finetuning of SA's parameters by designing a learnable proposal distribution speeding up convergence while limiting computational overhead to O(N) per step for problem size N.
CO algorithms fall into two categories: exact and approximate. Exact methods such as dynamic programming (Bellman 1952) and branch-and-hound (Land & Doig 1960) find global minimisers x", but are slow due to the NP-hardness of many CO problems. Approximate algorithms therefore seek a good enough solution under practical computational constraints. SA is one such approximate algorithm. In recent years there has been an explosion of works (Bengio et al. 2018) in machine learning for CO (MLACO). In MLACO, lot of work has focused on end-to-ent neural architectures (Bello al. 2016 Vinyals al. 2017 Dai et al.. 2017 Kool al. 2018 Emami & Ranka 2018 Bresson & Laurent 2021). These work by brute force learning the instance to solution mapping -nn CO these are sometimes referred to as construction heuristics. Other works focus on learning good parameters for classical algorithms, whether they be parameters of the original algorithm (Kruber ct al. 2017 Bonami et al. 2018)) or extra neural parameters introduced into the computational graph of classical algorithms (Gasse al.] 2019 Gupta et al., 22000] Kool et al., 2021; de O. da Costa et al., 2020 Wu et al., 2019b] Chen & Tian 2019] Fu et al. (022). Our method, neural simulated annealing (Neural SA) can be viewed as sitting firmly within this last category.
SA is an improvement heuristic; it navigates the search space of feasible solutions by iteratively ap- plying (small) perturbations to previously found solutions. Figure] I iillutrrates this for the Travelling

---

Under review as a conference paper at ICLR 2022
X
(i,j)
X6+1 x
X = X
solution
pack
propesal
accept/reject proposal
Figure 1: Neural SA pipeline for the TSP. Starting with a solution (tour) we sample an action (i from our learnable policy/proposal distribution, defining start and end j points 2-opt move (replacing two old with two new edges). Each pane shows both the linear and graph-based representations for a tour. From x and we form proposal x' which is either accepted or rejected according to the traditional MH step used in SA. Accepted moves assign X = x'; whereas, rejected moves assign X Xg.
Salesperson Problem (TSP), perhaps the most classic of NP-hard problems. this work, we pose this as Reinforeement Learning (RL) agent navigating environment, searching for better solu- tions. In this light the proposal distribution is an optimisable quantity. Conveniently, our method inherits convergence guarantees from SA. We are able directly optimise the proposal distribu- tion using policy optimisation for both faster convergence and better solution quality under fixed computation budget. We demonstrate Neural SA on four tasks: Rosenbrock's function, toy 2D optimisation problem, where we can easily visualise and analyse what is being learnt; the Knapsack and Bin Packing problems, which are classical NP-hard resource allocation problems; and the TSP.
Our contributions are:
We pose simulated annealing Markov decision process, bringing into the realm of reinforcement learning. This allows us to optimise the proposal distribution in a principled manner. Our method inherits all the convergence guarantees of vanilla simulated annealing.
We demonstrate superior performance to off-the- CO tools on the Knapsack, Bin Pack- ing, and Travelling Salesperson problems, in terms of solution quality and wall-clock time.
We show our methods transfer to problems of different sizes, and also perform well on problems up to 40x larger than the ones used for training.
Our method competitive within the MI4CO space, only using a very lightweight neural architecture, with number of learnable parameters of the order of 100s or fewer.
2 BACKGROUND AND RELATED WORK
Here we outline the basic simulated annealing algorithm and its main components. Then we provide an overview of prior works in the machine learning literature which have sought to learn parts of the algorithm or where SA has found uses in machine learning.
Combinatorial optimisation A combinatorial optimisation problem is defined by a triple (V, N, EE) where v/ E V are problem instances (city locations in the TSP), X' is the set of feasible solutions given sb (Hamiltonian cycles in the TSP) and E X' V + an energy function (tour length in the TSP). Without loss of generality, the task is to minimise the energy minxex E'x; +b). CO problems are in general Na-hard, meaning that there no known algorithm solve them in time polynomial in the number of bits that represents problem instance.
Simulated Annealing Simulated annealing (Kirkpatrick et al. 1987) ) is a metaheuristic for CO problems. It builds an inhomogeneous Markov chain Xo - - - ... for X₁ E X, asymp- totically converging to a minimizer of E. The stochastic transitions X - X depend on two quantities: 1) proposal distribution, and 2) a temperature schedule. The proposal distribution π. X' + P(2)), for PX()) the space of probability distributions on X', suggests new states in the chain. It perturbs current solutions to new ones, potentially leading lower energies immediately or later on. After perturbing a solution X₁ - x'. a Metropolis Metropolis-Hastingg Hastting (MH) step (Metropo-
lis et al. 1953
Hastings 1970) is executed. This either accepts the perturbation (x++1 x')
2

---

Under review as a conference paper at ICLR 2022
rejects it (Xt+1 xx) see Algorithm [ for details. The target distribution of the MH step has form p(x[Tx) x exp(-E(x)/ /Tx), where Th is the temperature at time k. In the limit Tj - O, this distribution tends to a of Dirac deltas the minimisers of the energy. The temperature is annealed, according to the temperature schedule, 71, 72, from high to low, to steer the target distribution smoothly from broad to peaked around the global optima. The algorithm is outlined in Algorithm [] Under certain regularity conditions and provided the chain is long enough, it will visit the minimisers almost surely (Geman & Geman 1984). More concretely,
lim P 10
Xk E arg min Exx; +b) 1.
(1)
xEX
Despite this guarantee, practical convergence speed is determined by π and the temperature sched- ule, which are hard to fine-tune. There exist mroblem-speciffe heuristics for setting these (Pereira & Fernandes 2004 Cicirello 2007), but in this paper we propose to learn the proposal distribution.
2.1 SIMULATED ANNEALING AND MACHINE LEARNING
A natural way to combine machine learning and simulated annealing is to design local improvement heuristics that feed off each other. Notable examples are Cai et al. (2019) and Vashisht et al. (2020) where RL is used to find good initial solutions later refined by standard SA. The two methods only interact via shared solutions, fundamentally different our approach, as focus augmenting SA with RL optimisable components. In fact, our method is perfectly compatible with theirs and any other SA application. Other works proposed the optimising components of SA. In particular, Blum et al. (2020) study the design of optimal cooling schedules using data, deriving theoretical guarantees on sample complexity. However, the authors do not provide empirical evaluations and focus exclusively on the cooling schedule while we concentrate on the proposal distribution. Simi- larly, Wauters et al. (2020) and Khairy et al. (2020) use RL to find optimal parameters for quantum variants of SA but their methods are not readily applicable to standard SA.
More closely to our method, other approaches improve the proposal distribution. In Adaptive Sim- ulated Annealing (ASA) (Ingber) 1996) the proposal distribution is not fixed but evolves throughout annealing process as a function of the variance of observed solution fitness. ASA improves the convergence of standard SA but is not learnable like Neural SA. To the best of our knowledge, Mar- cos Alvarez et al. (2012) are the only others to learn the proposal distribution for SA, but they rely on supervised learning, requiring high quality solutions or good search strategies to imitate, both expensive to compute. In contrast, Neural SA is fully unsupervised, thus easier to train and extend to different CO tasks. Finally, many Monte Carlo methods use proposal distribution. Noé et al. (2019) and Albergo et al. (2019) recently studied how to learn a proposal distribution of an MCMC chain for sampling the Bolızmann distribution of a physical system. While their results serve as motivation for our methods, we investigate a completely different context and set of applications.
Our work falls under bi-level optimisation methods, where an outer optimisation loop finds the best parameters of an inner optimisation. This encompasses situations such as learning the parame- ters (Rere al., 2015) or hyperparameters of a neural network optimiser (Maclaurin et al. [015] Andrychowicz et al. (0166) and meta-learning (Finn et al. 2017). However, most recent approaches assume differentiable losses on continuous state spaces [ Likhosherstov et al. (202T); Di et al. (202T): Vicol et al. (2021). while we focus on the more challenging CO setting. We note, however, methods in Vicol et al. (202I) are based on evolution strategies and could be used in the discrete setting.
2.2 MARKOV DECISION PROCESSES
Simulated annealing naturally fits into the Markov Decision Process (MDP) framework plain below. An MDP M = (S, R, P.7) consists of states s E S, actions a E A, an immediate reward function R: : S x A x S + E. a transition kernel P S x A - IP(S), and discount factor j0, 1). On top of this MDP we add a stochastic policy
ex-
S + P(A). The policy and transition (So. an, $1, 01, SK) ), which is a sample from the distribution P(r[z) = po(5o) I P(sx+1|sk, ax) TT (az (sk) and where 8q ~ Pa is sampled from the start-state distribution pu- One can then define the discounted return R(T) = =IK=1 7'rx over a trajectory, where Fą = R(sk. ag $K+1). ). We say that we have solved an MDP if we have found a policy that maximises the expected return Pr) (
kernel together define a length- K trajectory
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Neural simulated annealing. To get back to vanilla SA, replace the parametrised pro- posal distribution To with a uniform distribution π over neighbourhoods N(()..
Require: Initial state so = (Xo: 3 To), proposal distribution т, transition function P. temperature schedule Ti 2 T2 2 T3 .... energy function (()
for k = 1: K do
To (St)) Uniform(u; 0,
Sample action
b Metropolis Hastiinss step
u < exp { (x': x) Exxii 4))/TT;} then
Sk+1 +-+-- (x', 1, Th+1)
Accept
else
Sk+1 + (xk, $ Tx+1)
Reject
end if end for
METHOD
Here we outline our approach to learn the proposal distribution. First we define an MDP correspond- ing to SA. We then show how the proposal distribution can be optimised and provide a justification that this does not affect convergence guarantees of the classical algorithm.
3.1 MDP FORMULATION
We formalise SA as an MDP, defining states s = (x, T) E S for aa a parametric description of the problem instance
in Section 2 and T the instantaneous temperature. Examples are in Section[4 4 Our actions a E AA perturb (x, tb, T) + (x', vb, 7),, where x' E [N() neighbourhood of x. It is common to define small neighbourhoods, to limit energy variation from one state to the next. This heuristic discards exceptionally good and exceptionally bad moves, but given that bad moves are commoner than good ones, it generally leads to faster convergence.
x) is a solution in the
The MH step in SA can be viewed as a stochastic transition kernel, governed by the current temper- ature of the system, with transition probabilities following a Gibbs distribution and dynamics
Xk+11
Xk. with probability 1-p.
X': with probability p
where p min (I, + (E(x' -(xxx)))))
}
(2)
This defines a transition kernel 1( a), where 8 = (x', 1/, T) or Sk+1 = (x,, $b T), the two outcomes of the MH step. For rewards, we use either the immediate gain F(xx; {b) E(xx+1; xb) ) or the primal reward -5 minxex E(x; We explored training with two dif- ferent methods: Proximal Policy Optimisation (PPO) (Schulman et al. 2017) and Evolution Strate- gies (ES) Salimans et al. (017)). The immediate gain works best with PPO, where at each iteration of the rollout, the immediate gain gives frninne feedback whether the previous action helped or not. The primal reward works best with ES, because is non-local returning the minimum along an entire rollout at the very end. We explored using the acceptance count but found that this sometimes led to pathological behaviours. We also tried the primal integral (Berthold) (003)), which encourages finding good solution fast, but found we could not get training dynamics to converge.
3.2 POLICY NETWORK ARCHITECTURE
SA chains are long. It is because of this that we need as lightweight a policy architecture as possible. Furthermore, this architecture should have the capacity scale to varying numbers of inputs, so that we can transfer experience across problems of different size N. We opt for very simple network, shown in Figure 2 For each dimension of the problem we map the state (x, 1b, T) into a set of features. For all problems we try. there is natural way to do this. Each feature is fed into an MLP, embedding it into a logit space, followed by a softmax function to yield probabilities. The complexity of this architecture scales linearly with N, which is important since we plan to evaluate it many times. A notable property of this architecture is that is is permutation equivariant (Zaheer let al., 2017), an important requirement for CO problems. Note that model is a permutation equivariant set-to-set mapping, but we have not used attention or other kinds of pairwise interaction to keep the computational complexity linear in the number of items.
4

---

Under review as a conference paper at ICLR 2022
Convergence Convergence of SA the op- timum in the infinite time limit requires the Markov chain of the proposal distribution to be irreducible (van Laarhoven & Aarts 1987, Thm
[x; th, 7)
my (a(s)
To
1ttens
sof softmax ffaaxax
Fu
6, Chap 3), meaning that for any temperature, any two states are reachable through a sequence of transitions with positive conditional proba- bility under Our neural network policy satis- fies this condition as long as the softmax layer does not assign zero probability to any state, condition which is met practice. Thus Neural SA inherits convergence guarantees from SA.
fa
inputs
MLP
logits
policy
Figure 2: (a) Policy network: The same MLP is applied all inputs pointwise. We use this net- work in all CO problems.
4 EXPERIMENTS
We evaluate our method on 4 tasks Doskks-Rosenbrcck's function, the Knapsack, Bin Packing, and Trav- elling Salesperson problems-fixing the architecture and overall hyperparameters of Neural SA. This shows the wide applicability and case of use of our method. For each task (except for Rosen- brock's function) we test Neural SA on problems of different size N, training only on the smallest. Similarly, we consider rollouts of different lengths, training only on short ones. This accelerates training, showing Neural SA's generalisation capabilities. This type of transfer learning is rare in ML4CO, and is merit of our lightweight, equivariant architecture. In all experiments, we adopt an exponential multiplicative cooling schedule as originally proposed by Kirkpatrick et al.) (1987), with T3 a TT is computed for set To and Tk. This allows us vary the rollout length while maintaining the same range temperatures for every run. Exact training details are in the Appendix.
4.1 THE ROSENBROCK FUNCTION
The Rosenbrock function is non-convex over Euclidean space. Of course, gradient-based optimisers are more suited to this problem, but we use it as toy example to showcase the properties of Neural SA. Our policy an axis-aligned Gaussian Ta (a)s)) variance oe of shape 2 + 16 + 2 and a ReLU in the middle. Proposals are x' = x + and the Figure Bal Mathematically the function is
((; 0, (s:)). with MLP-parameterised
state is S (xt, a, b, T.). An example rollout
E(zo, T1;a, b) = (a =0)² + b(x1 - 20)?
(3)
which has global minimum x = (a, a²). We contrast Neural SA against vanilla SA with fixed proposal distribution, i.e. ass)) = σ, for different averaged over 217 problem instances. This shows in Figure 3d that no constant variance policy can outperform an adaptive policy on this prob- lem. Plots of acceptance ratio in Figure (b) show Neural SA has higher acceptance probability early in the rollout, a trend we observed in all experiments, suggesting its proposals are skewed towards lower energy solutions than standard SA. Figure shows the variance network o (s;) function of time. It has learnt to make large steps until hitting the basin, whereupon large moves will be rejected with high probability, variance must be reduced.
18-
141
30
(a) 2D rollout
(b) Acceptance ratios
(c) a by iteration
(d) Baseline sweep
Figure 3: Results on Rosenbrock's 's function: (a) Example trajectory. moving from red to blue, show- ing convergence around the minimiser (1,1) (b) Neural SA has higher acceptance ratio than the baseline, trend observed in all experiments, (c) Standard deviation of the learned policy a func- tion of iteration. Large initial steps offer great gains followed by small exploitative steps, (d) A non-adaptive vanilla SA baseline cannot match adaptive one, matter the standard deviation.
5

---

Under review as a conference paper at ICLR 2022
1.0
0.8
Knapsack state
20
30-
40
0.0
260
400
60D
mbc
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Iteration
Weights
Weights
(a) Solution per annealing step.
(b) KnapNet Policy (logit space)
Figure 4: (a) Exemplar knapsack rollout on KNAP50: Each row is an item and each column is subsequent iteration. Items absent from the knapsack in black and those present are in white. Items are ordered by value-to-weight ratio in ascending order top to bottom. We see that light, valu- able objects are held in the knapsack longer than heavy, valueless ones. (b) Knapsack logits: Policy logits for = 0 and I; 1 are shown in each pane. Light valuable objects are favoured to insert. Once inserted the policy downweights an object's probably of flipping state again. Interestingly, the ejection probability of heavy, valueless objects is low, perhaps because this only makes sense close to overflowing, but the policy does not receive free capacity as a feature.
4.2 KNAPSACK PROBLEM
The Knapsack problem is a classic CO problem resource allocation. Given a of items, each of different value v; >> O and weight w, >> O, the goal is to find subset that maximises the sum of values while respecting a limit W on its total weight. This has corresponding integer linear program
N-1
minimise B(x;b)) =
Σ T=
subject to Σ wet S W,
Nt E (0,
(4)
for 'out of the bin' and x; for in the bin'. Our proposal distribution flips individual bits, one at time, with the constraint that cannot flip 0 - 1 if the bin capacity will be exceeded. The neighbourhood of x₃. thus all feasible solutions at Hamming distance of 1 from XĄ. We use the proposal distribution described in Section 3.2 and illustrated in Figure [] consisting of a pointwise embedding of each item its weight, value, occupancy bit, the knapsack's 's overall capacity, and global temperature-inge a logit- space, followed by a softmax. Mathematically the policy and state aate-nctiion to proposal mapping are
Solutions represented as binary vector x, with
ne ((ls) = softmax (z);,
2; = fe( W/, 14 W, T])
x' x + onehot(1)
mod! 2.
where fo is a very small two-layer neural network 5 > 1 with a ReLU nonlinearity between the two layers. Actions are sampled from the categorical distribution induced by the softmax, and cast to one-hot vectors onehot(i).
Neural networks have been used to solve the Knapsack Problem in Vinyals et al. (0017) Nomer et al. 2020)), and Bello et al. (2016). We follow the setup of Bello et al. (2016), honing in on
Table 1: Average cost of solutions for the Knapsack Problem across five random seeds and, in parentheses, optimality gap to best solution found among solvers. Bigger is better. " *Vauues as reported by Bello et al. (2016) for reference.
Random Search
Bello RL
Bello
SA
Ours (PPO)
Ours (ES)
Greedy
OR- Tools
KNAP50
17.91*
19.86"
20.07*
18.90 (5.82%)
19.87 (0.90%
19.95 (0.65%
19.04 (0.60%)
20.12 (0.00%)
KNAP100
33.23*
40.27*
40.50"
36.75 26%)
39:92(1.479) (1.43%%
39.90 (1.9%%
40.17 (0.81%)
40.41 (0.00%)
35.95*
57.10"
(14.91%))
55.63
(3.25%%)
37.30
57.65. (0.00%)
KNAP500
126.94 (11.93%%
139.66 (3.1%%)
141.01 (2.17%)
143.77 (0.25%)
144.14 (0.014(0.00%)
(0.00%)
KNAPIK
254.44 (11.9666)
280. 300.33 (2.9989
2292.40 46 (2.22066
288.64 (0. 133%)
289.01 (0.0056)
KNAP2K
(12.08%)
(2.92%)
563.75(2
(0.066%)
577.28 (0.00%))

---

Under review as a conference paper at ICLR 2022
Item selector
Bin selector
50
Source capacity
Targel used capacity
20
Greedy Neural SA
10
Phima loss
0.6
10
30
25
0.0
100
200
100
600
500
0.6 Item weight
Itaration
Item weight
(a) Bin Packing primal objective
(b) Bin Packing policy (logits)
Figure 5: (a) Plot of the BIN50 primal objective for vanilla, Neural, and Greedy Neural SA. 25th 50th and 75th percentiles shown: Greedy and Neural SA have faster convergence than vanilla SA. Prolonged sampling improves over the greedy version. (b) Policy for the Bin Packing Problem: The bin packing policy consists of two networks, an item selector and a bin selector. The item selector uses item weight and bin used capacities select an item to move. The bin selector then places this item in a bin, based on target bin fullness and selected item weight. The learnt policy is very sensible. The item selector looks for a light item in an under-full bin. The bin selector then place sthis in an almost-full bin. We mask bins with insufficient free capacity, hence the triangular logit-spaces.
self- self-generated datasets: KNAP50, KNAP100 and KNAP200. KNAPN consists of N items with weights and values generated uniformly at random in (0, and capacities C5o 12.5, C100 25, and C200 = 25. We use OR Tools (Perron & Furnon) to compute groundtruth solutions. Results in Table 1 show that Neural SA improves over vanilla SA by up 10% optimality gap, and heuristic methods (Random Search) by much more. Neural SA falls slightly behind two methods by |Bello] al. (2016), which (1) a large attention-based pointer network with several orders of magni- tude more parameters in Bello RL, and (2) this coupled with 5000 iterations of their Active Search method. It also falls behind greedy heuristic for packing a knapsack based on the value-to-wedd weight ratio. In Figure 4 we analyse the policy network and a typical rollout. It has learnt mostly greedy policy fill its knapsack with light, valuable objects, only ejecting them when full. This is line with the value-to- weight greedy heuristic. Despite not coming top among methods, we note Neural SA typically within % of the minimum energy, while not designed for this problem particular.
4.3 BIN PACKING PROBLEM
The Bin Packing problem similar the Knapsack problem in nature. Here, one wants to pack all of N items into the smallest number of bins possible, where each item E {1,...,,N. ,N has weight wi and we assume, without loss of generality, bins of equal capacity W 2 max; (w;) there would be no valid solution otherwise. If zij denotes item i occupying bin j, then the problem can be written as minimising an energy
N
minimise F(x; xb) =
Σ
yj
1=1
N-1
N-1 yj min 1, Σ Tajz
subject
Wr S W.
Σ
Tij
= 1,
Fi E (0,1)
(8)
==
hin capacity constraint
bin per item
hin occupancy indicator
where the constraints apply for all and j. We define the policy in two steps: we first pick an item and then select bin j place it into. We can then write Te (i,j)(s) ( which we parametrise as
(ils) softmax (z)m)) ) Te (jlss i) = softmax (zhin)))
So ([wi, Cb(s): T]), item #
(9)
2j
So(lur, Cj. T)),
(10)

---

Under review as a conference paper at ICLR 2022
Table 2: Average cost of solutions for the Bin Packing Problem across five random seeds and, in parentheses, optimality gap to best solution found among solvers. Lower is better. We set time out of minute per problem for Or-Tools; * indicates only the trivial solution was found in this time.
SA
Ours (PPO)
Ours (ES)
OR-Tools (SCIP)
FFD
BIN50
29.48
(10.37%)
27.29 27.29 (2.17%)
27.24 (1.98%)
26.71 (0.00%)
27.10 27.10 (1.46%)
BIN100
60.03 (13.46%)
53.47 (1.06%)
53.38 (1.29%)
53.91 (1.89%)
52.91 (0.00%)
BIN200
121.21 (16.27%)
105.63 (1.32%)
(1.13%)
109. 19 (4.74%)
104.25 (0.00%)
BIN500
302.79
(17.81%)
259.08 (0.80%)
260.27 (1.26%)
267.63 (4.13%)
257.02 (0.00%)
BIN0000
605.09
(18.77%)
512.66 (0.63%)
516.84 (1.45%)
1000"
509.46 (0.00%)
BIN2000
1209. 48 (18.82%)
1017.88 (0.00%)
1028.67 (1.06%)
2000"
1028.67 (1.06%)
where b(i) is the bin item i is in before the action (in terms of Zaj, we have 20(()) = 1), oj is the free capacity bin j (c, = W - شin w;Jr;)), ) and both fo and fe are lightweight architectures 3 + 16 + 1 with a ReLU nonlinearity between the two layers. We sample from the policy ancestrally, sampling first an item from (i)s), followed by a bin from (i js, i). Results Table 2 show that our lightweight model is able to find a solution to about 1% higher energy than the minimum found by FFD Johnson| (173)) a very strong heuristic for this problem (Rieck] 202I). We even see that very often beat the SCIP (Gamrath et al. 2020a b) optimizer in OR-Toolls which timed out on most problems. Figure 5a compared convergence speed of Neural SA with vanilla SA and a third option, Greedy Neural SA, which uses argmax samples from the policy. The learnt policy, visualised in Figure 5b has much faster convergence than the vanilla version. Again, we see that our method, although simple, is competitive with hand-design alternatives.
4.4 TRAVELLING SALESPERSON PROBLEM
Imagine you will make round road-trip through N cities and want to plan the shortest route vis- iting each city once: this is the Travelling Salesperson Problem (TSP) (Applegate al. (006). The TSP has been long time favourite of computer scientists due to its easy description and NP-hardness. Here we use as an example of a difficult CO problem. We compare with Con- corde (Applegate et al. 2006) and LKH-3 (Helsgaun 2000), two custom solvers for TSP. Given cities 1 {0, 1, ..., . - If with spatial coordinates c, E [0, 1]3, we wish to find a linear or- dering of the cities, called a tour, denoted by the permutation vector (ro, (1:--.;N-11) for I; E {0, 1,..., N }} such that
N
minimise E(x; vp)
|ca.11
Cx. Cril12
(11)
subject to x; # x. for all i + and xy {0, (0,1,-.. N 1},
(12)
where we have defined Fy = Zo for convenience of notation. Our action space consists of so-called 2-opt moves (Croes) 1958). which reverse contiguous segments of tour. An example of a 2-opt move is shown in Figure g We have a two-stage architecture, like in Bin Packing, which selects the
Table 3: Comparison of Neural SA against different solvers and deep learning models on TSP. Extended version of this table is provided in the appendix. Lower is better.
TSP20
TSP50 Glap
TSP190
TSP200
TSP500)
Cost
Clap
Time
Cost
Gap
Time
Cost
Gap
Cost
Gap
CONCORDE
3,836
0.00%
48s
5.696
0.00%
2m
7.764
0.00%
7m
10.70
0.00%
38m
16.54
0.00%
7h:58m
LKH13
3,836
0.00%
Im
5.696
0.00%
14m
7.761
0.00%
1b
10.70
0.00%
21m
16.54
0.00%
15155m
3,881
1.17%
10s
5.943
4.34%
Im
8.341
7.43%
6m
11.98
11.96%
30m
20.22
22,25%
2h:35m
OURS (PPO)
0.42%
17c
5,762
1.16%
7.907
1.85%
14m
3.27%
17.87
8.04%
5h. 3m
OURS (ES)
3.840
0.10%
17%
5.828
2.32%
2m
8.191
5.50%
14m
11.74
9.725%
32m
20.27
22.55%
5h 3m
GAT-T: GOO0)
3.84
0.03%
12m
5.75
0.85%
16m
8.01
3.245
25m
Costa(500)
3.84
0.01%
5m
10m
8

---

Under review as a conference paper at ICLR 2022
start and end cities of the segment to reverse. Denoting i as the start and j as the end
( (i.))ls) no (o)
(13)
To ( (ils) = softmax (z); 2: = -fo([cx] -14 T()
(14)
To (ils d) softmax (z)z: Zj - fo ((x 1x TD,
(15)
where X(--13+1] are the indices of city and its tour neighbours i- and i + 1. WE use the standard policy: So has architecture 7 - 16 - and fo. 13 + 16 - 1. We test on publically available TSP20/50/100 (Kool al. 2018) with 10K problems each and generate TSP200/500 with IK tours each. Results, in Table 11 show Neural SA improves on vanilla SA. Neural improvement heuristics methods, GAT-T 1000} (Wu et al. 2019b) and (50) (de O. da Costa al. 2020), designed for routing problems, outperform us for small TSPs, but are neck-and-neck for TSPI00. Given Neural SA not custom designed for TSPs, we view this as surprisingly good.
DISCUSSION
Neural SA is general, plug-and-play method, requiring only definition of neighbourhoods and training problem instances. Our lightweight architecture shared for all problems we consider and, with maximum of 384 parameters on TSP, 160 for Bin Packing, and 112 for Knapsack can achieve within a few percentage points or less of global minimia. It can be trained with any policy optimi- sation method making it highly extendable. We found no winner between PPO and ES, apart from on the TSP, where PPO excelled. We also observed PPO to converge ~ 10x faster than ES, but ES policies were more robust, such as when we switched to greedy sampling. Here the PPO policy was usually hurt, but ES was not. An interesting observation we made was that the acceptance rate over trajectories was problem dependent, always higher in Neural SA than vanilla SA. This contradicts conventional wisdom that it should be held at 0.44 throughout rollout (Lam & Delosme, 1988).
While never achieving SOTA, this was never to be expected, given SA is an approximation meta- heuristic, but if left running long enough, results are guaranteed to improve, following from the convergence guarantees of SA. It is also worth pointing out we did little to no fine-tuning of the hyperparameters of SA, and yet achieved positive results even with an unsophisticated temperature cooling schedule. This demonstrates that besides improving convergence speeds, Neural SA is also more robust to variations in the optimisation dynamics of SA. In fact, our experiments show Neural SA generalises across different problem sizes and rollout lengths; a truly remarkable feat, as trans- fer learning notoriously difficult in reinforcement learning and combinatorial optimisation. That makes Neural SA an attractive alternative in many applications where problem sizes and time con- straints fluctuate, especially when computational power or energy consumption are limiting factors.
CONCLUSION
We presented Neural SA, neurally augmented simulated annealing, where the SA chain is trajec- tory from an MDP. In this light, the proposal distribution could be interpreted as a policy, which could be optmised. This has numerous benefits: 1) accelerated convergence of the chain, 2) abil- ity to condition the proposal distribution on side-information 3) we do not need groundtruth data to learn the proposal distribution, 4) our architectures are very lightweight and can be run on CPU unlike many contemporary ML4CO methods, 5) the method scales well due to its lightweight com- putational overhead, 6) we can train on small problems and generalise to much larger ones. Of these contributions, we believe 6 is the most impressive. Many MLACO solutions currently use huge transformer- based models, with computation scaling quadratically per step with problem size; whereas, neural SA instead scales linearly. This enabled us to yield results on larger problem sizes.
Removing pairwise interactions in the model, however, could be its limiting factor. In all experi- ments we were not able to achieve the minimum energy, but could usually get within a percentage point. The model also has no in-built termination condition, neither can provide a certificate on the quality of solutions found. There is still also the question of how to tune the temperature sched- ule, which we did not attempt in this work. These shortcomings are all points to be addressed in upcoming research. We are also interested in extending the framework to multiple trajectories, such as in parallel tempering Swendsen & Wang (986) or genetic algorithms Holland (1992). For these, would maintain population of chains, which could exchange information.
9

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
and 4.4 we provide details of the exact models we use and the datasets. Each dataset was generated synthetically, apart from the TSP20, 50, and 100 datasets, which are publically available. We have reported all our numbers, with standard deviations, and provide precise training details in the appendix. As a precaution, we plan to release code upon acceptance of this paper, for complete transpareney.
Our method is outlined in Algorithm [ In sections
4.1
ETHICS STATEMENT
Solving real world combinatorial optimisation problems can reduce waste, allocating searse re- sources near optimally. This paper in particular introduces a lightweight method to improve upon simulated annealing, a popular combinatorial optimisation method, such that can be targeted at a broad set of problems with ease. Where simulated annealing itself is deployed, for moral or likewise immoral purposes, is beyond the scope of this paper, but based on typical examples combinatorial optimisation problems, convergence speed we observed also reduce total FLOPs and therefore carbon footprint, a common problem with large-scale optimisations and deep learning models.
advances probably cause little downstream harm. The improvements in
REFERENCES
MS Albergo, G Kanwar, and PE Shanahan. Flow-based generative models for markov chain monte carlo in lattice field theory. Physical Review D, 100(3):034515, 2019.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
David L Applegate, Robert Bixby, Vasek Chvátal, and William Cook. The Traveling Salesman Problem: Computational Study. Princeton University Press, 2006.
Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences, 38(8)711-719, 1952. ISSN 0027-8424. doi: 00.1077/pnaa.38.8.11.. URL https:
// www. pnas org. /tt.://conten////////1
Irwan Bello, Hieu Pham, Quoe Le, Mohammad Norouzi, and Samy Bengio. Neural combina-
torial optimization with reinforcement learning. CoRR, abs/1611.09940, 2016. URL http:
/arxávvorg//ab//1611..11
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial op-
timization: methodological tour d'horizon. CoRR, abs/1811.06618, 2018. URL http:
/aaxii..rrg/abs/1111.111
Timo Berthold. Measuring the impact of primal heuristics. Operations Research Letters, 41(6): URL https:
611-614, 2013. ISSN 0167-6377. doi: https:/bol..rr/0..011......11111
w/wwwwsk. www.aciencedirest.
wwt. http://cc......ccoeoooc.eeeeetta
Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing, 2020.
Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning classification of mixed-integer quadratic programming problems. In Willem-Jan van Hoeve (ed.), Integration of Constraint Pro- gramming, Artificial Intelligence, and Operations Research, pp. 595-595-4 Cham, 2018. Springer International Publishing. ISBN 978-3-319-930311
Xavier Bresson and Thomas Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXiv: 103.0022, 2021.
Qingpeng Cai, Will Hang, Azalia Mirhoseini, George Tucker, Jingtao Wang, and Wei Wei. Rein- forcement learning driven heuristic optimization, 2019.
10

---

Under review as a conference paper at ICLR 2022
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 32:6281-6292 2019.
Vincent A Cicirello. On the design of an adaptive simulated annealing algorithm. In Proceedings of the international conference on principles and practice of constraint programming first workshop on autonomous search, 2007.
G. A. Croes. A method for solving traveling-salesman problems. Operations Research, 6:791-812, 1958.
Hanjun Dai, Elias B. Khalil, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. CoRR, abs/1704.01665, 2017. URL http:://axxii
org/abs/1704 01665
Paulo R. de da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2- opt heuristies for the traveling salesman problem via deep reinforcement learning. CoRR, 0bs/2004.01608, 2020. httllttt///aaatttit http:///.wrr//a/////////// 01608
Patrick Emami and Sanjay Ranka. Learning permutations with sinkhorn policy gradient. CoRR, abs/1805, 000.000000 2018. htLl:/ttee//aa.ci.orr//a////////
07010
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In International Conference on Machine Learning, pp. 1126-1135. PMLR, 2017.
Zhang-Hup Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7474-7482, 2021.
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christo- pher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Mil- tenberger, Erik Mühmer, Benjamin Müller, Mare E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020a.
DtT_D/D___TML/220000 0012220003377551110 URL http:/t/// //t://wwwe www. www.wpptiim.oo zat watiaiiinnn oo- int.ttioonoot www.:aatoooooooo.ooooo.ommoo htt.:oonooo.a..rrrr////////////0
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christo- pher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Mil- tenberger, Erik Mühmer, Benjamin Müller, Mare Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. ZepoRt 20- 20-10, Zuse Institute Berlin, March 2020b.
URL http:///bnnrrreeoeeeeeee wwcessiviin...mm www.nng..eeeeeee uur/ nbo de 0297 2-iz------ 78023
Maxime Gasse, Didier Chetelat, Nicola Ferroni. Laurent Charlin, and Andrea Lodi. Ex- act combinatorial optimization with graph convolutional neural networks. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL Intps://prooeedings neuriis.ers...... cc/paperr2019//ilee cd4c225788..aabe888555055
Paper. pdf
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6):
721-741, 1984.
Prateek Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. CoRR, abs/2006.1522 15212, 2020. URL org/ batg/abs//0 2006 15212
W. K. Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):77-10, 04 1970. ISSN 0006-3444. doi: 10.1093/biomee/57.1997 URL
https://doi .ww./oogg..... wtt../.../.....//...... 1093/b omet/577.... 1ttp://m...10/mm.mmt///5/77

---

Under review as a conference paper at ICLR 2022
Keld Helsgaun. An effective implementation of the lin kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-1)) 130, 2000.
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology. Control and Artificial Intelligence. MIT Press, Cambridge, MA, USA, 1992. ISBN 0262082136.
Lester Ingber. Adaptive simulated annealing (asa): lessons learned. Control and Cybernetics, 25(1), 1996.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pp. 4882 4892. PMLR, 2021.
David S Johnson. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. On learning paradigms for the travelling salesman problem. arXiv preprint arXiv:1910.072.0. 2019.
Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. Learning to optimize variational quantum circuits to solve combinatorial problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34003))3367-2335, Apr 2020. ISSN 2159-5399. doi: 10. 10.1669/aaii, v34103.5616
URL httt::://a..co...rr//000...1111. 160.//6119999 www.aa..v440000 v34103. 5616
doi
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL htth:
6980
Scott Kirkpatrick, Daniel Gelatt and Mario P Vecchi. Optimization by simulated annealing. In Readings in Computer Vision, pp. 606-615. Elsevier, 1987.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. arXiv preprint arXiv:2 1756, 2021.
Markus Kruber, Marco Lübbecke, and Axel Parmentier. Learning when to use a decomposition. pp- 202-210, 05 2017. ISBN 978-3-319-59775-1 doi: 10. (007/978--3-199-5777--
Jimmy Lam and Jean-Marc Delosme. Performance of new annealing schedule. In Proceedings of the 25th ACM/IEEE Design Automation Conference, pp. 306-311, 1988.
A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28(3);pp. 497-520, 1960. ISSN 00129682.
Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared Davis, and Adrian Weller. Debiasing first-order heuristic for approximate bi-level optimization. arXiv preprint 206.022006.02487, 2021.
Dougal Maclaurin, David Duvenaud, and Ryan P. Adams. Gradient-based hyperparameter optimiza- tion through reversible learning, 2015.
Alejandro Marcos Alvarez, Francis Maes, and Louis Wehenkel. Supervised learning to tune sim- ulated annealing for in silico protein structure prediction. In ESANN 2012 proceedings, 20th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, pp. 49-54. Ciaco, 2012.
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Ed- ward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics. 2186):1087-100 1953. doi: 10.194./1.1699114. URL https: /ooi. orq/1C. 1063/1 1699114
12

---

Under review as a conference paper at ICLR 2022
Frank Noé, Simon Olsson, Jonas Köhler, and Hao Wu. Boltzmann generators: Sampling equilibrium states of many-body systems with deep learning. Science, 365(6457), 2019.
Hazem AA Nomer, Khalid Abdulaziz Alnowibet, Ashraf Elsayed, and Ali Wagdy Mohamed. Neural knapsack: A neural network based solver for the knapsack problem. IEEE Access, 8:224200- 224210, 2020.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Anal I. Pereira and Edite M. G. P. Fernandes. A study of simulated annealing variants. In Proceedings of XXVIII Congreso de Estadística e Investigación Operativa, 2004.
Laurent Perron and Vincent Furnon. Or-tools. URL
optimm z on/
L.M. Rasdi Rere, Mohamad Ivan Fanany, and Aniati Murni Arymurthy. Simulated annealing algo- rithm for deep learning. Procedia Computer Science. 72:137-144, 2015. ISSN 1877-0509, doi: https://doi.org/100 10t..0000.ii.pp.c.015........... URL https: //t////ww /www. sciencedirect. com/ The Third Information Systems Interna-
tional Conference 2015.
Bastian Rieck. Basic analysis of bin-packing heuristies. arXiv preprint arXiv:2 12235, 2021.
Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as a scalable alterna- tive reinforcement learning. ArXiv, abs/1703.03864, 2017.
Khodakaram Salimifard, Hamid Shahbandarzadeh, and Ramin Raeesi. Green transportation and the role of operations research. In 2012 International Conference on Traffic and Transportation Engineering (ICTTE 2012), pp. 74-79, 2012.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:
2017.
Robert H. Swendsen and Jian-Sheng Wang. Replica monte carlo simulation of spin-glasses. Phys. Rev. Lett. 57:2607-2609, Nov 1986. doi: 10.1103/Physeeeeeett.7.....
URL https://
link. wtw.appp..gg/oooooaoa dtog///oo//10/ 111.1..11111000 11111101PPHS 1113:11haaeeeettt... 27.2677,
P.J. van Laarhoven and E.H. Aarts. Simulated Annealing: Theory and Applications. Mathematics
and Its Applications. Springer Netherlands, 1987. ISBN 9789027725134. URL https://
books. co. widpooksiidd-iiieoi......
IqUabbDp____ Iigaooooseid---Uuuuouuoo
Dhruv Vashisht, Harshit Rampal, Haiguang Liao, Yang Lu, Devika Shanbhag, Elias Fallon, and Levent Burak Kara. placement in integrated circuits using cyclic reinforcement learning and simulated annealing, 2020.
Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased gradient estimation in unrolled com- putation graphs with persistent evolution strategies. In International Conference Machine Learning. pp. 10553-10563. PMLR, 2021.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks, 2017.
Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro. Reinforcement- learning-assisted quantum optimization. Physical Review Research, 2(3), Sep 2020. ISSN 2643- 1564. doi: 10. 10. 1001100/hhyyrrrresrrch2.2...
URL http: dx. doi wow.orr//0..103//////0
PhysRevRessarch..2200
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving the travelling salesman problem. 2019a.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving the travelling salesman problem. CoRR, abs/1912.05784, 2019b. URL http://arxis www.worg///o/.o..ooo.oo...oooo.r httpab////111107771
13

---

Under review as a conference paper at ICLR 2022
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and
Alexander J. Smola. Deep sets. abs/1703.061 14, 2017. URL http: org/ /bs/ 1 1703. 06114
14

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENTAL INFORMATION AND RESULTS
Our code was implemented Pytorch 1.9 (Paszke et al. 2017) and run in a standard machine equipped with single GPU RTX2080. The randomly generated datasets used for testing can be recreated by setting the seed of Pytorch's random number generator to O.
Table 4: Running Times
Knapsack
Bin Packing
Ours
OR-Tools
Ours
OR-Tools
50N
0.74s
0.01s
1.14s
54s
100N
1.13s
< 0.01s
2.27s
56s
200N
3.01s
< 0.01s
4.79s
2 1m
500N
9.40s
0.01s
14.18s
1m
1000N
38.68s
0.02s
37.67s
1m
2000N
130.86s
0.08s
121.748
1m
A.1 KNAPSACK PROBLEM
Data We consider problems of different sizes, with KNAPN consisting of N items, each with weight wN and value i sampled from a uniform distribution, W4, 2/ M(o.))- Each problem has also an associated capacity, that is, the maximum weight the knapsack can comport. Here follow (Bello et al. (0166) and set C50 12.5, C100 = and C200 = 25. However, for larger problems set CN N/8.
Training We train only on KNAP50 with short rollouts of length K = 100 steps. The model trained for 1000 epochs each of which run on 256 random problems generated on the fly as described in the previous section. We set initial and final temperatures to To and Tk. and compute the temperature decay as a (Tk (
PPO: Both actor and critic networks were optimised with Adam (Kingma & Ba 2013) with learning rate of 1e-3, weight decay of 1e-2 and B = (0.9, 0.999). To and 7 0.1.
ES: We use a population of 16 perturbations sampled from Gaussian of standard deviation 0.05. Updates are fed into SGD optimizer with learning rate 1e-3 and momentum 0.9. To and Tk- = 0.1.
Testing We evaluate Neural SA test sets of 1000 randomly generated Knapsack problems, while varying the length of the rollout. For each problem size N, we consider rollouts of length K N, K 2.N. 5N and K 10N. The initial and final temperatures are kept fixed Ti 1 and (T)
Tk = 0.1, respectively, and the temperature decay varies as function of K,
We compare our methods against one of the dedicated solvers for knapsack in OR-Tools (Perron & Furnon) (KNAPSACK MULTIDIMENSION BRANCH AND BOUND SOLVER). We also com- pare sampled and greedy variants of Neural SA. The former naturally samples actions from the proposal distribution while the latter always selects the most likely action.
15

---

Under review as a conference paper at ICLR 2022
Table 5: ES results on the Knapsack benchmark. Bigger is better. Comparison among rollouts of different lengths: 1, 2, 5 or 10 times the dimension of the problem.
Greedy
Sampled
OR- Oo-Tools
x1
x1
x2
x5
x10
KNAP50
16.59
19.45
19.70
19.86
19.95
20.07
KNAP 100
31.15 1 .00
39.07
1 001
39.49 1 .01
39.76
1 .01
39.90 1 .01
40.50
KNAP200
55.96 1 .00
53.72 .02 .02
55.21 1 .02
56.22
.02
56.58 1 .01
57.45
KNAP500
135.92
.00
134.20
1: .05
137.89 1 .03
140.20
1 .02
141.01 1 .03
144.14
KNAPIK
259.20
269.21
276.48
280.94
282.46 .03
289.01
KNAP2K
489.02 - .00
537.53
+ .08
551.92 + .07
560.75 .07
563.75 = .02
577.28
Table 6: PPO results on the Knapsack benchmark. Bigger better. Comparison among rollouts of different lengths: 1, 2, 10 times the dimension of the problem.
Greedy
Sampled
OR-Tools
x1
x1
x2
x5
x10
KNAP50
19.46 1 .00
19.31 1 .011
19.43 1 .01
19.70 1 .01
19.87 1 .01
20.07
KNAPI00
38.79 +: .00
38.53 1 .02
38.92 1 .02
39.56
.02
39.92 1 .01
40.50
KNAP200
47.90 .00
48.76
.04
51.13 + -03
54.05
+ .22
55.65 + .01
57.45
KNAP500
117.51 .00
121.88
+ .05
128.78
.03
136.12 .03
139.66 = .02
144.14
KNAPIK
234.31 -00
245.48
.12
259.80
+ .05
273.96
..0
280.39 + .01
289.01
KNAP2K
464.92 + .00
491.48
48
.10
520.61 + .06
548.15
560.40 = .02
577.28
A.2
BIN PACKING PROBLEM
Data We consider problems of different sizes, with BIN consisting of N items, each with weight (size) sampled from uniform distribution, wA ~ ((..))- Without loss of generality. we also assume N bins, all with unitary capacity. Each dataset BINN in Tables and g contains 1000 such random Bin Packing problems used evaluate the methods test time.
Training We train only BIN50 with short rollouts of length K 100 steps. The model is trained for 1000 epochs each of which is ran on 256 random problems generated on the fly as described in the previous section. We set initial and final temperatures to To and Tk, and compute the temperature decay as a = (Tk/To)
PPO: Both actor and critic networks were optimised with Adam (Kingma Ba 2015) with learning rate of 2e-4, weight decay of 1e-2 and B (0.9, 0.999). To and Tk 0.1.
ES: We use a population of 16 perturbations sampled from a Gaussian of standard deviation 0.1. Updates are fed into an SGD optimizer with learning rate 1e-3 and momentum 0.9.
To 0.1 and Tk le 4.
Testing We evaluate Neural SA on test sets of 1000 randomly generated Bin Packing problems, while varying the length of the rollout. For each problem size N. we consider rollouts of length K N, = 2N, = 5N and K = 10N. The initial and final temperatures are kept fixed to To and Tk 0.1, respectively, and the temperature decay varies function of K, (Tk/To) *
We compare Neural SA against Fistr-iit (FFD) [Johnson] 1973). a powerful heuristic for the Bin Packing problem, and against OR-Tools (Perron & Furnon) MIP solver powered by SCIP Gammath et al. 2020a). The OR- Tools solver can be quite slow on Bin Packing so we set time out of one minute per problem so that we could complete
We also compare sampled and greedy variants of Neural SA. The former naturally samples actions from the proposal distribution while the latter always selects the most likely action.
16

---

Under review as a conference paper at ICLR 2022
Table 7: ES results on the Bin Packing benchmark. Lower is better.
Greedy x1
Sampled
OR-Tools
FFD
x1
x2
x5
x10
BIN50
27. 97.62++.0
27.43-t.01
27.36+.01
27.29
27.24::01
26.71
27.10
BIN
53.80=t000
53.63-.00
53.54#.01
53.44=.01
53.38=.01
53.91
52.91
BIN200
105 63.1.00
105. 005.78.1.02
105.641.00
105.511.01
105.43..01
109.19
104.25
BIN500
259.09+-00
260.86+.03
260.65+.01
260.42+-02
260.27--02
267.63
257.02
BINIK
512.662.00
517.87+.02
517.46+.02
517.08=.02
516.842.01
1000"
509.46
BIN2K
1017.88 = .00
1030.66#.01
1029.89+.01
1029.11#.02
1028.67=.02
2000"
1028.67
Table 8: PPO results the Bin Packing benchmark. Lower is better.
Greedy
Sampled
OR- Tools
FFD
x2
x5
x10
BIN50
27.62
27.83
27.65 1:
27.41
.01
27.29
26.71
27.10
BIN
53.80 .00
34.63 1
54.15 1 02
53.68
001
53.47 1:
53.91
52.91
BIN200
105.63 = .00
108.04 + .02
106.93
+ 02
106.08
+
105.75 - 011
109.19
104.25
BIN500
259.08 = .00
267.19 + .05
264.14
01
262.26
002
261.61
1: .01
267.63
257.02
BIN
512.66 1 .00
531.17
1 .05
524.78
1 03
521.32
1 03
520.32
1:
1000*
509.46
BIN2K
1017.88
1058.74 4
1045.36 + 1038.77
02
1037.15
2000"
1028.67
A.3
TRAVELLING SALESPERSON PROBLEM (TSP)
Data We generate random instances for 2D Euclidean TSP by sampling coordinates uniformly in
a unit square, as done in previous research (oool et al. 2018 Chen & Tian 2019)] de O. Costa et al. 2020). We assume complete graphs (fully-connected TSP), which means every pair of cities is connected by a valid route (an edge).
Training We train only on TSP20 with very short rollouts of length K 40. Just like in the other problems we consider, we train using 256 random problems generated on the fly for each. We also maintain the same initial temperature and cooling schedule with To and a (T /To) R but use lower final temperatures for the TSP. We set Tx 1c-2 for PPO and Tx = 1c-4 for ES, which we empirically found to work best with the training dynamics of each of these methods.
PPO: Both actor and critic networks were optimised with Adam (Kingma & Ba 2015) with learning rate of 2e-4, weight decay of 1e-2 and = (0.9, 0.999). We trained PPO for 1000 epochs.
ES: We population of 16 perturbations sampled from Gaussian of standard deviation 0.1. Updates are fed into an SGD optimizer with learning rate 1e-3 and momentum 0.9, and trained for 10 000 epochs.
Testing We evaluate Neural SA on TSP20, TSP50 and TSP100 using the 10K problem instances made available in Kool et al. (2018). This allows us directly compare our methods to previous re- search on the TSP. We also consider larger problem sizes, namely TSP200 and TSP500 to showcase scalability of Neural SA. For each of these, we randomly generate 1000 instances by uniformly sampling coordinates in 2D unit square. As for the other CO problems study, also compare sampled and greedy variants of Neural SA. The former naturally samples actions from the proposal distribution while the latter always selects the most likely action.
We compare Neural SA against standard solvers LKH-3 (Helsgaum, 2000) and Concorde (Applegate eet al.) 2006), which we have ourselves. We also compare against the self-reported results of other Deep Learning models that have targeted TSP and relied on the test data provided by Kool al. (018): GCN (Joshi al. 2019), GAT' (Kool et al. 2018), GAT-T (Wu al. 2019a), and the works of de O. da Costa et al. (020)) and Fu et al. 2021
Note that Fu et al. 2021 also provide results for TSP200 and TSP500, but given that there is no public dataset for these problem sizes, it is hard to make direct comparison to our results, especially regarding running times. They dataset of 128 instances, while we use 1000.
17

---

Under review as a conference paper at ICLR 2022
Table PPO results on the TSP benchmark. Lower is better
Greedy
Sampled
LKH-3
Concorde
x1
x1
x2
x5
x10
TSP20
4.937 0011
3.941 - .011
3.898
001
3.865 1 000
3.852
.000
3.836
3.836
TSP50
8.104 006
5.916 = 002
5.847
001
5.789 - 000
5.762
.000
5.696
5.696
TSP100
11.764 + .012
8.167 + 000
8.052
.001
7.956 + 0001
7.907
:00
7.764
7.764
Table 10: ES results on the TSP benchmark. Lower is better
Greedy
Sampled
LKH-3
Concorde
x1
x2
x5
x10
TSP20
3.868 0000
3.868 + .001
3.854 + .000
3.844 + 000
3.840 = .000
3.836
3.836
TSP50
6.020 .022
6.022 + .002
5.947 = .001
5.871 + .000
5.828 = .001
5.696
5.696
TSPI00
8.659 .003
8.660 +: .002
8.477 + .001
8.298
.00
8.191 = .002
7.764
7.764
First city selector
Second city selector
13
-
-2
10
66
88
110
Resulting tour if action accepted
Figure 6: Policy for the Travelling Salesperson Problem. At each step, action consists of selecting a pair of cities (i,j), one after the other. The figure depicts TSP problem layed out in the 2D plane, with the learnt proposal distribution over the second city j. given = 12. We mask out and exclude the neighbours of (0 and 14) as candidates for j because selecting those would lead has strong preference towards a few cities, but otherwise the probability mass is spread almost uniformly among the other nodes. However, once fixed, Neural SA strongly favours nodes that are close to i. That is desirable behaviour and even features in popular algorithms like LKH-3 (Helsgaun) 2000). That is because 2-opt move (V, j) actually adds edge (i, to the tour, so leaning towards pairs of cities that are close each other is more likely to lead to shorter tours.
the first city in the left, and in the right, the distribution
changes in the tour. is clear the model
18

---

Under review as a conference paper at ICLR 2022
Time
7h58m
1h15m
2h35m
5h13m
5h13m
6m
TSP500
Gap
0.00%
0.00%
22 22.25%
8.04%
22.55%
2.96%
Table 11: Comparison of different TSP solvers on the 10K instances for TSP20/50/100 provided in Kool et 2018
Cost
16.54
16.54
20.22
17.87
20.27
16.96
Time
38m
21m
30m
32m
32m
3m
TSP200
Gap
0.00%
0.00%
11 11.96%
3.27%
9.72%
0.88%
Cost
10.70
10.70
11 1..98
11.04
11.74
10.81
Time
7m
1h
6m
14m
14m
6m
40 m
h
25m
h
hh
10m
21 m
41m
15m
TSP100
Gap
0..0%
0.00%
7.43%
1.85%
5.50%
8.38%
1.39%
2.26%
3.24%
1.85%
1.42%
1.84%
1.26%
0.87%
0.03%
Cost
7.764
7.764
8.341
7.907
8.191
8.41
7.87
7.94
8.01
7.91
7.87
7.91
7.86
7.83
7.76
Time
2m
14m
1m
2m
2m
55s
18m
24m
16m
h
7m
13m
29m
9m
45
TSP50
Gap
0.00%
0.00%
4.34%
1.16%
2.32%
3.10%
0.01%
0.52%
0.83%
0.34%
0.20%
0.36%
0.21%
0.12%
0.01%
Cost
5.696
5.696
5.943
5.762
5.828
5.87
5.70
5.73
5.75
5.72
5.71
5.72
5.71
5.70
5.69
Time
48s
1m
10s
17s
12m
5 m
12m
39m
1h
5m
10m
15m
2m
TSP20
Gap
0.00%
0.00%
1.17%
0.42%
0.10%
0.60%
0.01%
0.08%
0.03%
0.00%
0.00%
0.01%
0.00%
0.00%
0.00%
Cost
3.836
3.836
3. 3,881
3.852
3 3.840
3.86
3.84
3.84
3.84
3.84
3.84
3.84
3.84
3.84
3.84
GCN Beam Search
Costa et (500)
1000)
Da Costa et al. {2000)
NEURAL SA PPO
NEURAL SA ES
GAT-T {1000}
GAT-T (3000]
GAT-T [5000]
Da Costa et al.
CONCORDE
LKH-3
Fu ct al.
GCN
GAT
SA
19


Reviews:
[{"review_id": "wg-rBQMhpHs", "reviewer": "Reviewer_4KAJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n=\n\n1. The idea is interesting and sound. Simulated annealing can be viewed as Markov decision process naturally, which motivates the use of reinforcement learning.\n\n2. Although there has been some studies for hybridizing SA and learning methods, the authors have distinguished their work from existing studies clearly. \n\n3. The experiments on four optimization problems demonstrate that the proposed neural SA works better than the SA alone. \n\n\nCons\n= \n\n1. 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. \n\n2. 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. \n\n3. 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_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. \n", "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. \n ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WwMErxtDJM", "reviewer": "Reviewer_HRDu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths** \n\nI believe the paper has the following strengths:\n- A modular and practical improvement on a traditional optimization technique (SA), which demonstrates clear improvement on the optimization benchmarks provided.\n- A detailed and thorough description of the method, including how SA can interact with reinforcement learning in a scalable manner. \n- 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.\n\n**Weaknesses**\n\nI think that the paper could be improved by:\n- 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.\n- 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?\n- 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?\n- 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.\n\nWhile I don't think this is necessary at this moment, I think it would have been nice to have the following as well:\n- 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. \n- An ablation of the state definition to see what information may or may not be critical for NSA to tackle the problem effectively. \n- 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. \n", "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.\n\nFollowing 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.", "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. \n\nI 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. \n\n----- Update During Discussion Period -----\n\nThe 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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KxI8AB7j0qp", "reviewer": "Reviewer_cPBg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper present a simple, lightweight approach for neural simulated annealing that outperforms \"vanilla SA\". The approach is general and amenable to many problems.\n- The approach shows promising results w.r.t generalization to larger problem sizes (a challenging aspect for many approaches to neural-guided combinatorial optimzation).\n\nWeaknesses:\n- 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.\n- 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: \n    1) comparisons with \"vanilla SA\" and not state-of-the-art SA solutions that are tailored to each problem.\n    2) In Knapsack, Bin packing, and TSP, the neural approaches that are tailored to the domain outperform neural SA.\n    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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EcQZEPH02rT", "reviewer": "Reviewer_C2r3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n- 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.\n\n- 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.\n\n- That Neural SA improves over vanilla SA so significantly, despite the very modest network sizes, is impressive.\n\n**Weakenesses**\n\n- 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.\n\n- 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.\n\n- 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.\n\n[1] “Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization”, arXiv:2002.04676 (2020)\n\n[2] \"Finding the ground state of spin Hamiltonians with reinforcement learning”, Nat Mach Intell 2, 509–517 (2020). \n\n[3] \"Exploratory Combinatorial Optimization with Reinforcement Learning”, arXiv:1909.04063 (2019).\n\n**Errata**\n\nA few minor points that do not require and response from the authors.\n\n- First paragraph of pg. 7: “groundtruth” - I think “ground truth” is more standard.\n- First paragraph of pg. 7: “Results in Table 1, show that…” - I do not think there should be a comma after ‘Table 1’.\n- First paragraph of pg. 8: “We sample from the policy ancestrally,” - should this be autoregressively?\n- First paragraph of pg. 9: “WE use the” - erroneous capitalisation.", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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