1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ @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$? $\endgroup$ Mar 26 '13 at 18:46
  • 1
    $\begingroup$ @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). $\endgroup$ Mar 26 '13 at 18:53
  • 1
    $\begingroup$ @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. $\endgroup$
    – GEL
    Mar 26 '13 at 19:01
  • 1
    $\begingroup$ @Mike But that's probably also wrong. Is a 40ft pipe really worth as much as 16 10ft pipes? $\endgroup$ Mar 26 '13 at 19:11
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 26 '13 at 20:02
0
$\begingroup$

@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

$\endgroup$

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.