A parallel statistical cooling algorithm. (English) Zbl 0601.65051

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.


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


Zbl 0578.00004