Multistage Cutting Stock Problems of Two and More Dimensions

P. C. Gilmore and R. E. Gomory
Additional contact information
P. C. Gilmore: Thomas J. Watson Research Center, Yorktown Heights, New York
R. E. Gomory: Thomas J. Watson Research Center, Yorktown Heights, New York

Operations Research, 1965, vol. 13, issue 1, 94-120

Abstract: In earlier papers [ Opns. Res. 9, 849–859 (1961), and 11, 863–888 (1963)] the one-dimensional cutting stock problem was discussed as a linear programming problem. There it was shown how the difficulty of the enormous number of columns occurring in the linear programming formulation could be overcome by solving a knapsack problem at every pivot step. In this paper higher dimensional cutting stock problems are discussed as linear programming problems. The corresponding difficulty of the number of columns cannot in general be overcome for there is no efficient method for solving the generalized knapsack problem of the higher dimensional problem. However a wide class of cutting stock problems of industry have restrictions that permit their generalized knapsack problem to be efficiently solved. All of the cutting stock problems that yield to this treatment are ones in which the cutting is done in stages. In treating these practical cutting problems, one often encounters additional conditions that affect the solution. An example of this occurs in the cutting of corrugated boxes, which involves an auxiliary sequencing problem. This problem is discussed in some detail, and a solution described for the sequencing problem under given simplifying assumptions.

Date: 1965
References: Add references at CitEc
Citations: View citations in EconPapers (109)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.13.1.94 (application/pdf)

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:inm:oropre:v:13:y:1965:i:1:p:94-120

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().