Thread: 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!

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!

Thanks for reply!

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:



... where 2, 5, 10 and 25 is pipe lengths and I want as many "d" and as few "a" as possible?

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).

.

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.

.

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.

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.

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.

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.

.

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.

Thanks for your time!