Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

Flow formulations have been widely studied for the one-dimensional cutting stock problem and several of its extensions. Among these, the so-called reflect model has shown the best empirical performance when solved directly with a general-purpose integer linear programming solver due to its reduced number of variables and constraints. However, existing adaptations of reflect for the skiving stock problem (SSP), the variable-sized cutting stock problem (VSCSP), and the multiple knapsack problem (MKP) leave room for improvement. In this work, we propose new reflect-specific modeling strategies, both for the case where rolls have variable sizes (as in the VSCSP and MKP) and where the objective is to maximize the number of rolls above a certain length threshold (as in the SSP). In particular, we introduce new pattern representations for variable-sized rolls and a new reduction procedure for the SSP, both of which further reduce the number of variables and constraints in the model and result in decreased running times compared to the original reflect formulation. We also show that these strategies can be extended and even combined when solving the variable-sized skiving stock problem, a combination of the VSCSP and SSP that has never been studied in the literature.

Details

Original languageEnglish
Pages (from-to)51-69
Number of pages19
JournalEuropean Journal of Operational Research
Volume334
Issue number1
Publication statusPublished - 1 Oct 2026
Peer-reviewedYes

External IDs

Scopus 105037471535

Keywords

Keywords

  • Computational experiments, Flow formulations, Integer linear programming, One-dimensional cutting and packing problems