# Cutting stock problem

### From Glossary

Determine a way to cut standard sheets of material into various shapes (like clothes parts) to minimize waste. This is a (linear) integer programming model: *patterns* are specified, and
is the amount of -th stock (e.g., sheet or roll of material) used to
generate the -th output by the -th pattern. Then, let be level of -th pattern used and . Thus, is the amount of the -th stock used, which is limited by its availability: ; and
is the amount of -th output generated, which is required to be in some range, say (allowing some demand overruns or underruns). Some models seek to minimize the total *waste*: . Other models consider cost too. The most common problems are 2-dimensional (odd shapes from sheets of material); the 1-dimensional case is called the *trim problem*. In the latter case, the stock index is not needed. For example, consider a stock of rolls of paper with a given width, which must be slit into rolls of various widths. Then, is how much of a stock roll is used by the -th pattern to generate a roll of the -th width. Moreover, is the amount of a stock roll used by pattern to generate a roll of width .