I have a woodworking project that calls for various lengths of lumber 
in various quantities (e.g. (4) 2x4x34", (4) 2x4x32, (1) 2x4x33, and 
(4) 2x4x27.25" pieces).  I have some available lumber, and I can tell 
that I will need to purchase more. For example, I own (1) 2x4x53", 
(1) 2x4x66", and (1)2x4x96" pieces - certainly not enough.

I want to maximize the use of my existing lumber, and buy the least 
amount of additional lumber that will result in minimal waste.
  Eventually, I would like to build a computer calculator (I work 
with various development languages) for my own use with other 
projects.

[Difficulty]
Intuitively, it seems that I should be able to calculate the optimum 
ways to cut the lumber, perhaps using an iterative calculation where 
I compare the results.  However, the permeations seem to grow quickly 
beyond manageability. I have considered arrays, and algebra seems to 
be applicable, but I have not been able to "see" the solution.

---

Request for Question Clarification by smudgy-ga on 18 Jun 2004 10:20 PDT

Hi cmaury,

Nice problem. This is close to a classic "bin packing" problem, and
the sad truth is that there is no efficient way to come up with an
ideal solution to an arbitrary bin packing problem. There do exist
algorithms for coming up with "good" (though not necessarily optimal)
solutions to this problem. Would such an algorithm be of any interest
to you as an answer?

Thanks,
smudgy.

---

Clarification of Question by cmaury-ga on 18 Jun 2004 10:28 PDT

At the risk of sounding ignorant, would the "bin packing" problem be a
3 dimensional problem verses a single dimensional problem I have here?
 My problem is that I can cut a board in various, finite combinations.
 Furthermore, I can purchase finite quantities of standard lengths
(96", 120", 144").  The worst solution to any variation of my problem
would be to buy 1 piece of lumber for each cut I require, assuming my
required piece is <= length of purchased piece.  So, if I need 12
"parts", I could simply buy 12 pieces of lumber <= length of each
required "part".  Good for the lumber store, bad for me! LOL.

---

Request for Question Clarification by smudgy-ga on 18 Jun 2004 10:39 PDT

Bin packing problems are generally phrased something like, "We have
several bins, each of which can hold various amounts of weight. If we
have a bunch of discrete items each of which has a different weight,
what are the fewest number of bins we need in order to bin all the
items?" This is basically equivalent to your problem, with bins
replaced by stock lumber, items replaced by cut lumber, and weight
replaced with length. It's still essentially a one-dimensional problem
in the sense you're thinking of, inasmuch as the bins are only
measured in one dimension.  In fact, "bin packing" style problems are
often framed as lumber-cutting problems in textbooks. Does this sound
like it might be helpful?

---

Clarification of Question by cmaury-ga on 18 Jun 2004 10:49 PDT

Sure, let's give it a shot!

Hi cmaury,

I hope you find the following answer satisfying. If not, please
request a clarification before rating and I will do my best to explain
further.

There are several different heuristics for solving the bin-packing (or
in this case, lumber-cutting) problem, and while none of them can
guarantee optimal efficiency, there are several that can get us
reasonably close to an ideal solution.

The algormithm I will provide is the "first-fit-decreasing" algorithm,
which is well-suited to situations, such as this one, where you know
all the lengths that you will need to cut the lumber into beforehand.
The basic algorithm goes something like this.

0: Usually in this algorithm every "bin" (or piece of lumber) is the
same size. This condition is not a huge hurdle to overcome and I don't
think the fact that your already-available pieces of lumber are
different sizes will affect the outcome too much. But for the purposes
of introducing the algorithm, assume that you have a bunch of stock
lumber, all of the same length.

1: First, make a list of all the lengths that the lumber needs to be
cut into, from largest to smallest.

2: Now, on the first piece of stock lumber, mark off the length of the
first piece you need to cut.

3: Look at the second length on the list. Can this be cut out of the
remainder of the first piece of stock? If so, then mark that distance
off too. If not, mark this distance off on a second piece of stock
lumber.

4: Repeat this process for every length in your list. First see if it
fits in the remainder of the first piece of stock, then the second,
etc. When you get to a piece of stock that has enough space to "fit"
the new cut, mark off that new cut. When you are done with the list,
you will have marked off two or three or four cuts on most pieces of
lumber, and in such a way that short cuts are paired with long cuts
relatively efficiently.


An example:

Let's say we have a bunch of boards that are 15 inches long.

We need to cut the following lengths in inches: 10, 8, 8, 7, 7, 7, 5, 5, 4, 2, 2, 2

On the first board, we mark off 10 inches.
We can't mark off a further 8 inches on the first board, so we mark it
on the second board.
Likewise, we can't mark off 8 more inches on the first or second
board, so we mark it off on a third board.
We can't mark off a further 7 inches on the first board, but we -can-
on the second board.

etc.

At the end of the process, this is how our boards are being cut up:

10+5
8+7
8+7
7+5+2
4+2+2

In this case, we have one inch of unused lumber on the second to last
piece of stock, and seven inches of unused lumber on the last piece of
stock. However, we can be relatively assured that we are not using
many more boards than is strictly necessary to use.

In your case, I feel that the algorithm can be modified simply by
letting the first three pieces of lumber be of the size that you have
on hand, and letting the remaining pieces of lumber be of some
arbitrary stock length that you pick.

I hope you find this answer satisfying! If you are not satisfied or if
you are having trouble understanding the algorithm, please request a
clarification and I will do my best to resolve any issues.

Thanks,
smudgy.


Here is a web page describing a few different bin-packing algorithms:
http://www.york.cuny.edu/~malk/tidbits/tidbit-bin-packing.html

and another one describing the bin-packing problem in general:
http://mathworld.wolfram.com/Bin-PackingProblem.html

and a couple with java-based bin packing solvers:
http://www.cs.ucf.edu/courses/cop3930H.01/JavaExamples/binpack.BinPack.html
http://www1.minn.net/~dchristo/BinPacker/BinPacker.html
http://www.research.compaq.com/SRC/JCAT/jdk10/binpacking/index.html
(This last is a really nice animation showing the -exact- method that
the algorithm described above uses. Check the box marked "first fit
decreasing" before running the demo. Unfortunately you can't enter
your own object sizes in this demo.)

This page has some computer code for a bin-packing computer program.
I'm not sure what language it's in... visual basic? You might be able
to glean some information from the program if you're planning to write
your own software:
http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm


Search method:
Google search <bin packing>
Google search <bin packing java>

Very good information provided.

On a side note, it is amazing to me that as sophisticated as we humans
are (Mars Landers, Men on the Moon, Great Pyramids, etc.), we haven’t
been able to come up with a definitive method to determine the most
efficient way to cut stock when building (or cutting or packing!)