Algorith/Code to create Minimum waste cutting program
I have been asked to develop a program which will let us calculate the optimal sequence to cut lengths of steel for customers resulting in the least waste and time.
Lengths of steel are purchased in industry standard lengths of 20, 40 and 60 feet.
We may have 10 clients. 5 want 12 lengths of 22 feet, 3 want 8 lengths of 43 feet and the last 2 want 20 lengths of 33 feet.
I want to write a program where i enter the lengths of standard pipe we have on hand, then enter the lengths we need to cut. The program spits out the best use of the lengths we have on hand to minimize waste and cuts.
I don't need to know how to write the program, just need help with the algorithms and use in the C# windows forms world. Researching on the web has come up with many theories on Stock Cutting but nothing i can understand at a level to modify to my needs.
The reason you aren't finding fast easy answers to this on the web is that your problem is technically a "very hard" problem. Your problem is a variation of the common "Knapsack" problem in mathematics. It is known to be an NP-Complete problem (which means that there is no algorithm much better than just trying every possible combination and comparing them all).
So, unfortunately, there is no efficient algorithm out there which will give you the optimal solution. (If you happen to write one, you win $1,000,000 http://www.claymath.org/millennium/ so don't try unless you have a few years of free time and an I.Q. > 150 because that offer's been out there quite some time)
So, that said, your options are:
1. Write an algorithm to try most of the possible combinations.
2. Write an algorithm that will run faster, but won't guarantee the best.
With modern computers and your relatively small input set, option 1 will probably work just fine. Just be comforted knowing that it's not really your fault that you couldn't find a better way. People way smarter than either of us have been trying and failing for years.
0
Winston SmithDeveloperAuthor Commented:
After a few more hours of researching and reading a few white papers from various brain trusts I would have to agree with you 100%.
As to option 1, any handy brute force methods out there? I am mo math wiz and am currently on iPhone so mo way to experiment. Otherwise thanks for your help so far!
0
Your question, your audience. Choose who sees your identityâ€”and your questionâ€”with question security.
Since your problem is related to the knapsack problem, which in turn is related to the subset sum problem, you may be able to speed up the NP problem to a polynomial time problem.
Look at "Pseudo-polynomial time dynamic programming solution" in: http://en.wikipedia.org/wiki/Subset_sum_problem
It offers a recursive algorithm using memoization to avoid repeating computations.
Also, take a look at the EE question which talks about converting an NP problem to a quicker solution: http://rdsrc.us/tyjnGh
I'll try to take a look at your problem in the next day or two if I have time.
Oh, I forgot about the statistics in the previous EE question, which may encourage you. The naive approach for the scenario stated in http://rdsrc.us/GBR7yA
took 317 seconds; but with a little tweaking here and there, the optimized version took only 0.08 seconds for the same data.
Hopefully, we can come up with a similar 4000-fold improvement over a brute force algorithm, or a less optimal greedy algorithm.
One thing that will make this a bit eaiser is to observe that if you use two 20' rods, you may as well have used one 40' rod. If you used one 40' and one 20', you may as well have used one 60' instead. So the only time you need to consider using a 20' is if you've filled a bunch of 60's and no 40's. You will only ever use a maximum of one 20' stock piece.
>> Lengths of steel are purchased in industry standard lengths of 20, 40 and 60 feet.
>> We may have 10 clients. 5 want 12 lengths of 22 feet, 3 want 8 lengths of 43 feet and the last 2 want 20 lengths of 33 feet.
It is important to know whether the above problem statement is to be taken concretely or symbolically. That is, do you need an algorithm where every bold number is considered an integer parameter that will vary from one run to the next?
Can you think of a scenario where you would not get the optimal by filling only the largest possible knapsacks and then swapping them out for smaller ones at the end if needed?
0
Winston SmithDeveloperAuthor Commented:
Phoffric-that is correct. All of the numbers you have in bold would be variables. The standard lengths of 20,40 and 60 may never change but I have been caught in that kind if hardcoded thinking before. Runs would be solved on a daily, if not hourly basis, as client work orders needed to ne filled. Any solution would be better than our current cut and guess method used by the guys on the floor.
As an aside, I work in research so this problem is new to me and only brought up over beer(s) with a few operations guys who thought programming was drag and dropping buttons.
Usually when designing an algorithm, we are concerned with the complexity - like O(nÂ²), O( n log n ). So, when you say:
>> 5 want 12 ..., 3 want 8 ..., 2 want 20 ...
Is this a typical quantity, or is a very fast algorithm required to handle, for example:
>> 500 want 1200 ..., 300 want 800 ..., 200 want 2000 ...
The smaller the max values of the numbers, the less we have to be concerned about how high n goes. In other words, if the program takes 2 hours for an optimal solution for you typical problems, but 2 years for the modified version just shown, that may not matter for practical purposes.
0
Winston SmithDeveloperAuthor Commented:
This is a small shop in relative terms. They may have 50 of each length of standard pipe on hand and only need to make 20-100 cuts in a day. Hopefully this brings down complexity. I have read that there is a large difference between integer and non integer variables In Linear programming so I should mention that the length of cuts will not always be even, there will be fractions of feet.
I just want to see if I understand the problem correctly.
I am assuming that you cannot use the 20 foot pipes for the OP scenario. In that case, isn't the minimal waste solution derived from only using the 60 foot pipes?
For the OP, you need to produce:
===============
60 pipes of 22 feet
40 pipes of 33 feet
24 pipes of 43 feet
=============== or equivalently:
24 pipes of 43 feet :: need 24 60 foot pipes; waste = 24*17 = 408 feet
----
40 pipes of 22 feet
40 pipes of 33 feet :: need 40 60 foot pipes; waste = 40*5 = 200 feet
----
20 pipes of 22 feet:: need 10 60 foot pipes; waste = 10*16 = 160 feet
===============
Total waste for OP is 768 feet using 74 60 foot pipes
======================================================
In the OP you didn't mention the quantities of pipes in stock. But in your last post, you said that they may have 50 of each standard length. If only 50 available, then the above solution does not compute. So, in addition to the OP numbers, I guess we also need to include the exact number of pipes available for the day for the algorithm.
I also assume that the number of customers and what they want is not that relevant to the algorithm; just the number of each part required is needed. That is, there is no best fit in terms of customer preferential treatment (or assigning weights to specific customers).
=====
Practically speaking, can't you make use of the 17 foot leftover pipes from one day to the next in case some orders come in for 15 foot pipes?
0
Winston SmithDeveloperAuthor Commented:
Correct on all points. The example i gave was just off the top of my head. Some days we may only need 10 lengths of 5 feet. Some days more complex. We never know what will be needed any given day, the only given is that we will have X number of each of the 3 standard lengths of pipe on hand.
Left-over pipe we have we will add into the available pipe lengths on hand for the next day.
How often do you have orders for fairly short lengths of pipe? The fact that you can roll over the offcuts makes the problem quite a bit more complicated. Instead of trying to get the minimum offcut, you may want to maximize the likelihood that the offcuts will be useful in the next few days.
Believe it or not, having a computer work on a problem isn't always better than having a person sit there and figure it out. There was once a million dollar prize offered for a computer that beat the level of a "clever 10 year old" at the game Go. The prize went unclaimed and the offer only expired because the one who made the offer expired. Many people smarter than me (as smart as phoffric even) have tried and the human brain is still better. The same goes for object detection and most other aspects of image processing. No computer can tell some pairs of identical twins apart. But their mothers can in miliseconds.
You can write an algorithm to spit out numbers, and it can be pretty good. But with multiple knapsacks and rollover of offcuts it will be hard to prove that an algorithm is optimal.
#!/usr/bin/perl
@lengths=(20,40,60);
@clients=([5*12,22],[3*8,43],[2*20,33]);
our %Q;
our @Q0;
sub dp{
my ($l0,$l,$p,$s,@s)=@_;
my $q=int($l/$s);
if( @s ){
do{
#print "(@{$p},$q),$l,$s,$s[0]\n";
dp($l0,$l-$s*$q,[@{$p},$q],@s);
}while( $q-- && $l > $s[0] );
}elsif( !$Q{"@{$p} $q"} || $Q{"@{$p} $q"}[0]>$l-$s*$q ){
$Q{"@{$p} $q"}=[$l-$s*$q,[$l0,@{$p},$q]];
}
}
sub dpl{
my @l=@{+shift};
my @C=sort{$b->[1]<=>$a->[1]}@_;
my @s=map{$_->[1]}@C;
#print "@l\n@s\n";
for( @l ){
my @q;
dp($_,$_,[],@s);
}
#print Dumper \%Q;
@Q0=grep/[1-9]/,keys %Q;
my ($s,@S)=@{search(map{$_->[0]}@C)};
#print Dumper $s,@S;
my %c;
for my$s( @S ){
$c{$s->[0]}{join",",map{($s[$_])x$s->[$_+1]}0..$#s}++
}
for my $p( keys %c ){
for( keys %{$c{$p}} ){
print "cut $p into ($_) $c{$p}{$_} times\n";
}
}
}
dpl(\@lengths,@clients);
sub search{
my @c=@_;
return $Q{"@c"} if $Q{"@c"};
#print "search(@c)\n";
my @s;
for( @Q0 ){
no warnings 'recursion';
my @q=split;
my @c1=();
for( 0..$#c ){
last if $c[$_]<$q[$_];
push @c1,$c[$_]-$q[$_];
}
next if @c1<@c;
my($t0,@t0)=@{$Q{$_}};
my($t1,@t1)=@{search(@c1)};
@s=($t0+$t1,@t0,@t1) if !@s||$t0+$t1<$s[0];
}
return $Q{"@c"}=[@s];
}
__END__
prints
cut 60 into (22,22) 10 times
cut 60 into (43) 24 times
cut 60 into (33,22) 40 times
@Halon,
>> the only given is that we will have X number of each of the 3 standard lengths of pipe on hand.
Is X constant? Is X the same for each of the 3 standard lengths?
>> Any solution would be better than our current cut and guess method used by the guys on the floor.
For starters, could you give us an idea of the methodology or heuristics used. Does it have various modalities based on the specifics of the orders and current inventory? Have you often realized later that your solution was sub-optimal and this situation is still occurring?
>> there is a large difference between integer and non integer variables In Linear programming
>> the length of cuts will not always be even, there will be fractions of feet
What is the resolution of your cuts? 1/2 foot, 1/10 foot, or ??
Reason I ask is that, say, the customer can specify a cut in terms of inches. Then there are a integral number of inches in your standard lengths, so now the problem is an integer problem.
======
@Ozo,
The author clarified in a post that there are only a finite set of standard pipes available in any given day, so our results are invalid if, for example, there are only 50 pipes of each standard length.
The author also clarified that the lengths of the pipes available on any day may also include non-standard lengths as a result of left-overs from the previous day.
So, the general problem is, given a set of pipes available {Ni, Li} (i.e., there are Ni standard pipes of length Li), and given the customer orders, what are the cuts to minimize waste?
But for this question, we can simplify the requirements for only 3 standard pipes; L={20,40,60}, and Ni and the customer orders are the inputs to the algorithm.
If there are many different non-standard lengths as a result of left-overs, or if the cut resolution gets small, it becomes less efficient, and you may want to use a different method.
0
Winston SmithDeveloperAuthor Commented:
Talked with the shop to get the final word on questions I now have.
The standard lengths of 20, 40 and 60 can be seen as unlimited. Stock will be brought in as per the needed lengths specified by the program.
Leftovers will not need to be accounted for, the unused portions of steel are used in other areas and need not be factored in. They want to have the best use of the steel they are cutting but waste is re-used on a daily basis.
cuts can go down to the 1/8th of an inch. I am not sure if it would be easier to do this in millimeters and then convert?
I didn't see your last post as I was writing this post.
>> cuts can go down to the 1/8th of an inch. I am not sure if it would be easier to do this in millimeters and then convert?
It looks like you have a solution from ozo which solves the unlimited availability scenario. You just change these two lines:
@lengths=(20,40,60);
@clients=([5*12,22],[3*8,43],[2*20,33]);
Later, I'll compare my heuristic approach against this perl script and see if I can get the right answer.
If you provide one or two more realistic orders, I'll give it a try. (I assume that your OP was made simpler than the usual case.)
I think I figured out how to do this using a linear algebra approach (with constraints ==> LP solution) as opposed to dynamic programming (so I think it should in general run much faster). It would take time, so if the perl is good for you, then by all means, go for it). Good luck. If it does work out, then maybe I'll commercialize it if it runs very fast.
As with a number of NP problems, often some practical applications are not that time-consuming to run.
>> cuts can go down to the 1/8th of an inch. I am not sure if it would be easier to do this in millimeters and then convert?
The integral issue comes up if a specific order length could be partially met and this is not the case. Since you have to pick an integral number of cuts of a specific order requirement, the integral issue for LP is being met.
0
Winston SmithDeveloperAuthor Commented:
The perl is very fuzzy to me on the way it runs. Would you have an example of your new approach in a language such as C# or C etc.
>> The perl is very fuzzy to me on the way it runs.
So, its only very fuzzy - that's not too bad. At first glance, it looks like a weather whiteout to me.
>> Would you have an example of your new approach in a language such as C# or C etc
>> It would take time
I have formulations jotted down in terms of matrices, vectors, and constraints. But before posting, I would have to verify its correctness, and compare results with the perl script (and I'd modify the perl script to print out the waste, as soon as I learn about perl). I did this for an unlimited supply of standard lengths, as you clarified; but I don't see why I couldn't add, say, another constraint to have a limited supply, of say, 50 pipes of each standard length.
Since you are looking for functionality, then if you modify:
@lengths=(20,40,60);
@clients=([5*12,22],[3*8,43],[2*20,33]);
and keep coming up with less waste than that produced on the shop floor, then you have an answer.
Given some of the constructs used in this particular perl, I would not attempt to convert to C since it is using the map container. But if you need to convert this to C# or C++ in order to integrate it into another program (and, you can integrate without converting), then you can close this question, and ask a related question to specifically ask for help in converting the perl to C# or C++ (or on how to integrate the perl into a C# program).
0
Winston SmithDeveloperAuthor Commented:
Thanks for the help everyone!! This site and its members rock again! I will take the advice and post a new question on converting the Perl script to C#.
Cheers and thank again
0
Question has a verified solution.
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
So, unfortunately, there is no efficient algorithm out there which will give you the optimal solution. (If you happen to write one, you win $1,000,000 http://www.claymath.org/millennium/ so don't try unless you have a few years of free time and an I.Q. > 150 because that offer's been out there quite some time)
So, that said, your options are:
1. Write an algorithm to try most of the possible combinations.
2. Write an algorithm that will run faster, but won't guarantee the best.