Pattern minimisation in cutting stock problems (Q1961237)

In the cutting stock pattern minimisation problem, we wish to satisfy demand for various customer reels by cutting as few as possible jumbo reels, and further to minimise the number of distinct cutting patterns used. We focus on the special case in which any two customer reels fit into a jumbo, but no three do: this case is of interest partly because it is the simplest case that is not trivial, and partly because it may arise in practice when one attempts to improve a solution iteratively. We find that the pattern minimisation problem is strongly NP-hard even in this special case, when the basic problem of finding a minimum waste solution is trivial. Our analysis focusses on `balanced' subsets, and suggests an approach for heuristic methods involving searching for balanced subsets.