Cutting and packing problems covers a diverse set of problems. It is useful to start with some real examples:
- Cutting jumbo rolls of paper into shorter rolls: this is considered a one dimensional cutting problem where the objective is to minimise the number of jumbos used to satisfy orders.
- Cutting glass sheets into smaller rectangles: this is a two dimensional problem where the objective is to minimise the waste glass.
- Packing a shipping container with boxes: this is a three dimensional problem where the objective is to pack the most value of item as possible.
Cutting and packing captures a set of optimisation problems that are must respect two types of geometric constraints:
- No overlap: items being cut or packed may not overlap each other
- Containment: items being cut or packed must be contained within a large object.
There may be other constrained depending on the specific problem.
In general, the problems have one of two objectives; minimise input or maximise output. A fully typology of the problems can be found here.