A pseudo-polynomial size formulation for 2-stage 2-dimensional knapsack problems

Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum profit subset of rectangular items obtainable through 2-stage guillotine cuts in a rectangular panel. We propose a formulation having a pseudopolynomial number of variables and constraints which can still be enumerated for the instances present in the literature. We compare the proposed formulation with the previous best known polynomial size one. Extensive computational experiments show that the new model is characterized by a stronger linear programming relaxation and can be effectively solved with a general-purpose MIP solver.