GLOB-CON: Regelbasierte Propagation von Globalen Constraints

Das Projekt behandelt die formal korrekte und effizient ausführbare Spezifikation der  Propagation von komplexen, grobalen Constraints durch Regeln. Ein Constraint-Satisfaction-Problem besteht aus einer Menge von Constraints, die von jeder Lösung erfüllt werden müssen. Derartige Probleme, unter anderem NP-vollständige, können durch Problemvereinfachungsansätze (Constraint-Propagation) kombiniert mit Suche gut gelöst werden. Insbesondere kann constraintspezifische Propagation kostengünstig zu einer erheblichen Reduktion des Suchraums führen und dadurch die Lösungszeit drastisch verkürzen.

Die Spezifikation und die korrekte Implementierung solcher Methoden verlangt jedoch tiefgehende Kenntnisse. Regeln haben sich als nützlicher Formalismus zur Beschreibung der Propagation von einfachen, primitiven Constraints erwiesen. Es gibt entsprechende regelbasierte Sprachen, etwa Constraint Handling Rules, und dazugehörige Implementierungen, durch die Verfahren zur Constraint-Propagation unmittelbar ausgeführt werden können. In den letzten Jahren wurden mehrere Methoden zur automatischen Erzeugung von Propagationsregeln aus deklarativen Definitionen von primitiven Constraints entwickelt.

Dieses Projekt untersucht die Spezifikation der Propagation von globalen Constraints durch Regeln und die automatische Erzeugung von regelbasierten Mechanismen zur Propagation solcher Constraints. Das Projekt verfolgt die klassische Idee der Erzeugung von ausführbaren Programmen aus formalen Spezifikationen.

Die Projektpartner und weitere Informationen finden Sie bei den Forschungprojekten.