high performance computing on graphics processing units: hgpu.org

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.