Upper Bounds Categorization for Constrained Two-Dimensional Guillotine Cutting

In the two-dimensional cutting problem, a large rectangular sheet has to be dissected into smaller rectangular desired pieces. If limits exist on the number of extracted pieces, the problem is classified as constrained, with a wide range of applications. Most literature solving methods are based on ad hoc tree search strategies, with top-down or bottom-up approach. In both cases, lower and upper bounds are exploited, leading to branch and bound algorithms. We present a review of the upper bounds and identify a set of features for their categorization.