Optimal integer solutions to industrial cutting stock problems

The ‘textbook’ treatment of the cutting stock problem, using a method termed column generation, solves the problem as if one is allowed to use fractional amounts of patterns. In practice, one can typically run only an integer quantity of a pattern. Dyckhoff was 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 describe and test an extension of a method proposed by Degraeve for embedding a column generation procedure within branch and bound. We show that our algorithm is quite general. It can easily cope with various combinations of real world complications, such as 1) upper bounds on the amount by which the demand may be oversatisfied, 2) a limit on maximum waste allowed in each pattern, and 3) a limit on the maximum number of knives in the cutting patterns. We validate our approach using both industrial data sets from the paper industry and generated data sets. The performance of the algorithm is compared with Dyckhoff's formulation.