Article ID: | iaor19881215 |
Country: | Netherlands |
Volume: | 39 |
Issue: | 1 |
Start Page Number: | 79 |
End Page Number: | 95 |
Publication Date: | Mar 1989 |
Journal: | European Journal of Operational Research |
Authors: | Aarts Emile H.L., Korst Jan H.M. |
Keywords: | optimization: simulated annealing |
Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. The present approach is tailored to the travelling salesman problem, but it can also be applied to a more general class of combinatorial optimization problems. For two distinct 0-1 programming formulations of the travelling salesman problem (as a linear and as a quadratic assignment problem) it is shown that near-optimal solutions can be obtained by mapping the corresponding 0-1 variables onto the logic computing elements of a Boltzmann machine, and by transforming the cost functions corresponding to the 0-1 programming formulations into the consensus function associated with the Boltzmann machine. Results of computer simulations are presented for two problem instances, i.e. with 10 cities and 30 cities, respectively.