3
$\begingroup$

This is an attempt to extend an idea from Computer Science.. the dynamic programming based solution of the rod cutting problem (given a rod of an integral length and an array of prices for each integral value of the length, find the optimal cuts that maximize profit). Thinking about it made me wonder.. what if we were not constrained to cut the rod at integral values, but could cut it any where we liked (fractional lengths are possible). Further, lets say that instead of a table of prices corresponding to the integral lengths, we are given a continuous (monotonically increasing, tapering) function that represents the value of the rod at different lengths. For example, for a rod of length 1, the value function might be given by the CDF of a beta distribution. Now, we want to find the number of cuts that we should make and at what values to optimize the total value. Has any one heard of such a problem (I couldn't find any thing online)?

$\endgroup$
1
4
$\begingroup$

If the function is monotonically increasing and tapering (i.e., positive derivative, negative second derivative), then the optimal solution is to make infinitely many cuts and see infinitesimally small pieces of the rod.

Of course, if you assume that the price function is monotonically increasing with positive second derivatives, your optimal solution is to sell a single piece.

Finally, if you assume a price function that is monotonically increasing with zero second derivative (i.e., a linear function), then any subdivision is optimal.

What this shows is that the integer constraints of the original problem really are an essential part of the problem and that removing them let the problem degenerate into one that has either a trivial solution (convex cost function) or no solution (concave cost function, where there is no maximal revenue with finitely many cuts, just a supremum). Of course, you could assume that the cost function is both convex and concave in parts of its domain, but in that case you likely have a problem that is no longer convex and that may have multiple local optima.

$\endgroup$
2
  • $\begingroup$ Thanks. So if you convert the continuous problem into the discrete problem, your observations probably still hold. If the price array is read off from a convex function, use the full rod and if it is read off from a concave function, split among as many parts as possible (length 1 each). I imagine the interesting cases of the dynamic programming version must arise when the price array can be considered to have been read off from a part convex and part concave function? $\endgroup$ Aug 10 '13 at 19:50
  • $\begingroup$ I suppose this is true. If you want to make it more practical -- there is typically a certain maximal demand for objects of given length. I.e., if your rod has length 100, you may not be able to sell more than 10 items of each length, including the ones of length 1 that bring you the most profit. $\endgroup$ Aug 10 '13 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.