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 obtain- able through 2-stage guillotine cuts in a rectangular panel. We propose a formulation having a pseudo-polynomial 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.
Article
View A pseudo-polynomial size formulation for 2-stage two-dimensional knapsack problems