A note on the integrality gap of cutting and skiving stock instances: Why 4/3 is an upper bound for the divisible case?

Research output: Contribution to journalResearch articleContributedpeer-review

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.

Details

Original languageEnglish
Pages (from-to)85-104
Number of pages20
Journal4OR
Volume20(1)
Publication statusPublished - Mar 2022
Peer-reviewedYes

External IDs

Scopus 85099517247
dblp journals/4or/Martinovic22
Mendeley 1ecda1c7-68f7-3923-a2ab-07ee6a46f768

Keywords

Keywords

  • Additive integrality gap, Cutting and packing, Cutting stock problem, Divisible case, Skiving stock problem