CiteWeb id: 20160000010

CiteWeb score: 1849

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. OME linear programming problems arising from combinatorial prob< lems become intractable because of the large number of variables involved. Usually each variable represents some activity, and the difficulty is that there are too many possible competing activities satisfying the combinatorial restrictions of the problem. An example of this is the cutting-stock problem described below in a form similar to that used by EISEMANN. [1] The purpose of this paper is to point out that this difficulty can be overcome by a method basically identical with the idea that can be considered as implicit in references 2 and 3, and whichisessentiallythis. When, in the simplex method, we reach the stage of 'pricing out' or looking for a new column or activity that will improve the solution, instead of looking over a vast existing collection of columns to pick out a useful one, we simply create a useful column by solving an auxiliary problem. In reference 2 the problem is a shortest-path problem, in reference 3 a problem in linear programming. In the problem considered here the auxiliary problem will be of the integer programming variety, but of such a special type (the 'knapsack' type) that it is solvable by several methods (see reference 4). If the same technique were applied to the problems discussed in reference 5, the calculation of WAGNER AND WHITIN 91 would be applicable to the auxiliary problem, while for the problem discussed in reference 6 a general integer programming technique such as discussed in references 7 or 8 would presumably be required. 849