L. V. Kantorovich and cutting-packing problems: new approaches to combinatorial problems of linear cutting and rectangular packing

In the middle of the XXth century L. V. Kantorovich and V. A. Zalgaller suggested to solve the problems of thrifty material using while cutting it with the help of linear programming. This resulted in permanent relaxation of planning the rational cutting problem and, as a matter of fact, closed up the problem in mass production. The paper briefly describes the ways of realization of the method for one-dimensional cutting. The problem is extended to integer cases typical for any cutting problem. The block structure technology has been worked out for two-dimensional cutting-packing problems. This technology reduces to solution of some special planning problem of one-dimensional cutting that can be solved by linear programming with the help of simple heuristics. Some calculating schemes and results of numerical experiments with wasteless packing are also shown in the paper. The comparison with other algorithms proves the efficiency of the block method.