Exact algorithm for minimising the number of setups in the one-dimensionalcutting stock problem

The cutting stock problem is that of finding a cutting of stock material to meet demands for small pieces of prescribed dimensions while minimising th e amount of waste. Because changing over from one cutting pattern to anothe r involves significant setups, an auxiliary problem is to minimise the numb er of different patterns that are used. The pattern minimisation problem is significantly more complex, but it is of great practical importance. In th is paper, we propose an integer programming formulation for the problem tha t involves an exponential number of binary variables and associated columns , each of which corresponds to selecting a fixed number of copies of a spec ific cutting pattern. The integer program is solved using a column generati on approach where the subproblem is a nonlinear integer program that can be decomposed into multiple bounded integer knapsack problems. At each node o f the branch-and-bound tree, the linear programming relaxation of our formu lation is made tighter by adding super-additive inequalities. Branching rul es are presented that yield a balanced tree. Incumbent solutions are obtain ed using a rounding heuristic. The resulting branch-and-price-and-cut proce dure is used to produce optimal or approximately optimal solutions for a se t of real-life problems.