2

I have varying lengths of pipe in inventory. When a customer requests various lengths I want to find the optimal way of cutting what I have in inventory. I need to make a program that does this.

This optimization needs to consider that longer lengths are exponentially more valuable than shorter lengths. Lets say a pipe of length x has a value of x1.12

How would I determine the optimal way to cut what is in inventory to get what the customer requested while maximizing the value of what is left in inventory? Can this be done efficiently without the problem growing exponentially with the number of pieces of pipe involved?

Mike
  • 133
  • I know you think otherwise, but the greedy algorithm which selects the shortest useable pipe is optimal. Consider the case where you have ten pipes of length $2$ and one of length $15$, and you have to make $10$ cuts of length $1.5$. If you cut the pipes of length $2$ the remaining value of the pipes is $10\cdot .5^{1.12}+15^{1.12}\approx 25.36$ while if you cut the pipe of length $15$ the value of the remaining pipes is $10\cdot 2^{1.12}\approx 21.73$. – Alex Becker Mar 27 '13 at 15:58
  • But if I have a piece of length 5 and a piece of length 10 in inventory and the customer requests a piece of length 3 and a piece of length 7 wouldn't this method leave me with a piece of length 2 and a piece of length 3 instead of leaving me one length 5. – Mike Mar 27 '13 at 16:06
  • Oh, added detail I forgot: you start with the largest cut. So you start by cutting the shortest pipe which has length at least $7$, and then the shortest pipe after that cut has been made with length at least $3$. Sorry about that. – Alex Becker Mar 27 '13 at 16:13
  • I see, that sounds very promising. I'll test it out in a little bit. Make that an answer so that if it works out I can mark it as a solution. (I guess I made this second question for nothing.) – Mike Mar 27 '13 at 16:17
  • Turns out I was wrong. Consider pipes of length $4,5$ and cuts of length $2,3$. It seems like a greedy solution is not possible. Perhaps a dynamic programming solution exists. – Alex Becker Mar 27 '13 at 17:21

1 Answers1

1

This turns out to be a very hard problem, and unless $P=NP$ there is no algorithm which runs in polynomial time as a function of the number of pipes and cuts. In fact, no such algorithm exists even if you only have $2$ pipes! The reason is because we can reduce the subset sum problem, a known NP-complete problem, to a special case of this with just $2$ pipes:

Suppose you have a set $c_1,\ldots,c_n$ of positive integers, with total sum $C$, and want to know whether some subset of them sums to $S$. If you have two pipes, one of length $S$ and the other of length $C+1$, then you can make cuts $c_1,\ldots,c_n$ with a leftover value of at least $(S+1)^{1.12}$ iff you can use all of the pipe of length $S$, that is iff there is some subset of $c_1,\ldots,c_n$ which sums to $S$.

There's a bit of hope left, as subset sum is only weakly NP-complete, so there are efficient algorithms when the size of the integers (i.e. the cuts) are small, which translate to efficient approximation algorithms regardless of size. However, this problem is a vast generalization of subset sum, so may be strongly NP-complete. I'll give the question some more thought.

Edit: This hope is also dashed, as the 3-partition problem, a strongly NP-complete problem, can be reduced to this:

Suppose you have a set of $3m$ positive integers $c_1,\ldots,c_{3m}$ which sum to $Cm$. If you have $m$ pipes of length $C$ and one of length $Cm$, then you can make cuts $c_1,\ldots,c_{3m}$ with leftover value of at least $(Cm)^{1.12}$ iff you can use all of the $m$ pipes of length $C$, i.e. iff you can partition $c_1,\ldots,c_{3m}$ in $m$ $3$-tuples which each sum to $C$.

Community
  • 1
Alex Becker
  • 60,569
  • Do you know if its possible to easily find what the value will be of whats left in inventory for the optimal combination of cuts without actually finding the optimal combination of cuts? I am guessing this isn't possible. – Mike Mar 28 '13 at 12:26
  • @Mike No, the reductions here work even if you just know the value, not the optimal combination. In general finding the value is just as hard as finding the optimal combination for any problem like this. – Alex Becker Mar 28 '13 at 13:28