Cutting stock problem

From Wikipedia, the free encyclopedia

The cutting stock problem is an optimization problem, or more specifically, an integer linear programming problem. It arises from many applications in industry. Imagine that you work in a paper mill and you have a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that you minimize the waste (amount of left-overs)?

Solving this problem to optimality can be economically significant: a difference of 1% for a modern paper machine can be worth more than US$ 1 million per annum.

1 Resolving
2 Illustration of one-dimensional stock cutting problem
3 Classification
4 Cutting stock problem in paper and film industries
5 References
6 Further reading
7 External links

[edit] Resolving

One approach for solving integer linear programming problems is to ignore the integer part (this is called relaxation). In general, solving an integer linear programming problem takes more time than solving the continuous linear programming problem.

For the cutting stock problem, the standard formulation (but not the only one) is to create a list of all combinations of cuts (often called "patterns") possible for a given set of customer orders. The linear program then determines how many times each pattern is to be used ( $x i$ ), whilst satisfying the $m$ orders, for each of which there is a need for $q_j, j=1,\dots,m$ pieces:

minimise $\sum_{i=1}^n c_i x_i$

subject to $\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m$ and

$x_i \ge 0$ , integer

where $a i j$ is the number of times order $j$ appears in pattern $i$ and $c i$ is the waste of pattern $i$ . The precise nature of the quantity constraints can lead to subtly different mathematical characteristics. The above formulation's quantity constraints are minimum constraints (at least the given amount of each order must be produced, but possibly more). In this case waste minimisation is equivalent to minimising the number of utilised master rolls. The most general formulation has two-sided constraints (for which minimising waste is no longer equivalent to minimising the number of master rolls):

$q_j \le \sum_{i=1}^n a_{ij} x_i \le Q_j, \quad \quad \forall j=1,\dots,m$

In general, the number of possible patterns grows exponentially as a function of the different order widths. For a very large number of different widths, it may therefore be impractical to enumerate the possible cut combinations and hence to solve the associated linear program.

An alternative is to use a Delayed Column Generation approach. This method solves the cutting stock problem by starting with just a few patterns. It generates additional patterns when they are needed. The new patterns are introduced by solving another optimization problem called the knapsack problem. The knapsack problem has well-known methods to solve it, such as branch and bound and dynamic programming. The Delayed Column Generation method turns out to be much more efficient than the original approach. The column generation approach was pioneered by Gilmore and Gomory in a series of papers published in the 1960's.^[1] ^[2]

The Gilmore and Gomory method starts by choosing an initial set of patterns to include in the model and solve the linear program. Since it is unlikely that the initial set is the right set of patterns, dual variable information from the linear program is used to generate a new pattern. The new pattern is generated using the knapsack problem. These two problems, the main linear program and the knapsack problem, are solved in turn until no more patterns can be generated that improve the solution. 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 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. 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^[3] ^[4]).

The cutting stock problem is often highly degenerate, in the sense that multiple solutions with the same waste are possible. This degeneracy arises because it is possible to move items around, creating new patterns, without affecting the waste. This give arise to a whole collection of related problems which are concerned with some other criterion, such as the following:

The minimum pattern count problem: to find a minimum-pattern-count solution amongst the minimum-waste solutions; this is a very hard problem, even when the waste is known^[5].

The minimum stack problem: this is concerned with the sequencing of the patterns so as not to have too many partially completed orders at any time^[6].

The minimum number of knife changes problem (for the one-dimensional problem): this is concerned with sequencing and permuting the patterns so as to minimise the number of times the slitting knives have to be moved. This is a special case of the generalised travelling salesman problem.

[edit] Illustration of one-dimensional stock cutting problem

A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. The following items must be cut:

Width	Rolls
1380	22
1520	25
1560	12
1710	14
1820	18
1880	18
1930	20
2000	10
2050	12
2100	14
2140	16
2150	18
2200	20

Solution

There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste; it is believed that in this case the minimum number of patterns with this level of waste is 10 (one such solution is shown below and in the picture, which also shows knife changes with small white circles):

Repetition	Contents
2	1820 + 1820 + 1820
3	1380 + 2150 + 2150
12	1380 + 2150 + 2050
7	1380 + 2100 + 2100
12	2200 + 1820 + 1560
8	2200 + 1520 + 1880
1	1520 + 1930 + 2150
16	1520 + 1930 + 2140
10	1710 + 2000 + 1880
2	1710 + 1710 + 2150
73

[edit] Classification

Cutting stock problems can be classified in several ways^[7]. One is the dimensionality of the cutting: the above example illustrates a one-dimensional (1D) problem; other industrial applications of 1D occur when cutting pipes, cables and steel bars. Two-dimensional problems (2D) are encountered in furniture, clothing and glass production. Not many three-dimensional (3D) applications involving cutting are known; however the closely related 3D packing problem has many industrial applications, such as packing objects into shipping containers (see e.g. containerization).

[edit] Cutting stock problem in paper and film industries

In the paper (see Pulp and paper industry) and plastic film industries the cutting stock problem has many variants and additional constraints. These arise because of machinery / process constraints, customer requirements and quality issues; they include the following:

Two stage problems where the rolls produced in the first stage are then processed a second time. For instance all office stationery (e.g. A4 size in Europe, Letter size in US) is produced in such a process. The complication arises because the machinery in the second stage is narrower than the primary. Metallised film (used in packaging of snacks), and plastic extrusion on paper (used in liquid packaging, e.g. juice cartons) are examples of such a process.

Winder constraints where the slitting process has physical or logical constraints: a very common constraint is that only a certain number of slitting knives are available, so that feasible patterns should not contain more than a maximum number of rolls. Because winder machinery is not standardised, very many other constraints are encountered.

An example of a customer requirement is when a particular order cannot be satisfied from either of the two edge positions: this is because the edges of the sheet tend to have greater variations in thickness and some applications can be very sensitive to these.

An example of a quality issue is when the master roll contains defects that have to be cut around. Photographic paper, which is particularly expensive and whose quality requirements are very high, has to be carefully optimised so that the wasted area is minimised.

Multi-machine problems arise when orders can be produced on more than one machine and these machines have different widths. Generally availability of more than one master roll width improves the waste considerably; in practice however additional order splitting constraints may have to be taken into account.

There is also a semi-continuous problem, where the produced rolls do not have to be of the same diameter, but can vary within a range. This typically occurs with sheet orders. This is sometimes known as a $1\tfrac{1}{2}$ dimensional problem.

Suppliers of such software to the paper industry include ABB Group, Greycon, Honeywell and TietoEnator.

[edit] References

^ Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem. Operations Research 9: 849-859
^ Gilmore P. C., R. E. Gomory (1963). A linear programming approach to the cutting-stock problem - Part II. Operations Research 11: 863-888
^ Goulimis C (1990). Optimal solutions for the cutting stock problem. European Journal of Operational Research 44: 197-208
^ de Carvalho V (1998). Exact solution of cutting stock problems using column generation and branch-and-bound. International Transactions in Operational Research 5: 35–44
^ S. Umetani, M. Yagiura, and T. Ibaraki (2003). One dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research 146, 388–402
^ Maria Garcia de la Banda, P. J. Stuckey. Dynamic Programming to Minimize the Maximum Number of Open Stacks. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.
^ Wäscher, G.; Haußner, H.; Schumann, H. An Improved Typology of Cutting and Packing Problems. European Journal of Operational Research Volume 183, Issue 3, 1109-1130

[edit] Further reading

Chvátal, V. (1983). Linear Programming. W.H. Freeman. ISBN 978-0716715870.
Hatem Ben Amor, J.M. Valério de Carvalho, Cutting Stock Problems in Column Generation, edited by Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, Springer, 2005, XVI, ISBN 0-387-25485-4