A company makes custom-sized decoration objects from sheets of metals and they got an order to make a collection of 18 pieces that require one of the most expensive metal sheets they have.

In total, they need slices of 8 different lengths to produce the entire collection. The length and the respective number of each slice required to make all the 18 pieces go as follows: 1: 3, 2: 2, 3: 2, 5: 2, 10: 3, 20: 3, 25: 2, 50: 1.

The company has only three sheets available of the required metal and all three sheets are 71 inches long. Since they have produced the same collection before, they know that it's possible to make all 18 pieces out of these three sheets without wasting an inch of the precious metal. However, no one remembers the pattern they used to slice the sheets at that time.

In addition, an apprentice has already cut a slice of 22 inches from Sheet 1 and another slice of 3 inches from Sheet 2.

From which sheet will they take the 50 inches slice?

Finding a subset of patterns that meet certain requirements, including the requirement to minimize cost, is common in many applications.

The example of the company that makes products out of metal sheets, for instance, is just one example of a whole class of problems known as cutting stock.

There is a whole body of literature that studies cutting stock problems and their applications.

Solution approaches range from enumeration techniques to metaheuristics to mathematical optimization and hybrid algorithms.