4.1 Einführung

Die Verwendung von Constraints ist eine vielfach eingesetzte Methode zur Repräsentation und Auswertung von Abhängigkeiten. Durch Constraints werden Relationen zwischen (Constraint-)Variablen definiert. Neben der Definition solcher ,,Beschränkungen`` werden Constraints eingesetzt, um die Werte von Variablen dynamisch den Anforderungen der Constraints entsprechend anzupassen (vgl. Syska und Cunis, 1991, S. 78). Constraints sind in diesem Sinne Randbedingungen, welche die Konsistenz der Variablenwerte in einem System sicherstellen. Sie können je nach Betrachtungsweise z.B. als Kontrollstruktur oder Suchproblem angesehen werden.

Ein Constraint besteht aus einer endlichen Menge von Variablen, die über eine Relation zueinander in Beziehung gesetzt werden. Jede Variable besitzt einen eigenen Wertebereich (Domäne). Der Lösungsraum ist das kartesische Produkt dieser Wertebereiche, und die Lösungsmenge selber eine Teilmenge dieses Raumes. Formal wird ein Constraint wie folgt definiert (vgl. Güsgen, 2000, S. 268):^4.1

Definition 4.1.1   (Constraint)
Ein k-stelliges Constraint C ist ein Paar bestehend aus einer Menge von Variablen $v_1,\ldots,v_k$ und einer entscheidbaren Relation R, wobei die $v_i$, $i = 1,\ldots,k$, Werte aus gegebenen Wertebereichen $D_i$ annehmen können und R eine Teilmenge von $D_1 \times \cdots \times D_k$ ist.

Constraints werden anhand der Anzahl der jeweils involvierten Variablen unterschieden. Constraints, die jeweils nur eine einzige Variable betreffen, d.h. im Regelfall einfache Wertezuweisungen sind, heißen unäre Constraints. Sind zwei Variablen zueinander in Relation gesetzt, so ist dies ein binäres Constraint, bei drei Variablen ein ternäres etc.

Sind sämtliche Abhängigkeiten zwischen einer Menge von Variablen jeweils in einem einzigen Constraint zusammengefasst, spricht man von totalen Constraints (vgl. Faltings, 1994, S. 365):

Definition 4.1.2   (totales Constraint)
Wenn zwischen einer Menge von Variablen $v_1,\ldots,v_k$ jeweils nur ein einziges Constraint C existiert, welches sämtliche Abhängigkeiten zwischen $v_1,\ldots,v_k$ beschreibt, so ist C ein totales Constraint (engl. total constraint).

Existieren mehrere Constraints, die über ihre Variablen zueinander in Beziehung stehen, d.h. Variablen aus einem Constraint sind gleichzeitig über eine Relation mit Variablen in einem anderen Constraint in Beziehung gesetzt, spricht man von einem Constraint-Netz, erstmals formalisiert von Montanari (1974). Ein Constraint-Netz ist also eine Menge von Randbedingungen für eine Menge von Variablen (vgl. Güsgen, 2000, S. 268):

Definition 4.1.3   (Constraint-Netz)
Ein Constraint-Netz auf den Variablen $v_1,\ldots,v_n$ ist eine Menge von Constraints $C_1,\ldots,C_m$, so dass die Variablen jedes Constraints eine Teilmenge von $v_1,\ldots,v_n$ sind.

Neben den in Abschnitt 3.6.2 ff. bereits eingeführten ENGCON-spezifischen Constraint-Arten Funktions-/Prädikat- und Tupel-Constraints, sowie den flexiblen Java-Constraints, gibt es viele weitere Arten von Constraints, die jeweils für bestimmte Domänen besonders geeignet sind. So werden z.B. spezielle räumliche Constraints zur Unterstützung des räumlichen Konfigurierens verwendet, temporale Constraints zur Beschreibung von Abhängigkeiten zwischen Zeitpunkten bzw. -intervallen bei Zeitplanungsproblemen (Scheduling), Sequenz-Constraints zur Repräsentation von DNA-Strängen in der Genforschung, Blocks-World-Constraints zur Planungsunterstützung, boolesche Constraints, in denen die Constraint-Variablen nur zwei Zustände annehmen können und über boolesche Operatoren verknüpft werden oder Constraints über bestimmte Datenstrukturen, z.B. über Bäume, sog. Tree-Constraints vgl. Günter, 1995b, S. 129 ff.; Marriott und Stuckey, 1999, S. 22 ff.; Tsang, 1993, S. 17 ff.. Alle aufgezählten Domänen bzw. Datenstrukturen weisen unterschiedliche Eigenschaften auf (Domänenelemente, Relationen), die von den jeweils eingesetzten speziellen Constraint-Solvern zum Auflösen der Constraints berücksichtigt werden.

Abbildung 4.1: Beispiele für unterschiedliche Constraint-Arten

Die Nutzung von Constraints wurde initiiert von David L. Waltz, der Constraints zur Analyse von Polyeder-Zeichnungen nutzte (vgl. Waltz, 1975). Neben Systemen zur Konfigurierung setzen seither zahlreiche Anwendungen Constraints ein, z.B. aus den Bereichen Analyse, Diagnose, Planung und zeitlichem Schließen (vgl. Freuder, 1997; Güsgen, 2000). Einen besonderen Stellenwert nimmt der Einsatz von Constraints für die logische Programmierung, insbesondere mit der Programmiersprache Prolog, ein. Dieser Zweig hat sich im Laufe der Zeit zu einem beinahe eigenständigen Forschungsgebiet entwickelt (vgl. Güsgen, 2000, S. 267). Die Idee der Logikprogrammierung, bzw. deklarativer Programmierung im Allgemeinen, dass durch den Programmierer festgelegt wird was gelöst werden soll anstatt wie etwas gelöst werden soll, steht dem Gedanken von Constraints sehr nahe (vgl. Barták, 1999b, S. 8). So werden beim Constraint Logic Programming (CLP) Constraints als eine Erweiterung der logischen Programmierung gesehen:^4.2 ,,Constraint Logic Programming began as a natural merger of two declarative paradigms: constraint solving and logic programming`` (Jaffar und Maher, 1994, S. 503).

Spezifische Constraints, die im Bereich Constraint Programming (CP), d.h. allgemein für die Programmierung von Lösungen für spezielle kombinatorische Problemstellungen mittels Constraint-Technologien, von besonderer Relevanz sind, werden von Systemen zur (logischen) Constraint-Programmierung explizit zur Verfügung gestellt. Die Propagationsregeln für diese Constraints werden i.d.R. separat und besonders effektiv implementiert.^4.3 Diese Art Constraints werden auch global constraints genannt, da sie i.A. mehr als zwei Variablen umfassen und dazu dienen, eine Menge kleinerer Constraints zur effektiveren Propagation zusammenzufassen. Die meisten CP- bzw. CLP-Systeme verfügen über eine Reihe von diesen fest vorgegebenen global constraints vgl. Barták, 2001, S. 12; Dechter und Rossi, 2003, S. 798.

Fußnoten

...^4.1

Die Notation der in diesem und den nachfolgenden Kapiteln aufgeführten Definitionen und Algorithmen wurde z.T. zugunsten einer einheitlichen Darstellung an die in dieser Arbeit verwendete Notation angepasst.

...^4.2

Der Prozess des Pattern-Matching während der Unifikation von Prolog wird durch Constraint Satisfaction erweitert bzw. ersetzt und erlaubt dadurch eine effiziente Verarbeitung von algebraischen Constraint-Ausdrücken innerhalb von logischen Programmiersprachen (vgl. Cohen, 1990; Pountain, 1995).

...^4.3

Beispielsweise all-different, cummulative, element (vgl. Marriott und Stuckey, 1999, S. 110 ff.).