Cutting stock problem
A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide.
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.
A simple lower bound is obtained by dividing the total amount of product by the size of each master roll.
When either the master item or the required parts are irregular-shaped (a situation often encountered in the leather, textile, metals industries) this is referred to as the nesting problem.
This is done e.g. in paper and plastic film industries but also in production of flat metals like steel or brass.
There are many variants and additional constraints arising from special production constraints due to machinery and process limits, customer requirements and quality issues; some examples are: The cutting stock problem was first formulated by Kantorovich in 1939.
[4] In 1951 before computers became widely available, L. V. Kantorovich and V. A. Zalgaller suggested[5] solving the problem of the economical use of material at the cutting stage with the help of linear programming.
, the objective minimises the number of utilised master items and, if the constraint for the quantity to be produced is replaced by equality, it is called the bin packing problem.
Many variations are possible, including one where the objective is not to minimise the waste, but to maximise the total value of the produced items, allowing each order to have a different value.
The knapsack problem has well-known methods to solve it, such as branch and bound and dynamic programming.
The Delayed Column Generation method can be much more efficient than the original approach, particularly as the size of the problem grows.
The column generation approach as applied to the cutting stock problem was pioneered by Gilmore and Gomory in a series of papers published in the 1960s.
[6][7] Gilmore and Gomory showed that this approach is guaranteed to converge to the (fractional) optimal solution, without needing to enumerate all the possible patterns in advance.
A limitation of the original Gilmore and Gomory method is that it does not handle integrality, so the solution may contain fractions, e.g. a particular pattern should be produced 3.67 times.
Rounding to the nearest integer often does not work, in the sense that it may lead to a sub-optimal solution and/or under- or over-production of some of the orders (and possible infeasibility in the presence of two-sided demand constraints).
This limitation is overcome in modern algorithms, which can solve to optimality (in the sense of finding solutions with minimum waste) very large instances of the problem (generally larger than encountered in practice[8][9]).
The cutting-stock problem is often highly degenerate, in that multiple solutions with the same amount of waste are possible.
This degeneracy arises because it is possible to move items around, creating new patterns, without affecting the amount of waste.
