A GPU accelerated parallel heuristic for the 2D knapsack problem with rectangular pieces

摘要

The 2D Knapsack Problem is a NP hard problem in combinatorial optimization which can be described easily, but it is very difficult to solve. If we take a rectangular container as well as a set of rectangular pieces into consideration, the two dimensional knapsack problem (2D-KP) consists of packing a subset of the rectangular pieces in the rectangular container in such a way that the sum of the total values of the packed rectangular pieces is maximized. If we consider the value of a rectangular piece by the area, the goal here is to maximizing the covered area of the rectangular container. It is not only very time consuming for Central Processing Units (CPU) but also very difficult to obtain an optimized solution when solving large problem instances. So, parallelism can be a good technique for reducing the time complexity, as well as improving the solution quality. Nowadays Graphics Processing Units (GPUs) have evolved supporting general purpose computing. In this paper, we propose GPU accelerated parallel heuristics for 2D Knapsack Problem and our experimental evaluation shows that this optimization algorithm efficiently accelerated on GPUs can provide with higher quality solutions within a reasonable time for 2D-KP.