marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Neural Simulated Annealing

Anonymous Authors1

††footnotetext:  1Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author
<EMAIL_ADDRESS>
Preliminary work. Under review by the International Conference on Machine
Learning (ICML). Do not distribute.

###### 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, parametrised by small equivariant
neural networks, outperforms SA baselines 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—generalising to significantly larger problems than the ones
seen during training—while achieving comparable performance to popular off-
the-shelf solvers and other machine learning methods in terms of solution
quality and wall-clock time.

##  1 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-deployment, but require manual tailoring to each
individual problem. One such metaheuristic is _Simulated Annealing_ (SA)
(Kirkpatrick et al., 1987), a simple, and equally very popular, iterative
global optimisation technique for numerically approximating the global minimum
of both continuous- and discrete-variable problems. While SA has wide
applicability, this is also its Achilles’ Heel, leaving many design choices to
the user. Namely, a user has to design 1) neighbourhood proposal
distributions, which define the space of possible transitions from a solution
${\mathbf{x}}_{k}$ at time $k$ to solutions ${\mathbf{x}}_{k{+}1}$ at time
$k{+}1$, and 2) a 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,
which we show improves convergence speed with little computational overhead
(limited to ${\mathcal{O}}(N)$ per step for problem size $N$).

In recent years, research on approximate optimisation methods has been
inundated by works in machine learning for CO (ML4CO) (Bengio et al., 2018). A
lot of the focus has been on end-to-end neural architectures (Bello et al.,
2016; Vinyals et al., 2017; Dai et al., 2017; Kool et al., 2018; Emami &
Ranka, 2018; Bresson & Laurent, 2021). These work by brute force learning the
instance to solution mapping—in CO these are sometimes referred to as
_construction heuristics_. Other works focus on learning good parameters for
classic algorithms, whether they be parameters of the original algorithm
(Kruber et al., 2017; Bonami et al., 2018) or extra neural parameters
introduced into the computational graph of classic algorithms (Gasse et al.,
2019; Gupta et al., 2020; Kool et al., 2021; da Costa et al., 2020; Wu et al.,
2019b; Chen & Tian, 2019; Fu et al., 2021). Our method, _neural simulated
annealing_ (Neural SA) can be viewed as sitting firmly within this last
category.

Figure 1: Neural SA pipeline for the TSP. Starting with a solution (tour)
${\mathbf{x}}_{k}$, we sample an action ${\mathbf{a}}{=}(i,j)$ from our
learnable policy/proposal distribution, defining start $i$ and end $j$ points
of a 2-opt move (replacing two old with two new edges). Each pane shows both
the linear and graph-based representations for a tour. From ${\mathbf{x}}_{k}$
and ${\mathbf{a}}$ we form a proposal ${\mathbf{x}}^{\prime}$ which is either
accepted or rejected in a MH step. Accepted moves assign
${\mathbf{x}}_{k+1}{=}{\mathbf{x}}^{\prime}$; whereas, rejected moves assign
${\mathbf{x}}_{k+1}{=}{\mathbf{x}}_{k}$.

SA is an _improvement heuristic_ ; it navigates the search space of feasible
solutions by iteratively applying (small) perturbations to previously found
solutions. Figure 1 illustrates this for the Travelling Salesperson Problem
(TSP), perhaps the most classic of NP-hard problems. In this work, we pose
this as a Reinforcement Learning (RL) agent navigating an environment,
searching for better solutions. In this light the proposal distribution is an
optimisable quantity. Conveniently, our method inherits convergence guarantees
from SA. We are able to directly optimise the proposal distribution using
policy optimisation for both faster convergence and better solution quality
under a fixed computation budget. We demonstrate Neural SA on four tasks:
Rosenbrock’s function, a toy 2D optimisation problem, where we can easily
visualise and analyse what is being learnt; the Knapsack and Bin Packing
problems, which are classic NP-hard resource allocation problems; and the TSP.

Our contributions are:

  * •

We pose simulated annealing as a Markov decision process, bringing it into the
realm of reinforcement learning. This allows us to optimise the proposal
distribution in a principled manner, still preserving all the convergence
guarantees of vanilla simulated annealing.

  * •

We show competitive performance to off-the-shelf CO tools and other ML4CO
methods on the Knapsack, Bin Packing, 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 $40\times$ larger than the ones used for training.

  * •

Our method is competitive within the ML4CO space, using a very lightweight
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
$(\bm{\Psi},{\mathcal{X}},E)$ where $\bm{\psi}\in\bm{\Psi}$ are problem
instances (city locations in the TSP), ${\mathcal{X}}$ is the set of feasible
solutions given $\bm{\psi}$ (Hamiltonian cycles in the TSP) and
$E:{\mathcal{X}}\times\bm{\Psi}\to{\mathbb{R}}$ is an _energy function_ (tour
length in the TSP). Without loss of generality, the task is to minimise the
energy $\min_{{\mathbf{x}}\in{\mathcal{X}}}E({\mathbf{x}};\bm{\psi})$. CO
problems are in general NP-hard, meaning that there is no known algorithm to
solve them in time polynomial in the number of bits that represents a problem
instance.

#### Simulated Annealing

Simulated annealing (Kirkpatrick et al., 1987) is a metaheuristic for CO
problems. It builds an inhomogeneous Markov chain
${\mathbf{x}}_{0}\to{\mathbf{x}}_{1}\to{\mathbf{x}}_{2}\to\cdots$ for
${\mathbf{x}}_{k}\in\mathcal{X}$, asymptotically converging to a minimizer of
$E$. The stochastic transitions ${\mathbf{x}}_{k}\to{\mathbf{x}}_{k+1}$ depend
on two quantities: 1) a proposal distribution, and 2) a temperature schedule.
The proposal distribution $\pi:\mathcal{X}\to{\mathbb{P}}(\mathcal{X})$, for
${\mathbb{P}}(\mathcal{X})$ the space of probability distributions on
${\mathcal{X}}$, suggests new states in the chain. It perturbs current
solutions to new ones, potentially leading to lower energies immediately or
later on. After perturbing a solution
${\mathbf{x}}_{k}\to{\mathbf{x}}^{\prime}$, a Metropolis–Hastings (MH) step
(Metropolis et al., 1953; Hastings, 1970) is executed. This either accepts the
perturbation (${\mathbf{x}}_{k+1}={\mathbf{x}}^{\prime}$) or rejects it
(${\mathbf{x}}_{k+1}={\mathbf{x}}_{k}$)—see Algorithm 1 for details. The
target distribution of the MH step has form
$p({\mathbf{x}}|T_{k})\propto\exp\\{-E({\mathbf{x}})/T_{k}\\}$, where $T_{k}$
is the _temperature_ at time $k$. In the limit $T_{k}\to 0$, this distribution
tends to a sum of Dirac deltas on the minimisers of the energy. The
temperature is annealed, according to the temperature schedule,
$T_{1},T_{2},...$, from high to low, to steer the target distribution smoothly
from broad to peaked around the global optima. The algorithm is outlined in
Algorithm 1. Under certain regularity conditions and provided the chain is
long enough, it will visit the minimisers almost surely (Geman & Geman, 1984).
More concretely,

$\displaystyle\lim_{k\to\infty}P\left({\mathbf{x}}_{k}\in\operatorname*{arg\,min}_{{\mathbf{x}}\in{\mathcal{X}}}E({\mathbf{x}};\bm{\psi})\right)=1.$
(1)

Despite this guarantee, practical convergence speed is determined by $\pi$ and
the temperature schedule, which are hard to fine-tune. There exist problem-
specific 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. Cai et al. (2019) and
Vashisht et al. (2020) use RL to find good initial solutions that are later
refined by standard SA. That is fundamentally different to our approach, as we
augment SA with RL-optimisable components, instead of simply using them as
standalone algorithms that only interact via shared solutions. In fact, our
method is perfectly compatible with theirs and any other SA application.
Another line of work seeks to optimise different components of SA with RL
(Wauters et al., 2020; Khairy et al., 2020; Beloborodov et al., 2020; Mills et
al., 2020) or statistical machine learning techniques (Blum et al., 2020). In
contrast to these methods that optimise individual hyperparameters in SA, we
frame SA itself as an RL problem, which allows us to define and train the
proposal distribution as a policy.

More closely to our method, other approaches improve the proposal
distribution. In Adaptive Simulated Annealing (ASA) (Ingber, 1996) the
proposal distribution is not fixed but evolves throughout the annealing
process as a function of the variance of the quality of visited solutions. ASA
improves the convergence of standard SA but is not learnable like Neural SA.
To the best of our knowledge, Marcos 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. Conversely, Neural SA is fully
unsupervised, thus easier to train and extend to different CO tasks. Finally,
SA is also akin to Metropolis-Hastings, a popular choice for Markov Chain
Monte Carlo (MCMC) sampling. Noé et al. (2019), Albergo et al. (2019) and de
Haan et al. (2021) recently studied how to learn a proposal distribution of an
MCMC chain for sampling the Boltzmann distribution of a physical system. While
their results serve as motivation for our methods, we investigate a completely
different context and set of applications.

Lastly, 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 parameters (Rere et al., 2015) or
hyperparameters of a neural network optimiser (Maclaurin et al., 2015;
Andrychowicz et al., 2016) and meta-learning (Finn et al., 2017). However,
most recent approaches assume differentiable losses on continuous state spaces
Likhosherstov et al. (2021); Ji et al. (2021); Vicol et al. (2021), while we
focus on the more challenging CO setting. We note, however, methods in Vicol
et al. (2021) 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 as we explain below. An MDP
${\mathcal{M}}=({\mathcal{S}},{\mathcal{A}},R,P,\gamma)$ consists of _states_
$s\in{\mathcal{S}}$, _actions_ $a\in{\mathcal{A}}$, an _immediate reward
function_
$R:{\mathcal{S}}\times{\mathcal{A}}\times{\mathcal{S}}\to{\mathbb{R}}$, a
_transition kernel_
$P:{\mathcal{S}}\times{\mathcal{A}}\to{\mathbb{P}}({\mathcal{S}})$, and a
_discount factor_ $\gamma\in[0,1]$. On top of this MDP we add a stochastic
_policy_ $\pi:{\mathcal{S}}\to{\mathbb{P}}({\mathcal{A}})$. The policy and
transition kernel together define a length-$K$ trajectory
$\tau=(s_{0},a_{0},s_{1},a_{1},...,s_{K})$, which is a sample from the
distribution
$P(\tau|\pi)=\rho_{0}(s_{0})\prod_{k=0}^{K-1}P(s_{k+1}|s_{k},a_{k})\pi(a_{k}|s_{k})$
and where $s_{0}\sim\rho_{0}$ is sampled from the _start-state distribution_
$\rho_{0}$. One can then define the _discounted return_
$R(\tau)=\sum_{k=0}^{K-1}\gamma^{t}r_{k}$ over a trajectory, where
$r_{k}=R(s_{k},a_{k},s_{k+1})$. We say that we have solved an MDP if we have
found a policy that maximises the expected return $\mathbb{E}_{\tau\sim
P(\tau|\pi)}[R(\tau)]$.

##  3 Method

Here we outline our approach to learn the proposal distribution. First we
define an MDP corresponding 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 classic algorithm.

###  3.1 MDP Formulation

We formalise SA as an MDP, with states
${\mathbf{s}}=({\mathbf{x}},\bm{\psi},T)\in{\mathcal{S}}$ for $\bm{\psi}$ a
parametric description of the problem instance as in Section 2, and $T$ the
instantaneous temperature. Examples are in Section 4. Our actions
${\mathbf{a}}\in\mathcal{A}$ perturb
$({\mathbf{x}},\bm{\psi},T)\mapsto({\mathbf{x}}^{\prime},\bm{\psi},T)$, where
${\mathbf{x}}^{\prime}\in{\mathcal{N}}({\mathbf{x}})$ is a solution in the
neighbourhood of ${\mathbf{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 since the latter are more
common than the former, it generally leads to faster convergence.

We view the MH step in SA as a stochastic transition kernel, governed by the
current temperature of the system, with transition probabilities following a
Gibbs distribution and dynamics

$\displaystyle{\mathbf{x}}_{k+1}$
$\displaystyle=\left\\{\begin{matrix}[l]{\mathbf{x}}^{\prime},&\text{with
probability }p\\\ {\mathbf{x}}_{k},&\text{with probability
}1-p,\end{matrix}\right.$ $\displaystyle\text{where }p$
$\displaystyle=\min\left\\{1,e^{-\frac{1}{T_{k}}(E({\mathbf{x}}^{\prime};\bm{\psi})-E({\mathbf{x}}_{k};\bm{\psi}))}\right\\}.$
(2)

This defines a transition kernel
$P({\mathbf{s}}_{k+1}|{\mathbf{s}}_{k},{\mathbf{a}})$, where we have
${\mathbf{s}}_{k+1}{=}({\mathbf{x}}_{k+1},\bm{\psi},T)$. For rewards, we use
either the immediate gain
$E({\mathbf{x}}_{k};\bm{\psi})-E({\mathbf{x}}_{k+1};\bm{\psi})$ or the primal
reward
$-\delta_{k=K-1}\min_{{\mathbf{x}}\in{\mathbf{x}}_{1:k}}E({\mathbf{x}};\bm{\psi})$.
We explored training with two different methods: Proximal Policy Optimisation
(PPO) (Schulman et al., 2017) and Evolution Strategies (ES) Salimans et al.
(2017). The immediate gain works best with PPO, where at each iteration of the
rollout, the immediate gain gives fine-grained feedback on whether the
previous action helped or not. The primal reward works best with ES because it
is non-local, returning the minimum along an entire rollout $\tau$ at the very
end. We explored using the acceptance count but found that this sometimes led
to pathological behaviours. Similarly, we tried the primal integral (Berthold,
2013), which encourages finding a good solution fast, but found we could not
get training dynamics to converge.

Algorithm 1 Neural simulated annealing. To get back to vanilla SA, replace the
parametrised proposal distribution $\pi_{\theta}$ with a uniform distribution
$\pi$ over neighbourhoods ${\mathcal{N}}(\bullet)$.

0: Initial state ${\mathbf{s}}_{0}=({\mathbf{x}}_{0},\bm{\psi},T_{0})$,
proposal distribution $\pi$, transition function $P$, temperature schedule
$T_{1}\geq T_{2}\geq T_{3}\geq...$, energy function $E(\bullet;\bm{\psi})$

for $k=1:K$ do

${\mathbf{a}}\sim\pi_{\theta}({\mathbf{s}}_{k})$ {Sample action}

$u\sim\text{Uniform}(u;0,1)$ {Metropolis–Hastings step}

if
$u<\exp\left\\{-(E({\mathbf{x}}^{\prime};\bm{\psi})-E({\mathbf{x}}_{k};\bm{\psi}))/T_{k}\right\\}$
then

${\mathbf{s}}_{k+1}\leftarrow({\mathbf{x}}^{\prime},\bm{\psi},T_{k+1})$
{Accept}

else

${\mathbf{s}}_{k+1}\leftarrow({\mathbf{x}}_{k},\bm{\psi},T_{k+1})$ {Reject}

end if

end for

###  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 to scale to varying numbers of inputs, so that we can transfer
experience across problems of different size $N$. We opt for a very simple
network, shown in Figure 2. For each dimension of the problem we map the state
$({\mathbf{x}},\bm{\psi},T)$ into a set of features. For all problems we try,
there is a 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$ and the
computation is embarrassingly parallel, which is important since we plan to
evaluate it many times. A notable property of this architecture is that it is
permutation equivariant (Zaheer et al.,
2017)—$\pi_{\theta}({\mathbf{a}}|{\mathbf{s}})=\pi_{\theta}(\sigma\cdot{\mathbf{a}}|\sigma\cdot{\mathbf{s}})$
for $\sigma$ a permutation of $N$ objects—an important requirement for the CO
problems we consider. Note that our 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.

Figure 2: (a) Policy network used in all experiments. The same MLP is applied
to all inputs pointwise.

#### Convergence

Convergence of SA to the optimum in the infinite time limit requires the
Markov chain of the proposal distribution to be irreducible van Laarhoven &
Aarts (1987), meaning that for any temperature, any two states are reachable
through a sequence of transitions with positive conditional probability under
$\pi$. Our neural network policy satisfies this condition as long as the
softmax layer does not assign zero probability to any state, a condition which
is met in practice. Thus Neural SA inherits convergence guarantees from SA.

##  4 Experiments

(a) 2D rollout

(b) Acceptance ratios

(c) $\sigma$ by iteration

(d) Baseline sweep

Figure 3: Results on Rosenbrock’s function: (a) Example trajectory, moving
from red to blue, showing convergence around the minimiser at (1,1) (b) Neural
SA has higher acceptance ratio than the baseline, a trend observed in all
experiments, (c) Standard deviation of the learned policy as a function of
iteration. Large initial steps offer great gains followed by small
exploitative steps, (d) A non-adaptive vanilla SA baseline cannot match an
adaptive one, no matter the standard deviation.

We evaluate our method on 4 tasks—Rosenbrock’s function, the Knapsack, Bin
Packing, and TSP problems— _using the same architecture and hyperparameters of
Neural SA for all tasks_. This shows the wide applicability and ease of use of
our method. For each task (except for Rosenbrock’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 one of the challenges in ML4CO Joshi et al.
(2019b), and is a merit of our lightweight, equivariant architecture. In all
experiments, we start from trivial or random solutions and adopt an
exponential multiplicative cooling schedule as originally proposed by
Kirkpatrick et al. (1987), with $T_{k}=\alpha^{k}T_{0}$. In practice, we
define the temperature schedule by fixing $T_{0}$, $T_{K}$ and computing
$\alpha$ according to the desired number of steps $K$. This allows us to vary
the rollout length while maintaining the same range of temperatures for every
run. We provide more precise experimental details in the appendix.

###  4.1 The Rosenbrock function

The Rosenbrock function is a common benchmark for optimisation algorithms. It
is a non-convex function over Euclidean space defined as

$\displaystyle E(x_{0},x_{1};a,b)=(a-x_{0})^{2}+b(x_{1}-x_{0}^{2})^{2},$ (3)

and with global minimum at ${\mathbf{x}}{=}(a,a^{2})$. Of course, gradient-
based optimisers are more suited to this problem, but we use it as a toy
example to showcase the properties of Neural SA. Our policy is an axis-aligned
Gaussian
$\pi_{\theta}({\mathbf{a}}|{\mathbf{s}})={\mathcal{N}}({\mathbf{a}};\bm{0},\sigma_{\theta}^{2}({\mathbf{s}}_{k}))$,
where we parametrise the variance $\sigma_{\theta}^{2}$ by an MLP of shape
$2{\to}16{\to}2$ with a ReLU in the middle. Proposals are of the form
${\mathbf{x}}^{\prime}{=}{\mathbf{x}}{+}{\mathbf{a}}$, and the state is given
by ${\mathbf{s}}_{k}=({\mathbf{x}}_{k},a,b,T_{k})$. An example rollout is in
Figure 3(a).

We contrast Neural SA against vanilla SA with fixed proposal distribution,
i.e. $\sigma({\mathbf{s}}_{i})=\sigma$, for different $\sigma$ averaged over
$2^{17}$ problem instances. This shows in Figure 3(d) that no constant
variance policy can outperform an adaptive policy on this problem. Plots of
acceptance ratio in Figure 3(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 3(c) shows the variance network
$\sigma_{\theta}^{2}({\mathbf{s}}_{i})$ as a function of time. It has learnt
to make large steps until hitting the basin, whereupon large moves will be
rejected with high probability, so variance must be reduced.

###  4.2 Knapsack Problem

The Knapsack problem is a classic CO problem in resource allocation. Given a
set of $N$ items, each of a different value $v_{i}>0$ and weight $w_{i}>0$,
the goal is to find a subset that maximises the sum of values while respecting
a maximum total weight of $W$. This is the 0-1 Knapsack Problem, which is
weakly NP-complete, has a search space of size $2^{N}$ and corresponding
integer linear program

$\displaystyle\text{minimise
}E({\mathbf{x}};\bm{\psi})=-\sum_{i=0}^{N-1}v_{i}x_{i},$
$\displaystyle\text{subject to }\sum_{i=0}^{N-1}w_{i}x_{i}\leq W,\qquad
x_{i}\in\\{0,1\\}.$ (4)

Figure 4: Knapsack Policy with logits for $x_{i}=0$ and $x_{i}=1$ 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, although the
policy does not receive free capacity as a feature. 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. *Values as reported by Bello et al. (2016) for reference.

| Random Search | Bello RL | Bello AS | SA | Ours (PPO) | Ours (ES) | Greedy | OR-Tools
---|---|---|---|---|---|---|---|---
Knap50 | $17.91^{*}$ | $19.86^{*}$ | $20.07^{*}$ | $18.43\,(8.40\%)$ | $19.69\,(2.23\%)$ | $19.95\,(0.84\%)$ | $19.94\,(0.89\%)$ | $\bm{20.12}\,(0.00\%)$
Knap100 | $33.23^{*}$ | $40.27^{*}$ | $40.50^{*}$ | $36.81\,(8.91\%)$ | $39.54\,(2.15\%)$ | $39.90\,(1.26\%)$ | $40.17\,(0.59\%)$ | $\bm{40.41}\,(0.00\%)$
Knap200 | $35.95^{*}$ | $57.10^{*}$ | $57.45^{*}$ | $50.89\,(11.73\%)$ | $55.03\,(4.54\%)$ | $55.58\,(3.59\%)$ | $57.30\,(0.61\%)$ | $\bm{57.65}\,(0.00\%)$
Knap500 |  | - | - | $126.92\,(11.95\%)$ | $138.14\,(4.16\%)$ | $141.01\,(2.17\%)$ | $143.77\,(0.25\%)$ | $\bm{144.14}\,(0.00\%)$
Knap1K | - | - | - | $254.45\,(11.96\%)$ | $277.41\,(4.01\%)$ | $282.46\,(2.26\%)$ | $288.64\,(0.13\%)$ | $\bm{289.01}\,(0.00\%)$
Knap2K | - | - | - | $507.72\,(12.03\%)$ | $554.32(3.97\%)$ | $563.75(2.34\%)$ | $576.89\,(0.06\%)$ | $\bm{577.28}\,(0.00\%)$

Solutions are represented as a binary vector ${\mathbf{x}}$, with $x_{i}=0$
for ‘out of the bin’ and $x_{i}=1$ for ‘in the bin’. Our proposal distribution
flips individual bits, one at a time, with the constraint that we cannot flip
$0\mapsto 1$ if the bin capacity will be exceeded. The neighbourhood of
${\mathbf{x}}_{k}$ is thus all feasible solutions at a Hamming distance of 1
from ${\mathbf{x}}_{k}$. We use the proposal distribution described in Section
3.2 and illustrated in Figure 2, consisting of a pointwise embedding of each
item—its weight, value, occupancy bit, the knapsack’s overall capacity, and
global temperature—into a logit-space, followed by a softmax. Mathematically
the policy and state–action to proposal mapping are

$\displaystyle\pi_{\theta}(i|{\mathbf{s}})$
$\displaystyle=\text{softmax}\left({\mathbf{z}}\right)_{i},\enspace
z_{i}=f_{\theta}([x_{i},w_{i},v_{i},W,T])$
$\displaystyle{\mathbf{x}}^{\prime}$
$\displaystyle={\mathbf{x}}+\text{onehot}(i)\mod 2.$ (5)

where $f_{\theta}$ is a small two-layer neural network $5{\to}16{\to}1$ with
ReLU activations, comprising only 112 parameters. Actions are sampled from the
categorical distribution induced by the softmax and cast to one-hot vectors
$\text{onehot}(i)$.

Neural networks have been used to solve the Knapsack Problem in Vinyals et al.
(2017), Nomer et al. (2020), and Bello et al. (2016). We follow the setup of
Bello et al. (2016), honing in on 3 self-generated datasets: Knap50, Knap100
and Knap200. Knap$N$ consists of $N$ items with weights and values generated
uniformly at random in $(0,1]$ and capacities
$C_{50}\\!=\\!12.5,C_{100}\\!=\\!25$, and $C_{200}\\!=\\!25$. We use OR-Tools
(Perron & Furnon, 2019) to compute ground truth solutions. Results in Table 1
show that Neural SA improves over vanilla SA by up to 10% optimality gap, and
heuristic methods (Random Search) by much more. Neural SA falls slightly
behind two methods by Bello et al. (2016), which use (1) a large attention-
based pointer network with several orders of magnitude more parameters in
Bello RL, and (2) this coupled with 5000 iterations of their Active Search
method. It also falls behind a greedy heuristic for packing a knapsack based
on the value-to-weight ratio. In Figure 4 we analyse the policy network and a
typical rollout. It has learnt a mostly greedy policy to fill its knapsack
with light, valuable objects, only ejecting them when full. This is in line
with the value-to-weight greedy heuristic. Despite not coming top among
methods, we note Neural SA is typically within 1-3% of the minimum energy,
although its architecture was not designed for this problem in particular.

###  4.3 Bin Packing Problem

The Bin Packing problem is similar to the Knapsack problem in nature. Here,
one wants to pack _all_ of $N$ items into the smallest number of bins
possible, where each item $i\in\\{1,\cdots,N\\}$ has weight $w_{i}$, and we
assume, without loss of generality, $N$ bins of equal capacity
$W\geq\max_{i}(w_{i})$; there would be no valid solution otherwise. This
problem is NP-hard and has a search space of size equal to the $N^{th}$ Bell
number. If $x_{ij}$ denotes item $i$ occupying bin $j$, then the problem can
be written as minimising an energy:

minimise $\displaystyle E({\mathbf{x}};\bm{\psi})=\sum_{j=0}^{N-1}y_{j},$ (6)
subject to $\displaystyle\underbrace{\sum_{i=0}^{N-1}w_{i}x_{ij}\leq
W}_{\text{bin capacity
constraint}},\quad\underbrace{\sum_{j=0}^{N-1}x_{ij}=1}_{\text{1 bin per
item}},$
$\displaystyle\underbrace{y_{j}=\min\left(1,\sum_{i=0}^{N-1}x_{ij}\right)}_{\text{bin
occupancy indicator}},\quad x_{ij}\in\\{0,1\\}$

where the constraints apply for all $i$ and $j$. We define the policy in two
steps: we first pick an item $i$, and then select a bin $j$ to place it into.
We can then write the policy as
$\pi_{\theta,\phi}({\mathbf{a}}{=}(i,j)|{\mathbf{s}}){=}\pi_{\phi}(i|{\mathbf{s}})\pi_{\theta}(j|{\mathbf{s}},i)$,
which we define as

$\displaystyle\pi_{\theta}(i|{\mathbf{s}}){=}\text{softmax}\left({\mathbf{z}}^{\text{item}}\right)_{i}$
$\displaystyle,\enspace z^{\text{item}}_{i}{=}f_{\theta}([w_{i},c_{b(i)},T]),$
$\displaystyle\pi_{\phi}(j|{\mathbf{s}},i){=}\text{softmax}\left({\mathbf{z}}^{\text{bin}}\right)_{j}$
$\displaystyle,\enspace z^{\text{bin}}_{j}{=}f_{\phi}([w_{i},c_{j},T]),$ (7)

where $b(i)$ is the bin item $i$ is in before the action (in terms of
$x_{ij}$, we have $x_{ib(i)}=1$), $c_{j}$ is the free capacity of bin $j$
($c_{j}=W-\sum_{i=1}^{N}w_{i}x_{ij}$), and both $f_{\theta}$ and $f_{\phi}$
are lightweight architectures $3{\to}16{\to}1$ with a ReLU nonlinearity
between the two layers. We sample from the policy ancestrally, sampling first
an item from $\pi_{\theta}(i|{\mathbf{s}})$, followed by a bin from
$\pi_{\phi}(j|{\mathbf{s}},i)$. Results in 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 (1973), a very strong heuristic for this problem (Rieck,
2021). We even see that we very often beat the SCIP (Gamrath et al., 2020a; b)
optimizer in OR-Tools, which timed out on most problems. Figure 5 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 6 has much faster convergence than the vanilla version.
Again, we see that our method, although simple, is competitive with hand-
designed alternatives, whereas vanilla SA is not.

Figure 5: Bin50 primal objective for vanilla, Neural, and Greedy Neural SA with 25th, 50th, and 75th percentiles.  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 a time out for Or-Tools of 1 minute per problem for Bin50-1000 and of 2 minutes for Bin2000; * indicates only the trivial solution was found in this time. | SA | Ours (PPO) | Ours (ES) | OR-Tools (SCIP) | FFD
---|---|---|---|---|---
Bin50 | $30.38\,(13.74\%)$ | $27.32\,(2.28\%)$ | $27.24\,(1.98\%)$ | $\bm{26.71}\,(0.00\%)$ | $27.10\,(1.46\%)$
Bin100 | $60.66\,(14.65\%)$ | $53.53\,(1.17\%)$ | $53.38\,(0.88\%)$ | $53.91\,(1.89\%)$ | $\bm{52.91}\,(0.00\%)$
Bin200 | $121.27\,(16.32\%)$ | $105.63\,(1.32\%)$ | $105.43\,(1.13\%)$ | $109.19\,(4.74\%)$ | $\bm{104.25}\,(0.00\%)$
Bin500 | $302.84\,(17.82\%)$ | $259.08\,(0.80\%)$ | $259.09\,(0.80\%)$ | $267.63\,(4.13\%)$ | $\bm{257.02}\,(0.00\%)$
Bin1000 | $605.23\,(18.79\%)$ | $512.66\,(0.63\%)$ | $512.66\,(0.63\%)$ | $1000^{*}$ | $\bm{509.46}\,(0.00\%)$
Bin2000 | $1209.72\,(18.84\%)$ | $\bm{1017.88}\,(0.00\%)$ | $\bm{1017.88}\,(0.00\%)$ | $2000^{*}$ | $1028.67\,(1.06\%)$
Figure 6: Bin Packing policy (logits), consisting of two networks, an item
selector and a bin selector. The item selector uses item weight and bin used
capacities to 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 this in an almost-full bin. We mask bins
with insufficient free capacity, hence the triangular logit-spaces.

###  4.4 Travelling Salesperson Problem

Imagine you will make a round road-trip through $N$ cities and want to plan
the shortest route visiting each city once; this is the Travelling Salesperson
Problem (TSP) (Applegate et al., 2006). The TSP has been a long time favourite
of computer scientists due to its easy description and NP-hardness (the base
search space has size equal to the factorial of the number of cities). Here we
use it as an example of a difficult CO problem. We compare with Concorde
(Applegate et al., 2006) and LKH-3 (Helsgaun, 2000), two custom solvers for
TSP. Given cities $i\in\\{0,1,...,N-1\\}$ with spatial coordinates
${\mathbf{c}}_{i}\in[0,1]^{2}$, we wish to find a linear ordering of the
cities, called a _tour_ , denoted by the permutation vector
${\mathbf{x}}=(x_{0},x_{1},...,x_{N-1})$ for $x_{i}\in\\{0,1,...,N-1\\}$ such
that

$\displaystyle\text{minimise
}E({\mathbf{x}};\bm{\psi})=\sum_{i=0}^{N-1}\|{\mathbf{c}}_{x_{i+1}}-{\mathbf{c}}_{x_{i}}\|_{2}$
$\displaystyle\text{subject to }x_{i}\neq x_{j}\text{ for all }i\neq j$ (8)
$\displaystyle\qquad\,\text{ and }x_{i}\in\\{0,1,...,N-1\\},$

where we have defined $x_{N}=x_{0}$ for convenience of notation. Our action
space consists of so-called _2-opt_ moves (Croes, 1958), which reverse
contiguous segments of a tour. An example of a 2-opt move is shown in Figure
1. We have a two-stage architecture, like in Bin Packing, which selects the
start and end cities of the segment to reverse. Denoting $i$ as the start and
$j$ as the end cities, we have
$\pi_{\theta,\phi}({\mathbf{a}}{=}(i,j)|{\mathbf{s}})=\pi_{\phi}(i|{\mathbf{s}})\pi_{\theta}(j|{\mathbf{s}},i)$,
parametrised as

$\displaystyle\pi_{\theta}(i|{\mathbf{s}})$
$\displaystyle=\text{softmax}\left({\mathbf{z}}\right)_{i},\enspace
z_{i}=f_{\theta}([{\mathbf{c}}_{{\mathbf{x}}_{[i-1:i+1]}},T]),$
$\displaystyle\pi_{\phi}(j|{\mathbf{s}},i)$
$\displaystyle=\text{softmax}\left({\mathbf{z}}\right)_{j},$ $\displaystyle
z_{j}$
$\displaystyle=f_{\phi}([{\mathbf{c}}_{{\mathbf{x}}_{[i{-}1:i{+}1]}},{\mathbf{c}}_{{\mathbf{x}}_{[j{-}1:j{+}1]}},T]),$
(9)

where ${\mathbf{x}}_{[i-1:i+1]}$ are the indices of city $i$ and its tour
neighbours $i-1$ and $i+1$. Again, we use simple MLPs: $f_{\theta}$ has
architecture $7{\to}16{\to}1$ and $f_{\phi}$, $13{\to}16{\to}1$. We test on
publicly available TSP20/50/100 (Kool et al., 2018) with 10K problems each and
generate TSP200/500 with 1K tours each. Results, in Table 12, show Neural SA
improves on vanilla SA. Albeit not outperforming Fu et al. (2021), Neural SA
is neck-to-neck with other neural improvement heuristics methods, GAT-T{1000}
(Wu et al., 2019b) and Costa{500} (da Costa et al., 2020). Since Neural SA is
not custom designed for TSP as the competing methods, we view this as
surprisingly good. A more complete comparison, including other neural
approaches, is given in the appendix, Table 12.

##  5 Discussion

Table 3: Comparison of Neural SA against competing methods with similar
running times on TSP. Extended version in Table 12. Lower is better. *Values
as reported in respective works (Wu et al., 2019a; da Costa et al., 2020; Fu
et al., 2021).

| TSP20 | TSP50 | TSP100 | TSP200 | TSP500
---|---|---|---|---|---
| Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time
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% | 7h58m
LKH-3 | 3.836 | 0.00% | 1m | 5.696 | 0.00% | 14m | 7.764 | 0.00% | 1h | 10.70 | 0.00% | 21m | 16.54 | 0.00% | 1h15m
SA | 3.881 | 1.17% | 5s | 5.943 | 4.34% | 37s | 8.343 | 7.45% | 3m | 11.98 | 11.87% | 9m | 20.22 | 22.25% | 56m
Ours (PPO) | 3.838 | 0.05% | 9s | 5.734 | 0.67% | 1m | 7.874 | 1.42% | 9m | 11.00 | 2.80% | 16m | 17.64 | 6.65% | 2h16m
Ours (ES) | 3.840 | 0.10% | 9s | 5.828 | 2.32% | 1m | 8.191 | 5.50% | 9m | 11.74 | 9.72% | 16m | 20.27 | 22.55% | 2h16m
OR-Tools* | 3.86 | 0.85% | 1m | 5.85 | 2.87% | 5m | 8.06 | 3.86% | 23m | - | - | - | - | - | -
GAT-T{1000}* | 3.84 | 0.03% | 12m | 5.75 | 0.83% | 16m | 8.01 | 3.24% | 25m | - | - | - | - | - | -
Costa {500}* | 3.84 | 0.01% | 5m | 5.72 | 0.36% | 7m | 7.91 | 1.84% | 10m | - | - | - | - | - | -
Fu et al.* | 3.84 | 0.00% | 1m | 5.70 | 0.01% | 8m | 7.76 | 0.04% | 15m | - | - | - | - | - | -

Neural SA is a general, plug-and-play method, requiring only the definition of
neighbourhoods for the proposal distribution and training problem instances
(no solutions needed). It also obviates time-consuming architecture design,
since a simple MLP is enough for a range of CO problems. In this section, we
discuss some of the main features of Neural SA.

Computational Efficiency Neural SA requires little computational resources
given its compact architecture, with 384 parameters on TSP, 160 for Bin
Packing, and 112 for Knapsack. Further, the cost of each step scales linearly
in the problem size, since the architectures are embarrassingly parallel. In
terms of running times, Neural SA is on par with and often faster than other
TSP solvers (see Tables 3, 12). For the Knapsack and Bin Packing problems, we
compare running times against OR-Tools, as shown in the appendix, Table 4.
Neural SA lags behind OR-Tools in the Knapsack, for which an efficient branch
and bound solver is known. However, for the Bin Packing problem, Neural SA is
much faster than the available Mixed-Integer Programming solver, which only
found trivial solutions for $N{\geq}1000$. Finally, Neural SA is also fast to
train; only a few minutes with PPO and up to a few hours with ES. This is can
be attributed to its low number of parameters but also to its generalisation
ability; in all experiments, we could get away with training _only on the
smallest instances with very short rollouts_.

PPO vs ES Neural SA can be trained with any policy optimisation method making
it highly extendable. We found no winner between PPO and ES, apart from on the
TSP, where PPO excelled and generalized better to larger instances. We also
observed PPO to converge $\sim 10\times$ faster than ES, but ES policies were
more robust, still performing well when we switched to greedy sampling, for
example. Interestingly, the acceptance rate over trajectories was problem
dependent and always higher in Neural SA (both PPO and ES) than in vanilla SA,
contradicting conventional wisdom that it should be held at 0.44 throughout a
rollout (Lam & Delosme, 1988).

Generalisation Our experiments show Neural SA generalises to different problem
sizes and rollout lengths; a remarkable feat for such a simple pipeline, since
transfer learning is notoriously difficult in RL and CO. Many ML4CO methods do
handle problems of different sizes but underperform when tested on larger
instances than the ones seen in training Kool et al. (2018); Joshi et al.
(2019b) (see appendix, Table 9). Fu et al. (2021) achieve better
generalisation results for the TSP but had to resort to a suite of techniques
to allow a small supervised model to be applied to larger problems. These are
not easy to implement, TSP-specific, and consist only the first step in a
complex pipeline that still relies on a tailored Monte-Carlo tree search
algorithm.

Solution Quality In all problems we considered, Neural SA, with little to no
fine-tuning of its hyperparameters, outperformed vanilla SA and could get
within a few percentage points or less of global minima. Conversely, state-of-
the-art SA variants are designed by searching a large space of different
hyperparameters Franzin & Stützle (2019), a costly process that Neural SA
helps us mitigate. Neural SA did not achieve state-of-the-art results, but
that was not to be expected nor our main goal. Instead, we envision Neural SA
as a general purpose solver, allowing researchers and practitioners to get a
strong baseline quickly without the need to fine-tune classic CO algorithms or
design and train complex neural networks. Given the good performance, small
computational resources, and fast training across a diverse set of CO
problems, we believe Neural SA is a promising solver that can strike the right
balance among solution quality, computing costs and development time.

##  6 Conclusion

We presented _Neural SA_ , neurally augmented simulated annealing, where the
SA chain is a trajectory 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) ability to condition the
proposal distribution on side-information 3) no need of ground truth data to
learn the proposal distribution, 4) lightweight architectures that can be run
on CPU unlike many contemporary ML4CO methods, 5) scalability to large
problems due to its lightweight computational overhead, 6) generalisation
across different problem sizes.

These contributions show augmenting classic, time-tested (meta-)heuristics
with learnable components is a promising direction for future research in
ML4CO. In contrast to expensive end-to-end methods in previous work, this
could be a more promising path towards machine learning models capable of
solving a wide range of CO problems. As we show in this paper, this approach
can yield solid results for different problems while preserving theoretical
guarantees of existing CO algorithms and requiring only simple neural
architectures that can be easily trained on small problems.

The ease of use and flexibility of Neural SA do come with drawbacks. In all
experiments we were not able to achieve the minimum energy, even though we
could usually get within a percentage point. The model also has no built-in
termination condition, neither can it provide a certificate on the quality of
solutions found. There is still also the question of how to tune the
temperature schedule, 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 (1986) or genetic algorithms Holland
(1992). For these, we would maintain a population of chains, which could
exchange information.

## References

  * Albergo et al. (2019) Albergo, M., Kanwar, G., and Shanahan, P.  Flow-based generative models for markov chain monte carlo in lattice field theory.  _Physical Review D_ , 100(3):034515, 2019.
  * Andrychowicz et al. (2016) Andrychowicz, M., Denil, M., Gomez, S., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., and De Freitas, N.  Learning to learn by gradient descent by gradient descent.  In _Advances in neural information processing systems_ , pp. 3981–3989, 2016.
  * Applegate et al. (2006) Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J.  _The Traveling Salesman Problem: A Computational Study_.  Princeton University Press, 2006.
  * Bello et al. (2016) Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S.  Neural combinatorial optimization with reinforcement learning.  _CoRR_ , abs/1611.09940, 2016.  URL http://arxiv.org/abs/1611.09940.
  * Beloborodov et al. (2020) Beloborodov, D., Ulanov, A. E., Foerster, J. N., Whiteson, S., and Lvovsky, A.  Reinforcement learning enhanced quantum-inspired algorithm for combinatorial optimization.  _Machine Learning: Science and Technology_ , 2(2):025009, 2020.
  * Bengio et al. (2018) Bengio, Y., Lodi, A., and Prouvost, A.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  _CoRR_ , abs/1811.06128, 2018.  URL http://arxiv.org/abs/1811.06128.
  * Berthold (2013) Berthold, T.  Measuring the impact of primal heuristics.  _Operations Research Letters_ , 41(6):611–614, 2013.  ISSN 0167-6377.  doi: https://doi.org/10.1016/j.orl.2013.08.007.  URL https://www.sciencedirect.com/science/article/pii/S0167637713001181.
  * Blum et al. (2020) Blum, A., Dan, C., and Seddighin, S.  Learning complexity of simulated annealing, 2020.
  * Bonami et al. (2018) Bonami, P., Lodi, A., and Zarpellon, G.  Learning a classification of mixed-integer quadratic programming problems.  In van Hoeve, W.-J. (ed.), _Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , pp. 595–604, Cham, 2018. Springer International Publishing.  ISBN 978-3-319-93031-2.
  * Bresson & Laurent (2021) Bresson, X. and Laurent, T.  The transformer network for the traveling salesman problem.  _arXiv preprint arXiv:2103.03012_ , 2021.
  * Cai et al. (2019) Cai, Q., Hang, W., Mirhoseini, A., Tucker, G., Wang, J., and Wei, W.  Reinforcement learning driven heuristic optimization, 2019.
  * Chen & Tian (2019) Chen, X. and Tian, Y.  Learning to perform local rewriting for combinatorial optimization.  _Advances in Neural Information Processing Systems_ , 32:6281–6292, 2019.
  * Cicirello (2007) Cicirello, V. A.  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\.
  * Croes (1958) Croes, G. A.  A method for solving traveling-salesman problems.  _Operations Research_ , 6:791–812, 1958.
  * da Costa et al. (2020) da Costa, P. R., Rhuggenaath, J., Zhang, Y., and Akcay, A.  Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning.  _CoRR_ , abs/2004.01608, 2020.  URL https://arxiv.org/abs/2004.01608.
  * Dai et al. (2017) Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., and Song, L.  Learning combinatorial optimization algorithms over graphs.  _CoRR_ , abs/1704.01665, 2017.  URL http://arxiv.org/abs/1704.01665.
  * de Haan et al. (2021) de Haan, P., Rainone, C., Cheng, M. C. N., and Bondesan, R.  Scaling up machine learning for quantum field theory with equivariant continuous flows, 2021.
  * Emami & Ranka (2018) Emami, P. and Ranka, S.  Learning permutations with sinkhorn policy gradient.  _CoRR_ , abs/1805.07010, 2018.  URL http://arxiv.org/abs/1805.07010.
  * Finn et al. (2017) Finn, C., Abbeel, P., and Levine, S.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , pp. 1126–1135. PMLR, 2017.
  * Franzin & Stützle (2019) Franzin, A. and Stützle, T.  Revisiting simulated annealing: A component-based analysis.  _Computers & operations research_, 104:191–206, 2019\.
  * Fu et al. (2021) Fu, Z.-H., Qiu, K.-B., and Zha, H.  Generalize a small pre-trained model to arbitrarily large tsp instances.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(8):7474–7482, May 2021.  URL https://ojs.aaai.org/index.php/AAAI/article/view/16916.
  * Gamrath et al. (2020a) Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M. E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., and Witzig, J.  The SCIP Optimization Suite 7.0.  Technical report, Optimization Online, March 2020a.  URL http://www.optimization-online.org/DB_HTML/2020/03/7705.html.
  * Gamrath et al. (2020b) Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M. E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., and Witzig, J.  The SCIP Optimization Suite 7.0.  ZIB-Report 20-10, Zuse Institute Berlin, March 2020b.  URL http://nbn-resolving.de/urn:nbn:de:0297-zib-78023.
  * Gasse et al. (2019) Gasse, M., Chetelat, D., Ferroni, N., Charlin, L., and Lodi, A.  Exact combinatorial optimization with graph convolutional neural networks.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/d14c2267d848abeb81fd590f371d39bd-Paper.pdf.
  * Geman & Geman (1984) Geman, S. and Geman, D.  Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , PAMI-6(6):721–741, 1984.  doi: 10.1109/TPAMI.1984.4767596.
  * Gupta et al. (2020) Gupta, P., Gasse, M., Khalil, E. B., Kumar, M. P., Lodi, A., and Bengio, Y.  Hybrid models for learning to branch.  _CoRR_ , abs/2006.15212, 2020.  URL https://arxiv.org/abs/2006.15212.
  * Hastings (1970) Hastings, W. K.  Monte Carlo sampling methods using Markov chains and their applications.  _Biometrika_ , 57(1):97–109, 04 1970.  ISSN 0006-3444.  doi: 10.1093/biomet/57.1.97.  URL https://doi.org/10.1093/biomet/57.1.97.
  * Helsgaun (2000) Helsgaun, K.  An effective implementation of the lin–kernighan traveling salesman heuristic.  _European Journal of Operational Research_ , 126(1):106–130, 2000.
  * Holland (1992) Holland, J. H.  _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.
  * Ingber (1996) Ingber, L.  Adaptive simulated annealing (asa): lessons learned.  _Control and Cybernetics_ , 25(1), 1996.
  * Ji et al. (2021) Ji, K., Yang, J., and Liang, Y.  Bilevel optimization: Convergence analysis and enhanced design.  In _International Conference on Machine Learning_ , pp. 4882–4892. PMLR, 2021.
  * Johnson (1973) Johnson, D. S.  _Near-optimal bin packing algorithms_.  PhD thesis, Massachusetts Institute of Technology, 1973.
  * Joshi et al. (2019a) Joshi, C. K., Laurent, T., and Bresson, X.  An efficient graph convolutional network technique for the travelling salesman problem.  _arXiv preprint arXiv:1906.01227_ , 2019a.
  * Joshi et al. (2019b) Joshi, C. K., Laurent, T., and Bresson, X.  On learning paradigms for the travelling salesman problem.  _arXiv preprint arXiv:1910.07210_ , 2019b.
  * Khairy et al. (2020) Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., and Balaprakash, P.  Learning to optimize variational quantum circuits to solve combinatorial problems.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(03):2367–2375, Apr 2020.  ISSN 2159-5399.  doi: 10.1609/aaai.v34i03.5616.  URL http://dx.doi.org/10.1609/aaai.v34i03.5616.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  In Bengio, Y. and LeCun, Y. (eds.), _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * Kirkpatrick et al. (1987) Kirkpatrick, S., Gelatt Jr, C. D., and Vecchi, M. P.  Optimization by simulated annealing.  In _Readings in Computer Vision_ , pp. 606–615. Elsevier, 1987\.
  * Kool et al. (2018) Kool, W., van Hoof, H., and Welling, M.  Attention, learn to solve routing problems!  In _International Conference on Learning Representations_ , 2018.
  * Kool et al. (2021) Kool, W., van Hoof, H., Gromicho, J., and Welling, M.  Deep policy dynamic programming for vehicle routing problems.  _arXiv preprint arXiv:2102.11756_ , 2021.
  * Kruber et al. (2017) Kruber, M., Lübbecke, M., and Parmentier, A.  Learning when to use a decomposition.  In _CPAIOR_ , pp. 202–210, 05 2017.  ISBN 978-3-319-59775-1.  doi: 10.1007/978-3-319-59776-8˙16.
  * Lam & Delosme (1988) Lam, J. and Delosme, J.-M.  Performance of a new annealing schedule.  In _Proceedings of the 25th ACM/IEEE Design Automation Conference_ , pp. 306–311, 1988.
  * Likhosherstov et al. (2021) Likhosherstov, V., Song, X., Choromanski, K., Davis, J., and Weller, A.  Debiasing a first-order heuristic for approximate bi-level optimization.  _arXiv preprint arXiv:2106.02487_ , 2021.
  * Maclaurin et al. (2015) Maclaurin, D., Duvenaud, D., and Adams, R. P.  Gradient-based hyperparameter optimization through reversible learning, 2015.
  * Marcos Alvarez et al. (2012) Marcos Alvarez, A., Maes, F., and Wehenkel, L.  Supervised learning to tune simulated 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.
  * Metropolis et al. (1953) Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E.  Equation of state calculations by fast computing machines.  _The Journal of Chemical Physics_ , 21(6):1087–1092, 1953.  doi: 10.1063/1.1699114.  URL https://doi.org/10.1063/1.1699114.
  * Mills et al. (2020) Mills, K., Ronagh, P., and Tamblyn, I.  Finding the ground state of spin hamiltonians with reinforcement learning.  _Nature Machine Intelligence_ , 2(9):509–517, 2020.
  * Noé et al. (2019) Noé, F., Olsson, S., Köhler, J., and Wu, H.  Boltzmann generators: Sampling equilibrium states of many-body systems with deep learning.  _Science_ , 365(6457), 2019.
  * Nomer et al. (2020) Nomer, H. A., Alnowibet, K. A., Elsayed, A., and Mohamed, A. W.  Neural knapsack: A neural network based solver for the knapsack problem.  _IEEE Access_ , 8:224200–224210, 2020.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  Pytorch: An imperative style, high-performance deep learning library.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Pereira & Fernandes (2004) Pereira, A. I. and Fernandes, E. M. G. P.  A study of simulated annealing variants.  In _Proceedings of XXVIII Congreso de Estadística e Investigación Operativa_ , 2004.
  * Perron & Furnon (2019) Perron, L. and Furnon, V.  Or-tools, 2019.  URL https://developers.google.com/optimization/.
  * Rere et al. (2015) Rere, L. R., Fanany, M. I., and Arymurthy, A. M.  Simulated annealing algorithm for deep learning.  _Procedia Computer Science_ , 72:137–144, 2015.  ISSN 1877-0509.  doi: https://doi.org/10.1016/j.procs.2015.12.114.  The Third Information Systems International Conference 2015.
  * Rieck (2021) Rieck, B.  Basic analysis of bin-packing heuristics.  _arXiv preprint arXiv:2104.12235_ , 2021.
  * Salimans et al. (2017) Salimans, T., Ho, J., Chen, X., and Sutskever, I.  Evolution strategies as a scalable alternative to reinforcement learning.  _ArXiv_ , abs/1703.03864, 2017.
  * Salimifard et al. (2012) Salimifard, K., Shahbandarzadeh, H., and Raeesi, R.  Green transportation and the role of operations research.  In _2012 International Conference on Traffic and Transportation Engineering (ICTTE 2012)_ , pp. 74–79, 2012.
  * Schulman et al. (2016) Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P.  High-dimensional continuous control using generalized advantage estimation.  In _Proceedings of the International Conference on Learning Representations (ICLR)_ , 2016.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Swendsen & Wang (1986) Swendsen, R. H. and Wang, J.-S.  Replica monte carlo simulation of spin-glasses.  _Phys. Rev. Lett._ , 57:2607–2609, Nov 1986.  doi: 10.1103/PhysRevLett.57.2607.  URL https://link.aps.org/doi/10.1103/PhysRevLett.57.2607.
  * van Laarhoven & Aarts (1987) van Laarhoven, P. and Aarts, E.  _Simulated Annealing: Theory and Applications_ , chapter 3, Thm. 6\.  Mathematics and Its Applications. Springer Netherlands, 1987.  ISBN 9789027725134.  URL https://books.google.co.in/books?id=-IgUab6Dp_IC.
  * Vashisht et al. (2020) Vashisht, D., Rampal, H., Liao, H., Lu, Y., Shanbhag, D., Fallon, E., and Kara, L. B.  Placement in integrated circuits using cyclic reinforcement learning and simulated annealing, 2020.
  * Vicol et al. (2021) Vicol, P., Metz, L., and Sohl-Dickstein, J.  Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies.  In _International Conference on Machine Learning_ , pp. 10553–10563. PMLR, 2021.
  * Vinyals et al. (2017) Vinyals, O., Fortunato, M., and Jaitly, N.  Pointer networks, 2017.
  * Wauters et al. (2020) Wauters, M. M., Panizon, E., Mbeng, G. B., and Santoro, G. E.  Reinforcement-learning-assisted quantum optimization.  _Physical Review Research_ , 2(3), Sep 2020.  ISSN 2643-1564.  doi: 10.1103/physrevresearch.2.033446.  URL http://dx.doi.org/10.1103/PhysRevResearch.2.033446.
  * Wu et al. (2019a) Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A.  Learning improvement heuristics for solving the travelling salesman problem.  _CoRR_ , abs/1912.05784, 2019a.  URL http://arxiv.org/abs/1912.05784.
  * Wu et al. (2019b) Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A.  Learning improvement heuristics for solving the travelling salesman problem.  _CoRR_ , abs/1912.05784, 2019b.  URL http://arxiv.org/abs/1912.05784.
  * Zaheer et al. (2017) Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J.  Deep sets.  _Advances in Neural Information Processing Systems_ , 30, 2017.

##  Appendix A Additional Experimental Information and Results

###  A.1 General Information

#### Implementation

Our code was implemented in Pytorch 1.9 (Paszke et al., 2019) and run in a
standard machine with a single GPU RTX2080. The code will be made publicly
available upon publication.

#### Architectures

In all experiments, the proposal distribution is parametrised by a two-layer
neural network, with ReLU activation and 16 neurons in the hidden layer:
$\text{input\\_size}\to 16\to 1$, where the size of the input is problem
specific. When using PPO, we also need a critic network to estimate the state-
value function so that we can compute advantages using Generalised Advantage
Estimator (GAE) (Schulman et al., 2016). The critic network does not share any
parameters with the proposal distribution (actor) but has the exact same
architecture. The only difference is that the actor outputs logits of the
proposal distribution, whereas the critic outputs action values from which we
compute the necessary state values.

#### Training

We train Neural SA using both Proximal Policy Optimisation (PPO) (Schulman et
al., 2017) and Evolution Strategies (ES) (Salimans et al., 2017). Across all
experiments, most of the hyper-parameters of both of these methods are kept
constant, as detailed below.

  * •

PPO: We optimise both actor and critic networks using Adam (Kingma & Ba, 2015)
with learning rate of $2\mathrm{e}{-4}$, weight decay of $1\mathrm{e}{-2}$ and
$\beta=(0.9,0.999)$. For PPO, we set the discount factor and clipping
threshold to $\gamma=0.9$ and $\epsilon=0.25$, respectively, and compute
advantages using GAE (Schulman et al., 2016) with trace decay $\lambda=0.9$.

  * •

ES: We use a population of 16 perturbations sampled from a Gaussian of
standard deviation 0.05. Updates are fed into an SGD optimizer with learning
rate 1e-3 and momentum 0.9.

#### Testing

The randomly generated datasets used for testing can be recreated by setting
the seed of Pytorch’s random number generator to $0$. Similarly, we evaluate
each configuration (problem size, number of steps) 5 times and report the
average as well as the standard deviation across the different runs. For
reproducibility, we also seed each of these runs (seeds $1$, $2$, $3$, $4$ and
$5$).

#### Running Times

We compare the running times of Neural SA and other combinatorial optimisation
methods. Table 4 shows the running times of Neural SA against those of OR-
Tools at the Knapsack and Bin Packing problems, while Table 12 show running
times on the Travelling Salesperson Problem for Neural SA and a number of
competing solvers.

Table 4: Comparison of running times (at test time) for Neural SA (PPO/ES) against OR-tools for the Knapsack and Bin Packing Problems. We report the average time to evaluate one instance with each method for different problem sizes. | Knapsack | Bin Packing
---|---|---
| Ours | OR-Tools | Ours | OR-Tools
50N | $<1s$ | $<1s$ | $<1s$ | $54s$
100N | $1s$ | $<1s$ | $1s$ | $56s$
200N | $2s$ | $<1s$ | $3s$ | $\geq 1m$
500N | $6s$ | $1s$ | $10s$ | $\geq 1m$
1000N | $18s$ | $2s$ | $29s$ | $\geq 1m$
2000N | $1m5s$ | $8s$ | $1m43s$ | $\geq 2m$

###  A.2 Knapsack Problem

#### Data

We consider different problem sizes, with Knap$N$ consisting of $N$ items,
each with a weight $w_{i}$ and value $v_{i}$ sampled from a uniform
distribution, $w_{i},v_{i}\sim{\mathcal{U}}_{(0:1)}$. Each problem has also an
associated capacity, that is, the maximum weight the knapsack can comport.
Here we follow (Bello et al., 2016) and set $C_{50}{=}12.5,C_{100}{=}25$ and
$C_{200}{=}25$. However, for larger problems we set $C_{N}=N/8$.

#### Initial Solution

We start with a feasible initial solution corresponding to an empty knapsack,
that is, ${\mathbf{x}}=\mathbf{0}$. That is the trivial (and worst) feasible
solution, so our models do not require any form of initialisation pre-
processing or heuristic.

#### Training

We train _only on_ Knap50 with short rollouts of length $K=100$ steps. The
model is trained for 1000 epochs each of which is run on 256 random problems
generated on the fly as described in the previous section. We set initial and
final temperatures to $T_{0}=1$ and $T_{K}=0.1$, and compute the temperature
decay as $\alpha=\left(T_{K}/T_{0}\right)^{\frac{1}{K}}$.

#### Testing

We evaluate Neural SA on 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=2N$, $K=5N$ and $K=10N$. The initial
and final temperatures are kept fixed to $T_{0}=1$ and $T_{K}=0.1$,
respectively, and the temperature decay varies as function of $K$,
$\alpha=\left(T_{K}/T_{0}\right)^{\frac{1}{K}}$.

We compare our methods against one of the dedicated solvers for knapsack in
OR-Tools (Perron & Furnon, 2019) (Knapsack Multidimension Branch and Bound
Solver). We also compare sampled and greedy variants of Neural SA. The former
samples actions from the proposal distribution while the latter always selects
the most likely action.

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-Tools
---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |
Knap50 | $16.59\pm.00$ | $19.45\pm.01$ | $19.70\pm.00$ | $19.86\pm.00$ | $19.95\pm.00$ | $\bm{20.12}$
Knap100 | $31.15\pm.00$ | $39.07\pm.01$ | $39.49\pm.01$ | $39.76\pm.01$ | $39.90\pm.01$ | $\bm{40.41}$
Knap200 | $55.96\pm.00$ | $53.72\pm.02$ | $55.21\pm.02$ | $56.22\pm.02$ | $56.58\pm.01$ | $\bm{57.65}$
Knap500 | $135.92\pm.00$ | $134.20\pm.05$ | $137.89\pm.03$ | $140.20\pm.02$ | $141.01\pm.03$ | $\bm{144.14}$
Knap1K | $259.20\pm.00$ | $269.21\pm.04$ | $276.48\pm.05$ | $280.94\pm.02$ | $282.46\pm.03$ | $\bm{289.01}$
Knap2K | $489.02\pm.00$ | $537.53\pm.08$ | $551.92\pm.07$ | $560.75\pm.07$ | $563.75\pm.02$ | $\bm{577.28}$
Table 6: PPO 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-Tools
---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |
Knap50 | $19.52\pm.00$ | $19.37\pm.01$ | $19.42\pm.01$ | $19.55\pm.01$ | $19.69\pm.01$ | $\bm{20.12}$
Knap100 | $38.97\pm.00$ | $38.64\pm.01$ | $38.81\pm.01$ | $39.20\pm.01$ | $39.54\pm.01$ | $\bm{40.41}$
Knap200 | $48.58\pm.00$ | $48.99\pm.06$ | $51.00\pm.04$ | $53.57\pm.03$ | $55.03\pm.01$ | $\bm{57.65}$
Knap500 | $119.38\pm.00$ | $122.40\pm.03$ | $128.46\pm.05$ | $134.95\pm.03$ | $138.14\pm.04$ | $\bm{144.14}$
Knap1K | $238.18\pm.00$ | $246.54\pm.09$ | $259.15\pm.08$ | $271.68\pm.05$ | $277.41\pm.03$ | $\bm{289.01}$
Knap2K | $472.67\pm.00$ | $493.47\pm.07$ | $519.27\pm.08$ | $543.72\pm.11$ | $554.32\pm.04$ | $\bm{577.28}$

###  A.3 Bin Packing Problem

#### Data

We consider problems of different sizes, with Bin$N$ consisting of $N$ items,
each with a weight (size) sampled from a uniform distribution,
$w_{i}\sim{\mathcal{U}}_{(0:1)}$. Without loss of generality, we also assume
$N$ bins, all with unitary capacity. Each dataset Bin$N$ in Tables 7 and 8
contains 1000 such random Bin Packing problems used to evaluate the methods at
test time.

#### Initial Solution

We start from the solution where each item is assigned to a different bin,
e.g. $x_{ij}=i$.

#### Training

We train _only on_ 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 keep the same
temperature decay with $\alpha=\left(T_{K}/T_{0}\right)^{\frac{1}{K}}$, but
use different initial and final temperatures for PPO and ES. For PPO, we set
$T_{0}=1$ and $T_{K}=0.1$, whereas for ES we set $T_{0}=0.1$ and $T_{K}=1e-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$, $K=2N$, $K=5N$ and $K=10N$. The initial
and final temperatures are kept the same as in training, and the temperature
decay parameter varies as function of $K$,
$\alpha=\left(T_{K}/T_{0}\right)^{\frac{1}{K}}$.

We compare Neural SA against First-Fit-Decreasing (FFD) (Johnson, 1973), a
powerful heuristic for the Bin Packing problem, and against OR-Tools (Perron &
Furnon, 2019) MIP solver powered by SCIP (Gamrath et al., 2020a). The OR-Tools
solver can be quite slow on Bin Packing so we set a time out of 1 minute per
problem for BIN50-1000 and of 2 minutes for BIN2000 to match Neural SA running
times (see Table 4).

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.

Table 7: ES results on the Bin Packing benchmark. Lower is better. | Greedy | Sampled | OR-Tools | FFD
---|---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |  |
Bin50 | 27.62$\pm.00$ | 27.43$\pm.01$ | 27.36$\pm.01$ | 27.29$\pm.00$ | 27.24$\pm.01$ | $\bm{26.71}$ | 27.10
Bin100 | 53.80$\pm.00$ | 53.63$\pm.00$ | 53.54$\pm.01$ | 53.44$\pm.01$ | 53.38$\pm.01$ | 53.91 | $\bm{52.91}$
Bin200 | 105.63$\pm.00$ | 105.78$\pm.02$ | 105.64$\pm.01$ | 105.51$\pm.01$ | 105.43$\pm.01$ | 109.19 | $\bm{104.25}$
Bin500 | 259.09$\pm.00$ | 260.86$\pm.03$ | 260.65$\pm.01$ | 260.42$\pm.02$ | 260.27$\pm.02$ | $267.63$ | $\bm{257.02}$
Bin1K | 512.66$\pm.00$ | 517.87$\pm.02$ | 517.46$\pm.02$ | 517.08$\pm.02$ | 516.84$\pm.01$ | $1000^{*}$ | $\bm{509.46}$
Bin2K | $\bm{1017.88}\pm.00$ | 1030.66$\pm.01$ | 1029.89$\pm.01$ | 1029.11$\pm.02$ | 1028.67$\pm.02$ | $2000^{*}$ | $1028.67$
Table 8: PPO results on the Bin Packing benchmark. Lower is better. | Greedy | Sampled | OR-Tools | FFD
---|---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |  |
Bin50 | $27.62\pm.00$ | $27.95\pm.01$ | $27.71\pm.01$ | $27.45\pm.01$ | $27.32\pm.01$ | $\bm{26.71}$ | 27.10
Bin100 | $53.80\pm.00$ | $54.88\pm.02$ | $54.27\pm.02$ | $53.75\pm.01$ | $53.53\pm.01$ | $53.91$ | $\bm{52.91}$
Bin200 | $105.63\pm.00$ | $108.51\pm.01$ | $107.20\pm.01$ | $106.21\pm.01$ | $105.86\pm.01$ | $109.19$ | $\bm{104.25}$
Bin500 | $259.08\pm.00$ | $268.42\pm.02$ | $264.79\pm.01$ | $262.66\pm.02$ | $261.98\pm.01$ | $267.63$ | $\bm{257.02}$
Bin1K | $512.66\pm.00$ | $533.97\pm.04$ | $526.23\pm.02$ | $522.30\pm.03$ | $521.22\pm.02$ | $1000^{*}$ | $\bm{509.46}$
Bin2K | $\bm{1017.88}\pm.00$ | $1064.74\pm.11$ | $1048.80\pm.06$ | $1041.02\pm.01$ | $1039.09\pm.04$ | $2000^{*}$ | $1028.67$

###  A.4 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 (Kool et al., 2018;
Chen & Tian, 2019; da 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).

#### Initial Solution

We start with a random tour, which is simply a random permutation of the city
indices. This is likely to be a poor initial solution, as it ignores any
information about the problem, namely the coordinates of each city.
Nevertheless, Neural SA achieves competitive results in spite of this, and it
is reasonable to expect an improvement in its performance (at least in running
time) when using better initialisation methods, like in LKH-3 (Helsgaun, 2000)
for instance.

#### 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 epoch. We also maintain the same initial
temperature and cooling schedule with $T_{0}=1$ and
$\alpha=\left(T_{K}/T_{0}\right)^{\frac{1}{K}}$, but use lower final
temperatures for the TSP. We set $T_{K}=1\mathrm{e}{-2}$ for PPO and
$T_{K}=1\mathrm{e}{-4}$ for ES, which we empirically found to work best with
the training dynamics of each of these methods. We also use different number
of epochs for each training method, 1000 for PPO and 10 000 for ES, as the
latter has slower convergence.

#### 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 to directly
compare our methods to previous research on the TSP. We also consider larger
problem sizes, namely TSP200 and TSP500 to showcase the scalability of Neural
SA. For each of these, we randomly generate 1000 instances by uniformly
sampling coordinates in a 2D unit square. For each problem size $N$, we
consider rollouts of length $K=N^{2}$, $K=2N^{2}$, $K=5N^{2}$ and $K=10N^{2}$.
That is different from the other CO problems we study since the complexity in
the TSP is related to the number of edges $N^{2}$ rather than the number of
cities $N$. 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.

We compare Neural SA against standard solvers LKH-3 (Helsgaun, 2000) and
Concorde (Applegate et al., 2006), which we have run 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 et al. (2018):
GCN (Joshi et al., 2019b), GAT (Kool et al., 2018), GAT-T (Wu et al., 2019a),
and the works of da Costa et al. (2020) and Fu et al. (2021).

Note that Fu et al. (2021) also provide results for TSP200 and TSP500, but
given that we do not know the exact test instances they used, it is hard to
make a direct comparison to our results, especially regarding running times;
they use a dataset of 128 instances, while we use 1000. For that reason, we
omitted these results from Table 3 in the main text, but for the sake of
completeness, presented them in Table 12.

#### Generalisation

We always train Neural SA only on the smallest of problem sizes we consider.
In Table 9, we compare Neural SA with other models in the literature that have
been evaluated the same way: trained on TSP20 only and tested on TSP20, 50 and
100. While not outperforming the model by Fu et al. (2021), Neural SA,
especially with PPO, does generalise better than previous end-to-end methods
Kool et al. (2018).

Table 9: Optimality gap for models trained on TSP20 and evaluated on the test instances provided by Kool et al. (2018) for TSP20/50/100; *Values taken from respective papers. | TSP20 | TSP50 | TSP100
---|---|---|---
Kool et al. (2018)* | $0.34\%$ | $\sim 5.0\%$ | $>14.0\%$
Fu et al. (2021)* | $0.00\%$ | $0.01\%$ | $0.04\%$
SA | $1.17\%$ | $4.34\%$ | $7.43\%$
Neural SA (PPO) | $0.42\%$ | $1.16\%$ | $1.85\%$
Neural SA (ES) | $0.10\%$ | $2.32\%$ | $5.50\%$
Table 10: ES results on the TSP benchmark. Lower is better | Greedy | Sampled | LKH-3 | Concorde
---|---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |  |
TSP20 | $3.868\pm.000$ | $3.868\pm.001$ | $3.854\pm.000$ | $3.844\pm.000$ | $3.840\pm.000$ | 3.836 | 3.836
TSP50 | $6.020\pm.002$ | $6.022\pm.002$ | $5.947\pm.001$ | $5.871\pm.000$ | $5.828\pm.001$ | 5.696 | 5.696
TSP100 | $8.659\pm.003$ | $8.660\pm.002$ | $8.477\pm.001$ | $8.298\pm.002$ | $8.191\pm.002$ | 7.764 | 7.764
Table 11: PPO results on the TSP benchmark. Lower is better | Greedy | Sampled | LKH-3 | Concorde
---|---|---|---|---
| $\times 1$ | $\times 1$ | $\times 2$ | $\times 5$ | $\times 10$ |  |
TSP20 | $3.864\pm.000$ | $3.865\pm.000$ | $3.850\pm.000$ | $3.841\pm.000$ | $3.838\pm.000$ | 3.836 | 3.836
TSP50 | $5.828\pm.001$ | $5.828\pm.000$ | $5.786\pm.000$ | $5.752\pm.001$ | $5.734\pm.001$ | 5.696 | 5.696
TSP100 | $8.074\pm.001$ | $8.073\pm.001$ | $7.986\pm.001$ | $7.912\pm.001$ | $7.874\pm.000$ | 7.764 | 7.764
TSP200 | $11.41\pm.00$ | $11.41\pm.00$ | $11.23\pm.00$ | $11.09\pm.00$ | $11.00\pm.00$ | 10.70 | 10.70
TSP500 | $18.44\pm.002$ | $18.43\pm.001$ | $18.07\pm.003$ | $17.79\pm.006$ | $17.64\pm.003$ | 16.54 | 16.54
Figure 7: Policy for the Travelling Salesperson Problem. At each step, an
action consists of selecting a pair of cities $(i,j)$, one after the other.
The figure depicts a TSP problem layed out in the 2D plane, with the learnt
proposal distribution over the first city $i$ in the left, and in the right,
the distribution over the second city $j$, given $i=12$. We mask out and
exclude the neighbours of $i$ ($0$ and $14$) as candidates for $j$ because
selecting those would lead to no changes in the tour. It is clear the model
has a strong preference towards a few cities, but otherwise the probability
mass is spread almost uniformly among the other nodes. However, once $i$ is
fixed, Neural SA strongly favours nodes $j$ that are close to $i$. That is a
desirable behaviour and even features in popular algorithms like LKH-3
(Helsgaun, 2000). That is because a 2-opt move $(i,j)$ actually adds edge
$(i,j)$ to the tour, so leaning towards pairs of cities that are close to each
other is more likely to lead to shorter tours. Table 12: Comparison of
different TSP solvers on the 10K instances for TSP20/50/100 provided in Kool
et al. (2018), and 1K random instances for TSP200/500. We report the average
solution cost, optimality gap and running time (to solve all instances) for
each problem size. We split competing neural methods in two groups:
construction heuristics Kool et al. (2018); Joshi et al. (2019a) and
improvement heuristics like Neural SA Wu et al. (2019a); da Costa et al.
(2020); Fu et al. (2021). *Values as reported in the corresponding paper. †
Different test data.

| TSP20 | TSP50 | TSP100 | TSP200 | TSP500
---|---|---|---|---|---
| Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time | Cost | Gap | Time
Concorde (Applegate et al., 2006) | 3.836 | 0.00% | 48s | 5.696 | 0.00% | 2m | 7.764 | 0.00% | 7m | 10.70 | 0.00% | 38m | 16.54 | 0.00% | 7h58m
LKH-3 (Helsgaun, 2000) | 3.836 | 0.00% | 1m | 5.696 | 0.00% | 14m | 7.764 | 0.00% | 1h | 10.70 | 0.00% | 21m | 16.54 | 0.00% | 1h15m
OR-Tools (Perron & Furnon, 2019) | 3.86 | 0.85% | 1m | 5.85 | 2.87% | 5m | 8.06 | 3.86% | 23m | - | - | - | - | - | -
SA | 3.881 | 1.17% | 10s | 5.943 | 4.34% | 37s | 8.343 | 7.45% | 3m | 11.98 | 11.87% | 9m | 20.22 | 22.25% | 56m
Neural SA PPO | 3.837 | 0.02% | 17s | 5.727 | 0.54% | 1m | 7.856 | 1.18% | 9m | 10.96 | 2.50% | 15m | 17.64 | 6.65% | 2h16m
Neural SA ES | 3.840 | 0.10% | 10s | 5.828 | 2.32% | 1m | 8.191 | 5.50% | 9m | 11.74 | 9.72% | 15m | 20.27 | 22.55% | 2h16m
GCN Greedy (Joshi et al., 2019a)* | 3.86 | 0.60% | 6s | 5.87 | 3.10% | 55s | 8.41 | 8.38% | 6m | - | - | - | - | - | -
GCN Beam Search (Joshi et al., 2019a)* | 3.84 | 0.01% | 12m | 5.70 | 0.01% | 18m | 7.87 | 1.39% | 40m | - | - | - | - | - | -
GAT Greedy (Kool et al., 2018)* | 3.85 | 0.34% | 0s | 5.80 | 1.76% | 2s | 8.12 | 4.53% | 6s | - | - | - | - | - | -
GAT Sampling (Kool et al., 2018)* | 3.84 | 0.08% | 5 m | 5.73 | 0.52% | 24m | 7.94 | 2.26% | 1 h | - | - | - | - | - | -
GAT-T {1000} (Wu et al., 2019a)* | 3.84 | 0.03% | 12m | 5.75 | 0.83% | 16m | 8.01 | 3.24% | 25m | - | - | - | - | - | -
GAT-T {3000} (Wu et al., 2019a)* | 3.84 | 0.00% | 39m | 5.72 | 0.34% | 45 m | 7.91 | 1.85% | 1 h | - | - | - | - | - | -
GAT-T {5000} (Wu et al., 2019a)* | 3.84 | 0.00% | 1 h | 5.71 | 0.20% | 1 h | 7.87 | 1.42% | 2 h | - | - | - | - | - | -
da Costa et al. (2020) {500}* | 3.84 | 0.01% | 5m | 5.72 | 0.36% | 7m | 7.91 | 1.84% | 10m | - | - | - | - | - | -
da Costa et al. (2020) {1000}* | 3.84 | 0.00% | 10m | 5.71 | 0.21% | 13m | 7.86 | 1.26% | 21 m | - | - | - | - | - | -
da Costa et al. (2020) {2000}* | 3.84 | 0.00% | 15m | 5.70 | 0.12% | 29m | 7.83 | 0.87% | 41m | - | - | - | - | - | -
Att-GCRN+MCTS (Fu et al., 2021)* | 3.84 | 0.00% | 2m | 5.69 | 0.01% | 9m | 7.76 | 0.03% | 15m | 10.81† | 0.88%† | 3m† | 16.96† | 2.96%† | 6m†