Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number 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, 1991, vol. 39, issue 3, 378-406

Abstract: This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization. Simulated annealing is a randomized technique proposed by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi for improving local optimization algorithms. Here we report on experiments at adapting simulated annealing to graph coloring and number partitioning, two problems for which local optimization had not previously been thought suitable. For graph coloring, we report on three simulated annealing schemes, all of which can dominate traditional techniques for certain types of graphs, at least when large amounts of computing time are available. For number partitioning, simulated annealing is not competitive with the differencing algorithm of N. Karmarkar and R. M. Karp, except on relatively small instances. Moreover, if running time is taken into account, natural annealing schemes cannot even outperform multiple random runs of the local optimization algorithms on which they are based, in sharp contrast to the observed performance of annealing on other problems.

Keywords: mathematics; combinatorics: number partitioning heuristics; networks/graphs; heuristics: graph coloring heuristics; simulation; applications: optimization by simulated annealing (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (64)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.3.378 (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:39:y:1991:i:3:p:378-406

Access Statistics for this article

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