Gomory cuts from a position-indexed formulation of 1D stock cutting
Gleb Belov, Guntram Scheithauer, Cláudio Alves, José Valério de Carvalho
in "Intelligent Decision Support", Gabler-Verlag (ISBN-10: 3-8349-0930-0), pp. 3-14, 2008

ABSTRACT
Most integer programming problems can be formulated in several ways. Some formulations are better suited for solution by exact methods, because they have either (i) a strong LP relaxation, (ii) few symmetries in the solution space, or both. However, solving one formulation, we can often branch and/or add cutting planes which are implicitly based on variables of other formulations, working in fact on intersection of several polytopes. Traditional examples of this approach can be found in, e.g., (capacitated) routing and network planning where decomposed models operate with paths or trees, and thus need to be solved by column generation, but original models operate on separate edges. We consider such a 'capacity-extended formulation', the so-called arc-flow model, of the 1D cutting stock problem. Its variables are known to induce effective branching constraints leading to small and stable branch-and-bound trees. In this work we explore Chv´atal-Gomory cuts on its variables. The results are positive only for small instances. Moreover, we compare the results to the cuts constructed on the variables of the direct model. The latter are more involved but also more effective

BIBTEX ENTRY
@incollection{Belovetal2008,
author = {Gleb Belov and Guntram Scheithauer and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho},
title = {Gomory cuts from a position-indexed formulation of 1D stock cutting},
booktitle = {Intelligent Decision Support},
editor = {A. Bortfeldt and J. Homberger and H. Kopfer and G. Pankratz and R. Strangmeier},
publisher = {Gabler-Verlag},
year = {2008},
pages = {3-14} }