Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning

David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch and Catherine Schevon
Additional contact information
David S. Johnson: AT&T Bell Laboratories, Murray Hill, New Jersey
Cecilia R. Aragon: University of California, Berkeley, California
Lyle A. McGeoch: Amherst College, Amherst, Massachusetts
Catherine Schevon: Johns Hopkins University, Baltimore, Maryland

Operations Research, 1989, vol. 37, issue 6, 865-892

Abstract: In this and two companion papers, we report on an extended empirical study of the simulated annealing approach to combinatorial optimization proposed by S. Kirkpatrick et al. That study investigated how best to adapt simulated annealing to particular problems and compared its performance to that of more traditional algorithms. This paper (Part I) discusses annealing and our parameterized generic implementation of it, describes how we adapted this generic algorithm to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm. (For sparse random graphs, it tended to outperform Kernighan-Lin as the number of vertices become large, even when its much greater running time was taken into account. It did not perform nearly so well, however, on graphs generated with a built-in geometric structure.) We also discuss how we went about optimizing our implementation, and describe the effects of changing the various annealing parameters or varying the basic annealing algorithm itself.

Keywords: networks/graphs; heuristics: algorithms for graph partitioning; simulation; applications: optimization by simulated annealing (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (92)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.6.865 (application/pdf)

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:inm:oropre:v:37:y:1989:i:6:p:865-892

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().