In this and two companion papers, the authors 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 the present parameterized generic implementation of it, describes how the authors 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.) The authors also discuss how they went about optimizing their implementation, and describe the effects of changing the various annealing parameters or varying the basic annealing algorithm itself.
