The Proper Relaxation and the Proper Gap of the Skiving Stock Problem

Abstract

We consider the 1D skiving stock problem (SSP) which is strongly related to the dual bin packing problem: find the maximum number of items with minimum length $ L $ that can be constructed by connecting a given supply of $ m \in \mathds{N} $ smaller item lengths $ l_1,\ldots,l_m $ with availabilities $ b_1,\ldots, b_m $. For this optimization problem, we consider the proper relaxation and introduce a new modeling approach based on graph theory. Additionally, we investigate the quality of the gap, i.e., the difference between the optimal objective values of the proper relaxation and the SSP itself. In this context, we also present a construction principle for non-proper-IRDP instances and an enumerative approach that leads to the currently largest known gap.

PDF, (Preprint MATH-NM-04-2015, TU Dresden, November 2015)

Back