V. M. Kartak, A. V. Ripatti, G. Scheithauer, S. Kurz
Minimal proper non-IRUP instances
of the one-dimensional Cutting Stock Problem
We consider the well-known one dimensional cutting stock problem
(1CSP). Based on the pattern structure of the classical
ILP formulation of Gilmore and Gomory, we can decompose the
infinite set of 1CSP instances, with a fixed
number $n$ of demand pieces, into
a finite number of equivalence classes. We show up a strong
relation to weighted simple games.
Studying the integer round-up property (IRUP)
we use the proper LP relaxation of the
Gilmore and Gomory model that allows us to consider the 1CSP as
the bin packing problem (BPP).
We computationally show that all
1CSP instances with $n\le 9$ have the proper IRUP, while we
give examples of proper non-IRUP instances with $n=10$
and proper gap 1.
Proper gaps larger than $1$ occur for $n \ge 11$.
The largest %worst
known proper gap is raised from $1.003$ to $1.0625$. The
used algorithmic approaches are based on exhaustive enumeration
and integer linear
programming. Additionally we give some theoretical bounds showing
that all 1CSP instances with some specific parameters have the
(to appear in Discrete Applied Mathematics 2015,
Preprint MATH-NM-08-2013, TU Dresden, November 2013)