Optimal integer solutions to real-life cutting-stock problems

'Textbook' treatments of the cutting-stock problem effectively solve the problem as if one is allowed to use fractional amounts of patterns using a method termed column generation. In practice, one can typically only run an integer quantity of a pattern. Dychoff (1981) is the first to propose an integer linear programming formulation for the problem of getting a guaranteed global optimum to cutting-stock problems under the integrality requirement. We propose a new method for this problem by embedding the column generation procedure within a branch and bound scheme. We validate our approach using generated and real-life data sets from the machine construction and paper industry and compare the performance of our algorithm with Dychoff's formulation.status: publishe