Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288456 
Year of Publication: 
2020
Citation: 
[Journal:] 4OR [ISSN:] 1614-2411 [Volume:] 20 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 85-104
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
In this paper, we consider the (additive integrality) gap of the cutting stock problem (CSP) and the skiving stock problem (SSP). Formally, the gap is defined as the difference between the optimal values of the ILP and its LP relaxation. For both, the CSP and the SSP, this gap is known to be bounded by 2 if, for a given instance, the bin size is an integer multiple of any item size, hereinafter referred to as the divisible case. In recent years, some improvements of this upper bound have been proposed. More precisely, the constants 3/2 and 7/5 have been obtained for the SSP and the CSP, respectively, the latter of which has never been published in English language. In this article, we introduce two reduction strategies to significantly restrict the number of representative instances which have to be dealt with. Based on these observations, we derive the new and improved upper bound 4/3 for both problems under consideration.
Subjects: 
Cutting and packing
Cutting stock problem
Skiving stock problem
Additive integrality gap
Divisible case
JEL: 
C10
C27
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.