1D Stock Cutting in Grasshopper


(Cottonbale) #1

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.

Any suggestions ?


(Thomas Wortmann) #2

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.


(Cottonbale) #3

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.


(Graham) #4

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


(Cottonbale) #5

Hi 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.

Its for metal profiles.


(Graham) #6

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 :smiley:


(Cottonbale) #7

That’s very helpful - thank you Graham.

Topic renamed - will update this with my progress

Cheers


(Thomas Wortmann) #8

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.


(Graham) #9

Maybe not so helpful with that one but there are others:


(Cottonbale) #10

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 :grin:


(Cottonbale) #11

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 :grinning:


(Graham) #12

You could run an external Cpython instance with Scipy to solve it. Maybe using the subprocess module in python…?


(Graham) #13

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?


(Cottonbale) #14

Thomas’s solution suddenly looks really optimal…


(Cottonbale) #15

That was sage advice actually Graham - thanks for your help


(Graham) #16

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 !


#17

Have you seen this thread? If you can handle the humour of @PeterFotiadis
Linear cutting in a grasshopper


(Cottonbale) #18

OMG, that’s completely melted my mind! :grinning: