Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections

Chang Sung Jeong, Myung Ho Kim

Research output: Contribution to journalArticlepeer-review

25 Citations (Scopus)

Abstract

In this paper, we present a fast parallel simulated annealing algorithm for solving traveling salesman problem(TSP) on SIMD machines with linear interconnections among processing elements. Simulated annealing is a generally applicable algorithm for solving combinatorial optimization problems by generating a sequence of moves at decending values of a control parameter. In our algorithm for TSP, the move operation can be executed in proportional to the time taken to broadcast a bit in one processing element (PE) to all the other PE's. Therefore, if a control unit has the broadcasting capability as is often the case with the SIMD machine, the move operation can be done in constant time and the whole simulated annealing algorithm has the time complexity only proportional to the number of the moves.

Original languageEnglish
Pages (from-to)221-228
Number of pages8
JournalParallel Computing
Volume17
Issue number2-3
DOIs
Publication statusPublished - 1991 Jun
Externally publishedYes

Keywords

  • SIMD multi-processors
  • Simulated annealing
  • parallel implementation features
  • traveling salesman problem

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections'. Together they form a unique fingerprint.

Cite this