Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/288456 
Autor:innen: 
Erscheinungsjahr: 
2020
Quellenangabe: 
[Journal:] 4OR [ISSN:] 1614-2411 [Volume:] 20 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 85-104
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
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.
Schlagwörter: 
Cutting and packing
Cutting stock problem
Skiving stock problem
Additive integrality gap
Divisible case
JEL: 
C10
C27
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.