Cutting stock problem. The production of paper or cloth often uses the following process. We first produce the paper on long rolls which we then cut to meet specific demand requirements. The cutting stock problem is to meet the specified demand by using the minimum number of rolls. Suppose that the rolls all have length L and that we have a demand of di for smaller rolls of size Li • There might be many ways to cut any roll into smaller rolls. For example, if L = 50 and the Li have lengths 10, 15, 25, 30, we could cut the rolls into several, different patterns: for example, (1) 5 rolls of size 10; (2) 3 rolls of size 15; (3) 2 rolls of size 10 and 1 roll of size 25. Note that in the first pattern, we use the entire roll of size L, but in the other two patterns we incur a waste of 5. Let P denote the collection of all patterns, and for any pattern p ∈ P, let ni,p denote the number of small rolls of size Li in pattern p. (a) Letting xp be a nonnegative integer variable indicating how many rolls we cut into pattern p, show how to formulate the cutting stock problem of finding the fewest number of large rolls to meet the specified demands as an optimization model with a variable for each cutting pattern. (b) Suppose that we wish to cut a single roll of size L into sub-rolls and that we receive a profit of πi for every sub-roll of size Li that we use in the solution. Show how to formulate this problem as an integer knapsack problem. (c) Show how to use the column generation technique to solve the linear programming relaxation of the cutting stock problem in part (a), using knapsack problems of the form stated in part (b) to price out columns.
