Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of objects, each having a length of at least L, that can be constructed by connecting a given supply of $$ m \in \mathbb {N} $$ m ∈ N smaller item lengths $$ l_1,\ldots ,l_m $$ l 1 , … , l m with availabilities $$ b_1,\ldots , b_m $$ b 1 , … , b m . For this $$\mathcal {NP}$$ NP -hard discrete optimization problem, the (additive integrality) gap, i.e., the difference between the optimal objective values of the continuous relaxation and the skiving stock problem itself, is known to be strictly less than 3 / 2 if $$ l_i \mid L $$ l i ∣ 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, i.e., a gap smaller than one, of a given instance. As a main contribution, we present improved upper bounds for the gap (of special subclasses) of the divisible case by means of combinatorial and algorithmic approaches. In a final step, possible generalizations of the introduced concepts are discussed. Altogether, the results presented in this paper give strong evidence that 22 / 21 represents the best possible upper bound for the gap of divisible case instances.