Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network

This paper is the first to present a parallelization of a highly efficient best-first branch-and-bound algorithm to solve large symmetric traveling salesman problems on a massively parallel computer containing 1024 processors. The underlying sequential branch-and-bound algorithm is based on 1-tree relaxation. The parallelization of the branch-and-bound algorithm is fully distributed. Every processor performs the same sequential algorithm but on a different part of the solution tree. To distribute subproblems among the processors we use a new direct-neighbor dynamic load-balancing strategy. The general principle can be applied to all other branch-and-bound algorithms leading to an “automatic” parallelization. At present we can efficiently solve traveling salesman problems up to a size of 318 cities on networks of up to 1024 transputers. On hard problems we achieve an almost linear speed-up