Guillotine cutting

The challenge comes from the fact that the original sheet might not be rectangular - it can be any rectilinear polygon.

The following assumptions are often made:[2] In the pattern verification problem, there is a cutting-pattern given as a sequence of points (xi,yi), for i in 1,...,m, where (xi,yi) is the bottom-left coordinate of rectangle i (there is a single rectangle of each target-dimension).

Ben Messaoud, Chengbin and Espinouse[5] present a stronger condition, which is both necessary and sufficient.

All conditions together imply that, if any set of adjacent rectangles contains more than one element, then they can be separated by some guillotine cut.

The necessary and sufficient condition can be used to present the guillotine-strip-cutting problem as a mixed integer linear program.

[6] The special case in which there is only one type (i.e., all target rectangles are identical and in the same orientation) is called the guillotine pallet loading problem.

However, when there are two or more types, all optimization problems related to guillotine cutting are NP hard.

"A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting-stock problem."

A guillotine cutting: an optimised sheet of smaller rectangles which can be divided intact through the correct series of bisecting end-to-end cuts.
A non-guillotine cutting: these rectangles cannot be separated by making single bisecting cuts across the plane.