in reply to Re: Packaging Algorithm in thread Packaging Algorithm
Actually, no it isn't like a binpacking problem. It's like
the spherepacking problem. It is unbounded since he specifically
asked for the smallest container. I'm pretty sure that is
a rather bit nastier than binpacking, since the only way to
find the answer is to run the binpacking work on a huge
series of various container sizes. As I recall, that was
what made this such a nasty problem, there isn't a specific
strategy for finding the "best" answer, just a good strategy
for finding a "fair" answer for a single facet of the problem.
OTOH, mentioning Sedgewick's book is good enough for a
++ in my book, anyday =) And you are correct in that refactoring
the problem can surely help make it solvable.

$you = new YOU;
honk() if $you>love(perl)
RE: RE: Re: Packaging Algorithm
by Fastolfe (Vicar) on Nov 07, 2000 at 09:34 UTC

Why a sphere? He has a bunch of boxes. This seems perfect for a binpacking problem. He just needs to try the algorithm against successively larger containers until he's able to fit everything. He's followed up with a comment indicating that he's already planned to limit himself to a predetermined discrete set of box sizes.  [reply] 

One, Sphere packing is a special problem class, that is
especially hard to solve. I shouldn't have mentioned it.
Two, try it. But first, some numbers...
Lets limit ourselves here. 10 boxes. I'm not letting you
have cubical, so they have 6 orientations that matter.
We'll limit ourselves to 4 inch increments and reasonable
box sizes and so 52" is max. That is boxes ranging from
1 to 13 "increments" on a side. (btw that is not 13**3 types
of boxes but it doesn't matter, we are only interested in
ten at a time. Discrete box sizes doesn't help at all anyway,
except if you can keep the number of positions low.)
Now, max and min cases, the container can't be smaller than 4x3x3
and 130x130x130 is clearly large enough.
So, for each box to place you have around 2 million origins,
and 6 orientations. For 10 boxes. And in each of these
120 million cases, you have to determine that none of them
intersect.
Just whip that out in perl real quick and run it. You can
do it with a 3d matrix or be fancy about it. You can throw
entire sub trees out if you can tell that a case is already
bigger than the smallest case you've found so far.
It is still like 100 million cases you have to run,
brute force. It's an ugly problem and I've not seen
a good suggestion as to how to break it down much better
to throw out large sets of fails. Worse, I don't think
anyone has found an "answer", a strategy that lets you
cut thru the bruteforce approach and jump straight to the
answer.
And I suppose you are correct that you can start small
and work your way up, but as I recall the algorithm in the
books is just a "prettygood" solution that is a bugout
bruteforce. That means you are going to repeat trying
cases you know are bad, over and over again as you go up
in size. And you won't be SURE you have the right
answer, just sure that you have AN answer.
I really don't want to be a spoilsport on this and
I don't know everything® but I'm pretty sure
this is a frustration fest. Don't let me stop you guys from
trying tho. Just consider using a box you don't mind letting
sit a while. =)

$you = new YOU;
honk() if $you>love(perl)
 [reply] 

Okay, how many crate sizes can you buy at UHaul? Or are you expecting him to buy sheet cardboard and build a custom crate in order to achieve maximal packing? The number of crate sizes to try is just a few. But then, I wouldn't try any sizes of crates at all!
Where did you get this crazy idea to try every possible origin for a package? If I put packages together tightly, then every package shares part of a side with another package. And we aren't talking about some theory trying to prove that we have the maximally tightest packing (which would be very hard, sure). Just assume that a reasonable packing exists where one package hits a corner of the crate (when was the last time you put packages in a crate in such a way that no package shared a corner with the crate?).
Now all you have to do is place a package in the corner of an infinite box (the positive octant) and add boxes in the resulting "corners". As you place boxes, keep track of the bounding crate. Iterate through all of the possibilities. Sure, this isn't trivial to code and the number of possiblities is huge. If you have a large number of packages, then try at random and report the best solution so far once you are tired of waiting. Who cares if it is brute force? Also, if you haven't placed all of the boxes yet and you are already worse off then your best solution so far, no need to continue adding packages.
Take N boxes.
First box: N choices (orientation doesn't matter yet)
Second box: N1 boxes * <=3 corners * 6 orientations
Third box: N2 boxes * <=5 corners * <=6 orientations
...
If I change the *3*5*7*9... terms to *4*6*8*10... then we are bounded by N! * 2^(N1)*N! * 6^(N1) == N!^2 * 12^(N1). So assuming a worsethanworstpossible case where we don't trim any chunks from the decision tree (we try all of the combinations in exactly the wrong order and don't eliminate overlapping boxes until we've placed all boxes), then we can still exhaustively search for 5 packages pretty quickly.
For 6 or 7, easy trimming of the decision tree might let you exhaustively search (hard to predict). For more than 7, you'd probably have to settle for stopping early and having a less optimal solution.
Brute force is often a very good way to solve reallife problems. That is why they computers that are fast. (:

tye
(but my friends call me "Tye")  [reply] 

(tye)Re2: Packaging Algorithm
by tye (Sage) on Nov 07, 2000 at 21:42 UTC

BTW, I used to work for a guy who had several good solutions for packing spheres. He used them for designing composites (for example, what mixes of sizes of gravel to use for certain types of concrete). One involved selecting spheres from the chosen mix at random and dropping them into a virtual cylinder and letting them settle. Sure, he wasn't proving the maximally tightest possible packing. But he was able to make good predictions about how certain mixes of sizes of spheres would pack in practice.
He also sometimes repeated the experiment of make a bunch of spheres, put them in a bag, squeeze the bag for a few days, poor wax in, let it cool, remove bag, analyze positions of spheres.
Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well enough to get your work done!

tye
(but my friends call me "Tye")
 [reply] 

Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well
enough to get your work done!
(smartest thing said so far in this whole discussion.)
Well, again, "the sphere packing problem" is different
than that. In fact, there have been some neat breakthru's
in the field. We have 9600 baud and up modems thanks to
a trelliscode based on packing spheres efficiently in
8 dimensions. Turns out a single sphere can be touched
by 1024 spheres in a tightlypacked regular array. =)
That result is basically cool in anyone's book.
The original problem was that given a bunch of spheres
that are the same size, how many can you get to touch a
single sphere at the same time. In 2d, the answer is clearly
6. (try it with pennies.) In 3d, 12 is the answer but if you
look at the spherical cone of impact that each outer sphere
makes, it would seem that 13 COULD be possible. The deal is
that no one has found a function that provably states for
each dimension what the number is. Only a special case exists
for multiples of 8. Highweirdness, plain and simple.

$you = new YOU;
honk() if $you>love(perl)
 [reply] 

I suggest you do a search for "sphere packing problem" and see the variety of problems that fall under this category. I ran into several before hitting the "kissing number" problem for idential spheres in different numbers of dimensions that you seem to think is the only one.
From what I read, the original problem was popularized by Kepler when he guessed how tightly you could pack identical spheres in 3 dimensions. This one was recently solved (by proving the "obvious").

tye
(but my friends call me "Tye")
 [reply] 


