A parallel threads coordination scheme for solving combinatorial optimization problems

This paper presents a parallel approach of coordinating massive parallel threads on many-core platforms to solve combinatorial optimization problems. The parallel approach is based on heuristic search that exploits parallelism at two cascade levels: (1) search level for launching multiple searches in parallel, and (2) move level for exploring multiple solutions concurrently. Those parallel searches are coordinated during the search process and a mutation scheme is proposed to improve solution quality. The Traveling Salesman Problem is used as a case study to illustrate the effectiveness of the proposed approach. Experimental results show that the proposed technique can improve solution quality by 5.9%. Compared with a parallel CPU implementation, the proposed many-core based approach can search solutions 389.7 times faster and improve solution quality by 10.4%.