# Minimize the pipe usage.

This is a problem/brain teaser (my dad asked it as a problem which he encountered earlier from his work).

You have to create a set of 4m and 4.75m pipes from 6m pipes. You can also join/weld two pipes to create a 4m/4.75m pipe (but, there should be only one joint). For example, 2+2 will work, but 1+1+2 will not (because it has 3 joints).

We want to create 108 (let's round it to 100) 4m and 4.75m pipes each. How many do you need to buy the 6m pipes to minimize the wastage?

I tried this approach: Cut two 4m pipes from two 6m pipes. We get 2+2m pipes left. Then we cut 2.75+2.75m pipes from a 6m pipe. Then we can join the 2m and 2.75m to get a 4.75m pipe. Overall wastage would be 0.6m per 2 pieces of 4m and 4.75m pipes. This is a lot of wastage. Is there any other optimal solution to this problem?

My brother also told me that this might be a linear optimization problem (don't know much about that).

• Read "Model Building in Mathematical Programming" by H. Paul Williams wiley.com/en-us/… . Then you should be able to figure out how to formulate this as an integer integer linear programming problem, for which many free packages are available to solve. – Mark L. Stone Mar 24 at 11:21
• You might be interested in reading about the "cutting stock problem": en.wikipedia.org/wiki/Cutting_stock_problem – awkward Mar 24 at 12:32
• @MarkL.Stone So I guess we produce for each possible length $l$ of pipe a variable $x_l$. How do we prove that it's sufficient to let $l$ be millimeter/centimeter-accurate? (i.e. $l = 0.001$ to $l=4.750$) – Sudix Mar 24 at 13:25
• This should be solvable by a dynamic programming algorithm. – Trebor Mar 25 at 8:18
• @MaJoR21 Unless there's a trick I'm not seeing, the general problem (i.e. where we say, we want to produce $k_1$,$k_2$ pipes of length 4m, 4.75m) is most likely rather hard to solve. However, the specific case with $k_1 = k_2 = 108$ could have an "easy" solution (i.e. one which uses some special reasoning which can't be applied for the general problem). E.g. it might be possible to verificiate the optimal solution per trial and error (by showing that the total length of the leftovers is $<6m$). – Sudix Mar 25 at 17:19

Here's how you can create 24 pieces each of 4.75 and 4 meter pipes with no wastage.

Cut three pipes into 24 sections of 0.75m each.
For 32 pipes, cut them into 32 4m and 32 2m sections.

Join 24 4m sections with the 24 0.75m sections to get 24 4.75m pipes.
Use the 32 2m sections to get 16 4m pipes.
You now have 8 4m sections left over, which give you your remaining 8 4m pipes.

There is no wastage, since $$35\cdot 6=24\cdot(4+4.75)= 210$$ Now, you can apply the above four times to get 96 4m and 96 4.75m sections, using 140 pipes.

If you want 100 pieces of each kind, you now need 4 more of each kind. You can use the approach given in the original post to do this, with 1m total wastage, which is the best you can do since the pipes come in 6m units.

It's not entirely clear to me how you would find a good algorithm for the more general problem (given a set of desired pipe lengths, how many 6-meter pipes do you need to construct them in this way?).