Djinni: Approximating NP-Complete Problems, Fast

Robert Hansen, Research Associate, University of Iowa
Tristan Thiede, Research Assistant, The University of Iowa

Track: Programming
Date: Friday, July 28
Time: 10:45am - 11:30am
Location: D136

In late 2004, two researchers at the University of Iowa (Drs. Jeffrey Ohlmann and Barrett Thomas) were working on developing new algorithms for approximating solutions to extraordinarily difficult problems. Implementing these algorithms required Robert Hansen joining the team, and in mid-2005 Djinni 1.0 was released.

In late 2005 work began on Djinni 2.0, which uses a new architecture, has stronger support for Python scripting, builds on more platforms, and is more efficient. During the 2.0 cycle Tristan Thiede was brought onto the team, and after much hacking Djinni 2.0 was released on February 11, 2006.

Djinni 2.0 is not just an algorithm; it is a framework for local search, where any local search technique or problem can be introduced as a module in the system.