Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization

Abstract : Branch-and-bound (B&B) algorithms are attractive methods for solving to optimality combinatorial opti-mization problems using an implicit enumeration of a dynamically built tree-based search space. Neverthe-less, they are time-consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow-Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimiza-tion. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based single core execution using an Intel Core i7-970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equiv-alent peak performance, GPU-accelerated B&B is twice faster than its multi-core counterpart.
Type de document :
Article dans une revue
Concurrency and Computation: Practice and Experience, Wiley, 2014, 26 (16), pp.17. 〈10.1002/cpe.3155〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01095244
Contributeur : Nouredine Melab <>
Soumis le : mercredi 21 janvier 2015 - 15:30:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

Citation

Nouredine Melab, Imen Chakroun, Ahcène Bendjoudi. Graphics processing unit-accelerated bounding for branch-and-bound applied to a permutation problem using data access optimization. Concurrency and Computation: Practice and Experience, Wiley, 2014, 26 (16), pp.17. 〈10.1002/cpe.3155〉. 〈hal-01095244〉

Partager

Métriques

Consultations de la notice

127