An Optimization Engine based on Constraint Programming and Local Search


Welcome to the DragonBreath engine's homepage!

Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. The "final" mirror of our development repository (with documentation, source code, and examples) can be downloaded below.



The engine is built to solve search problems, i.e., problems for which you don't really know how to construct a solution but can describe what potential parts a solution can consist of and which restrictions must be satisfied by the parts / the parts' constellation. Parts can be variables as well as structural components. In addition, you can specify a preference between different solutions, i.e., solve optimization problems. Examples for such problems are scheduling, action planning and configuration.
The engine is specifically designed to support:
  • Real time: Instead of switching to an off-line mode for calculating your solution, the engine provides you with solution approximations of increasing quality over time.
  • Dynamics: Even during the search for a solution, changes to your problem specification can easily be incorporated. Also, an existing solution can be adapted in case of changes instead of having to start a complete recalculation.
  • Domain Knowledge: If you know some particular strategies/heuristics for your specific domain, it's easy to plug in this knowledge to speed up the search process.
  • Extendibility: The engine is built in a very modular way, and if you need to express constraints that are not part of the base distribution, you can add these on your own.
The engine is based on artificial intelligence techniques such as constraint programming and local search. More details can be found in the publications Using Global Constraints for Local Search and Applying Local Search to Structural Constraint Satisfaction.



The engine is a Java package that can be queried/accessed via Java or a graphical interface (an XML-based stream interface is also planned). All software components are available for download and can be used under terms of a permissive non-copyleft free software license.
However, please keep in mind that the download below is simply a snapshot of the files as they were last checked into our repository when the development of our engine was discontinued. Quite a few features and files might thus be unstable, hardly documented, or even described in a wrong/outdated way!
Note that the repository snapshot is not simply a slightly extended version of version ALPHA-2, which was the previous "packaged" version that we published, but extended in many major ways (the relation of 77,256 vs. 27,464 lines of source code is probably a good indication).

Please extract the ".zip"-file below into a new directory and follow the instructions given in the "README" file of the "engine" directory:



The screenshots below show a very preliminary view of the engine's graphical visualization.
Screenshot 1: Variables, constraints and costs (DragonBreath engine version 0.1)
Screenshot 2: Extensible constraints and object constraints (DragonBreath engine version 0.3)
Screenshot 3: Graphical user interface for planning (DragonBreath engine version ALPHA-3)


Last update:
May 31, 2005 by Alexander Nareyek