Editing Cutting stock problem (section)

== Illustration of one-dimensional cutting-stock problem ==

A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600&nbsp;mm wide. The following 13 items must be cut, in the table below.

The important thing about this kind of problem is that many different product units can be made from the same master roll, and the number of possible combinations is itself very large, in general, and not trivial to enumerate.

The problem therefore is to find an optimum set of patterns of making product rolls from the master roll, such that the demand is satisfied and waste is minimized.

::{| class="wikitable"
|-
! width="80pt" |  Width
! width="80pt" | #Items
|-
| align=center | 1380   || align=center | 22
|-
| align=center | 1520   || align=center | 25
|-
| align=center | 1560   || align=center | 12
|-
| align=center | 1710   || align=center | 14
|-
| align=center | 1820   || align=center | 18
|-
| align=center | 1880   || align=center | 18
|-
| align=center | 1930   || align=center | 20
|-
| align=center | 2000   || align=center | 10
|-
| align=center | 2050   || align=center | 12
|-
| align=center | 2100   || align=center | 14
|-
| align=center | 2140   || align=center | 16
|-
| align=center | 2150   || align=center | 18
|-
| align=center | 2200   || align=center | 20
|}

===Bounds and checks===
A simple lower bound is obtained by dividing the total amount of product by the size of each master roll. The total product required is 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160&nbsp;mm. Each master roll is 5600 &nbsp;mm, requiring a minimum of 72.7 rolls, which means 73 rolls or more are required.

===Solution===
[[File:CuttingStock.gif|thumb|430px|A minimum-waste solution, sequenced to minimise knife changes, shown as small white circles]]
There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste; it can be shown computationally that in this case the minimum number of patterns with this level of waste is 10. It can also be computed that 19 different such solutions exist, each with 10 patterns and a waste of 0.401%, of which one such solution is shown below and in the picture:
:{| class="wikitable"
!Repetition
!align=center | Contents
|-
| align=center | 2 || 1820 + 1820 + 1820
|-
| align=center | 3 || 1380 + 2150 + 1930
|-
| align=center | 12 || 1380 + 2150 + 2050
|-
| align=center | 7 || 1380 + 2100 + 2100
|-
| align=center | 12 || 2200 + 1820 + 1560
|-
| align=center | 8 || 2200 + 1520 + 1880
|-
| align=center | 1 || 1520 + 1930 + 2150
|-
| align=center | 16 || 1520 + 1930 + 2140
|-
| align=center | 10 || 1710 + 2000 + 1880
|-
| style="border-bottom:3px solid grey" align=center | 2 || 1710 + 1710 + 2150
|-
|  align=center | '''73'''
|}