Skip to Main content Skip to Navigation
Conference papers

A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems

Tiago Carneiro Pessoa 1, * Jan Gmys 2, 3 Nouredine Melab 2 de Carvalho Junior Francisco Heron 1 Daniel Tuyttens 3
* Corresponding author
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : This work presents a GPU-based backtracking algorithm for permutation combinatorial problems based on the Integer-Vector-Matrix (IVM) data structure. IVM is a data structure dedicated to permutation combinatorial optimization problems. In this algorithm, the load balancing is performed without intervention of the CPU, inside a work stealing phase invoked after each node expansion phase. The proposed work stealing approach uses a virtual n-dimensional hypercube topology and a triggering mechanism to reduce the overhead incurred by dynamic load balancing. We have implemented this new algorithm for solving instances of the Asymmetric Travelling Salesman Problem by implicit enumeration, a scenario where the cost of node evaluation is low, compared to the overall search procedure. Experimental results show that the dynamically load balanced IVM-algorithm reaches speed-ups up to 17X over a serial implementation using a bitset-data structure and up to 2X over its GPU counterpart.
Complete list of metadatas

https://hal.inria.fr/hal-01419073
Contributor : Nouredine Melab <>
Submitted on : Sunday, December 18, 2016 - 3:14:35 PM
Last modification on : Wednesday, June 24, 2020 - 10:48:04 AM

Identifiers

Collections

Citation

Tiago Carneiro Pessoa, Jan Gmys, Nouredine Melab, de Carvalho Junior Francisco Heron, Daniel Tuyttens. A GPU-Based Backtracking Algorithm for Permutation Combinatorial Problems. 16th International Conference, ICA3PP 2016, Dec 2016, Granada, Spain. pp.15, ⟨10.1007/978-3-319-49583-5_24⟩. ⟨hal-01419073⟩

Share

Metrics

Record views

548