UvA- & VU-informatici lossen als eerst wiskundig inpakprobleem op
Stel je hebt een stapel met 34 kerstcadeaus van verschillende afmetingen die je na de kerstinkopen in de achterbak van de auto moet passen. Je weet dat de cadeaus qua oppervlakte precies in de achterbak zouden moeten passen, de vraag is alleen hoe? Een team van informatici van de UvA en de VU waagde een sprong in het diepe met een soortgelijke vraag en publiceerde voor het eerst een oplossing.
‘Ik was totaal verbaasd toen ik de oplossing in mijn mail kreeg,’ zegt Daan van den Berg, lid van het docententeam Instituut voor Informatica (IvI)/UvA. Hij leidde het project aanvankelijk aan de VU, maar stapte later over naar de bètafaculteit aan de UvA.
Nog nooit eerder was er een antwoord op dit inpakprobleem naar buiten gebracht. Het inpakprobleemEen Italiaan zei een aantal jaar geleden dat hij het probleem op zijn normale persoonlijke computer had opgelost, maar weigerde die oplossing openbaar te maken. komt uit de categorie perfect rectangle packing problems waarin het de bedoeling is om een verzameling rechthoeken van verschillende grootte op zo’n manier naast elkaar te plaatsen, dat ze samen ook een rechthoek vormen.
Almost squares
Voor het huidige project ging het om rechthoeken die bijna vierkant zijn. Bij de zogenaamde Asqas-problemen (Almost squares in almost squares) blijft het principe vergelijkbaar: een reeks bijna-vierkanten van opeenvolgende grootte moeten worden samen gevoegd tot een bijna-vierkant. In dit geval mochten de bijna vierkanten elkaar niet overlappen, net zoals het fysiek niet mogelijk is om verschillende kerstcadeaus in elkaar te verstrengelen.
Laatste inpakprobleem
De Asqas-34 is niet het enige inpakprobleem in zijn reeks. Informatici hadden eerder al bewezen dat er vijf verschillende reeksen bijna-vierkanten zijn waarvoor dit probleem oplosbaar is. Van vier van die reeksen (Asqas-1, -3, -8 en -20) was al bekend hoe je de bijna-vierkanten zo moet neerleggen dat ze precies passen. De Asqas-34 was tot nu toe onopgelost. ‘Dat wij in deze categorie op het laatste inpakprobleem een oplossing hebben gevonden, maakt het extra bijzonder,’ zegt Van den Berg.
Het was van tevoren nooit de intentie van de studenten om hiermee aan de slag te gaan. Zij hadden zich eerst over de gemakkelijkere en al eerder opgeloste Asqas-20 gebogen, maar die wisten ze binnen een mum van tijd te tackelen. ‘Zij vroegen mij daarom om zwaardere kost en ik heb hen toen het Asqas-34-probleem voorgeschoteld,’ vertelt Van den Berg. Al snel werd hen duidelijk dat dit inpakprobleem alleen met een slim trucje opgelost zou kunnen worden.
Op goed geluk
‘De opdracht is recht toe recht aan maar stiekem toch heel moeilijk. Het aantal mogelijke combinaties is namelijk zo groot – een één met 48 nullen om precies te zijn – dat het zelfs de snelste computers er maanden over zouden doen om alle individuele combinaties langs te gaan,’ vertelt Van den Berg. Samen met zijn team wist hij het inpakprobleem op goed geluk terug te dringen naar een behapbare grootte.
‘Wij zagen dat bij de meeste oplossingen van de Asqas-20 de randen uit relatief grote rechthoeken bestonden,’ vertelt Van den Berg. ‘Hoewel dit een minieme aanwijzing is, namen wij de proef op de som en pasten wij hetzelfde idee toe bij de Asqas-34.’ Deze gewaagde gok pakte goed uit en leverde de informatici 4,4 miljoen kandidaat-randen van twaalf bijna-vierkanten op.
Supercomputers
Wat overbleef was een puzzel van de 22 overgebleven stukjes, volgens Van den Berg alsnog ‘best veel’. Om de rekencapaciteit op te krikken zetten de studenten ‘heel Nederland aan’. Ze ontwikkelden een ingenieus computerprogramma dat binnen de kandidaat-randen verder kon puzzelen met de overgebleven stukjes. Maar liefst duizend supercomputers verspreid over het hele land kwamen er aan te pas om de 22 stukjes perfect in te passen. ‘Studenten kunnen op verschillende universiteiten in Nederland een account aanvragen waarmee ze toegang hebben tot allerlei servers. Op ieder beschikbaar account draaiden ze hun experimenten,’ vertelt Van den Berg.
Dat ging niet altijd van een leien dakje: ‘Processen werden soms halverwege afgebroken, omdat bijvoorbeeld de systeembeheerder dacht dat hij werd gehackt. Wij zaten dan met halve datasets. Het leverde een enorme puinhoop aan data op.’
Maar vijftien oplossingen
Na 55 dagen rolden er uit die enorme stapel aan data toch vijftien mogelijke configuraties voor het Asqas-34-probleem. Naast dat hiermee het inpakprobleem op een vernuftige manier is opgelost, zijn de oplossingen ook meteen toepasbaar in de praktijk. Zo kunnen de oplossingen bijvoorbeeld gebruikt worden voor het optimaal benutten van opslagruimte of om te bepalen hoe componenten op een chip het beste naast elkaar geplaatst kunnen worden.
