A Boltzmann machine solution of the traveling salesperson problem: a study for parallel implementation

Neural net algorithms are intrinsically parallel. They are also often used for solving difficult optimization problems. It is therefore natural to investigate the speedup which might be obtained by implementing a neural net algorithm on a parallel architecture. This work explores that question by looking at three possible implementations of the traveling salesperson problem (TSP) on a binary Boltzmann machine. These three implementations vary in their degree of parallelization. The results suggest that there are important relationships between the amount of speedup obtainable and the quality of solutions obtained. A general framework for studying such questions is described