Parallel implementation of simulated annealing using transaction processing

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

7 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)107-113
Journal / PublicationIEE Proceedings: Computers and Digital Techniques
Volume146
Issue number2
Publication statusPublished - 1999

Abstract

Simulated annealing is an effective method for solving large combinatorial optimization problems. Because of its iterative nature the annealing process requires a substantial amount of computation time. A new parallel implementation based on the concurrency control theory of database systems is presented; the parallelized annealing process is serializable. Concurrent updates to the base solution are allowed provided that they do not have data conflict. Using the travelling salesman problem as the example application, the parallel simulated annealing algorithm is implemented on a Motorola Delta 3000 shared-memory multiprocessor system with eight processors. With a moderate problem size of 400 cities, a speedup efficiency of over 90% is achieved at high annealing temperature and close to 100% at a low annealing temperature.