Trading accuracy for speed in parallel simulated annealing algorithms

Simulated annealing is an iterative algorithm to find approximate solutions to intractable optimization problems. It uses a cost function to evaluate the quality of the intermediate solutions. Since simulated annealing is effective but slow, researchers have turned to parallelism to improve its performance. For many parallel implementations of simulated annealing, synchronization is a bottleneck. By allowing processors to use out-of-date state information to compute the cost function, the speed of the algorithm can be improved because the need for synchronization is reduced. However, as a result, errors are introduced into the cost calculations. In some experimental work reported in the literature, these errors resulted in worse solution quality, whereas in others the error had little or no effect on the final result. My work provides a better understanding of reduced synchronization in parallel simulated annealing and the effect of the resulting error. I present a formal model of how processors interact when synchronization is reduced in parallel simulated annealing and the cost calculation error which results. For a parallel simulated annealing algorithm to converge, synchronization constraints may be relaxed but not eliminated completely. The minimum synchronization needed can be determined from the model. This indicates how tasks should be scheduled in parallel simulated annealing. I present bounds on the error which occurs when synchronization is reduced for both shared memory and distributed memory paradigms and show that the worst-case error for the distributed memory case is always greater than or equal to the worst-case error in the shared memory case. These bounds on errors in the cost calculations can be translated into worst-case bounds on perturbations in the parameters which describe the behavior of the algorithm. The results show that the behavior of parallel simulated annealing does not differ greatly from the behavior of serial simulated annealing when the errors are small compared to the temperature. Worst-case bounds on the effect of error on final solution quality are also given. Experimental results confirming the theoretical work are presented.