Content area
An experimental evaluation is presented of a parallel version of simulated annealing, following the theoretic framework for a distributed parallel implementation set by Barbosa and Gafni (1989). Such an implementation uses up to as many processing elements as there are variables in a problem. The technique has been applied to the minimum vertex cover problem, which is NP-complete and admits a fast centralized heuristic with known performance bounds. This problem is well suited to acceleration through the form of parallel stochastic search under investigation. It is also representative of a broader class of equally hard problems with the same property. Experiments on random graphs have demonstrated that the parallel technique significantly surpasses the heuristic in quality of the solution. The tests were conducted on a transputer-based system, using the OCCAM language for parallel programming.