Combinatorial Investigations on the Maximum Gap for Skiving Stock Instances of the Divisible Case

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 discrete 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. This gap is known to be stricly less than $ 3/2 $ if $ l_i \mid L $ is assumed for all items, hereinafter referred to as the divisible case. Within this framework, we derive sufficient conditions that ensure the integer round-down property (IRDP) of a given instance. By means of combinatorial and algorithmic approaches we derive improved upper bounds for the gap of special subclasses of the divisible case. As a final step, possible generalizations of the presented concepts are discussed.

PDF, (Preprint MATH-NM-01-2017, TU Dresden, January 2017, 23 p.)

Back