# Pipes, length and numbers

• Jan 15th 2009, 12:22 AM
maxald
Pipes, length and numbers
Hello! Since I don't really know the solution of this problem this might be posted in the wrong forum, sorry if that's the case.

My problem is this; I have pipes in different lengths, let's say 2, 5 and 8 meters each. Now I am going to connect x pipes of each length so that I get a total length of 28 meters. I want to do this in a way that I get minimum overhead, second I want to use as many long pipes as possible.

The answer of my example is easy to calculate "in head", 3*8 and 2*2 pipes, but if there are 9 different pipe lengths and a total length of 155337 meters?

Can someone please help with an algoritm that I can use to calculate different pipes and lengths and an easy-to-understand explanation how it works? Thanks in advance!
• Jan 15th 2009, 04:22 AM
HallsofIvy
Quote:

Originally Posted by maxald
Hello! Since I don't really know the solution of this problem this might be posted in the wrong forum, sorry if that's the case.

My problem is this; I have pipes in different lengths, let's say 2, 5 and 8 meters each. Now I am going to connect x pipes of each length so that I get a total length of 28 meters. I want to do this in a way that I get minimum overhead, second I want to use as many long pipes as possible.

The answer of my example is easy to calculate "in head", 3*8 and 2*2 pipes, but if there are 9 different pipe lengths and a total length of 155337 meters?

Can someone please help with an algoritm that I can use to calculate different pipes and lengths and an easy-to-understand explanation how it works? Thanks in advance!

This is an example of a "Diophantine equation" in which all coefficients and solutions are integers. It is relatively easy to solve Diophantine equations with two unknowns, much harder to solve for 9 unknowns!
• Jan 15th 2009, 04:42 AM
maxald

I have written a small program in Excel (VBA) that test all possible combinations, one in a time. But when there are 4 or more pipe lengths unfortunately it gets really, really slow (and there will be nestled loops in absurdum).

What about four or five pipe lengths? Is this calculateble:

\$\displaystyle
2a + 5b + 10c + 25d = 167253
\$

... where 2, 5, 10 and 25 is pipe lengths and I want as many "d" and as few "a" as possible?
• Jan 15th 2009, 04:59 AM
Constatine11
Quote:

Originally Posted by HallsofIvy
This is an example of a "Diophantine equation" in which all coefficients and solutions are integers. It is relatively easy to solve Diophantine equations with two unknowns, much harder to solve for 9 unknowns!

More like a combinatorial optimisation problem (depending on what "minimum overhead" means, I assume it means minimum waste when a pipe is cut to give the exact length, but it is vague).

.
• Jan 15th 2009, 05:01 AM
Constatine11
Quote:

Originally Posted by maxald
Hello! Since I don't really know the solution of this problem this might be posted in the wrong forum, sorry if that's the case.

My problem is this; I have pipes in different lengths, let's say 2, 5 and 8 meters each. Now I am going to connect x pipes of each length so that I get a total length of 28 meters. I want to do this in a way that I get minimum overhead, second I want to use as many long pipes as possible.

The answer of my example is easy to calculate "in head", 3*8 and 2*2 pipes, but if there are 9 different pipe lengths and a total length of 155337 meters?

Can someone please help with an algoritm that I can use to calculate different pipes and lengths and an easy-to-understand explanation how it works? Thanks in advance!

If you are allowed to cut one of the pipes a greedy algorithm may perform adequately, that is you always choose the next pipe to be the longest available, and you may have to cut the last pipe to give the exact length.

.
• Jan 15th 2009, 05:06 AM
maxald
Quote:

Originally Posted by Constatine11
More like a combinatorial optimisation problem (depending on what "minimum overhead" means (I assume it means minimum waste when a pipe is cut to give the exact length, but it is vague).
.

Yes, that's correct.
• Jan 15th 2009, 05:10 AM
maxald
Quote:

Originally Posted by Constatine11
If you are allowed to cut one of the pipes a greedy algorithm may perform adequately, that is you always choose the next pipe to be the longest available, and you may have to cut the last pipe to give the exact length.
.

Yes, that would do... but its more out of curiosity if it is possible to find the optimal combination of pipes in different lengths. (Smirk)
• Jan 15th 2009, 10:57 PM
Constatine11
Quote:

Originally Posted by maxald
Yes, that would do... but its more out of curiosity if it is possible to find the optimal combination of pipes in different lengths. (Smirk)

It's a knap-sack like problem, a solution can in principle be found by exhastive search. But the general problem is NP-complete (which for all practical purposes means that the required computaional time for all known algorithms grows exponentially with problem size, and so only small problems can be solved)

Having said that, of course if the available pipe lengths satisfy some convienient conditions which in practice often occur(for example if a is the shortest pipe length and the others are 2a, 4a, 8a) the greedy algorithm will be optimal.

.
• Jan 16th 2009, 12:38 AM
maxald
Quote:

Originally Posted by Constatine11
Having said that, of course if the available pipe lengths satisfy some convienient conditions (for example if a is the shortest pipe length and the others are 2a, 4a, 8a) the greedy algorithm will be optimal.

Unfortunately, that's not the case. Well, seems like this problem is more tricky than I excpected, still you ppl have learn med what a "Diophantine equation" is and for that I thank you - very intresting! I didn't like math at all back in school, but now when I got older I start to enjoy math and it's beauty... hopefully it's never to late to learn, though I probably won't be an expert in this subject. (Wink)