A Note on the Integrality Gap of Cutting and Skiving Stock Instances: Why 4/3 is an Upper Bound for the Divisible Case?
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 … Read more