Parallel Rejectionless Annealing for Discrete Combinatorial Optimisation

A parallel implementation of the rejectionless annealing algorithm of Greene and Supowit is presented. This extends the work done by Lister, which demonstrated that a parallel version of the algorithm was possible. This approach has been applied to rejectionless annealing and the results presented here. The implementation was first tested on the Ising Spin problem. The Travelling Salesman problem was then implemented to demonstrate the efficient parallel nature of the algorithm. The paper shows that the model is efficient for the parallel solution of combinatorial optimisation problems, and reports on some performance results. 1 Introduction Combinatorial optimisation is an active area of computing science research. There are many different techniques for solving such problems. A good general technique is simulated annealing [4]. Rejectionless annealing extends conventional simulated annealing to improve the solutions obtained at the cost of increased run time [2]. Parallel computing ..