ESTRATÉGIAS PARALELAS INTELIGENTES PARA O MÉTODO BRANCH-AND-BOUND APLICADAS AO PROBLEMA DO CAIXEIRO VIAJANTE ASSIMÉTRICO / PARALLEL STRATEGIES FOR INTELLIGENT METHOD BRANCH-AND-BOUND TO APPLY traveling salesman problem ASYMMETRICAL

AUTOR(ES)

Tiago Carneiro Pessoa

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

25/07/2012

RESUMO

To the use of different architectures to process distinct portions of the same code, in order to maximize the performance, it is given the name Heterogeneous Computing. The Heterogeneous Computing is closely related to the high performance computing, and raised in a moment when the parallel computers, in that time with homogeneous execution, could no longer provide the needs of complex emergent parallel applications. The use of graphics processing unities (GPU) to process general-purpose applications, in order to accelerate computationally intensive routines (GPGPU), has been the most highlighted heterogeneous architecture. This work presents a new parallel procedure designed to process combinatorial branch-and-bound (B&B) algorithms by using GPU. The schema involves so elementary concepts such that any combinatorial B&B algorithm based on depth-first search (DFS) could be easily adapted, taking advantage of the high GPUs throughput. Our strategy is to perform B&B sequentially till a specific depth, saving the current path in B&B tree as a node into the Active Set, and then force the backtracking. Each node into the Active Set is a DFS-B&B root that will be concurrently processed by the GPU. Two implementations were conceived: a loyal DFS-B&B implementation of the proposed schema, and a massively parallel version of Jurema method. We compare our results with multicore and serial versions of the same searches, using explicit enumeration (all possible solutions) and implicit enumeration (branch-and-bound search), for some asymmetrical traveling salesman problems instances. Our computational results indicate the superiority of our GPU computing based method mainly for the B&Bs worst case. The results also show that Jurema method, in massively parallel environments, is slightly superior than DFS.

ASSUNTO(S)

branch-and-bound gpgpu caixeiro viajante assimétrico cuda ciencia da computacao branch-and-bound gpgpu atsp cuda

Documentos Relacionados

• O problema do caixeiro viajante com restrições de empacotamento tridimensional
• The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm
• Branch-and-bound method application in a single machine earliness/tardiness scheduling problem with a common due date.
• Algoritmo memético com infecção viral: uma aplicação ao problema do caixeiro viajante assimétrico
• Rede neural recorrente com perturbação simultânea aplicada no problema do caixeiro viajante