A New Parallel Schema for Branch-and-Bound Algorithms Using GPGPU

• Tiago Carneiro UECE
• Albert Einstein Muritiba UFC
• Marcos Negreiros UECE-IFCE / UFC
• Gustavo Augusto Lima de Campos UECE

Resumo

This work presents a new parallel procedure designed to process combinatorial B&B algorithms using GPGPU. In our schema we dispatch a number of threads that treats intelligently the massively parallel processors of NVIDIA GeForce graphical units. The strategy is to build sequentially a series of initial searches that can map a subspace of the B&B tree by starting a number of limited threads after achieving a specific level of the tree. The search is then processed massively by DFS. The whole subspace is optimized accordingly to memory and limits of threads and blocks available by the GPU. We compare our results with its OpenMP and Serial versions of the same search schema using explicitly enumeration (all possible solutions) to the Asymmetrical Travelling Salesman Problem's instances. We also show the great superiority of our GPGPU based method.

Palavras-chave: Cities and towns, Graphics processing unit, Approximation algorithms, Algorithm design and analysis, Search problems, Multicore processing, CUDA, Branch-and-Bound, ATSP, GPGPU