Optimization algorithms and methods | Discrete geometry
Guillotine cutting
Guillotine cutting is the process of producing small rectangular items of fixed dimensions from a given large rectangular sheet, using only guillotine-cuts. A guillotine-cut (also called an edge-to-edge cut) is a straight bisecting line going from one edge of an existing rectangle to the opposite edge, similarly to a paper guillotine. Guillotine cutting is particularly common in the glass industry. Glass sheets are scored along horizontal and vertical lines, and then broken along these lines to obtain smaller panels. It is also useful for cutting steel plates, cutting of wood sheets to make furniture, and cutting of cardboard into boxes. There are various optimization problems related to guillotine cutting, such as: maximize the total area of the produced pieces, or their total value; minimize the amount of waste (unused parts) of the large sheet, or the total number of sheets. They have been studied in combinatorial geometry, operations research and industrial engineering. A related but different problem is guillotine partition. In that problem, the dimensions of the small rectangles are not fixed in advance. The challenge comes from the fact that the original sheet might not be rectangular - it can be any rectilinear polygon. In particular, it might contain holes (representing defects in the raw material). The optimization goal is usually to minimize the number of small rectangles, or minimize the total length of the cuts. (Wikipedia).
