Guillotine problem


The guillotine problem is a problem in combinatorial geometry and in printing.
Closely related to packing problems and specifically to cutting stock and bin packing problems, it is the question of how to get the maximum number of sheets of one rectangular size out of a larger sheet, only orthogonal cuts that bisect one component of the sheet are allowed, as on a paper cutting guillotine.
The Guillotine problem is important in glass machining. Glass sheets are scored along horizontal and vertical lines and then broken along these lines to obtain smaller panels.
Like the cutting stock problem, it is NP hard, but various approximate and exact solutions have been devised.