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

摘要

Branch-and-bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimizationrnproblems using an implicit enumeration of a dynamically built tree-based search space. Nevertheless,rnthey are time-consuming when dealing with large problem instances. Therefore, pruning tree nodesrn(subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space.rnPruning requires to perform the bounding operation, which consists of applying a lower bound functionrnto the subproblems generated during the exploration process. Preliminary experiments performed on thernFlow-Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of thernexecution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU)rncomputing as a major complementary way to speed up the search. We revisit the design and implementationrnof the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization.rnExtensive experiments have been carried out on well-known FSP benchmarks using an Nvidia TeslarnC2050 GPU card. Compared to a CPU-based single core execution using an Intel Core i7-970 processorrnwithout GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalentrnpeak performance, GPU-accelerated B&B is twice faster than its multi-core counterpart.