Antoine Jouglet

Solving guillotine-cutting problems

We consider the problem of determining whether a given set of rectangular
items can be cut from a larger rectangle using so-called guillotine cuts
only. A guillotine cut is parallel to one of the sides of the rectangle,
and must go from one edge all the way to the opposite edge of a currently
available rectangle. This decision problem is interesting in itself,
and also as a subproblem of open-dimension packing problems. The problem
occurs in industry if pieces of steel, wood, or paper need to be cut
out of larger pieces. It is sometimes referred to as the unconstrained
two-dimensional guillotine-cutting problem (UTDGC). This problem is
NP-complete, as it generalizes the classical bin-packing problem 1BP.
We introduce a new model for this problem, based on arc-colored
and oriented graphs. Thus, a unique undirected uncolored multigraph
is sufficient to represent exactly two guillotine-cutting classes.
Combining the use of our model, and constraint-programming techniques,
we develop an exact method for the problem. Computational experiments
are reported on benchmarks from the literature: our algorithm outperforms
previous methods when solving exactly the most difficult instances.