Leonid Kantorovich's methods cut waste in steel sheets

Person: Leonid Kantorovich
Lived: 1912–1986
Field: Mathematical economics
From: Soviet

The story

One of the problems Leonid Kantorovich identified in his 1939 work on linear programming was 'rational material cutting': how to cut standard sheets, rolls or bars into the pieces a factory needs while wasting as little as possible. In his 1939 booklet he had already sketched methods for minimising the waste of materials cut from standard forms, and the cutting stock problem, as it is now called, is generally credited as having first been formulated by him that year.

The problem is harder than it looks. Even a small order can be cut from standard stock in hundreds of different patterns, and choosing the best combination is a demanding mathematical task. After the Second World War, Kantorovich put his ideas into practice. From 1948 to 1950 the geometer V. A. Zalgaller, working under his guidance at the Leningrad Carriage-Building Works, calculated the optimal use of steel sheets with linear programming methods. In his Nobel autobiography Kantorovich noted that the work saved material.

In 1951, before computers became widely available, the two men published a book summing up the experience and giving a systematic explanation of their algorithms. It included a combination of linear programming with the idea of dynamic programming, reached independently of the American mathematician Richard Bellman. The technique they proposed for the cutting problem was later called the column generation method, an approach developed further by the American researchers Gilmore and Gomory in a series of papers in the 1960s.

The cutting stock problem remains one of the classic applications of optimisation. One-dimensional versions arise when cutting paper rolls, pipes, cables and steel bars; two-dimensional versions in furniture, clothing and glass production; and irregular shapes in the leather, textile and metal industries.

Modern solvers still use the column generation approach for such problems, because it handles large orders far more efficiently than listing every pattern. The savings Kantorovich and Zalgaller achieved in a Leningrad railway carriage works pointed the way to methods that reduce waste in factories around the world.

Why it matters

Optimal cutting methods descended from this work help industries from steel to paper and textiles reduce waste and save resources.

About Leonid Kantorovich

Leningrad mathematician who invented linear programming in 1939 while solving a plywood factory’s puzzle, and the only Soviet economist to win the Nobel Prize, in 1975.

Read the full profile

Leonid Kantorovich

1912–1986 · Mathematical economics

View profile →