In article ,
WillR wrote:
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.
Nit-pick, all 'real-world' applicatins only attempt to find a "close to best"
fit. they offer no assurance, let alone a 'guarantee' that there is not a
better solution involving radically different organization.
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).
The original statement of the knapsack problem involves filling a fixed-size
container with a mixture of same-diameter rods of varying length. Stuffing
dowels in a shipping crate? grin
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.)
The complexity is all "relative". *snicker* groan
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.
*Approximations* exist that are workable, subject to constraints. They can
get you a 'close to best' answer at affordable "cost". *NONE* of them
promises a "best" fit.
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.
"knapsack" is a '2 D' packing problem. build 'm' segments of length 'n', from
the random set of pieces (length less-equal to 'n') supplied. (Note: this _is_
a more complex problem than finding a set of pieces that total 'm * n' in
length.) "Best fit" on sheet stock, is similarly "2 D". The "order" of the
complexity is the same, although the multiplier is higher for the sheet layout
problem. Packing shipping containers, with random-dimension objects is a '3 D'
packing problem -- an additional order of complexity,
I don't have appropriate references handy, but I believe all are known to
be NP-Complete.
Of course, _that_ is why the questions keep coming up. The 'easier' problems
*have* solutions; the 'best way' to do those things *is* known. "Solved
problems" are no longer "a 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
Coming up with 'adequate' solutions is usually *not* terribly time-consuming
nor epensive. The 'cost' of a solution goes up radically, as the nature of
the solution gets 'better'. A _provably_ 'best' solution is unaffordable.
"Good enough for who it's for" *is* frequently economically achievable.
The 'real' questions a
1) how close to 'optimal' is the current solution?
2) _how_much_ are you willing to pay for the next increment of improvement?
c) can you _get_ that increment of improvement for that cost?
"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...
Finding "better fits" is _not_ the same problem as finding the 'perfect' fit.
Algorithms that find "near best" fits do *NOT* necessarily find a 'perfect'
fit, when it exists.
The math involved gets very hairy, but that deficiency is well established.
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.
No maybe about it. you have to test every possible arrangement, until
one of two things happens:
A) you run out of possibilities
B) you find a perfect fit.
Algorithms that work on 'local minimization' _cannot_ guarantee that there
is not a lower minimum 'over the next hill'.
If you know a perfect fit exists, then the average search length is
1/2 the number of possibilities.
if you do _not_ know a perfect fit exists, then there are two situations to
consider:
1) the perfect fit _does_ exist. average search length 1/2 the
possibilities
2) perfect fit does not exist -- average search length _all_ the
possibilities
The weighted mean across those two situtions is _guaranteed_ to be higher
that that of the 'perfect fit known to exist' scenario. How much greater
depends on the relative probability of the two situations.
(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
|