Rule-based specification, analysis and implementation of propagation algorithms for global constaints

• Applicant: Professor Dr. Thom Frühwirth
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 18899577

Der Inhalt dieses Projekts ist die formal korrekte und effizient ausführbare Spezifikation der Propagierung von komplexen, sogenannten globalen Constraints mit Hilfe von regelbasierten Programmen. Ein Constraint-Problem besteht aus einer Menge von Einschränkungen (Constraints), die von jeder Lösung erfüllt werden müssen. Solche Probleme, darunter NP-voIlständige, können durch Methoden zur Vereinfachung - der Constraint- Propagierung - in Kombination mit Suchverfahren gelöst werden. Constraintspezifische Propagierungsverfahren können den Suchraum massiv und mit geringem Aufwand reduzieren. Allerdings erfordert die Beschreibung und korrekte Implementierung dieser Verfahren besondere Expertise. Die Propagierung einfacher, elementarer Constraints kann durch Regeln beschrieben werden, die in Sprachen wie Constraint Handling Rules direkt ausgeführt werden können. Verschiedene Methoden zur automatischen Generierung solcher Regeln aus der Definition einfacher Constraints existieren. In diesem Projekt soll untersucht werden, wie Propagierungsverfahren für komplexe (globale) Constraints durch Regeln spezifiziert werden können, und unter welchen Bedingungen eine automatische Generierung der Regeln möglich ist. Dieser Projektvorschlag verfolgt damit das klassische Ideal vom Erzeugen effizient lauffähiger Programme aus formalen Spezifikationen im Bereich der Constraint-Propagierung. Es sind zu diesem Ziel weltweit bereits erste, allerdings begrenzte Vorarbeiten vorhanden. Es bietet sich aufgrund unserer Vorarbeiten und Forschungskontakte eine konkrete Chance, einen wesentlichen, international relevanten Beitrag leisten zu können.

• DFG Programme: Research Grants