PARALLEL TEMPERING FOR THE TRAVELING SALESMAN PROBLEM

Chiaming Wang (), Jeffrey D. Hyman (), Allon Percus () and Russel Caflisch ()
Additional contact information
Chiaming Wang: Mathematics Department, University of California at Los Angeles, Los Angeles, CA 90095-1555, USA
Jeffrey D. Hyman: Mathematics Department, University of California at Los Angeles, Los Angeles, CA 90095-1555, USA
Allon Percus: Information Sciences Group, Los Alamos National Laboratory, Los Alamos, NM 87545, USA;
Russel Caflisch: Mathematics Department, University of California at Los Angeles, Los Angeles, CA 90095-1555, USA

International Journal of Modern Physics C (IJMPC), 2009, vol. 20, issue 04, 539-556

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.

Keywords: Parallel tempering; combinatorial optimization; simulated annealing; traveling salesman problem; 11.25.Hf; 123.1K (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183109013893
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:20:y:2009:i:04:n:s0129183109013893

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183109013893

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().