V. M. Kartak, A. V. Ripatti, G. Scheithauer
Minimal proper non-IRUP instances
of the one-dimensional Cutting Stock Problem
We consider the well-known one-dimensional cutting stock problem (1CSP).
It is shown that all possible instances of the 1CSP can be divided into
a finite number of equivalence classes when the number of items $m$ is fixed.
A method for enumerating all these classes is investigated.
This method is improved for searching proper non-IRUP instances with minimal number of items.
We found the minimal number of items is $m=10$ when a proper non-IRUP instance exists. We also found 365 equivalence classes that consist of such instances.
(Preprint MATH-NM-08-2013, TU Dresden, November 2013)