Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths

This paper considers the integer one-dimensional cutting stock problem with different types of standard lengths and the objective of cost minimization. Decomposition approaches based on the well-known column-generation technique for exactly solving the continuous relaxation of the problem and specific methods for separately solving the arising residual problems are proposed. For evaluating the performance of the different approaches, more than 12,000 randomly generated test problems have been solved. The computational experiments prove the effectiveness of one of the proposed decomposition procedures with respect to the computing effort and the quality of the solutions obtained.