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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
Seiten (von - bis)85-104
Seitenumfang20
Fachzeitschrift4OR
Jahrgang20(1)
PublikationsstatusVeröffentlicht - März 2022
Peer-Review-StatusJa

Externe IDs

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

Schlagworte

Schlagwörter

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