Scientists from Mainz beat world records for the best arrangement of circular discs
23.03.2009
How do I pack a car so that everything fits in? How can I pack a parcel in such a way that it is optimally filled? How much flatware will fit into a kitchen cupboard? When it comes to packing, a team of scientists from Mainz University are unbeatable. They were able to equal or beat any of the world records set during an international competition to find the best solution to a special packing problem.
"As part of an interdisciplinary project between theoretical physics and computer studies, we have been working for some time now to develop an optimal computer algorithm for packing problems," explains PD Dr. Johannes J. Schneider of the newly established Research Unit Computer-based Research Methods in the Natural Sciences at Mainz University. When, quite by chance, the scientists found out about the international competition only shortly before it ended, they were only able to set a single world record, with the results of some other groups being somewhat better in other areas. Driven by the ambition to beat the best groups worldwide - some of which had been working on similar problems for many years -, they continued to develop their computer algorithms and were able to beat the world records that had been set during the competition - in some cases by a clear margin. Their work was published in the well-known journal of statistical physics, Physical Review E.
The competition was about arranging round disks of various sizes in a circle in such a way that they require as little space as possible. The radius of the large circle into which the smaller circular disks were packed was to be as small as possible. Some 155 groups from 32 countries took part in this competition and submitted their solutions. For problems involving between 24 and a maximum of 50 differently sized circular disks, PD Dr. Johannes J. Schneider, Professor Elmar Schömer of the Mainz Institute for Computer Studies, and undergraduate André Müller found by far the best solutions. When it came to smaller problems involvin 23 or fewer circular disks, they managed to equal the best solutions found thus far, which probably indicates that there is no better solution. "For this problem involving various sizes of circular disks, we managed to develop the world's best packing algorithm," Schneider sums up the situation.
However, the scientists are not only looking at this kind of scientific problem, but are also transferring their algorithms to practical applications. For example, the group is doing research for a major German automobile manufacturer to find out how the volume of a car boot can best be measured. In accordance with the standars prescribed by the European Union (EU), tetrapacks of a certain size must be packed into a specified car boot in such a way that the space is filled to the greatest extent possible. "Currently we are still trying to fit in as many tetrapacks as possible manually using wooden blocks," explains Schneider. In the USA, on the other hand, sets of suitcases belonging to the super-rich must be optimally accommodated in the boot, which is why the information about the amount of boot space available does not quite correspond in German and American advertising brochures. Based on a comparison with the results of the competition, the scientists now have certainty that their algorithm can optimally solve even these car boot packing problems.
Such optimization algorithms can also be used to solve an entirely different set of problems. For example, the truck journeys to farm organized by a dairy producer to fetch milk could be optimized in such a way that the distances covered by the trucks are as short as possible, depending on the order in which the farms are visited. Another example from the automobile industry is the final assembly of vehicles: A computer can be used to determine the sequence in which the various preassembled car bodies should be placed onto the conveyor belt to ensure the most efficient production process possible. There are competitions for similar problems, some of which are even organized by companies. Schneider, a doctoral student at Regensburg at the time, entered a competition organized by a Bavarian automobile manufacturer some years ago as an individual candidate, ultimately finishing in fourth place, easily beating a number of established companies in the field of optimization, which had delegated entire groups of employees to enter the competition.
The scientists from Mainz find the best method for solving the problem by approximating the solution. So-called Monte Carlo simulations- named after the district in Monaco in which the famous casino is located - are used to simulate random events, using a computer. "Like the number twelve might randomly come up when playing roulette at the casino, the computer will come up with a random arrangement," explains Schneider. When applied to the example of the circular disks, the computer will then displace one of these disks anywhere and compare this new solution to the previous solution. The change will be reversed if the solution is far worse; otherwise the new solution will remain in place. "In this way the arrangement of the circular disks will be changed on a step-by-step basis, until a final result has been achieved."
It is remarkable that various solutions, which are almost as good as the solution, often have something in common. According to Schneider, some structures are frequently found. In the circular disk competition, for example, the largest circular disks are often found close together in the good solutions. What exactly the good solutions and the best solution have in common, is the subject of the scientists' own research, which is also to be published in Physical Review E.
The Research Unit Computer-based Research Methods in the Natural Sciences was newly established by the Johannes Gutenberg University so that the eminent position of the natural sciences in Mainz could be even better supported by efficient, innovative computer studies.