Solving the skiving stock problem by a combination of stabilized column generation and the Reflect Arc-Flow model

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.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

The skiving stock problem is a counterpart of the cutting stock problem and has become an independent branch of research in the operations research (OR) community. A graph-theoretic approach called the reflect arc-flow model has shown promising results in solving specific skiving stock instances. However, there are still challenging benchmark instances that current formulations cannot solve. In this study, a new approach based on sparse graphs and a stabilized column-generation approach is proposed, which demonstrates optimal solutions for previously unsolved benchmark instances.