Pattern generating procedure for the cutting stock problem

One of the factors that add to the complexity of the cutting stock problem is the large number of cutting patterns that may be encountered. When the cutting stock problem is expressed as an integer-programming problem, the large number of cutting patterns involved generally makes computation infeasible. However, if the linear programming formulation of the cutting stock problem is free of integer variables, then the effect of the number of cutting patterns will be mitigated. An auxiliary problem arises from the formulation where the columns of the linear programming constraint matrix need to be determined. In this work, a simple pattern generating procedure is developed for solving the auxiliary problem. It is based on an ad hoc solution method described in literature for the knapsack problem. A search tree is used to develop the pattern generation method. Examples are given to illustrate the procedure and its applications.