| Cutting Stock Problem |
Article Index for Cutting |
Website Links For Cutting |
Information AboutCutting Stock Problem |
| CATEGORIES ABOUT CUTTING STOCK PROBLEM | |
| combinatorial optimization | |
|
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 |
|
|