Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01095244
Contributor : Nouredine Melab <>
Submitted on : Wednesday, January 21, 2015 - 3:30:39 PM
Last modification on : Thursday, April 4, 2019 - 10:18:06 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

255