Cutting Stock problem

http://en.wikipedia.org/wiki/Cutting_stock_problem

There is an example in this article. In summary, assume you have a bar 5600mm long. You must cut various sizes from the bar, ranging from 22 @ 1300mm up to 20 @ 2200mm.

The article states that there are 308 possible patterns. Is there a simple formula for calculating this (I dont believe that there is)?

I think this has to be iterated. For example, if 9 is the longest length, and 1 is the shortest length, my starting point would be :-

1,1,1,1,..... until you cant fit any more 1's in (ie 1,1)
now see if you can fit any others in (eg 1,1,2 or 1,1,3) and iterate (eg 1,1,3,3)
now replace the last 1 in the first solution with the next item (ie 2) so you now have 1,2 and iterate again (eg 1,2,2 or 1,2,3 etc etc)
and repeat until you have the maximum (probably 9,9,9,9,9,9,9 etc)

Is my theory correct? :) If it is, any suggestions as to how to program it :D

In the example:-

there are 13 lengths
the longest length 1 (2200mm) fits 2.54 times
the shortest length 13 (1380mm) fits in 4.05 times

So the maximum number of pieces is 4, and the minimum is 2. Even though we know length 1 will not fit more than twice, would the simplest solution be to calculate the lengths for the following combinations :-

13 x 13 (2 fits)
13 x 13 x 13 (3 fits)
13 x 13 x 13 x 13 (4 fits)

Your first algorithm would work if you did it right, though it's a bit indirect. I can see a couple of algorithms. The first is direct iteration that your second post hints heavily at. It would loop through the possible pattern lengths (between 2 and 4 in your example, which is easily calculated), generating patterns effectively by brute force search. One thing, though--sometimes you'd have more left-over space that could fit another pattern element. For instance, in your example you might try the pattern [1380, 1380], which has 2840 space left over. Since you could fit an extra element in this pattern, you may as well ignore the pattern entirely.

Suppose the minimum pattern length is m, maximum is M [m=2, M=4 in your example]. Suppose there are k possible pattern elements [k=13 above]. Your iteration would take
[sum from i = m to M of k^i] times through loops. This could get pretty bad pretty quickly, though since this problem is NP-Complete, there's not much you'll be able to do anyway for large problem sizes.

I can see a possible improvement on this naive algorithm through recursion. Pick the first element of your pattern, and recursively generate a list of all possible completions to this pattern. Merge them, and continue iterating through each first element. The improvement here is that in each recursive call, you would decrease the total roll length (since some is used up), which decreases m and M as you loop, sometimes by more than 1 per iteration. Depending on your application, this could either generate orders of magnitude in improvement, or add more overhead probably hurting overall performance. I would imagine if the initial m << M, the improvement would be gigantic. In pseudocode...

Code:

---

function GenPatterns(Array PatternElements, RollLength)
    For element in PatternElements
        patterns = GenPatterns(PatternElements, RollLength - element)
        Add element as the first element of each pattern in patterns
        Add patterns to GenPatterns

    return GenPatterns

---

Thanks jemidiah :)

I think I have found a solution by approaching it from the opposite direction. Assuming 9 is the shortest length, and 1 is the longest length :-

9,9,9,9 - fits
9,9,9,8 - fits
9,9,9,7 - doesnt fit (so ignore everything 6 to 1)
9,9,8,8 - fits
9,9,8,7 - doesnt fit (so ignore etc)
9,9,7,7 - doesnt fit either, so ignore 6,6 to 1,1
9,8,8,8 etc etc

and then when there are no more available options of 4 elements, remove one element and begin the iteration again (eg 9,9,9)

Seems to work quite well - although I end up with 294 possible options for the Wikipedia example when they state 308 :confused:

Sure, that should work. You're basically describing the first method I talked about, using direct iteration. I get 1 length-4 pattern, 203 length-3 patterns, 91 length-2 patterns, and 13 length-1 patterns. The length-1 patterns should all be useless in this particular case, but in the general case they might not be. Adding these up, I have 1+203+91+13 = 308 patterns, as the Wikipedia article says. Taking out the length-1 patterns, I have 295 patterns, which is just 1 off from yours. Perhaps you were only counting length-2 and length-3 patterns on accident, or perhaps your counting is just off by 1.

InertiaM

did you manage to solve this?
I am looking to do the same in Access.
Can you post your solution?
I am happy to make a contribution!