Optimal solutions for the cutting stock problem

This paper is about the solution of certain classes of the cutting stock problem to optimality. The work is based on enumerating the possible cutting patterns, and solving the associated integer program by a combination of cutting planes and branch and bound. The resulting program was initially implemented in February 1985 for a one-dimensional cutting stock problem in a large board mill in the U.K., where it has generated average savings of 2.5% of production compared to the best of two previous computer programs. The solutions obtained by the program are usually optimal in trim loss terms. Subsequent, post-solution optimisation minimises cutting patterns and reduces knife setups.