A Linear Programming Approach to the Cutting-Stock Problem

TLDR

The cutting‑stock problem seeks to satisfy specified length orders from stock material at minimum cost, but its integer‑programming formulation generates so many variables that even linear‑programming approximations become computationally infeasible. This paper proposes a technique to overcome the computational difficulty of the linear‑programming formulation of the cutting‑stock problem. The method restructures the LP so that the constraint matrix is square or column‑deficient, limiting the number of variables relative to constraints. The technique guarantees that the matrix used in computation never has more columns than rows.

Abstract

The cutting-stock problem is the problem of filling an order at minimum cost for specified numbers of lengths of material to be cut from given stock lengths of given cost. When expressed as an integer programming problem the large number of variables involved generally makes computation infeasible. This same difficulty persists when only an approximate solution is being sought by linear programming. In this paper, a technique is described for overcoming the difficulty in the linear programming formulation of the problem. The technique enables one to compute always with a matrix which has no more columns than it has rows.