Cutting stock problem
|
|
The cutting stock problem arises from many physical applications in industry. Imagine that you work in a paper mill, and you are a manager in the paper cutting division. You have a number of rolls of paper of fixed width waiting to be cut, yet different manufacturers want different numbers of rolls of various-sized widths. How are you going to cut the rolls so that the least amount of left-overs are wasted? This turns out to be an optimization problem, or more specifically, an integer linear programming problem.
A usual technique 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). We then have to solve a linear programming problem. Linear programs are common optimization problems. Fortunately there are good techniques for solving them. One method 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.
There is one problem to our formulation so far. To formulate the linear program, we have to create all possible patterns that might be cut from a roll. If there are many different order widths to cut from a paper roll, it is possible for there to be an exponential number of patterns that need to be included in the linear program (LP). As a result, the LP will be too large to even formulate and impossible to solve.
The 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.
We choose an initial set of patterns to include in the model and solve the linear program. Since it is unlikely that we chose the right set of patterns, we use the dual variable information from the linear program to generate a new pattern. We generate this pattern 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 which will reduce the number of rolls cut.
External links
- Page on the cutting stock problem (http://www-fp.mcs.anl.gov/otc/Guide/CaseStudies/cutting/formulation.html) at the Argonne National Laboratory