On the two-dimensional knapsack problem

We address the two-dimensional Knapsack Problem (2YP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness. (C) 2003 Elsevier B.V. All rights reserved.