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

G Scheithauer, J Terno, A Müller () and G Belov
Additional contact information
G Scheithauer: Dresden University of Technology
J Terno: Dresden University of Technology
A Müller: Dresden University of Technology
G Belov: Dresden University of Technology

Journal of the Operational Research Society, 2001, vol. 52, issue 12, 1390-1401

Abstract: 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: linear programming; integer programming; cutting stock problem; cutting planes; column generation (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601242 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:52:y:2001:i:12:d:10.1057_palgrave.jors.2601242

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601242

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().