The ever-elusive riddle: What's the best way to cut Christmas cookies?

December 07, 2020

At some point in life, most people have stood over a rolled-out slab of cookie dough and pondered just how to best cut out cookies with as little waste as possible. Now, even math experts have given up on finding a computer algorithm to answer this type of geometric problem.

How can we maximize dough while cutting out Christmas cookies? How do we pack a suitcase or fill a kitchen cabinet while making the best use of space? One may have thought, "there must be a best way to do this." Pondering such questions too deeply now appears to be a complete waste of time. The science is now here to support that it is impossible, for the time being, to figure out what works best for more than four or five spicy gingerbread men or Christmas tree cookies.

Assistant Professor Mikkel Abrahamsen of the Department of Computer Science 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 Mikkel 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.

Only four gingerbread cookies

We know the size of the smallest square container in which we can pack up to 10 square 1x1 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, Mikkel Abrahamsen says that optimal solutions can only be found for up to four objects today.

An infinite number of options

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 Mikkel Abrahamsen.
-end-
FACTS:

University of Copenhagen

Related Cookie Dough Articles from Brightsurf:

The ever-elusive riddle: What's the best way to cut Christmas cookies?
At some point in life, most people have stood over a rolled-out slab of cookie dough and pondered just how to best cut out cookies with as little waste as possible.

Researchers find that cookies increase ad revenue for online publishers
How long has it been since you logged onto a Web site and you were prompted to decide whether to opt out of 'cookies' that the site told you will enhance your online experience?

'Marshmallow test' redux: Children show better self-control when they depend on each other
The researchers say their experiments are the first to show that children are more willing to delay gratification for cooperative reasons than for individual goals.

Just don't eat it: Play Doh, dry pasta show little gluten transfer when used for play
Parents who worry their child with celiac disease may be exposed to gluten at school might be able to strike two common school substances -- Play Doh and dry, uncooked pasta -- from the exposure risk list, as long as children don't consume them.

Industrial bread dough kneaders could use physics-based redesign
When making bread, it's important not to overknead the dough, because this leads to a dense and tight dough due to a reduced water absorption capacity that impairs its ability to rise.

Health effects of eating marijuana is subject of a new study
Researchers have conducted a study in which mice voluntarily ate a dough containing THC, the primary psychoactive component in marijuana.

Change the bias, change the behavior? Maybe not
In a meta-analysis of published research, psychologist Calvin Lai of Washington University in St.

Do images of food on kids' clothes influence eating behavior?
As some sweet treat fans celebrate National Doughnut Day on June 7, 2019 a pediatrician examines the new trend of donuts showing up on children's clothing.

Fat fruit flies: High-sugar diet deadens sweet tooth; promotes overeating, obesity in flies
Some research suggests that one reason people with obesity overeat is because they don't enjoy food -- especially sweets -- as much as lean people.

Junk food purchases increase after recreational marijuana legalization
New research by a UConn economist found a link between state recreational marijuana legalization and increased consumption of certain high-calorie foods.

Read More: Cookie Dough News and Cookie Dough Current Events
Brightsurf.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.