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