A practical solution for the Beltway problem

The Beltway problem is a famous, important, and basic problem in computational geometry with a vast application in bioinformatics and crystallography. Not only the complexity class of the Beltway problem is not known, but there is no practical non-polynomial time algorithm to solve it. This paper presents a fast algorithm using constraint satisfaction modeling to solve the problem. To the best of the author’s knowledge, there is no deterministic algorithm that can solve the Beltway problem for large instances. The experiments on the presented algorithm in this paper, show that the algorithm runs well for random instances and has acceptable results for hard instances.