Constraint - Techniken

In ConSolve^® werden Optimierungsprobleme als Auswahlprobleme spezifiert. Eine Lösung des Problems muss also für jede Variable aus ihren alternativen Belegungen genau eine zulässige Belegung auswählen. Hierbei dienen Bedingungen (Constraints) dazu, die Auswahl einzuschränken.

Die Zielfunktion bewertet die Qualität einer Variablenbelegung und identifiziert dadurch Lösungen des Optimierungsproblems. Bei ConSolve ergibt sich die Zielfunktion aus der Bewertung der definierten Bedingungen. Harte Bedingungen sind von einer Lösung des Optimierungsproblems unbedingt zu erfüllen. Gewichtete und unscharfe Bedingungen müssen von einer möglichen Lösung nicht zwangsläufig erfüllt werden, gehen jedoch in die Zielfunktion ein.

Zur Lösung eines Problems durchsucht ConSolve den Lösungsraum (Suchraum), indem Variablenbelegungen aufgezählt werden. Hierbei wird ein sogenannter Suchbaum aufgebaut. Während der Suche werden die Bedingungen ausgewertet (Propagierung), wodurch Variablenbelegungen, die keine Lösungen darstellen, frühzeitig erkannt und aus dem Suchbaum entfernt werden. Erst die Kombination dieser beiden Verfahren führt bei größeren Optimierungsproblemen zu einem akzeptablen Zeitverhalten. Die Suche nach einer Lösung soll anhand eines Beispiels erläutert werden:

Die obige Abbildung zeigt die Variablen A, B und C, die jeweils mit einer Ungleich-Bedingung miteinander verbunden sind. Jede der Variablen besitzt den Wertebereich "rot", "grün" und "blau". Bei der Suche werden Bedingungen ausgewertet, wodurch unzulässige Variablenbelegungen sofort erkannt werden. Hieraus ergibt sich folgenden Suchbaum, der sechs Lösungen enthält: 

Beispielsweise wird nach dem Belegen der Variable A mit dem Wert "rot" gleich erkannt, dass die Variable B nicht ebenfalls mit "rot" belegt werden kann (Ungleich-Bedingung zwischen A und B), wodurch der entsprechende Zweig aus dem Suchbaum gestrichen werden kann.
Wenn wir alternativ eine vollständige Baumsuche ohne Propagierung der Bedingungen durchführen, ergibt sich ein viel größerer Suchbaum aus 27 Variablenbelegungen. Die folgende Abbildung zeigt einen Ausschnitt dieses Suchbaums, bei dem ein Zweig (Variable A wird mit "rot" belegt) vollständig durchlaufen wird. 

Hier ist zu erkennen, dass innerhalb des Zweiges sieben unzulässige Lösungen aufgezählt werden, die jeweils zu einem Rücksprung im Baum (Backtracking) führen.