GPU-based branch-and-bound method to solve large 0-1 knapsack problems with data-centric strategies

An out-of-core branch-and-bound (B&B) method to solve large 0-1 knapsack problems on a graphics processing unit (GPU) is proposed. Given a large problem that produces many subproblems, the proposed method dynamically swaps subproblems to CPU memory. Because such a CPU-centric subproblem management scheme increases CPU-GPU data transfer, we adopt three data-centric strategies to eliminate this side effect. The first is an out-of-order search (O3S) strategy that reduces the data transfer overhead by adaptively transferring subproblems between the CPU and GPU. The second is an explicitly-managed pipelining strategy that hides the data transfer overhead by overlapping data transfer with GPU-based B&B operations. The third is a GPU-based stream compaction strategy that reduces the sparseness of arrays to be transferred. Experimental results demonstrate that the proposed out-of-core method stored 41 times as many subproblems as a previous in-core method that manages subproblems in GPU memory, solving approximately twice as many problem instances on the GPU. In addition, compared to a previous breadth-first search (BFS) strategy, the proposed O3S strategy achieved an average speedup of 7.5 times.