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

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

@article{a082a73897944aac959a41bfae69b617,
title = "Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm",
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.",
keywords = "Column generation, Cutting planes, Cutting stock problem, Integer programming, Linear programming",
author = "G. Scheithauer and J. Terno and A. M{\"u}ller and G. Belov",
year = "2001",
month = "1",
day = "1",
doi = "10.1057/palgrave.jors.2601242",
language = "English",
volume = "52",
pages = "1390--1401",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan",
number = "12",

}

Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm. / Scheithauer, G.; Terno, J.; Müller, A.; Belov, G.

In: Journal of the Operational Research Society, Vol. 52, No. 12, 01.01.2001, p. 1390-1401.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Scheithauer, G.

AU - Terno, J.

AU - Müller, A.

AU - Belov, G.

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

KW - Column generation

KW - Cutting planes

KW - Cutting stock problem

KW - Integer programming

KW - Linear programming

UR - http://www.scopus.com/inward/record.url?scp=0035576826&partnerID=8YFLogxK

U2 - 10.1057/palgrave.jors.2601242

DO - 10.1057/palgrave.jors.2601242

M3 - Article

VL - 52

SP - 1390

EP - 1401

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 12

ER -