Exact algorithms for the two-dimensional guillotine knapsack

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 48-53

Mohammad, Dolatabadi , Andrea, Lodi , Michele, Monaci

The two-dimensional knapsack problem requires to pack a maximum profit subset of “small” rectangular items into a unique “large” rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem.In this paper we present a recursive exact procedure that, given a set of…