Optimization by simulated annealing: An experimental evaluation. I: Graph partitioning. (English) Zbl 0698.90065

Johnson, David S.; Aragon, Cecilia R.; McGeoch, Lyle A.; Schevon, Catherine

Oper. Res. 37, No. 6, 865-892 (1989).

The method of simulated annealing is applied to graph partitioning problems. Following an explanation of the basic concepts of annealing, problem-specific details, tested problem classes, and experimental results are described. Optimization of parameters as well as modifications of the generic algorithm are discussed. In comparison to other heuristics simulated annealing is judged to be a competitive approach to graph partitioning problems.

Reviewer: U.Zimmermann

MSC:

90C27	Combinatorial optimization
65K05	Numerical mathematical programming methods
90C35	Programming involving graphs or networks

Keywords:

simulated annealing; graph partitioning; experimental results; heuristics