J. Martinovic and G. Scheithauer,
Improved Upper Bounds for the Gap of the Skiving Stock Problem
We consider the one-dimensional skiving stock problem (SSP) which is strongly related to the dual bin packing problem. In the classical formulation, different (small) item lengths and corresponding availabilities are given. We aim at maximizing the number of objects with a certain minimum length that can be constructed by connecting the items on hand. Such computations are of high interest in many real world application, e.g. in industrial recycling processes, wireless communications and politico-economic questions.
Since the SSP is known to be NP-hard a common solution approach consists in solving an LP-based relaxation and the application of (appropriate) heuristics. Practical experience and computational simulations have shown that there is only a small difference (called gap) between the optimal objective values of the relaxation and the SSP itself. In this paper, we aim at evaluating the quality of the continuous relaxation by providing some new results and improved upper bounds for the gap of an arbitrary instance $ E=(m,l,L,b) $. To this end, we introduce and mainly refer to the theory of residual instances.
(Preprint MATH-NM-03-2015, TU Dresden, September 2015)