Have you ever drank a can of soda and wondered: Why the hell is it shaped like a cylinder?
Mathematically, it makes zero sense. A square can would allow us to pack boxes with 100% volume utilization. A round can loses about 22% of the space in a shipping truck to the “air gaps” between the circles. In an industry where margins are measured in pennies, 22% is a fortune.
So, are manufacturers stupid? No. The shape of your soda can is the scar tissue from a battle between Logistics and Physics. Physics won.
1. The Pressure Problem:
Soda is carbonated. It exerts outward pressure. In a round can, this creates “hoop stress” which is distributed evenly. In a square can, pressure pushes against the flat sides, bulging them out until they are round anyway. Worse, the stress concentrates on the sharp corners, blowing the can apart like a bomb.
2. The Speed Limit:
Metal “wants” to be round. You can take a flat disk of aluminum and “draw” it (stretch it) into a cup shape in milliseconds without tearing it. Making a square box requires folding edges and creating seams. It is slower, weaker, and more expensive.
The cylindrical shape is what mathematicians call a “Hard Constraint.” We cannot change the shape of the item without it exploding. Therefore, the burden of efficiency shifts from “Design” to “Arrangement.”
We stop asking “How do we design the product?” and start asking “How do we pack the truck?”
That is the exact definition of the Bin Packing Problem.
The Combinatorial Explosion
Imagine you are moving houses. You have 50 different items (books, lamps, pillows, a microwave) and a stack of identical cardboard boxes.
The Goal: Put all items into the fewest number of boxes possible.
The Catch: You cannot overfill a box (weight limit) and items cannot stick out of the top (volume limit).
Sounds straightforward? It is actually one of the hardest problems in mathematics. It is classified as NP-Hard. The only way to find the perfect arrangement is to check every single possibility.
- 5 Boxes: There are 5! (5 factorial) ways to arrange them. 5x4x3x2x1 = 120. Easy.
- 20 Boxes: If you add just 15 more items, the possibilities jump to 2.4 Quintillion.
If a supercomputer checked one billion arrangements per second, it would take 77 years to find the optimal packing for just 20 boxes. If you have 100 boxes, the heat death of the universe would happen before the computer finished.
The Intuition Trap (2D)
But surely, if we make the items simple? say, identical squares, it gets easier?
Consider a square container of size s=4. How many 1×1 boxes fit inside?
Intuitively, 4×4=16. Easy.
But what is the smallest container needed to fit 17 boxes?
Intuition says you need a size of 5 (5×5=25 slots). But that is wasteful.
Theoretically, the answer should be slightly larger than 4.
In 1997, John Bidwell found the answer. It wasn’t a grid. It was this traumatizing arrangement:
The squares in the middle are rotated to wedge into the gaps left by the outer frame. This proves that Order (rows and columns) is not always efficient. To get the absolute smallest container (s ~ 4.675), you have to embrace “Calculated Chaos.”
But since this doesn’t work, what if we try to reduce the problem to just 1-D. Surely, that should make it intuitively simpler, right?
Bin Packing in 1-D: The “Big Rocks” Theory
Since 2D packing leads to “calculated chaos,” mathematicians often simplify the problem to 1-Dimension to understand the logic. Imagine you have a collection of lines of varying lengths, and you need to fit them into fixed-length containers.
This seems trivial, but even here, the order matters immensely.
Total lines in the top half and Best Fit in the bottom half
The “First Fit” Algorithm:
This is how most humans pack lazily. You pick up an item and put it in the first bin that has room. If it doesn’t fit, you open a new bin.
The First Fit algorithm places a new object in the leftmost bin that still has room.
Result: Fast, but messy. You end up with many bins that are half-empty because you filled them with small debris first, leaving no room for the big items later.
The “Best Fit” Algorithm:
You look at the item and scan all open bins to find the one where it fits tightest (leaving the least empty space).
The Best Fit algorithm places a new object in the fullest bin that still has room.
Result: Better efficiency, but much slower to calculate.
The Golden Rule: Sorting (Descending Order)
The single most effective trick in bin packing is simple: Sort the items from Largest to Smallest.
If you pack the huge items first, the small items can easily slide into the remaining gaps (like pouring sand into a jar of rocks). If you pack the sand first, the rocks won’t fit.
In simulations, simply sorting the input data (Descending) before running the “First Fit” algorithm improves efficiency by over 20%. This is why shipping companies always load the biggest crates first. It isn’t just about weight; it’s about the math of space.
In real applications, the sizes to be packed may all be known in advance. In that case, better results are achieved by packing the largest objects first. This illustration shows the results of sorting the input in descending order before applying the Best Fit algorithm.
Would suggest checking out this awesome in-depth explanation: https://www2.cs.arizona.edu/icon/oddsends/bpack/bpack.htm
When stuck with such problems, it is usually a good idea to look at nature solving it. After years of evolution, nature usually arrives at a pretty good and efficient solution so let us look at how it tackles this problem.
How Nature Solves It: The DNA Problem
If you think fitting sorted lines is hard, try fitting the code of life into your body.
Every single cell in your body contains a copy of your DNA. If you stretched the DNA from one cell into a straight line, it would be 2 meters long.
The container (the nucleus) is only 6 micrometers wide.
The Ratio: This is equivalent to packing a 40 km long thread (the length of a marathon) into a tennis ball.
Nature cannot just shove it in randomly (it would tangle and break). It also cannot pack it too tightly (the cell needs to “read” the data to survive).
The Fractal Solution:
In 2009, scientists discovered that Nature uses a mathematical shape called a Hilbert Curve (a type of fractal).
A Hilbert Curve is a continuous line that folds in on itself to fill a 2D or 3D space completely without crossing itself.
- Density: It packs the DNA incredibly tight (no wasted space).
- Locality: Regions of DNA that need to work together are physically close to each other in the 3D ball, even if they are far apart on the 1D string.
Nature realized billions of years ago what John Bidwell realized in 1997: The most efficient way to pack information is not a grid, it is a crumpled, fractal mess that only looks chaotic.
How AI Solves It: The Floorplanning Revolution
For decades, we solved Bin Packing with “Greedy Algorithms” (like the 1-D First Fit). They are fast, but never perfect. But recently, the Bin Packing problem became a billion-dollar bottleneck for Computer Chips.
A modern Google TPU has billions of transistors. Engineers spend months playing “Tetris,” arranging blocks to minimize wire length.
Enter Reinforcement Learning
In 2021, Google trained an AI agent to place the blocks.
Human Engineers: Arranged blocks in neat rows and columns (Manhattan style).
The AI Agent: Arranged blocks in scattered, alien-looking clusters. It looked “wrong.”
The Result: The AI’s “messy” layout was superior, reducing wire length and power consumption significantly. Just like the DNA fractal, the AI discovered that the optimal solution to packing isn’t order. It’s complexity.
Layouts with macros in red and standard cells in green, locations produced by RL (left) and Replace(right) for the ibm10 benchmark
The Price of Chaos: Why We Still Use Grids
So, if Nature and AI prove that “Chaos” is efficient, why do we still pack shipping containers in straight lines? Why are Amazon warehouses built in grids?
The answer is Retrieval.
Nature optimizes for Storage Density. It packs DNA tightly because it has special enzymes that can chemically “unzip” just the part it needs to read. It doesn’t need to move the rest of the DNA.
Humans optimize for Accessibility.
If you packed a cargo ship like a protein strand (a crumpled mess), you would achieve 100% volume utilization. But if you needed to unload the crate of bananas at the center of the ball, you would have to unload the entire ship first.
We use grids not because they are space-efficient (they aren’t), but because they are time-efficient. We sacrifice space so that a forklift can drive in a straight line and grab exactly what we need.
The Lesson:
If you never need to open the box again (like storing nuclear waste), pack it like Nature (Chaos).
If you need to find your keys every morning, pack it like a Human (Grid).
Conclusion
We humans love straight lines. We associate “Order” with “Efficiency.”
But the Bin Packing problem teaches us that the universe is more nuanced. Whether it’s the frustration of the soda can’s cylinder or the genius of the DNA’s fractal, the math shows us that the perfect fit usually looks like a mess.
Sometimes, to fit everything in, you have to break the grid.
