Parallel implementation of simulated annealing using transaction processing: a preliminary study

Simulated annealing is an effective method for solving large combinatorial optimization problems. It has been successfully applied to the cell placement and routing problem of VLSI circuit design and to other classical optimization problems such as the traveling salesman problem and the graph partitioning problem. One major drawback of simulated annealing is that it requires a substantial amount of computation time. In this paper, we present a new parallel implementation of simulated annealing which is based on the concurrency control theory of database systems. The parallelized computation is serializable. Hence, the result obtained is equivalent to a serial execution of the original sequential annealing algorithm. In our implementation, we assume a shared-memory MIMD multiprocessing environment with 16 to 32 processors. Preliminary analysis shows that our method is able to achieve an efficiency (ratio of speedup to the number of processors) of from about 40 to over 90%, depending on the acceptance rate