Solving the Skiving Stock Problem by a Combination of Stabilized Column Generation and the Reflect Arc-Flow Model

Research output: Contribution to journalResearch articleContributedpeer-review



The skiving stock problem represents a natural counterpart of the extensively studied cutting stock problem and requires the construction of as many large units as possible from a given set of small items. In recent years, it has been able to develop into an independent branch of research within the OR community, exhibiting a wide variety of specific applications and associated integer programs, reaching its preliminary peak with the introduction of a powerful graph-theoretic approach, the reflect arc-flow model. However, there are still many benchmark instances that even the current formulations cannot yet contribute to solving. To this end, we present a new approach that is based on the observation that solutions of very good quality can already be determined on rather sparse (arc-flow) graphs, in general. More precisely, the arc sets of these graphs are defined by appropriate patterns obtained from a stabilized column-generation approach, so that considering the complete integer reflect arc-flow model is only necessary in a few cases. Compared to the reflect+ approach originally introduced for the cutting stock problem, we apply several modifications, discuss their numerical advantages by extensive computational tests, and end up with an adaptive solution method showing the most convincing results. In particular, we succeed in optimally solving some very challenging benchmark instances for the first time.


Original languageEnglish
Pages (from-to)145-162
Number of pages18
JournalDiscrete Applied Mathematics
Publication statusPublished - 31 Jul 2023

External IDs

Scopus 85152950121
WOS 000984966700001
ORCID /0000-0003-0953-3367/work/142244068



  • Column generation, Cutting, Flow formulation, Packing, Skiving stock problem