V. M. Kartak, A. V. Ripatti, G. Scheithauer
Minimal proper non-IRUP instances of the one-dimensional Cutting Stock Problem

Abstract
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.
PDF, (Preprint MATH-NM-08-2013, TU Dresden, November 2013)
Back