Gomory Cuts from a Position-Indexed Formulation of 1D Stock Cutting

Gleb Belov (), Guntram Scheithauer (), Cláudio Alves () and José M. Valério de Carvalho ()
Additional contact information
Gleb Belov: Technische Universität Dresden
Guntram Scheithauer: Technische Universität Dresden
Cláudio Alves: Universidade do Minho
José M. Valério de Carvalho: Universidade do Minho

A chapter in Intelligent Decision Support, 2008, pp 3-14 from Springer

Abstract: 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&bounsd trees. In this work we explore Chvátal-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.

Keywords: Integer programming; cutting; cutting planes; column generation (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-8349-9777-7_1

Ordering information: This item can be ordered from
http://www.springer.com/9783834997777

DOI: 10.1007/978-3-8349-9777-7_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().