Exact solution of one-dimensional cutting stock problems using branch-and-bound and column generation

If an integer solution to the one-dimensional cutting stock problem is required, after solving the linear programming relaxation, one frequently resorts to heuristics based on rounding up and down the continuous solution, or other heuristics similar type. The difficulties arise from the fact that it may not be practically possible to enumerate all the structural variables of the problem, whose number may be in the order of millions, even for instances of moderate size. In this article the paper presents a formulation with a number of variables and constraints that is polinomial with respect to the width of the stock and the number of orders. For some classes of instances, it is possible to enumerate completely all the variables and to obtain an integer optional solution using a branch-and-bound method. For larger instances, the paper presents a procedure that combines column generation and branch-and-bound. It defines the subproblem, and the way it is modified during the branch-and-bound phase. Computational results are presented for several test problems.