Arc-flow model for the two-dimensional guillotine cutting stock problem
Rita Macedo, Cláudio Alves, José Valério de Carvalho
Computers and Operations Research, vol. 37, n.o 6, pp. 991-1001, 2010

ABSTRACT
We describe an exact model for the two-dimensional cutting stock problem with two stages and the guillotine constraint. It is an integer linear programming (ILP) arc-flow model, formulated as a minimum flow problem, which is an extension of a model proposed by Valério de Carvalho for the one dimensional case. In this paper, we explore the behavior of this model when it is solved with a commercial software, explicitly considering all its variables and constraints. We also derive a new family of cutting planes and a new lower bound, and consider some variants of the original problem. The model was tested on a set of real instances from the wood industry, with very good results. Furthermore the lower bounds provided by the linear programming relaxation of the model compare favorably with the lower bounds provided by models based on assignment variables.

BIBTEX ENTRY
@article{MacedoAlvesCarvalhoCOR10,
author = {Rita Macedo and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho},
title = {Arc-flow model for the two-dimensional guillotine cutting stock problem},
journal = {Computers and Operations Research},
volume = {37},
number = {6},
year = {2010},
pages = {991-1001} }