Computers Still Can't Solve This Cookie Cutter Dilemma

nata_nytiaga/Shutterstock.com

Even math experts have given up on finding a computer algorithm to answer this type of geometric problem.

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.

X
This website uses cookies to enhance user experience and to analyze performance and traffic on our website. We also share information about your use of our site with our social media, advertising and analytics partners. Learn More / Do Not Sell My Personal Information
Accept Cookies
X
Cookie Preferences Cookie List

Do Not Sell My Personal Information

When you visit our website, we store cookies on your browser to collect information. The information collected might relate to you, your preferences or your device, and is mostly used to make the site work as you expect it to and to provide a more personalized web experience. However, you can choose not to allow certain types of cookies, which may impact your experience of the site and the services we are able to offer. Click on the different category headings to find out more and change our default settings according to your preference. You cannot opt-out of our First Party Strictly Necessary Cookies as they are deployed in order to ensure the proper functioning of our website (such as prompting the cookie banner and remembering your settings, to log into your account, to redirect you when you log out, etc.). For more information about the First and Third Party Cookies used please follow this link.

Allow All Cookies

Manage Consent Preferences

Strictly Necessary Cookies - Always Active

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Sale of Personal Data, Targeting & Social Media Cookies

Under the California Consumer Privacy Act, you have the right to opt-out of the sale of your personal information to third parties. These cookies collect information for analytics and to personalize your experience with targeted ads. You may exercise your right to opt out of the sale of personal information by using this toggle switch. If you opt out we will not be able to offer you personalised ads and will not hand over your personal information to any third parties. Additionally, you may contact our legal department for further clarification about your rights as a California consumer by using this Exercise My Rights link

If you have enabled privacy controls on your browser (such as a plugin), we have to take that as a valid request to opt-out. Therefore we would not be able to track your activity through the web. This may affect our ability to personalize ads according to your preferences.

Targeting cookies may be set through our site by our advertising partners. They may be used by those companies to build a profile of your interests and show you relevant adverts on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. If you do not allow these cookies, you will experience less targeted advertising.

Social media cookies are set by a range of social media services that we have added to the site to enable you to share our content with your friends and networks. They are capable of tracking your browser across other sites and building up a profile of your interests. This may impact the content and messages you see on other websites you visit. If you do not allow these cookies you may not be able to use or see these sharing tools.

If you want to opt out of all of our lead reports and lists, please submit a privacy request at our Do Not Sell page.

Save Settings
Cookie Preferences Cookie List

Cookie List

A cookie is a small piece of data (text file) that a website – when visited by a user – asks your browser to store on your device in order to remember information about you, such as your language preference or login information. Those cookies are set by us and called first-party cookies. We also use third-party cookies – which are cookies from a domain different than the domain of the website you are visiting – for our advertising and marketing efforts. More specifically, we use cookies and other tracking technologies for the following purposes:

Strictly Necessary Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Functional Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Performance Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Sale of Personal Data

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.

Social Media Cookies

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.

Targeting Cookies

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.