Your small company uses custom-cut steel reinforcing rod for construction jobs in metro Atlanta. These rods are purchased from a steel products distributor who is willing to cut the rods for you to specification.

However, the distributor cuts your pieces from stock that is only available in fixed 60-foot lengths. That is, if you need two lengths of rod, one of 15 feet and the other of 45 feet, then a single 60-foot piece is cut in the obvious way with nothing left over (and all is well). On the other hand, if you need eight, 7-foot pieces, then the 4 feet left over from the 60-foot original is yours to pay for as well. Of course, some of these excess pieces may be useful later, but you will have to find storage areas for such pieces which, in turn, costs something too. Indeed, what is left over may be useless altogether and is simply counted as scrap.

Thus, we would like to minimize the number of full 60-foot units/rods that have to be used in cutting all of the given lengths, which means that we may have to be reasonably clever in how we specify the pattern of cuts on each. For example, suppose you need to place an order for 10 pieces of rod having lengths 41, 24, 24, 22, 21, 19, 9, 7, 7 and 6 feet respectively. Since the total length of the 10 pieces is 180 feet, it is obvious that the best we could hope to use is three of the 60-foot spans, but is this even possible?

Naturally, this small numerical example is just a "toy" version of what might be a fairly messy problem in general. Indeed, in a real-world setting, you might have an order for hundreds or thousands of pieces to be cut from stock. In addition, the latter might come in varying sizes as well. And yes, your problem might be "multidimensional". For example, you might seek cutting patterns for 2-dimensional figures from rectangular sheets of aluminum with the aim of minimizing wasted area. You might be operating in a 3-dimensional setting where the requirement is to find a best packing configuration of irregularly shaped boxes into large unit shipping containers employed by an express mail carrier. Regardless, the underlying theme for any of these packing problems is the same; so too, by the way, is their enormous difficulty.