MPSA

MPSA: A methodology to parallelize simulated annealing and its application to the traveling salesman problem. The Methodology to Parallelize Simulated Annealing (MPSA) leads to massive parallelization by executing each temperature cycle of the Simulated Annealing (SA) algorithm in parallel. The initial solution for each internal cycle is set through a Monte Carlo random sampling to adjust the Boltzmann distribution at the cycle beginning. MPSA uses an asynchronous communication scheme and any implementation of MPSA leads to a parallel Simulated Annealing algorithm that is in general faster than its sequential implementation version while the precision is held. This paper illustrates the advantages of the MPSA scheme by parallelizing a SA algorithm for the Traveling Salesman Problem.