Trading accuracy for speed in parallel simulated annealing with simultaneous moves

Abstract

A common approach to parallelizing simulated annealing is to generate several perturbations to the current solution simultaneously, requiring synchronization to guarantee correct evaluation of the cost function. The cost of this synchronization may be reduced by allowing inaccuracies in the cost calculations. We provide a framework for understanding the theoretical implications of this approach based on a model of processor interaction under reduced synchronization that demonstrates how errors in cost calculations occur and how to estimate them. We show how bounds on error in the cost calculations in a simulated annealing algorithm can be translated into worst-case bounds on perturbations in the parameters which describe the behavior of the algorithm.