Boltzmann machines for travelling salesman problems (Q1119182)

Boltzmann machines are proposed as a massively parallel alternative to the (sequential) simulated annealing algorithm. Our 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 formulations of the traveling 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.