Depth-First Search versus Jurema Search on GPU Branch-and-Bound Algorithms: a case study

Tiago Carneiro, Ricardo Nobre, Marcos Negreiros
Mestrado Academico em Ciencias da Computacao (MACC), Universidade Estadual do Ceara, Brazil
CSBC, 2012


   title={Depth-First Search versus Jurema Search on GPU Branch-and-Bound Algorithms: a case study},

   author={Carneiro, Tiago and Nobre, Ricardo and Negreiros, Marcos and de Campos, Gustavo Augusto Lima},



Download Download (PDF)   View View   Source Source   



Branch-and-Bound (B&B) is a general problem solving paradigm and it has been successfully used to prove the optimality of combinatorial optimization problems. The development of GPU-based parallel Branch-and-Bound algorithm is a brandnew and challenging topic on high performance computing and combinatorial optimization, motivated by GPU’s high performance and low cost. This work presents a strategy designed to parallelize Jurema searchbased B&B algorithms on GPUs, evaluated for the Asymmetric Traveling Salesman Problem, called Juremal. Jurema search is a search mainly based on DFS concepts, developed to mitigate DFSB&B flaws. Results show the search strategy chosen (DFS or Jurema) is not critical. But it is necessary to develop a trigger mechanism to determine when the process must be halted, and how the remaining search space must be redistributed. Strategies to reduce serialization of instructions are also need, in order to obtain higher speedups in GPU DFS-B&B based algorithms.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2019 hgpu.org

All rights belong to the respective authors

Contact us: