Parallelizing an exact algorithm for the traveling salesman problem

We describe a project of an exact parallel algorithm for traveling salesman problems (TSPs) of large sizes. It is based on the algorithm developed by E. Balas and N. Christofides almost 40 years ago. Balas' and Christofides' algorithm uses branch-and-bound, Hungarian algorithm for assignment problem, and several heuristics to effectively eliminate unnecessary branches of the solution tree. We propose several modifications (including parallelization) of the simplified version of their algorithm which should improve its performance. The modified algorithm was implemented in C++ with OpenMP and tested on graphs with around 1000 nodes. Computational results indicate a possibility of getting exact solutions of TSPs with 10000 nodes in minutes. New heuristic algorithms could be derived from the exact algorithm to solve even bigger problems. Such algorithms could be applied to genome assembly.