Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Testing the "No Free Lunch Theorem" for Circle and Sphere Packings with MathOptimizer Professional

Frank Kampas
Organization: Physicist at Large Consulting

2007 Wolfram Technology Conference
Conference location

Champaign, IL


The "No Free Lunch Theorem" in global optimization (see wikipedia.org/wiki/No_free_lunch_in_search_and_optimization) states that roughly the same number of function evaluations must be performed to find a solution of a given (guaranteed) quality, no matter what approach is taken. We test this idea for circle and sphere packing problems by performing an initial optimization and then using local search techniques to improve the initial solution. These local search techniques involve swapping the position of the circles or spheres in order to improve the objective function, the radius of an enclosing circle or sphere. The different variations studied include swapping all pairs of adjacent sized circles or spheres, swapping all pairs, swapping adjacent sized pairs starting from the smallest pair, and performing the previously described swapping techniques either once or repeatedly until the objective function stops improving. The various techniques are themselves performed multiple times and the best objective function result is plotted versus time. The initial optimization and local searches are performed using MathOptimizer Professional, taking advantage of its ability to reuse machine-compiled code for function evaluation. The new graphics features in Mathematica 6, especially for three-dimensional plots, are employed to display our results.

*Applied Mathematics > Optimization
*Applied Mathematics > Visualization
*Wolfram Technology
*Wolfram Technology > Application Packages > Applications from Independent Developers > MathOptimizer Professional

Downloads Download Wolfram CDF Player

TestingTheNoFreeLunchTheorem.nb (992.2 KB) - Mathematica Notebook [for Mathematica 6.0]