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…?
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.
Its for metal profiles.
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?
That’s very helpful - thank you Graham.
Topic renamed - will update this with my progress
Here’s an idea for exhaustive branch-and-bound:
Start greedy to find a basic solution.
Then use branch-and-bound.
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.
Maybe not so helpful with that one but there are others:
Yeah, I kinda didn’t want to just copy code and often it takes longer than grokking something first and implementing it yourself.
Knew I should’ve read that dusty old algorithms book back when
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
You could run an external Cpython instance with Scipy to solve it. Maybe using the subprocess module in python…?
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?
Thomas’s solution suddenly looks really optimal…
That was sage advice actually Graham - thanks for your help
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 !
OMG, that’s completely melted my mind!
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?
I think it took so long for me to decide what to do a workaround was put into place so the need disappeared.
If I remember correctly, this is a classic algorithm problem, but again, I cannot remember the name.
I will have a look into it but don’t count on me finding an answer
Okay, thats how it often goes with these sort of issues.
You shouldn’t. I was just keen on hearing if you came up with anything.
Here is another method with OpenNest:
Thank you @djordje
I’ve realized that my problem more reassembles the multiple knapsack problem.
I have multiple unique lines, which I would like to cut in accordance to a group of constant line lengths with a little leftover as possible. So in some way, it is sort of the 1D cutting but upside down.
In my case the knapsack weights would then be changed to resemble line lengths.