Combinatorial complexity of a certain 1-dimensional Cutting Stock Problem

The classical Cutting Stock Problem (1dCSP) is considered. It is known that 1CSP is at least NP-hard. In the present paper a combinatorial algorithm for its solution based on the Branch and Bound Method is described. We estimate the complexity of this algorithm presented for a class of problems that is called compact. The most difficult examples to solve by combinatorial algorithms are identified. This result is consistent with experimental data and could be used to generate difficult test problems, as well as for predicting the time of the algorithm.