| Article ID: | iaor20043217 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 1 |
| Start Page Number: | 5 |
| End Page Number: | 14 |
| Publication Date: | Jan 2004 |
| Journal: | Operations Research Letters |
| Authors: | Caprara Alberto, Monaci Michele |
| Keywords: | programming: integer |
We address the two-dimensional Knapsack Problem (2KP), 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.