| Cutting Stock Problem |
Article Index for Cutting |
Website Links For Cutting |
Information AboutCutting Stock Problem |
| CATEGORIES ABOUT CUTTING STOCK PROBLEM | |
| combinatorial optimization | |
|
One approach for solving integer linear programming problems is to just forget about the integer part; this is called ''relaxation'' (later, we may use some integer programming techniques to ensure we get an integer solution). In general, solving the linear programming problem is much easier than solving the integer linear programming problem. One method for solving linear programming problems is the Simplex Method (duality), which starts from some non-optimal point and iteratively finds better and better solutions. The algorithm concludes with the optimal solution when no steps can be made to improve the solution. For the cutting stock problem, the standard formulation is to create all possible patterns that might be cut from a roll. The linear program then determines how many times each pattern is to be used, whilst satisfying the orders. In general, the number of possible patterns grows exponentially as a function of the different order widths to cut from a paper roll. Depending on the number of different widths it may therefore be too difficult to enumerate the possible patterns 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, among which are 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. 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 reduce the number of rolls cut. 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 1.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-produce some of the orders. These limitations are overcome in modern algorithms, which can solve to optimality very large instances of the problem (generally larger than encountered in practice). EXAMPLE A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. The following items must be cut: There are 308 possible patterns for this small instance. The optimal answer requires 73 master rolls and has 0.401% waste. |
|
|