New Theoretical Investigations on the Gap of the Skiving Stock Problem

Abstract

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of products with minimum length $ L $ that can be constructed by connecting a given supply of $ m \in \mathds{N} $ smaller item lengths $ l_1,\ldots,l_m $ with availabilities $ b_1,\ldots, b_m $. For this NP-hard optimization problem, we investigate the quality of the continuous relaxation by considering the gap, i.e., the difference between the optimal objective values of the continuous relaxation and the skiving stock problem itself. In a first step, we derive an improved upper bound for the gap by focusing on residual instances. Moreover, we show how other upper bounds can be obtained if all problem-specific input-data are considered. Furthermore, we prove the integer round-down property (IRDP) for two new classes of instances, and introduce several construction principles to obtain gaps greater than or equal to one.

PDF, (Preprint MATH-NM-03-2016, TU Dresden, August 2016, 26 p.)

Back