2D Cutting Problem

The two-dimensional cutting problem can be found as the core task in many real-world applications such as cutting of standardized stock units in the glass, wood, and the paper industries.

It consists of fitting a set of pieces to a given layout that leads to a minimum total waste and that fulfills a set of constraints depending on the nature of the material to be cut (e.g., cutting wood is different from cutting glass).

 This is a NP-hard problem with many subclasses. As it grows exponentially with the dimension of the problem it is unapproachable with exact methods (because of their needs in terms of memory usage and CPU time consumption). This is the reason why feasible and real world solutions found in the literature are often based on metaheuristic algorithms. This problem can be treated as a two or more objective problem, for example minimizing the number of cuts and the waste.