The Cutting-Stock Problem

Chapter 13 of Chvátal’s Linear Programming explains that paper is produced in big, wide rolls called raws. Customers can order rolls of different widths which are formed by cutting the raws; the resulting rolls are called finals. For example, a manufacter that makes raws 200cm wide might receive orders for several finals of 47cm and 33cm and decide to cut a raw into two rolls of width 47cm and three rolls of width 33cm with 7cm left over as waste (200 = 47×2 + 33×3 + 2).

We can use linear programming to find the most economical way of cutting raws into finals. This is known as the cutting-stock problem.