optimized cutting solution (knapsack/bin packing) C#

Question

1.00/5 (1 vote)

See more:

Hi,
I need the following solution and have been battling to get it right. I have also searched high and low but could not find anything that I could use. Perhaps I am not understanding my own problem well enough.

I need to be able to programmatically find the best way to cut lengths of Rope/Pipe.
Here is the scenario:
I have the following lenthgs in stock: 3 X 4.7m 5 X 7.4m 3 X 11.2m 4 X 9.8m (these are lengths of rope that I currently have in stock)

I need to cut the following lengths for an order: 2 X 3m 4 X 1.2m 1 X 6m 2 X 5.4m

I have started of with a formula that will break down all my stock in to 1 X something lengths (meaning if I have 3 X 4.7m i obviously have 1 X 4.7m and 1 X 4.7m and 1 X 4.7m) I did the same for the lengths i need to cut for the order.
I have proceeded to match the longest cut length to the shortest stock length, if it can be done I need to add another length if there are enough rope remaining before going on to the next stock item.
Basically on paper I was able to work out every possibility and combination of how to cut these and then see which option wastes the least amount of rope ( i have calculated the left overs from the pieces I have cut and the least amount of leftovers or waste was the best option).

Now my problem is that I need to do this with code and cannot seem to get it right especially the fact that the cut lengths and amounts are dynamic per order.

If someone could please point me in the right direction or assist me with writing the code for this it would be much appreciated.

Regards,
Ben

Posted 27-Feb-13 2:23am

Thebenmandude

Add a Solution

2 solutions

Solution 1

1) It should never matter how many pieces of rope are being requested, just that all the lengths requested are available in your stock.
2) The simplest algorithm for something like this could be:
   a) Sort your requested items by length descending.
   b) For each of your sorted requested items
      i) Fullfil the order using the shortest stock rope possible.
      ii) Return the unused portion of the stock rope used in step i back into your inventory so that another request can make use of it.
      iii) Rinse and Repeat until complete.

Posted 27-Feb-13 3:45am

fjdiewornncalwe

Comments

Thebenmandude 27-Feb-13 11:11am

Thanks for the reply.
That was the approach that I started with, my only problem is that if I do not explore every possibility I might end up wasting more than I should. i.e If I have a 3m and a 6m in stock and need to cut 2 X 2m your mentioned logic wil cut 2m from the 3m leaving 1m and cut the second 2m from the 6m leaving 4m. Technically I will be "wasting" 5m where I could also cut the 2m and 2m from the 6m "wasting" only 2m since I did not use the 3m. As far as I know its called "best fit bin packing" or something to that affect. This might not be the best example but as I ran through multiple scenarios I found that it does not always pick the best fit solution.
I need to be able to group every possible combination, lets say i have the following cuts to make: a b c d
I can thus cut (a b c d) from different stock peices or
cut (a+b c d) or (a+c b d) or (a+b+c d) etc.
I could do this easily if I always have four/three pieces to cut, i would just hard code the combinations but since I don't i am not sure how handle the groupings dynamically.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Alberto Montibelli · Accepted Answer · 2014-01-06T08:38:00

Solution 2

Hi Ben,
I've just posted an application to solve your problem.
You can find it at C# Bin Packing - Cutting Stock Solver[^]

Regards

Alberto Montibelli

Posted 6-Jan-14 8:38am

Alberto Montibelli

Comments

CPallini 6-Jan-14 16:13pm

Looks interesting, my 5.