6.4.3 Heterogenes Constraint-Lösen

Für die Berechnung von globalen Lösungen ist ein übergeordneter Constraint-Lösungsmechanismus erforderlich. Wenn aus den möglicherweise teils überlappenden Teillösungen unterschiedlicher Strategien Gesamtlösungen generiert werden sollen, stellt dies ein neues kombinatorisches Problem dar: ein extensionales, n-äres Meta CSP:

Definition 6.4.5   (Meta Constraint Satisfaction Problem)
Ein Meta CSP besteht aus unterschiedlichen Teilproblemen $P_{Meta} = \{P_1,\ldots,P_m\}$ und setzt eine endliche Menge von Variablen $V = \{v_1,\ldots,v_n\}$ mit assoziierten Wertebereichen $D = \{D_1,\ldots,D_n\}$ mit $\{v_1 : D_1,\ldots,v_n : D_n\}$ in Relation zueinander. Für jedes Teilproblem $P_1,\ldots,P_m$ existiert eine Menge von konsistenten Teillösungen $T = \{T_1,\ldots,T_m\}$, wobei jede Teillösung in $T_i$, $i \in \{1,\ldots,m\}$, eine Teilmenge der Variablen $v_j \in V$, $j \in \{1,\ldots,n\}$ mit einem jeweils zugeordnetem Wert $d_j \in D_j$ beinhaltet.

Jede Teillösung umfasst sämtliche involvierte Variablen des Teilproblems und stellt dadurch eine extensional repräsentierte Relation zwischen diesen Variablen dar.^6.10 Aufgabe eines übergeordneten Constraint-Lösungsverfahrens ist es, aus den n-ären Relationen konsistente Lösungen zu generieren.

Wenn durch die Constraint-Verfahren einer Lösungsstrategie im Rahmen eines Teilproblems ein Wert einer Variable aus deren Domäne entfernt wird, geschieht dies deshalb, weil dieser Wert inkonsistent mit einem Constraint ist, und auf keinen Fall Teil einer Lösung sein kann. Das heißt die Teillösungen unterschiedlicher Strategien ergänzen sich nicht, sondern schließen sich gegenseitig aus. Eine mögliche Lösung des Meta CSPs besteht deshalb darin, die Teillösungen einer Strategie jeweils mit den Teillösungen der anderen Strategien zu kombinieren und auf widersprüchliche oder konsistente Wertebelegungen zu überprüfen. Dies entspräche allerdings einem Generate-SPMamp;-Test-Vorgehen (vgl. Abschnitt 5.2.4.1).

Aus Effizienzgründen sollte stattdessen ein systematisches Suchverfahren zur Anwendung kommen. Eine vollständige Suche muss durch sukzessives, systematisches Belegen aller Variablen, durch Testen, ob die jeweils aktuelle (Teil-)Belegung von allen Teillösungen unterstützt wird und durch Backtracking im Fall von Inkonsistenzen systematisch Lösungen anhand der existierenden Relationen in den Teillösungen generieren. Das Lösungsverfahren ist umso aufwendiger, je mehr Teillösungen das Constraint-Problem aufweist. In Problemen mit niedriger Lösungsdichte, bezogen sowohl auf die Teillösungen als auch auf die Gesamtlösungen, ist die Lösungssuche effizienter. Gegebenenfalls bietet sich eine Unterstützung des Meta-Constraint-Solvers durch intelligente Suchverfahren an (z.B. durch eine Backjumping-Variante, vgl. Abschnitt 5.2.4.3).

Die Effizienz der globalen Lösungssuche kann zudem gesteigert werden, wenn weitere bestehende Inkonsistenzen vor der Initiierung des Suchvorgangs durch Ausnutzung des in den Teillösungen vorhandenen Wissens eliminiert werden. Bezogen auf ein spezifisches Problem stellt die Aufzählung aller möglichen Lösungen globale Konsistenz hinsichtlich der Wertebereiche dar. Für die vorhandenen Teillösungen bedeutet dies, dass sich die Wertebereiche der Constraint-Variablen ggf. weiter einschränken lassen. Dies resultiert daraus, dass sich mögliche Teillösungen nicht addieren, sondern sich gegenseitig ausschließen und ggf. Inkonsistenzen identifizieren: Werte, die nicht innerhalb einer Teillösung als gültige Belegung auftauchen, sind als inkonsistent herausgefiltert worden und dürfen dementsprechend bei Überlappungen der Constraint-Netze auch in keiner anderen Teillösung respektive einer globalen Lösung vorkommen. Entsprechend können aus Teillösungen eingeschränkte Wertebereiche abgeleitet werden. Ein Algorithmus muss folgendermaßen vorgehen:

1. Die ursprünglichen Wertebereiche der Variablen werden in einer temporären Struktur zwischengespeichert.

2. Für alle Teilprobleme und jeweils für alle Variablen v des aktuellen Teilproblems gilt: Alle Werte für v, die im Vergleich zur kopierten Domäne nicht in der aktuellen Teillösung enthalten sind, können ebenfalls nicht Teil einer Lösung in anderen Teillösungen sein. Die entsprechenden, einzelnen Teillösungen (anderer Constraint-Lösungsstrategien bzw. Teilprobleme), die trotzdem eine derartige Belegung für v enthalten, sind zu entfernen.^6.11

3. Zur Vermeidung redundanter Such- und Vergleichsvorgänge sind jeweils Wertebelegungen, nach denen bereits gesucht worden ist, aus den zwischengespeicherten ursprünglichen Wertebereichen zu entfernen. Anschließend erfolgt die Überprüfung der nächsten Wertebelegung, bis sämtliche Variablen in allen Teilproblemen überprüft worden sind.

Abbildung 6.10: Algorithmus zur Unterstützung eines Meta-Constraint-Solvers.

Ein Algorithmus, der zur Unterstützung eines Meta-Constraint-Solvers aufgrund der vorhandenen Teillösungen inkonsistente Teillösungen entfernt, ist in Abbildung 6.10 zu sehen. Durch die Vorgehensweise des Algorithmus wird kein spezifischer Konsistenzgrad hergestellt, da keine Wertekombinationen verglichen und auf Konsistenz überprüft werden. Durch einen Algorithmus, der oben beschriebene (Teil-)Relationen entfernt, werden lediglich die Wertebereiche der Variablen der einzelnen Teillösungen angeglichen - in diesem Fall anhand extensional repräsentierter Relationen.

Ebenso können in Bezug auf das Meta CSP in weiteren Algorithmen Konsistenzverfahren zur Vereinfachung eingesetzt werden. Die Anwendung geht allerdings mit einer hohen Komplexität einher, da das Meta CSP durch n-äre, extensionale Relationen - den (vollständigen) Teillösungen - repräsentiert wird. Die Komplexität des Problems ist abhängig davon, wieviele Variablen an den einzelnen Teillösungen beteiligt sind. Eine Teillösung, die z.B. zwanzig Variablen umfasst, würde entsprechend die Behandlung eines 20-stelligen Constraints bedeuten.

In Bezug auf Konsistenz- und Suchverfahren, die auf das Meta CSP angewendet werden, ist weiterhin zu beachten, dass ggf. heterogene Constraints innerhalb eines heterogenen Constraint-Problems verarbeitet werden müssen. Dies sind Constraints, die sowohl Variablen mit finiten als auch infiniten Wertebereichen gleichzeitig beschränken. Die entsprechenden Konvertierungsmethoden, d.h. Diskretisierungen und Überführungen von finiten Wertebereichen in kontinuierliche Intervalldomänen, sind zu berücksichtigen und die entsprechenden Lösungsalgorithmen anzupassen.

Grundsätzlich problematisch in Bezug auf ein Meta CSP sind Lösungsverfahren, die unvollständig sind. Dies sind Suchverfahren, die nicht alle Lösungen eines (Teil-)Problems berechnen, sondern z.B. aus Effizienzgründen lediglich die Erstbeste. Werden solche Lösungsverfahren eingesetzt, so kann auch insgesamt die Vollständigkeit nicht garantiert werden, d.h. es können mögliche Lösungen für ein Problem verloren gehen. Bezogen auf einen Meta-Constraint-Solver bedeutet dies, dass es äußerst unwahrscheinlich werden kann eine globale Lösung zu finden, wenn für jedes Teilproblem max. eine einzige Teillösung generiert wird.

Weiterhin ist zu beachten, dass in allen Phasen des Lösungsvorgangs und in allen Strategien die Inkrementalität der Lösungsverfahren gewährleistet sein muss. Das heißt, dass bei einer erneuten Propagation mit zusätzlichen Constraints und Variablen die vormals erstellten Constraint-Netze nicht erneut instantiiert werden müssen. In Bezug auf Preprozessingverfahren sind hinzukommende Variablen und Constraints unkritisch. Das Hinzufügen neuer (umfassender) Variablen für eine Binärisierung von FD-Constraints ist ebenso wie das Hinzufügen neuer Variablen bei einer Zerlegung von (Intervall-)Constraints in primitive Constraints voneinander unabhängig in jedem Teilproblem inkrementell möglich. Auf Konsistenz- und Suchverfahren trifft dies ebenfalls zu. Die anwachsenden Constraint-Netze müssen innerhalb der Strategien von einer Phase zur nächsten ,,durchgereicht`` werden. Ob Inkrementalität dabei von den einzelnen Constraint-Verfahren selbst angeboten wird, oder ob dies ggf. eine geeignete (Wrapper-)Schnittstelle simuliert (z.B. für eingebundene Fremdsysteme), ist für YACS unerheblich. Einzelne Constraint-Solver werden als Black Box aufgefasst. Die im Rahmen dieser Arbeit umzusetzenden Constraint-Lösungsverfahren sollten allerdings inkrementell anwachsende Constraint-Netze von sich aus unterstützen.

Fußnoten

...^6.10

Anstatt einer n-dimensionalen Matrix kann eine Teillösung zur Vereinfachung, und analog zur Repräsentation von extensionalen (Tupel-)Constraints in ENGCON, als Tabelle mit der Anzahl Spalten aufgefasst werden, wie Variablen im jeweiligen Teilproblem existieren, und mit der Anzahl Zeilen, wie gültige Relationen in Form von einzelnen Teillösungen existieren.

...^6.11

Entspricht dem Löschen einer Zeile aus der Tabelle mit der Menge der Teillösungen für ein Teilproblem.