It ended up being a bin packing problem that no one actually did till I wrote a script to do it for me. This in turn led to some interesting conversations with my manager and the head of Capital Markets and Banking's CFO.
You can read more details about it here: https://twitter.com/alexpotato/status/1296856648435326976
It is clear that optimal algorithms are out of the question, which is the conclusion of the article, even with the constraints of orthogonal placement of simple boxes. In fact, in real life, when taking into account packages that are not simple boxes, items that can be squished a little and those that shouldn't be, etc... I wouldn't be surprised if humans were actually better than computers.
[1] https://kingbird.myphotos.cc/packing/squares_in_squares.html
Having worked on something that required "optimal" box packing for deliveries[1], the answer is "very, and then some (and that was with the help of that fancy USMIL pallet-packing algorithm, IIRC)".
[1] They wanted to use the smallest possible box plus some other constraints like "product X cannot have anything on top of it", etc.
The whole story might become a blog post some day, but the punchline is that Moore's law ain't got nothing on NP-hard problems
Some light optimisation such as utilising symmetries to reduce work, combined with multiple GPUs in parallel could bring this down to hours or even minutes.
It would be a fun thing to cloud-host, spinning up spot-priced GPUs on demand.
Similar brute-force tricks can be applied to other NP-hard problems such as optimising electronic circuit board wiring, factory floor planning, etc...
The ridiculous amount of compute we have available to us in a GPU reminds me of this quote from Stargate Atlantis:
JEANNIE: The energy you'd need would be enormous to the point of absurd.
McKAY: Absurd we can do. We have something called a Zero Point Module which essentially does what we're attempting on a smaller scale -- extract energy from subspace time.
A frequently asked for feature was box-packing - clients would complain that their packers would chuck something tiny in a huge box, use loads of packaging, and still manage to have the thing damaged on arrival due to shaking about in there.
So we implemented the feature. It worked great. Clients bought it.
Literally nobody used it, as humans inevitably decide they know better. Instead, we just ended up with clients reporting “the boxer told our packer to put a stick of gum in a 1m2 palletised delivery!”, as that was what the packer would report, when it had done no such thing, so all we had done was move the point of blame from minimum wage warehouse workers to ourselves.
We withdrew the feature.
Although we couldn't guarentee the "best" approach possible we generally came up with something good enough, often in many orders of magnitude less time.
A good example of the performance improvements you can make when you move from thinking of what the best solution is to what a "good enough" one is.
Then one would only have to specify the constraints and let the solver optimize a solution, rather than trying to write a customized packing problem algorithm from scratch. I'm sure it'd be fun, but when trying to best solve a real-world problem, I'd think using well-researched tools would be the quickest and safest way to go.
https://github.com/dvdoug/BoxPacker?tab=readme-ov-file#boxpa...
Hey I'm a programmer, I'll tell a computer to brute-force it.
To someone who only has a hammer everything looks like a nail.
1) Surely there are a bunch of more obvious optimizations, like don't place candies where they would fall because of gravity and nothing supporting them underneath, or always placing the candies in order of largest to smallest, and ignore anything symmetrical or rotationally equivalent to a previous solution... and how much would this reduce the search space?
2) What is the actual metric for fitting in a box "in the best way"? That lower layers are as full as possible before adding upper layers? That shifting of contents is minimized while upright? That shifting of contents is minimized in any orientation? To minimize small gaps and try to make non-used space as contiguous and compact as possible? Or is the box size arbitrary and the goal is to find the minimal box volume?
3) Is there separately a metric for "good enough"? Should the metric not to be to fit in a specified box, but rather find the smallest box of a set of standard box sizes that can fit the candies, with any arbitrary arrangement rather than a "best"? Is this a much easier problem, or is it just as hard or harder?
I feel like Amazon must have solved this for all practical purposes.
I suspect that it would work well and be fast if you simply place items in order from largest to smallest by volume, filling from bottom to top, quickly determine which box sizes are too small, and then just find the first arrangement that works. Curious if there are pathological cases where that wouldn't work?