On Fri, 18 Jul 2008 20:11:00 GMT, Grant Erwin
wrote:

Bob La Londe wrote:
"Joe Pfeiffer" wrote in message
...

Grant Erwin writes:

I have a problem which cannot be unique to me. I have to cut a whole
bunch of pieces of known length from several lengths of stock. What I
need is some
software which will run on a Windows box which can take as input the
piece lengths I need and also the material length (often 20') and tell
me how many
lengths of material I need to order and what size pieces to cut out
of each
piece of stock.


That's actually a variant on the "Knapsack Problem", which is one of
the standard problems we use to teach advanced algorithms. It turns
out that there are pathological cases for which no better solution
is known than just trying all the different possibilities and seeing
which one works best.


Kinda like calculating intersects. For some there is no exact answer,
just the level of precision you require?

I was going to order 15 lengths of 1x2x.120" rectangular stainless grade 304
tube. Then I got Marv Klotz's software, and found out I can get by with 13,
plus it gave me the exact cut list to give to the sawyer. Saved me over $300
just for asking!

Grant

I'm pleased to hear that it worked for you, Grant.

Regards, Marv

Home Shop Freeware - Tools for People Who Build Things
http://www.myvirtualnetwork.com/mklotz

Marv, I have an enhancement suggestion. As we all know, there is no such
thing as a zero-kerf cut. It is possible to manually add .025" or .035" or .050"
or .125" or .3125" to each part length, but it's painful. It would be so dang
handy to be able to just input the kerf in the data file ..

I'm very pleased with CUTS and plan to use it a lot!

Grant

On Sat, 19 Jul 2008 01:10:57 GMT, Grant Erwin
wrote:

Marv, I have an enhancement suggestion. As we all know, there is no such
thing as a zero-kerf cut. It is possible to manually add .025" or .035" or .050"
or .125" or .3125" to each part length, but it's painful. It would be so dang
handy to be able to just input the kerf in the data file ..

I'm very pleased with CUTS and plan to use it a lot!

Grant

Grant,

The reason CUTS doesn't provide for a kerf is that I wrote it to test
my concept for doing the problem and didn't want to deal with the
complication of the kerf.

Do me a favor. Set your problem up with REMNANT. It includes the
ability to specify a kerf width in its data file. It's intended to
accept unequal length remnants as input but it should work with a
collection of equal length pieces of stock as in your case.

Assuming it works, compare the answer you get with what you got with
CUTS. They should be similar. And it should run more quickly because
REMNANT uses the greedy algorithm while CUTS uses exhaustive search.

I'd do this check myself except I want to do it with your specific
data. None of these algorithms are perfect and results can vary
depending on the specific problem.

If what I suggest is too much work for you, email me your problem data
and I'll do the experiment on my own. My email is: mklotz at alum dot
mit dot edu.

Marv wrote:

On Sat, 19 Jul 2008 01:10:57 GMT, Grant Erwin
wrote:


Marv, I have an enhancement suggestion. As we all know, there is no such
thing as a zero-kerf cut. It is possible to manually add .025" or .035" or .050"
or .125" or .3125" to each part length, but it's painful. It would be so dang
handy to be able to just input the kerf in the data file ..

I'm very pleased with CUTS and plan to use it a lot!

Grant


Grant,

The reason CUTS doesn't provide for a kerf is that I wrote it to test
my concept for doing the problem and didn't want to deal with the
complication of the kerf.

Do me a favor. Set your problem up with REMNANT. It includes the
ability to specify a kerf width in its data file. It's intended to
accept unequal length remnants as input but it should work with a
collection of equal length pieces of stock as in your case.

Assuming it works, compare the answer you get with what you got with
CUTS. They should be similar. And it should run more quickly because
REMNANT uses the greedy algorithm while CUTS uses exhaustive search.

I'd do this check myself except I want to do it with your specific
data. None of these algorithms are perfect and results can vary
depending on the specific problem.

If what I suggest is too much work for you, email me your problem data
and I'll do the experiment on my own. My email is: mklotz at alum dot
mit dot edu.


REMNANT runs almost instantly on this set of data while CUTS takes about four
hours. The output is similar but not identical. It appears that REMNANT has
a small floating point issue somewhere - here is a line of its output:

Length 240 - 131, 102.5, 4.625, (0.15 kerf + 1.72499 drop = 1.87499 waste)

My calculator gets 1.725, not 1.72499. Also, it seems anomalous that when you
print out the part length you only give 2 decimal places (e.g. 4.63 not 4.625)
when below you print out five. I would rather see three decimal places in
the part length.

Here is my data if you want to play with it:

stock length: 240

2,131.00
2,127.00
2,124.00
2,120.00
2,117.00
2,113.00
2,102.50
2,100.00
2,98.50
2,96.00
2,54.50
2,50.50
2,46.00
2,43.50
2,42.00
2,39.50
6,16.625
2,16.625
2,10.625
2,4.625

Grant

On Sat, 19 Jul 2008 15:17:11 GMT, Grant Erwin
wrote:


REMNANT runs almost instantly on this set of data while CUTS takes about four
hours. The output is similar but not identical. It appears that REMNANT has
a small floating point issue somewhere - here is a line of its output:

Length 240 - 131, 102.5, 4.625, (0.15 kerf + 1.72499 drop = 1.87499 waste)

My calculator gets 1.725, not 1.72499. Also, it seems anomalous that when you
print out the part length you only give 2 decimal places (e.g. 4.63 not 4.625)
when below you print out five. I would rather see three decimal places in
the part length.

Here is my data if you want to play with it:

stock length: 240

2,131.00
2,127.00
2,124.00
2,120.00
2,117.00
2,113.00
2,102.50
2,100.00
2,98.50
2,96.00
2,54.50
2,50.50
2,46.00
2,43.50
2,42.00
2,39.50
6,16.625
2,16.625
2,10.625
2,4.625

Grant

The program is using the C language %g format which prints out all
non-zero digits. I need to do this since the program has no a priori
knowledge of the user's desired print out precision. Roundoff will
differ from one machine to another.

For instance, on my (XP) machine, your line...

Length 240 - 131, 102.5, 4.625, (0.15 kerf + 1.72499 drop = 1.87499
waste)

looks like...

Length 240 - 131, 102.5, 4.625, (0.45 kerf + 1.425 drop = 1.875 waste)

[BTW, I can't explain why yours says 0.15 + 1.425 and mine says 0.45 +
1.425. I downloaded and used the program from my web page so we're
both using the same code.]

although another line looks like...

Length 240 - 54.5, 54.5, 50.5, 50.5, 16.625, 10.625, (0.9 kerf +
1.85001 drop = 2.75001 waste)

The part lengths are printed with two decimals only to conserve space.
Internally, the program uses all the precision specified in the data
file.

Since REMNANT runs quickly and produces a thirteen stock length
solution, my experiment seems to be successful. I recommend that you
use it for future work.

I suggest that we discuss this further via email.

Regards, Marv

Home Shop Freeware - Tools for People Who Build Things
http://www.myvirtualnetwork.com/mklotz