Cosmos Editorial
If you struggle to use space optimally when cutting out lots of shapes or packing a drawer, then feel free to give up.
Three European researchers suggest that it may well be too hard to work it out, unless by accident, particularly if the shapes are an odd shape.
Packing problems are a class of optimisation problems and mathematicians have been addressing them for centuries, says Mikkel Abrahamsen, from Denmark’s University of Copenhagen.
“While algorithms let us solve seriously complex problems, this is one that remains too much of a mouthful for today’s computers. For now, it isn’t possible to pack more than five to 10 objects optimally, and our result suggests that this number probably won’t increase much for the time being.”
Abrahamsen is lead author of a paper presented to the IEEE Symposium on Foundations of Computer Science and available on the pre-print server arXiv. His co-authors are Tillmann Miltzow from Utrecht University in the Netherlands and Nadja Seiferth from Germany’s Freie Universität.
In maths speak, they write that “many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials”.
It is, of course, a serious issue in industries that need to cut out materials or pack products with as little waste as possible.
We know the size of the smallest square container in which we can pack up to 10 square pallets, Abrahamsen says, but by simply adding one additional pallet, it becomes impossible to calculate the optimal size of the container.
“As more pallets are added, the calculation time increases beyond exponentially. Not even the best computers can keep up. Theoretically it’s possible. But based upon the speed at which computing power is growing, it will probably take millions of years before we are able to optimise the handling of a few additional objects.”
Working with complicated shapes makes the problem worse, he suggests. Optimal solutions can only be found for up to four objects today.
The reason? “Our study proves that the problem has a nature that we in mathematics refer to as continuous, which, in a nutshell, means that one must know all of the coordinates at which the [objects] can be placed and all of the angles at which they can be rotated.”
As the possible combinations are infinite, the researchers say, there is no way to create a list of all the locations needed to try in order to find an optimal solution. Instead, algorithms that solve packing problems optimally need to be more analytical, which is time consuming.
This contrasts with many other algorithmic problems, where one can try a limited number of combinations before finding one that is optimal.
So in practice, there are no better solutions than the ones humans can come up with.
“In both industry and over the kitchen counter we must continue to be satisfied with our less-than-optimal solutions and rest assured that we humans are still better than computers for these types of tasks – for the time being,” Abrahamsen concludes.