I need to implement an algorithm in GH for the Cutting Stock problem. Well I think I do.
Algorithm folks will know this as a staple problem; similar to the classic knapsack one. It’s only 1D not 2D like template nesting but with the ‘normal’ cutting stock problem the lengths of stock are fixed and I need the algorithm to be able to handle stock of varying lengths.
From what I gather, the varying stock lengths means this no longer conforms to the cutting stock problem and instead falls under the domain of the bin packing problem and I have not found any pseudocode for this, only some scary looking maths in whitepapers.
I think you could solve this with an iterative knapsack (where the value is proportional to size). Start with the largest stock and work your way down. This would not be guaranteed to be optimal, but probably effective anyway.
So by extension of that logic I guess I could just run the cutting stock cutting algorithm for n number of times where n is the number of varying stock length. I’m not convinced this is the way but it’s got me thinking. Thanks.
Hi,
What exactly are you aiming to achieve in practical terms? On what type of geometry? In how many dimensions? With what constraints? For what aim?
If you are seeking help with pure algorithms then stackoverflow may be a good place to look/ask…?
-Graham
Yes, this is one for stackoverflow really. I should have gone there first.
It’s a simple 1D cutting stock issue where, given a number of beams to cut at varying lengths from a set of stock of say 3 fixed lengths I have to output the selection of stock that will produce the required cut lengths with minimum wastage.
I work with a grasshopper scripter that wishes me to add a python or c# script that accepts the lengths of required beams as parameters and outputs a single number of required stock beams to be ordered.
OK understood. Update - I dont think this is helpful as it requires PyGLPK
This repo claims to solve the cutting stock problem using python - seemingly with pure python. You only need the .py files and not the .pyc files.
Based on the print statements it seems to we written under legacy 2.7 python so should run in Rhino / GH. I would be interested to know how you get on. By the way could you rename thi topic ‘1D Stock Cutting in Grasshopper’ or similar so it is easier to find in future?
Good luck
For the bound, find the combination of stocks with the smallest length that is at least the length of the remaining pieces minus the remaining length of currently used stock, discarding remainders that are smaller than the smallest remaining piece.
This subproblem can be solved as a (much easier) branch-and-bound itself.
So it seems that this can’t be done without some linear programming library, which is in turn based on linear algebra. Is that correct? What a can of worms I have opened. I’ve started on stackoverflow and really gone down the rabbit hole with this one
Or use Thomas’ solution of grabbing the longest fitting item at each step, possibly followed by a few iterations seeking to swap elements to reduce wastage?
Great ! I’d be interested to know how you get on. I am unlikely to have stock cutting needs but may need to optimise placement in 2D and/or 3D in the future when preparing wind tunnel models. I would tend to go via Python because it’s what I know the best !
I’m sitting here with a similar problem, and I couldn’t handle the complexety of PeterFotiadis’ ‘discussion’.
I’m interested to hear if you came up with anything?
