LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap

John Martinovic () and Guntram Scheithauer ()
Additional contact information
John Martinovic: Technische Universität Dresden
Guntram Scheithauer: Technische Universität Dresden

A chapter in Operations Research Proceedings 2015, 2017, pp 49-54 from Springer

Abstract: Abstract We consider the one-dimensional skiving stock problem (SSP) which is strongly related to the dual bin-packing problem in literature. 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. For this optimization problem, we give a short introduction by outlining different modelling approaches, particularly the pattern-based standard model, and mentioning their relationships. 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 will present some new results and improved upper bounds for the gap of the SSP that are based on the theory of residual instances of the skiving stock problem.

Keywords: Cutting and packing; Skiving stock problem; Continuous relaxation; Gap; Residual Instances (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-42902-1_7

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_7

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().