A company makes standard 115-inch-wide rolls of thin sheet metal, and slits them into smaller rolls to meet customer orders for widths of 13, 16, and...

A company makes standard 115-inch-wide rolls of thin sheet metal, and slits them into smaller rolls to meet customer orders for widths of 13, 16, and 25 inches. The demands for these widths vary from week to week. From a 115-inch roll, there are many different ways to slit 13-, 16-, and 25-inch pieces.

A cutting pattern is a configuration of the number of smaller rolls of each type that are cut from the raw stock. Of course, one would want to use as much of the roll as possible to avoid costly scrap. For example, one could cut seven 16-inch rolls, leaving a 3-inch piece of scrap. Finding good cutting patterns for a large set of end products is in itself a challenging problem.