We address the 2-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 1-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.
Caprara, A., Monaci, M. (2004). On the 2-Dimensional Knapsack Problem. OPERATIONS RESEARCH LETTERS, 32, 5-14 [10.1016/S0167-6377(03)00057-9].
On the 2-Dimensional Knapsack Problem
MONACI, MICHELE
2004
Abstract
We address the 2-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 1-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.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
