A New Linear Programming Approach to the Cutting Stock Problem

Abstract

A new approach to the one-dimensional cutting stock problem is described and compared to the classical model for which Gilmore and Gomory have developed a special column-generation technique. The new model is characterized by a dynamic use of simply structured cutting patterns. Nevertheless, it enables the representation of complex combinations of cuts. It can be advantageous in practical applications where many different stock lengths or a relatively large number of order lengths have to be dealt with. The new approach is applied to a real problem where the “trim loss” is not valueless, since it can be used for further demands arising in later planning periods.