Cutting Stock

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

This program will try to find optimal solutions for what is commonly known as the 1-dimensional Cutting Stock Problem,  The Cutting Stock problem requires that we find the best (cheapest) way to cut one-dimensional stock pieces (pipe, dimensional lumber, wire, rolls of paper or other sheet material to be slit, etc.) in such a way that a given number of pieces of specified lengths or widths are created.
 

Background & Techniques

I ran across this problem via feedback from viewers wondering if my Cutlist program would work for cutting stock to specified lengths.  It will not.  However  there is a technique known as Delayed Column Generation for efficiently solving the problem.  Solutions are not perfect in the sense that extra pieces of the required lengths are not counted as waste.     

Program Usage

The program takes two types of data as input, Parts and Stock: The "Solve" button finds the lowest cost way to cut the required material. Results are displayed in text and graphical form. Check boxes specify whether the text version of fractional and/or integer solutions are displayed. The fractional solution assumes that unused "waste" has value. I.E. fractional stock pieces left over are not charged to the coast. In the integer solution, any piece cut from a stock piece results in a charge for the entire stock piece. There is also a "Verbose" checkbox used for debugging which displays information about intermediate results.  The graphical integer solution is always displayed.

The "Parts" grid reflects the desired output part defined by part lengths and the number of each part length required.  "Stock" input defines the lengths of stock material required and the cost of each length.  Enter data by clicking on a row of data and entering new values. There should always be a blank line for entering a new row of data. If not, the "Insert" keyboard key will create one. The "Delete" key will delete any selected row. For the Parts list, the system defines a random default color of that length for the graphical display. Click on any color in the Parts grid to bring a dialog where color may be changed to your preference.

Cases may be saved and restored using  "Save" and "Load" buttons. Cases are saved in text format and include the solution if the case has been solved. Printing a saved case file is an easy way to obtain a printout of the problem and solution.

I you're not interested in the math or programmer notes, click here to skip to the bottom of this page to download executable version of the program.

The Math

This is an LP (Linear programming) problem with the complication that the number of different ways to cut each stock piece grows exponentially with the number of lengths required and may get too large for traditional LP techniques. The different lengths required are rows of the solution matrix and the unique cutting patterns are the columns. The intersections of the input matrix contain the number of that length (row) which can be cut from that pattern (column). Since there may be hundreds (or thousands or millions) of columns, they cannot all be generated. The solution uses a technique called "Delayed Column Generation". Here we generate enough columns to define a solution, usually not the optimal one. Specifically, for each part length, cut as many as possible of that length from the longest available stock piece) until enough parts have been cut.. That solution is used as input to the second part of the algorithm, a "Knapsack" algorithm, which searches for an unused pattern that improves the solution, i.e. reduces the total cost. Since the Knapsack algorithm maximizes the value of goods that can be collected in a knapsack of a given size, the trick here is use the "dual variables" of the LP problem to maximize the amount of material cut per unit cost.  This process continues, swapping in each pattern which lowers the cost until no such pattern is found.

The solution produced by the above process is "fractional".   It minimizes the total cost with the implicit assumption that extra parts produced by a particular pattern can be utilized and are and are not "waste".  These Argonne National Laboratories pages provide the most referenced and best problem description I have found.

The final step in the process attempts to convert this to an integer solution where costs are accumulated for entire stock pieces, i.e. the customer would pay for all of the stock that has any part cut from it.  The fractional solution provides a lower bound for the cost.   Commercials programs will do a better job of this and/or may also satisfy other constraints such as minimizing the number of knife changes required to producew the parts.

Non-programmers are welcome to read on, but may want to skip to the bottom of this page to download executable version of the program.

Notes for Programmer's  

 The code was adapted to Delphi code from a Pascal version published several years ago by a group of Korean students working under Professor Soondal Park. Follow this link to find the original code. I wish I could say that I fully understood every step of the code, but my mother taught me never to lie. :>)

I replaced static arrays to dynamic, making them one position longer than necessary so that index values remain relative to 1 as in the original code.  I also moved the code to a separate unit (UDelayedColumnGenration) and made a separate TCaseRec record to contain the fields that I needed to access in the U_CutStock unit which calls the original solution code but need access to the results for finding the Integer solution and creating the results displays.

The section of the code which generates the integer solution from the fractional solution is original by me.  I am not sure that the method I use guarantees an optimal solution.  It assumes that no new patterns will be introduced in moving from fractional to integer solutions, which I have not seen proven, or even stated in my reading so far.  The specific technique I used was round each fractional stock piece up to the next higher integer.  The fractional solution defines a lower bound for the cost; those values rounded up provide an upper bound, but may add too much to the cost.   I  recursively remove a stock piece from of each pattern, one at a time,  until the original order quantities are not met.    

As usual, bug reports, comments, and suggestions are welcome. 

Addendum April 29, 2007:  The first bug fix was posted today.   Although I thought that fractional stock and part lengths were handled correctly, they were not.  The code which determines which pattern to select next (the Dynamic Knapsack procedure) is deeply dependent on the lengths being integers.  Until I find a replacement, my work-around is to scale the the lengths up by 10 or 100 (for 1 or 2 decimal accuracy) as necessary, solve the problem, and then scale the results back to the original fractional values.   A new case, Kevins.txt, with non-integer part lengths was added to the test cases in the zip files.

Addendum August 19, 2008: A while ago, a user submitted a case that Cutstock could not solve. It has many part lengths (19) and a wide range of lengths (134 to 6004).  Today's update, Cutstock3,  allows that case (SortTest.txt) to run by sorting the input stock in decreasing stock length before solving.  The base code for this program is not mine, and I'll admit that I have a difficult time debugging it, but I did notice that the other test cases were presorted and sorting this case allows a solution.     I also modified the cutting pattern graphic display to omit displaying length values when there is not enough space (for example, many adjacent short lengths cut from long stock).

This is one of three or four programs on DFF that needs a month dedicated to understanding and improving it, (but this this not the month J).              

Addendum September 25, 2008:  One more step towards understanding and possibly improving the search for optimum integer solutions.  A "Manual Cutting Stock" program posted today allows users to select which patterns (and how many) to use in producing the required number of parts.  The idea of course is to produce the parts with minimum cost.  So far I have  been able to match the original program solutions some of the time, but usually not.  Both "Manual Cutting Stock" and the original "Cutting Stock" programs  will read and create case files that ate compatible with the other.   It might be the basis for a challenging new puzzle game!     

November 11, 2010:  Version 4 posted today fixes a problem with part lengths that are not whole numbers.  Even though the code was modified in 2007 to handle such lengths, all the test files just had ".00" added to the data.  Any real fractional value was handled incorrectly.  Should be OK now.  The Manual Cutting Stock program still does not handle fractional part or stock lengths correctly.

  

Running/Exploring the Program 

Suggestions for Further Explorations

Run more cases for which solution is known, especially the Integer solution.

 

Original Date: March 31, 2007

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.