The analysis of cost error in parallel simulated annealing

Simulated annealing is a powerful and general algorithm for solving combinatorial optimization problems, but it takes an extremely long time to execute. The resulting cost error from a reduction of the costly synchronization in distributed-memory multicomputers is tolerated by the hill climbing nature of simulated annealing. The authors address the behavior of algorithms that contain the cost error. The new cost error measurement and relaxing synchronization method predicts the amount of cost error that an algorithm will tolerate and still converge. This method also explains certain interesting phenomena of the cost error statistically. Finally, the authors apply the new method to the problem of composite material stock cutting. Implementation results of the parallel space-decomposition algorithm on an Intel iPSC/2 are reported.