Exact Algorithms for the Two-Dimensional Guillotine Knapsack

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 items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are compu- tationally evaluated on well-known benchmark instances from the literature. The C++ source code of the recursive procedure is available upon request from the authors.