Robert Bonomi wrote:

A pretty good answer -- a couple more notes for anyone who might face
this commercially -- and may want to explore saving some money. There
are solutions for the right circumstances.

In article ,
Rob V wrote:

Doh! Major brain fart - Tnx for the help.
Nothing like over thinking things.

(BTW - the reason for the brain fart is when I do poker tables - to get the
most use of 1 sheet of ply - I have to nest 2 archs together (think about
facing C's) so I can get the rail and the mounting peice from 1 piece of
ply.)
So for what ever reason I had the nesting thing on my mind.

But that still would be a kewl feature to have in cad.


"kewl feature", yes. "practical", no, unfortunately. That particular
problem has been studied _a_lot_. There aren't even any algorithms known
(short of try every thing in every possible arrangement), to find a best-fit
solution.

There are -- it's a logistics problem -- packing -- it's a little worse
in 3D though. Tiling algorithms have been done -- in Lisp -- even for
the "old" AutoCad. Sometimes they are "good enough".


Genetic Search (GSA), branch and bound etc. Used in scheduling and
optimization theory -- are some of the algorithms used to find a best
fit in this situation.

The geometric part of the problem can make it a challenge because you
have to consider orientation -- not just pure numbers -- which is what
IMHO the knapsack problem is (usually) all about -- just integer numbers
(fixed quantities).

However, Calling that geometric problem a variation of the (relatively)
straightforward Knapsack Problem is like calling the math behind
relativity a variation of simple calculus. :-) (Just a little joke there.)

Most of these problems end up with someone spotting a way to do them --
usually it's serendipity -- then we call it heuristics -- cause it
sounds important. Others say -- "rule of thumb". :-)

I have seen/evaluated some Heuristic systems -- when people called the
optimizers I believe they were indulging in self-flattery. So if you
have a need and someone touts a systems -- you might want to ask "how"
it optimizes. In one system I evaluated the programmer did not know that
he had a "Heuristic" system -- he actually believed that it found the
optimum answer for packing randomly sized cartons. He was given the
algorithm by someone who had a high school education -- but he never
checked -- just did his job. When I showed him the "real arithmetic" he
was unbelieving to say the least -- until I ran an analysis of the
answers the system provided. The they found a better cover up so you
couldn't tell as easily... Goes to show -- there's always an answer. :-)

So if you have a problem to solve and you buy a solution -- and they do
exist -- ask some questions.


If you want to play with a 'trivial' illustration of the problem, there is
a game called "pentominos" twelve pieces, made by combining 5 1x1 squares.
thus, the total 'area' of those pieces is 60 square units. They *can* be
assembled into a rectangle that is 3x20. Care to guess how many possible
arrangements have to be checked to find the solutions (yes, there is _more_
than_one_solution_)?



And _that_ is with only four possible orientations of each piece allowed.

Add in 'irregular' shapes, and possible 'non-orthagonal' orientations, and
the 'magnitude' of the problem increases immeasurably.

It's just more "fun" -- that's all.

A 'closely related' matter, in the realm of pure math, is known as the
'knapsack problem'.

Sort of. Knapsack is NP Complete (CRC page 28-7, Reducibility and
Completeness,1999 edition) I believe for Integer solutions. There are
approximation solutions for many types of this problem.

In other words, if some one is in a business where this problem is faced
often, hire someone with a bent for optimization theory, and see if you
can find a solution for your _particular_ problem. You can save a lot of
money if you make a lot of parts. If you make only a few, you will spend
more money finding the best solution than wasting some material -- most
of the time. ymmv


"big-money" commercial [cryptography optimisation and logisitcs maybe :-) ]
systems have been
built around the difficulty of finding a 'perfect' fit for a bunch of
pieces into a larger container, *given*that*you*know* that a perfect fit
_is_ possible.

It can be easier if you know -- but you don't even have to know to write
a program to find better fits. See GSA, branch and bound etc...

Trying to find a 'best' (not perfect) fit, when you don't
know *if* a perfect fit exists, is a much more time-consuming problem.

Maybe. Depends on the algorithm.

(If you find a perfect fit, you can stop searching, that is guaranteed to
be the 'best' fit. if you don't find that perfect fit, you have to check
_every_possible_ combination, to figure out which is 'best'.)


If anyone is interested, and faces this problem daily, you can learn
about Floor Plan Sizing -- for example.

The technique is used for IC real Estate layout and such as well.
You can see the CRC handbook Chapter 23, VLSI Layout algorithms for
example. By Andrea S Lapaugh, Princeton U.




my $.02 :-)


--
Will
Occasional Techno-geek