Computers Still Can't Solve This Cookie Cutter Dilemma

Today’s computers still aren’t ready for a common holiday question: How to cut out cookies with as little waste as possible.

Even math experts have given up on finding a computer algorithm to answer this type of geometric problem, which might also apply to packing a suitcase or filling a kitchen cabinet while making the best use of space.

Assistant professor Mikkel Abrahamsen of the University of Copenhagen’s computer science department and two research colleagues studied how difficult it is to figure out the optimal way to pack objects in two dimensions without overlap—a conundrum that computer scientists have plugged away at for decades.

“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 5-10 objects optimally. And, our result suggests that this number probably won’t increase much for the time being,” explains Abrahamsen.

Packing things optimally isn’t just an occasional problem at home, but in a variety of industries, including clothing manufacturing and metal processing. In each case, it is important to cut out materials with as little waste possible. In shipping, it applies to the packing of containers.

We know the size of the smallest square container in which we can pack up to 10 square 1×1 meter pallets. But by simply adding one additional pallet, it becomes impossible to calculate the optimal size of the container. Abrahamsen explains:

“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 optimize the handling of a few additional objects.”

Furthermore, if one is working with more complicated shapes, like Christmas tree-shaped gingerbread, Abrahamsen says that optimal solutions can only be found for up to four objects today.

What makes it so difficult? Abrahamsen explains that the problem is similar to solving equations of degree five or higher, and with many unknowns. Here, it is known that such a solution cannot always be written down using regular arithmetic operations.

“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 cookies can be placed and all of the angles at which they can be rotated,” explains Abrahamsen.

As the possible combinations are infinite, there is no way to create a list of all the locations needed to try in order to find an optimal packing solution. Instead, algorithms that solve packing problems optimally need to be more analytical, which is time consuming. This contrasts with many other known algorithmic problems, where one can try a limited number of combinations before finding one that is optimal. Thus, packing problems are much more difficult.

So in practice, there are no better solutions to packing problems than the ones we 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,” concludes Abrahamsen.

The researchers presented the study at FOCS 2020 (IEEE Symposium on Foundations of Computer Science). Additional researchers from the University of Copenhagen, Utrecht University in the Netherlands, and Freie Universität Berlin in Germany.

The research has received funding from the VILLUM Foundation, among others.

This article was originally published in Futurity. It has been republished under the Attribution 4.0 International license.