In this paper, we consider the two-stage extension of the one-dimensional cutting stock problem which arises when technical requirements inhibit the cutting of large stock rolls to demanded widths of finished rolls directly. Therefore, the demands on finished rolls are fulfilled through two subsequent cutting processes, in which the rolls produced in the former are used as an input for the latter, while the number of stock rolls used is minimized.We tackle the pattern-based formulation of this problem which has exponentially many variables and constraints. The special structure of this formulation induces both a column-wise and a row-wise increase when solved by column generation. We design an exact simultaneous column-and-row generation algorithm whose novel element is a row-generating subproblem that generates a set of columns and rows. For this subproblem, which is modeled as an unbounded knapsack problem, we propose three algorithms: implicit enumeration, column generation which renders the overall methodology nested column generation, and a hybrid algorithm. The latter two are integrated in a well-known knapsack algorithm which forges a novel branch-and-price algorithm for the row-generating subproblem. Extensive computational experiments are conducted, and performances of the three algorithms are compared.
Article
View Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem