Algorithm to find optimal cuts of pipe 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?
 A: 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$.
