Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory. (3rd October 2018)

• Record Type: Journal Article
• Authors: Martinovic, John; Scheithauer, Guntram
• Is Part Of: Optimization. Volume 67:Number 10(2018)
• Page Start: 1797
• Page End: 1817
• Publication Date: 2018-10-03
• Subjects: Cutting and packing -- skiving stock problem -- integer round-down property -- polyhedral theory -- additive integrality gap; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2018.1494171
• Languages: English
• ISSNs: 0233-1934

Abstract

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.