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.

Terminology and assumptions

The following terms and notations are often used in the literature on guillotine cutting. Some problems accept additional inputs, as explained below. The goal is to cut, from the raw rectangle, some smaller rectangles having the target dimensions. The following assumptions are often made:

Checking a given pattern

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). The goal is to decide whether this pattern can be implemented using only guillotine cuts, and if so, find a sequence of such cuts. An obvious necessary condition is that no two input rectangles overlap in both dimensions. Ben Messaoud, Chengbin and Espinouse present a stronger condition, which is both necessary and sufficient. The input rectangles are ordered from left to right, such that x1 ≤ ... ≤ xm. There is a permutation p on the indices such that, with this permutation, the rectangles would be ordered from bottom to top, i.e., yp(1) ≤ ... ≤ yp(m). Given four indices i1 ≤ i2 and j1 ≤ j2, the set E(i1,i2,j1,j2) contains the indices of all rectangles whose bottom-left corner is in the rectangle [xi1,xi2] X [yp(j1),yp(j2)]. A cutting pattern is a guillotine pattern if and only if, for all quadruplets of indices i1 ≤ i2 and j1 ≤ j2, at least one of the following conditions is fulfilled for E(i1,i2,j1,j2): Condition 2 implies that the rectangles in E(i1,i2,j1,j2) can be separated by a vertical cut (going between the two disjoint horizontal intervals); condition 3 implies the rectangles in E(i1,i2,j1,j2) can be separated by a horizontal cut. 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. This condition can be checked by the following algorithm. Finding a guillotine cut for a given pattern is done as follows: The ordering step is done once, and the merging step is done m-1 times. Therefore, the run-time of the entire algorithm is O(m2). When the algorithm returns "yes", it also produces a sequence of guillotine cuts; when it returns "no", it also produces specific subsets of rectangles that cannot be separated by guillotine cuts. The necessary and sufficient condition can be used to present the guillotine-strip-cutting problem as a mixed integer linear program. Their model has 3n4/4 binary variables and 2n4 constraints, and is considered not practically useful.

Finding an optimal cutting-pattern

These are variants of the two-dimensional cutting stock, bin packing and rectangle packing problems, where the cuts are constrained to be guillotine cuts.

Optimization algorithms

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. Tarnowski, Terno and Scheithauer present a polynomial-time algorithm for solving it. However, when there are two or more types, all optimization problems related to guillotine cutting are NP hard. Due to its practical importance, various exact algorithms and approximation algorithms have been devised.

Implementations

Guillotine separation

Guillotine separation is a related problem in which the input is a collection of n pairwise-disjoint convex objects in the plane, and the goal is to separate them using a sequence of guillotine cuts. Obviously it may not be possible to separate all of them. Jorge Urrutia Galicia asked whether it is possible to separate a constant fraction of them, that is, whether there exists a constant c such that, in any such collection of size n, there is a subset of size cn that are guillotine-separable. **Pach and Tardos ** proved: Abed, Chalermsook, Correa, Karrenbauer, Perez-Lantero, Soto and Wiese proved: Khan and Pittu proved: See also:

More variants

Some recently studied variants of the problem include: