Parallel implementation of simulated annealing using transaction processing

Simulated annealing is an effective method for solving large combinatorial optimisation problems. Because of its iterative nature the annealing proces s requires a substantial amount of computation time. A new parallel impleme ntation based on the concurrency control theory of database systems is pres ented; the parallelised annealing process is serialisable. Concurrent updat es to the base solution are allowed provided that they do not have data con flict. Using the travelling salesman problem as the example application, th e parallel simulated annealing algorithm is implemented on a Motorola Delta 3000 shared-memory multiprocessor system with eight processors. With a mod erate problem size of 400 cities, a speedup efficiency of over 90% is achie ved at high annealing temperature and close to 100% at a low annealing temp erature.