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

Authors: Scheithauer G.¹; Terno J.¹; Müller A.¹; Belov G.¹; Correspondence

Source: Journal of the Operational Research Society, Volume 52, Number 12, 1 December 2001 , pp. 1390-1401(12)

Publisher: Palgrave Macmillan

Key:

- Free Content

- New Content

- Subscribed Content

- Free Trial Content

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

Document Type: Original article

Affiliations: 1: Dresden University of Technology, Dresden, Germany

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$32.43 plus tax Refund Policy