1

I need to make a program that calculates the optimal way to cut pieces of pipe to what a customer wants.

My advanced math skills are bad but I know this is the cutting stock problem. My first problem is that I don't really understand much on that wikipedia page. The other thing is that the page describes solving this problem when all the pieces you have in inventory are the same size. How do you optimize when you have varying sizes in inventory and you want to use up the small ones first?

For example say we have pieces of this length in inventory: 2', 18'

And a customer wants these lengths: 1', 12'

My understanding of the wikiepdia page is that it is trying to reduce the left over(waste) which would mean that you would take the requested 1', 12' out of the 18' to have a left over of 5'.

The optimal solution I would want is to take 1' out of the 2' and 12' out of the 18' even though the total left over is 7' because we want to keep pieces as long as possible.

I am having a hard time describing this. Any general guidance on this would be great.

Mike
  • 133

2 Answers2

1

I assume you are trying to maximize the length of the shortest resulting pipe, breaking ties by going to the second shortest pipe, third shortest, etc. Luckily this is a much easier problem than the cutting stock problem, and in fact can be solved by a greedy algorithm. All you need to do is take the longest cut from the longest pipe remaining. More formally, let $P$ be the set of pipes and $C$ the set of cuts, and perform the following:

  1. Remove the largest cut $c$ from $C$.
  2. Cut the largest pipe $p$ in $P$, and replace $p$ with $p-c$ in $P$.
  3. If $C$ is not empty, go to step 1.

Proof of correctness: Clearly this is correct if $C$ consists of just $1$ cut. Assume it is correct for all sets of $n$ cuts, and let $C$ consist of $n+1$ cuts. Let $P'$ be the optimal set of pipes after all cuts have been performed, and $P''$ be the same set of pipes, but before the last cut. By assumption, by the time the algorithm reaches its last iteration we will have $P=P''$. But since it is optimal to cut the largest pipe any time we have only one cut to make, the algorithm must produce exactly $P'$ after the last iteration. Thus by induction the algorithm is correct.

Alex Becker
  • 60,569
  • I am not trying to maximize the length of the shortest resulting pipe. In fact I want to leave my largest pipes alone when possible. One piece of 20' pipe is more valuable than 2 pieces of 10' pipe. I am sorry I am having a hard time conveying exactly what I want. That is probably part of my problem of getting to a solution. – Mike Mar 26 '13 at 18:43
  • 1
    @Mike Well it's impossible to design an optimization algorithm without knowing exactly what to optimize, so you'll have to come up with a precise notion. Perhaps you have some monotonic increasing function $f$ of the length of a pipe (the value), and you want to maximize the sum of $f(p)$ over all pipes $p$? – Alex Becker Mar 26 '13 at 18:46
  • Not to sure about how a monotonic function works but I think what you were saying is what I want. The bigger a pipe is the more valuable and so I want to maximize the lengths of pipe left after removing the requested cuts. – Mike Mar 26 '13 at 18:50
  • 1
    @Mike But "the lengths of the pipe left after removing the requested cuts" can't be maximized, since it's a set of numbers rather than just one. One thing to maximize is the sum of these lengths, but you're already ruled that out, as well as the shortest length. It would be very helpful if you know what the value of a pipe of length $x$ is (say, $x^2$ for example). – Alex Becker Mar 26 '13 at 18:53
  • 1
    @Mike, based on your comments, it sounds like you could use a greedy algorithm that operates on the heuristic to select the smallest pipe in your inventory exceeding the customer's smallest length of pipe as the one to cut from. This would enable you to work through the scraps first and then move on to the larger stock as a last resort. – GEL Mar 26 '13 at 19:01
  • The problem is that if a group of pieces that a customer wants can add up very close to one of the bigger pieces in inventory then that should be the better result than to use a little bit out of several pieces and leave a lot of little pieces left over. – Mike Mar 26 '13 at 19:05
  • It seems like that the comment of having a pipe of length x be worth x squared might work. This would mean that I want to maximize the sum of the squares of the lengths that are left in inventory after cutting. How would I go about that? – Mike Mar 26 '13 at 19:10
  • 1
    @Mike But that's probably also wrong. Is a 40ft pipe really worth as much as 16 10ft pipes? – Alex Becker Mar 26 '13 at 19:11
  • Good point. This is going to take a lot more thought on my part. – Mike Mar 26 '13 at 19:14
  • So if I do come up with the value of the length what would be the next step. Suppose that x squared is correct. Is there an efficient way to solve this problem? – Mike Mar 26 '13 at 19:57
  • 1
    @Mike It depends on the nature of the function. If it has positive second derivative (such as $x^2$), then the greedy algorithm which uses the shortest possible length of pipe at every step is correct. – Alex Becker Mar 26 '13 at 20:02
  • I don't think that works right but I think at this point I should make a new question which I can hopefully make much clearer thanks to your help. – Mike Mar 26 '13 at 20:17
0

@mike

I'll try

  1. Let P' be the set of all pipes longer than c
  2. Cut the shortest pipe in P'.
  3. Go to step 1

To avoid too much scrap

user452027
  • 1