Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm

G. Scheithauer, J. Terno, A. Müller, G. Belov

Research output: Contribution to journalArticleResearchpeer-review

21 Citations (Scopus)

Abstract

When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore-Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported.

Original languageEnglish
Pages (from-to)1390-1401
Number of pages12
JournalJournal of the Operational Research Society
Volume52
Issue number12
DOIs
Publication statusPublished - 1 Jan 2001

Keywords

  • Column generation
  • Cutting planes
  • Cutting stock problem
  • Integer programming
  • Linear programming

Cite this