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

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

0.00 Avg rating0 Votes
Article ID: iaor20022840
Country: United Kingdom
Volume: 52
Issue: 12
Start Page Number: 1390
End Page Number: 1401
Publication Date: Dec 2001
Journal: Journal of the Operational Research Society
Authors: , , ,
Keywords: programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.