Optimal integer solutions to industrial cutting-stock problems: Part 2, benchmark results

In this paper we present a state-of-the-art version of the branch-and-price procedure of Degraeve and Schrage for the exact solution of the cutting-stock problem. The average solution time is reduced by a factor of more than 300. This allows us to solve problems twice as large as the largest problems solved in the literature today. The two most important improvements are (1) a hybrid simplex method/subgradient-optimization procedure to find the LP relaxation, and (2) a branching scheme that first focuses on the residual problem throughout the enumeration tree. In addition, the strength of our algorithm is the integration of different components into one comprehensive procedure. The other components are using heuristics intensively, a pruning rule, and the use of a dominance rule. We validate our methodology with both industrial and generated data sets. The performance of our algorithm is compared extensively with other implementations and various heuristics for the problem. The proposed algorithm is very efficient for solving the bin-packing problem as well. The major implication of our methodology is that we solve industrial sizes of an NP-hard problem practically in a time to solve its LP relaxation.