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

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. 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.

Article

Download

View PDF