An Efficient Simulated Annealing Schedule: Implementation and Evaluation
Jimmy Lam and Jean-Marc Delosme
Report 8817
September 1988
Department of Computer Science, Yale University.
Department of Electrical Engineering, Yale University.
Abstract
We present an implementation of an efficient general simulated annealing schedule and demonstrate experimentally that the new schedule achieves speedups often exceeding an order of magnitude when compared with other general schedules currently available in the literature. To assess the performance of simulated annealing as a general method for solving combinatorial optimization problems, we also compare the method with efficient heuristics on well-studied problems: the traveling salesman problem and the graph partition problem. For high quality solutions and for problems with a small number of close to optimal solutions, our test results indicate that simulated annealing out-performs the heuristics of Lin and Kernighan and of Karp for the traveling salesman problem, and multiple executions of the heuristic of Fiduccia and Mattheyses for the graph partition problem.