Cutting stock problem

Grasshopper
1

Hello dear community. its been a long time since I have been here. and I have been wondering something lately. Lets see if you guys can guide me to solve this problem I have.

I have 70 and something… different values. (this is a real life situation) This values are all different measurements. All small pieces of wood. The longest its 1.3 meters and the shortest its 0.53 meters. All the values are different for example. 0.53, 0.60, 1.3, 1.0, 1.10, etc etc.

I need to calculate how many pieces of wood I will need to buy at the store to cut all the individual short pieces.

At the store the wood I need comes in 2.6 meters long. So for example in 1 piece of wood 2.6 meters long, I can nest 3 small pieces of: 0.53+ 0.90+ 1.10 meters long.
All that adds to 2.53 meters so its perfect and I can extract those 3 pieces out of 1 wood of 2.6 meters long.

Does it make sence?
The measurements I have are:

1,3
1,29
1,28
1,27
1,26
1,25
1,24
1,23
1,22
1,21
1,2
1,19
1,18
1,17
1,16
1,15
1,14
1,13
1,12
1,11
1,1
1,09
1,08
1,07
1,06
1,05
1,04
1,03
1,02
1,01
1
0,99
0,98
0,97
0,96
0,95
0,94
0,93
0,92
0,91
0,9
0,89
0,88
0,87
0,86
0,85
0,84
0,83
0,82
0,81
0,8
0,79
0,78
0,77
0,76
0,75
0,74
0,73
0,72
0,71
0,7
0,69
0,68
0,67
0,66
0,65
0,64
0,63
0,62
0,61
0,6
0,59
0,58
0,57
0,56
0,55
0,54
0,53

How many 2.6 pieces of wood will I need to extract all this small pieces of wood that I need. I’m doing a cost evaluation. And your help would be great appreciated.

2

24 I make it!

I think this should do the trick Set your max length and paste your lengths in the text area (with “.” not “,”) and you should get out what you need!

image
image.png1204×721 65.5 KB

SetMatcher.gh (15.0 KB)

3

Tom this looks like would do the trick. It’s amazing! Thanks for your help. I am currently at the phone but once I get home I will check it out. I see that you used C+ as a main component of this definition. I am have so little knowledge on scripts and programming. I wonder what’s inside. Anyhow I am truly thankful for your help. I will let you know how this works. Have a happy day.

4

Hello,

This is called the Cutting Stock problem and you will find some more discussions on this forum under similar names

5

I have to be honest I did this math manually. its was really tedious. and I got 32 pieces of wood that I will need. with your method it saids that I will need 24. its a lot less.
Can you explain a little more the math behind the scenes? Thanks Tom!

6

Wow, thanks so much for this link. I just what I was looking for a few days ago but I coulnd find. its still super usefull for me. so apreciated.

7

Sure,

To start with its sorts the list from longest to shortest.

Then it finds list items which are longer then the max length or less or equal to zero and removes them from the list.

Then it goes through the list, trying to find “sets”, until the list is empty with the steps:

  • Create a new Set
  • Set a variable “current set length” to 0.
  • Start Loop “A” with the first Item in the list.
  • if “current set length” + list item <= max length then:
    -add the List Item to the Set
    -add the List Item’s Length to the “current set length”
    -Remove the Item from the list
  • Get next Item in the list and repeat loop “A”
  • Once we get to the end of the list it means all the items have been checked to see if they fit and none do so the set is complete and the process starts again

Because the list is sorted we know that in loop “A” none of the previously checked item would have fit into the current set so we do not need to check them after each new item is added to a set.

I know this is not the Maths as as such but I figure this is not taking an intelligent Mathematical approach but rather just checking each item one by one to see if they fit.

If its easier we can also track the items onto the outputs to help see how its working?

Hope this Helps!

8

Just a heads up, I been looking at the code and there was a typo which meant the looping was cutting short, so the correct answer should be 30 I think?!

The definition attached also include an Index mapping for verification… So please use this one:

SetMatcher.gh (15.0 KB)

image
image1369×729 70.5 KB

Also its definitely not the optimal solution as it predicts 82 Rolls for the example on the Wikipedia the @Dancergraham posted where the best is 78, but something which can be used as a base line i guess…

9

Thanks Tom for the update. I did read the Wikipedia example. and there it says that the optimal solution its 73. and you say that you tried those numbers in the wikipedia post and the result for your definition its 82? I will try it myself and also I will read the other post that Dancegraham sugested and I will get back to oyu. Thanks for everything. Good day!

10

So I did the test with the values from wikipedia just to compare and have a reference. and its not working well. please take a look.
regards.

Cubicador Lineal (Cutting stock problem) NOT WORKING YET.gh (17.2 KB)

11

The input list needs 219 inputs if you are trying to match the Wiki’s one?

I have inputted the wiki table here below the orignial:
SetMatcher.gh (12.7 KB)

12

Tom. I have been reading. Maybe we can together solve this perfect. Also I have found this. matecconf_rsp2017_00050.pdf (108.8 KB)
Maybe it makes more sence to you.
I have also found a plug in payed for excel that does a perfect work and it even displays graphics of nesting. It’s awesome. I am sure we can achive something similar for all the community here. It would be great!

13

its this any help for youTom? you know more than I
https://www.mathworks.com/help/optim/ug/cutting-stock-problem-solver-based.html

14

Hi @ciscolara

I have been looking at the problem, and it’s something I think we can implement, but it requires more time than I have at the moment spare. So any helpers are welcome!

It requires a more complex coding solution than the initial response, as it will need to build a tree or dictionary of all the possible combinations of lengths, which can then be picked from in a similar fashion to first solution, but with the goal to minimise the waste or a completely new picking algorithm

15

Yes I understand. Maybe galapagos its the right tool for it. what you think? that evolutionary solver. inside grasshopper. I have no rush for now. we have time to solve this. I will keep on looking. I will let you know. if you find something please also let me know.
regards