Results 1 to 9 of 9

Math Help - Pipes, length and numbers

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    5

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,713
    Thanks
    1472
    Quote Originally Posted by maxald View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    5
    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:

     <br />
2a + 5b + 10c + 25d = 167253<br />

    ... where 2, 5, 10 and 25 is pipe lengths and I want as many "d" and as few "a" as possible?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by HallsofIvy View Post
    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).

    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by maxald View Post
    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.

    .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jan 2009
    Posts
    5
    Quote Originally Posted by Constatine11 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jan 2009
    Posts
    5
    Quote Originally Posted by Constatine11 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2006
    Posts
    244
    Quote Originally Posted by maxald View Post
    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.

    .
    Last edited by Constatine11; January 16th 2009 at 01:00 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jan 2009
    Posts
    5
    Quote Originally Posted by Constatine11 View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. contact area of two touching pipes
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 23rd 2010, 09:44 PM
  2. Length needed from a known length and angle
    Posted in the Geometry Forum
    Replies: 4
    Last Post: July 21st 2009, 06:17 AM
  3. Pipes Working Individually
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 09:34 PM
  4. arc length and parameterized curve length
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 5th 2008, 02:33 AM
  5. pipes and work done
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: December 13th 2006, 06:44 PM

Search Tags


/mathhelpforum @mathhelpforum