A parallel statistical cooling algorithm. (English) Zbl 0601.65051

Aarts, E. H. L.; de Bont, F. M. J.; Habers, J. H. A.; van Laarhoven, P. J. M.

Theoretical aspects of computer science, 3rd annu. Symp., Orsay/France 1986, Lect. Notes Comput. Sci. 210, 87-97 (1986).

[For the entire collection see Zbl 0578.00004.]
Statistical cooling is a new optimization technique based on Monte-Carlo iterative improvement. Here we propose a parallel formulation of the statistical cooling algorithm based on the requirement that quasi- equilibrium is preserved throughout the optimization process. It is shown that the parallel algorithm can be executed in polynomial time. Performance of the algorithm is discussed by means of an implementation on an experimental multi-processor architecture. It is concluded that substantial reductions of computation time can be achieved by the parallel algorithm in comparison with the sequential algorithm.

MSC:

65K05	Numerical mathematical programming methods
65C05	Monte Carlo methods
90C27	Combinatorial optimization

Keywords:

combinatorial optimization; Statistical cooling; Monte-Carlo iterative improvement; parallel algorithm; multi-processor

Citations:

Zbl 0578.00004