Paper geaccepteerd op FOCS (Foundations of Computer Science) conferentie

Onderzoekers berekenen moeilijkheid van kerstkoekjes optimaal snijden

Wat is de optimale manier om uit een rechthoekig vel koekjesdeeg zoveel mogelijk kerstboomvormige koekjes te snijden? Dat is een voorbeeld van een packing problem (pakkingsprobleem), een notoir moeilijke opgave in de theoretische informatica. Een paper hierover van informaticus Tillmann Miltzow, samen met Mikkel Abrahamsen (Københavns Universitet) en Nadja Seiferth (Freie Universität Berlin), is geaccepteerd op de conferentie Foundations of Computer Science, de meest prestigieuze conferentie op het gebied van theoretische informatica. In de tekst hieronder leggen de onderzoekers hun resultaten uit.

In de paper beschrijven de onderzoekers hoe moeilijk het is om veel versies van tweedimensionale pakkingsproblemen op te lossen. Een pakkingsprobleem is eigenlijk een puzzel waarbij je een set stukken probeert in een bepaalde vorm te plaatsen zonder dat ze elkaar overlappen, of om te bepalen dat er niet genoeg ruimte beschikbaar is om dit te doen.

Real examples of nesting on a leather hide (top) and a piece of fabric (bottom), kindly provided by MIRISYS
Figuur 1. Echte voorbeelden van ‘nesting’ (het ordenen van vormen) op een dierenhuid (boven) en een stuk stof (onder), geproduceerd door de software van MIRISYS.

Zulke problemen komen overal in het dagelijks leven voor. Je lost bijvoorbeeld een pakkingsprobleem op als je bepaalt waar in de kamer je je meubels neerzet, als je naaipatronen zo efficiënt mogelijk ordent op een stuk stof, of als je zoveel mogelijk kerstkoekjes uit een lap deeg probeert te snijden.

In veel takken van industrie is het cruciaal om ingewikkelde pakkingsproblemen efficiënt op te lossen. Naast kledingproductie geldt dat bijvoorbeeld ook voor het snijden van leer, glas, hout en plaatwerk, selectief lasersinteren, logistiek (om zoveel mogelijk goederen te verpakken in laadcontainers) en 3D-printen (om zoveel mogelijk te printen onderdelen te ordenen in het printvolume); zie figuur 1.

Toepassingen

Verschillende toepassingen leiden tot verschillende pakkingsproblemen. Bij het rangschikken van naaipatronen op een rol stof is het belangrijk dat elk patroondeel op de juiste manier geörienteerd is ten opzichte van het weefpatroon of op de stof gedrukte patronen. Dat betekent dat de patroondelen niet mogen worden gedraaid. Bij andere toepassingen, zoals het snijden van leer, glas of plaatwerk, zijn er meestal geen beperkingen, zodat de stukken kunnen worden gedraaid om afval te minimaliseren. Weer andere versies van het probleem ontstaan wanneer de vorm van de stof of de stukken beperkt is.

Onderzoeksfilm over het paper

Moeilijkheid

Van de meeste versies van pakkingsproblemen was het al bekend dat deze NP-moeilijk zijn. In de publicatie laten we zien dat veel problemen waarschijnlijk nog moeilijker zijn, door te bewijzen dat ze ∃R-compleet zijn. Dat geldt in ieder geval voor het pakken van polygonen in een vierkant met toegestane rotaties. Dat wil zeggen dat deze problemen in wezen net zo moeilijk zijn als de vraag of een systeem van polynomiale vergelijkingen en ongelijkheden een echte oplossing heeft – een probleem dat naar verwachting van de meeste onderzoekers moeilijker zal zijn dan NP-complete problemen, hoewel dit nog steeds een openstaande vraag is. Houd dit in gedachten de volgende keer dat u kerstkoekjes bakt!

Publicatie

Framework for ∃R-Completeness of Two-Dimensional Packing Problems
Mikkel Abrahamsen, Tillmann Miltzow*, Nadja Seiferth
Foundations of Computer Science conference, gepresenteerd op 18 november 2020

* onderzoeker verbonden aan de Universiteit Utrecht