An optimization problem in the paper, steel, and wood industries is the cutting-stock problem.  The main feature of this problem is that finished goods of varying lengths are cut from larger raw material pieces of varying lengths.  The goal is to cut the raw materials using an efficient set of patterns to minimize the total amount of raw materials required, while meeting demand for all finished products.  Examples would include sheet metal and paper manufacturers that take larger rolls of product and cut them into smaller rolls for sale to customers.

As an example, suppose you are a steel fabricator that takes 45 foot steel beams and cuts them into 14, 12 and 7 foot beams for sale to construction firms.  Cutting one 45 foot beam into one 14 foot piece, two 12 foot pieces and one 7 foot piece would be very efficient in that it would exactly use up the 45 foot raw material piece with no trim waste.  On the other hand, a pattern of one 14 foot piece, one 12 foot piece and two seven foot pieces would not be as efficient due to a 5 foot piece of trim waste.

A brute force method for attacking the cutting-stock problem would be to generate all possible efficient patterns and run an optimization model to determine how may copies of each pattern to run to satisfy demand at minimal cost.  The drawback here is that the number of patterns grows exponentially as the number of different finished good lengths increase.  For all but the smallest problems, brute force pattern generation will yield large, intractable models.

Gilmore and Gomory published a paper in 1961 titled A Linear Programming Approach to the Cutting-Stock Problem.  In this paper they outline a two-stage, iterative approach for solving cutting-stock problems that dramatically reduced the number of patterns one must generate to get good solutions.  The basic idea involves solving a master problem containing a limited number of patterns.  The dual prices on the finished goods are then passed to a small knapsack subproblem that selects a new cutting pattern that maximizes the sum of the dual values of all the finished goods contained in the pattern subject to not exceeding the length of the raw material. This pattern is then appended to the previous master problem, which is then re-solved.  This iterative process continues until no further beneficial patterns can be generated by the knapsack subproblem.  In which case, we have the optimal solution to the original, linear cutting-stock problem.  The remarkable feature of this algorithm is that it typically takes relatively few passes to reach the optimal solution, thereby making it possible to solve very large cutting-stock models in an extremely reasonable amount of time.  This approach of iteratively appending new columns to models is also referred to as column generation.