Parallel tempering for the traveling salesman problem

Chiaming Wang, Jeffrey D. Hyman, Allon Percus, Russel Caflisch

Research output: Contribution to journalArticlepeer-review

Abstract

We explore the potential of parallel tempering as a combinatorial optimization method, applying it to the traveling salesman problem. We compare simulation results of parallel tempering with a benchmark implementation of simulated annealing, and study how different choices of parameters affect the relative performance of the two methods. We find that a straightforward implementation of parallel tempering can outperform simulated annealing in several crucial respects. When parameters are chosen appropriately, both methods yield close approximation to the actual minimum distance for an instance with 200 nodes. However, parallel tempering yields more consistently accurate results when a series of independent simulations are performed. Our results suggest that parallel tempering might offer a simple but powerful alternative to simulated annealing for combinatorial optimization problems.

Original languageEnglish (US)
Pages (from-to)539-556
Number of pages18
JournalInternational Journal of Modern Physics C
Volume20
Issue number4
DOIs
StatePublished - Apr 2009

Keywords

  • Combinatorial optimization
  • Parallel tempering
  • Simulated annealing
  • Traveling salesman problem

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics
  • General Physics and Astronomy
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Parallel tempering for the traveling salesman problem'. Together they form a unique fingerprint.

Cite this