Time Magazine chooses computer algorithm for packing problems as one of "The 50 Best Inventions of 2009"

When it comes to packing, the scientists of Mainz University are unbeatable

09.12.2009

Time Magazine has nominated a computer algorithm for the optimization of packing problems as one of the 50 most important inventions made in 2009. The algorithm was developed at Mainz University by PD Dr. Johannes Josef Schneider, Professor Elmar Schömer, and André Müller. It solves the task of how to fit several  disks of different sizes into a circle in such a way that they take up as little room as possible. With his solution, Johannes Schneider was able to equal and even beat all world records set at an international competition for solving this problem. "Our algorithm is not only eminently suitable for solving circular disk problems, but it also solves any other packing problem. It can even be applied to problems arising in the fields of tour planning, production planning, or staff deployment planning," says Schneider.

Practical applications of the optimization algorithm are frequently found in the automobile industry: A computer may, for example, be used to determine the sequence in which various pre-assembled car bodies should be placed onto the conveyor belt for fina assembly so that production can take place as efficiently as possible. The group is currently doing research for a major German automobile manufacturer to find out how the volume of a car boot can best be used. Optimization algorithms may also be important for transport companies and in logistics. "We were very surprised and pleased to find that our packing algorithm had made it to the list of the 50 best inventions of the year, as compiled by the US new magazine Time," Schneider explains this special distinction.

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 p with a random arrangement," explains Dr. 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."