 # Cutting stock problem

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 $LaTeX: A_{i, j, k}$ is the amount of $LaTeX: i$-th stock (e.g., sheet or roll of material) used to generate the $LaTeX: j$-th output by the $LaTeX: k$-th pattern. Then, let $LaTeX: x_k$ be level of $LaTeX: k$-th pattern used and $LaTeX: y = Ax$. Thus, $LaTeX: \textstyle s_i = \sum_j y_{i,j}$ is the amount of the $LaTeX: i$-th stock used, which is limited by its availability: $LaTeX: s \le S$; and $LaTeX: \textstyle v_j = \sum_i y_{i, j}$ is the amount of $LaTeX: j$-th output generated, which is required to be in some range, say $LaTeX: L \le v \le U$ (allowing some demand overruns or underruns). Some models seek to minimize the total waste: $LaTeX: \textstyle \sum_i S_i - s_i$. 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 $LaTeX: i$ 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, $LaTeX: A_{j, k}$ is how much of a stock roll is used by the $LaTeX: k$-th pattern to generate a roll of the $LaTeX: j$-th width. Moreover, $LaTeX: \textstyle y_j = \sum_k A_{j, k} x_k$ is the amount of a stock roll used by pattern $LaTeX: j$ to generate a roll of width $LaTeX: j$.