An LP-based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns

摘要

The one dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industries. As the setup costs of cutting patterns become more important in recent cutting industry, we consider a variant of 1D-CSP, in which the total number of applications of cutting patterns is minimized under the constraint that the number of different cutting patterns is specified in advance. We propose a local search algorithm that uses the neighborhood obtained by perturbating one cutting pattern in the current set of patterns, where the perturbations are done by utilizing the dual solution of the auxiliary linear programming problem (LP). In this process, instead of solving a large number of LPs from scratch, we quickly solve them by employing a variant of the simplex algorithm called the criss-cross algorithm. According to our computational experiment, it is observed that the proposed algorithm attains comparable quality of solutions while using smaller number of different cutting patterns than those required by existing heuristic approaches.