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

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

0.00 Avg rating0 Votes
Article ID: iaor20131719
Volume: 25
Issue: 1
Start Page Number: 72
End Page Number: 86
Publication Date: Dec 2013
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: graphs, cutting stock
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.

Reviews

Required fields are marked *. Your email address will not be published.