A New Graph-Theoretical Model for the Guillotine-Cutting Problem

François Clautiaux, Antoine Jouglet, Aziz Moukrim

INFORMS Journal on Computing · 2013 · Volume 25 · Issue 1

Abstract

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. We introduce a new class of arc-colored directed graphs called guillotine graphs and show that each guillotine graph can be associated with a specific class of pattern solutions that we call a guillotine-cutting class . The properties of guillotine graphs are examined, and some effective algorithms for dealing with guillotine graphs are proposed. As an application, we then describe a constraint programming method based on guillotine graphs, and we propose effective filtering techniques that use the graph model properties in order to reduce the search space efficiently. Computational experiments are reported on benchmarks from the literature: our algorithm outperforms previous methods when solving the most difficult instances exactly.

Keywords

two-dimensional packing, graph model, constraint programming

Enable JavaScript for citation tools and additional paper interactions.