6.3 Constraint-Lösungsstrategien

Flexibilität bzgl. der einzusetzenden Lösungsverfahren kann durch ein Konzept von modularen und austauschbaren Constraint-Lösungsstrategien erreicht werden. Zur Strukturierung des Constraint-Lösungsvorgangs wird dieser Prozess in drei Phasen eingeteilt:

1. Preprozessing

2. Konsistenzherstellung

3. Lösungssuche

Diese Phasen spiegeln sich innerhalb von Constraint-Lösungsstrategien wieder (vgl. Abbildung 6.1). In der ersten Phase wird ein Preprozessing des Constraint-Problems vorgenommen. Dies kann sich z.B. auf die Binärisierung eines Constraint-Netzes oder die Zerlegung von Constraints in primitive Constraints beziehen, um anschließend darauf aufbauende Lösungsalgorithmen anwenden zu können. In der zweiten Phase werden Filter- bzw. Konsistenzalgorithmen zur Einschränkung der Domänen der Constraint-Variablen angewendet. Da dies allein i.A. nicht zu einer Lösung des Constraint-Problems führt, können in einer dritten Phase Suchverfahren zum Auffinden von Lösungen in den reduzierten Wertebereichen eingesetzt werden.^6.2

Abbildung 6.1: Aufbau einer Constraint-Lösungsstrategie

Zu beachten ist, dass in jeder Phase mehrere Einträge innerhalb einer Lösungsstrategie existieren können. So ist es z.B. möglich, mehrere Preprozessing-Schritte auf ein Problem anzuwenden, bevor Verfahren aus der nächsten Phase zum Einsatz kommen. Dies gilt ebenso für Konsistenz- und Suchverfahren.

Während es für Konsistenzverfahren durchaus sinnvoll erscheint bspw. Knotenkonsistenz herzustellen, bevor ein Algorithmus zum Herstellen von Kantenkonsistenz eingesetzt wird, erschließt sich der Sinn mehrerer Einträge im Fall von Suchverfahren nicht sofort. Für den Fall allerdings, dass für eine geeignete Anwendung aus Effizienzgründen anstatt systematischer Suchverfahren lokale bzw. stochastische Suchverfahren zum Einsatz kommen, kann hierdurch die Unvollständigkeit lokaler Verfahren abgemildert werden: Wenn ein (lokales) Suchverfahren keine Lösung für ein Constraint-Problem gefunden hat, sich aber mehrere Einträge in der Phase für die Lösungssuche befinden, kann entsprechend das nächste Suchverfahren angewendet werden.^6.3

Ebenso ist es möglich, dass für eine Phase innerhalb einer Strategie keine Einträge existieren. Nicht für alle Konsistenz- und Suchverfahren ist ein Preprozessing erforderlich. Gleichfalls kann ein Suchverfahren auch ohne vorherigen Filteralgorithmus angewendet werden, insbesondere wenn das Suchverfahren bereits Filtermechanismen enthält. Sind für eine Anwendung keine exakten Lösungen sondern nur eingeschränkte Wertebereiche erforderlich, kann auf ein Suchverfahren in der dritten Phase verzichtet werden. Mehrere Beispiele für mögliche Constraint-Lösungsstrategien sind in Abbildung 6.2 zu sehen.

Die Verwaltung derartiger Constraint-Lösungsstrategien muss von einer Komponente vorgenommen werden, die in der Lage ist, aufgrund einer klaren Spezifikation die Zuordnung der jeweiligen Strategien zu einzelnen Teilproblemen des gesamten Constraint-Problems vornehmen zu können. Wie dies im Detail geschieht, wird im nächsten Abschnitt verdeutlicht.

Abbildung 6.2: Beispiele für Constraint-Lösungsstrategien

Fußnoten

...^6.2

In Bezug auf Problemstellungen mit intervallwertigen Domänen dienen Splitting-Verfahren der Suche nach kanonischen Lösungen (vgl. Abschnitt 5.3.2).

...^6.3

Lokale Suche wird aufgrund der Unvollständigkeit dieser Verfahren nicht im Zusammenhang der strukturbasierten Konfigurierung mit ENGCON umgesetzt.