LAUSR

ABSTRACT We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: given a supply of (small) items, the aim is to construct as many large items (specified by some target length) as possible. For this -hard combinatorial optimization problem, practical experience and computational simulations have shown that the continuous relaxation of the pattern-based ILP model provides very tight bounds. Although many instances are known to possess the integer round-down property (IRDP), there is only a very few number of corresponding theoretical results. In this article, we present a new approach to characterize IRDP-instances by means of polyhedral theory which, in a first step, provides an alternative proof for a well-known result of E.J. Zak. As a main contribution, we formulate the IRDP for two new classes of instances appearing in the context of the divisible case.