Next: Phase II Up: Computing the Facilities Previous: Computing the Facilities

### Phase I

We choose a standard simulated annealing approach for continuous global optimization problems to compute approximations of global optima. Since there are already good implementations of several codes in the public domain, we choose the code of Goffe, Ferrier and Rogers [11] as a starting point for our own implementation. After preliminary testing, we found that their code outperformed the code of Ingber [12] when applied to the facility dispersion problem above. However, we have not tried to fine tune every possible parameter in the implementation of Ingber. Doing this may result in significant performance gains.

It turned out that after the implementation of the objective function some changes in the parameters were necessary in order to have a program that produces good results. We list here only the most important parameters, for details about the implementation we refer to [10, 11].

We set the starting temperature of the simulated annealing algorithm to T := 5.0. If N denotes the total number of facilities in the problem, the temperature is reduced after 5 N steps according to . The maximum number of function evaluations is set to 100 N. The algorithm stops when the maximum number of function evaluations is achieved or when the changes in the best known function values during the last four temperature reductions and the differences between the function values in the last step are less than . Note that, due to the peculiar chosen parameters, at most 20 temperature reductions take place. Since the temperature is reduced by a fixed amount, the algorithm used is in fact a specific form of simulated quenching, not simulated annealing. However, after experimenting with different annealing schemes, we never found that the algorithm got stuck in a nonglobal minimum, even with such a strict annealing schedule.

As it can be seen, the stopping criterion based on function values is not a particular strict one. This is the case because there is no necessity for high accuracy in Phase I. The algorithm of the second phase will converge to the minimum approached by the simulated annealing algorithm much faster than a stochastic method.

Next: Phase II Up: Computing the Facilities Previous: Computing the Facilities

Joerg Fliege
Thu Dec 23 19:39:35 CET 1999