Mit Constraint Satisfaction wird die Suche nach einer global konsistenten Wertebelegung für alle Constraint-Variablen eines CSP bezeichnet, d.h. es müssen alle Constraints erfüllt sein. Ein Constraint wird erfüllt, wenn die Wertezuweisungen zu den jeweils involvierten Variablen den Anforderungen der Constraint-Relation genügen (vgl. Güsgen, 2000, S. 269):
Es genügt allerdings nicht, wenn jedes Constraint für sich genommen gültige Wertekombinationen aufweist, d.h. konsistent ist. Dies ist aber häufig die Vorstufe, um zu einer globalen Lösung eines CSP zu gelangen, welche ,,aus einer eindeutigen Belegung der Variablen mit genau einem Wert aus dem jeweiligen Wertebereich besteht, so dass alle Constraints erfüllt sind`` (Kolbe, 2000, S. 36). Die Lösung eines CSP lässt sich formal folgendermaßen definieren (vgl. Güsgen, 2000, S. 269):
Das Auflösen eines CSP stellt sich als Suche im Lösungsraum dar, welcher durch alle möglichen Lösungen aufgespannt wird. Jede Variable kann dabei Werte aus ihrem Wertebereich annehmen.5.8 Je nach Fragestellung können unterschiedliche Ergebnisse erwünscht sein. So kann sich zum einen die Frage nach der Existenz einer Lösung stellen, zum anderen, wenn es mehrere Lösung gibt, die Frage nach deren Anzahl bzw. nach deren konkreten Ausprägungen. Weiterhin ist bei Optimierungsproblemen die Frage nach der besten Lösung von Interesse (vgl. Dechter, 1999, S. 195). Da bei einem CSP die Frage nach der Lösbarkeit gleichbedeutend mit der Suche nach der ersten Lösung ist, reduziert sich die Aufgabenstellung hier auf die Suche nach einer Lösung bzw. nach allen möglichen Lösungen (vgl. Kolbe, 2000, S. 37). Die Berechnung erfolgt durch spezielle Lösungsverfahren, die innerhalb von Constraint-Solvern implementiert werden. Durch Constraint-Solver wird die Trennung von Problemstellung und Lösungsverfahren realisiert, da sie generelle Mechanismen zum Auflösen von kombinatorischen Problemen, formalisiert als CSP, bieten. In ihnen können unterschiedliche Algorithmen Verwendung finden, die je nach Bedarf für bestimmte Problemstellungen optimiert sein können, und die ebenfalls nach Bedarf ein entsprechendes Antwortverhalten bieten. Die meisten Algorithmen zum Lösen eines CSP sind Varianten bzw. Kombinationen von Lösungsverfahren, die sich in zwei Klassen einteilen lassen: Konsistenzverfahren und Suchverfahren:
Stochastische Suchverfahren werden oftmals auch lokale Suchverfahren (engl. local search), (heuristische) Reparaturverfahren oder GSAT-Verfahren (Greedy SATisfiability) genannt. Im Gegensatz zu systematischen Verfahren, folgen stochastische Suchverfahren keinem ,,Pfad`` zur schrittweisen Belegung der Constraint-Variablen mit Werten durch den Suchraum, sondern bewegen sich aufgrund von lokalen Kriterien und Zufallswerten. Die Suche beginnt mit einer zufälligen Wertezuweisung an alle Variablen. Schritt für Schritt wird diese Wertezuweisung durch Auswertung der vorliegenden Relationen ,,verbessert``, bis keine bzw. möglichst nur noch wenige Konflikte vorliegen. Stochastische Verfahren finden häufig auch in sehr großen Suchräumen relativ schnell eine Lösung. Zudem liegt zu jedem Zeitpunkt eine, wenn auch suboptimale, Lösung vor, da alle Variablen mit Beginn der Suche mit einem Wert belegt sind.5.10 Allerdings besteht die Gefahr, dass die Algorithmen bereits bei einem lokalen Minima terminieren und keine global gültige Lösung finden.5.11 Stochastische Verfahren sind heuristische, nichtdeterministische und unvollständige Suchverfahren, d.h. sie können im Gegensatz zu systematischen Verfahren nicht garantieren, dass eine oder gar alle Lösungen eines Problems gefunden werden. Beispiele für bekannte Ansätze sind Hill Climbing, Min-Conflicts, Simulated Annealing, Tabu-Suche und Genetische Algorithmen (vgl. Barták, 1999a,b; Minton et al., 1992; Tsang, 1993; Russel und Norvig, 2002).
Für bestimmte Anwendungen, für die frühzeitig eine teilweise korrekte Lösung nützlicher ist, als eine vollständige Lösung, deren Berechnung um ein vielfaches länger dauern würde, können unvollständige Suchverfahren sinnvoll sein. Sie stehen allerdings nicht im Fokus dieser Arbeit. Für Konfigurierungsaufgaben kann eine Reduktion des Lösungsraums durch Konsistenztechniken zum Ausschließen einer Vielzahl von fehlerhaften Konfigurationen sehr sinnvoll sein, wenn es, wie in ENGCON, übergeordnete Inferenzmechanismen zur weitergehenden Konfigurierung gibt. Ebenfalls wünschenswert ist die Berechnung einer oder aller globaler Lösungen, bzw. einer möglicherweise sogar optimalen Lösung, als Ergebnis eines vollständigen Suchverfahrens. Fatal für den Konfigurierungsvorgang könnte es sich allerdings auswirken, wenn der Constraint-Solver potentiell falsche Lösungen als Ergebnis einer unvollständigen Suche liefern würde. Diese suboptimalen Lösungen, in denen nicht alle Constraints erfüllt sind, würden, wenn dem nicht durch gesonderte Mechanismen Rechnung getragen wird,5.12 unweigerlich in Konfigurierungskonflikten münden.
Daneben gibt es noch weitere spezielle, strukturbasierte Verfahren zum Auflösen von FCSPs. Strukturbasierte Verfahren nutzen neben Such- und Konsistenzverfahren besondere Eigenschaften der Topologie des Constraint-Graphen, um effizient zu einer Lösung zu gelangen vgl. Dechter, 1999, S. 196; Van Hentenryck und Saraswat, 1996, S. 708. Bekannte Verfahren sind das Tree-Clustering (vgl. Dechter und Pearl, 1989) und die Cycle-Cutset-Methode, auch Cutset Conditioning (vgl. Dechter, 1990a, S. 292 ff.) genannt. In Abhängigkeit von der Problemstellung können mit diesen Verfahren gute Ergebnisse erzielt werden. Sie sind allerdings ebenso wie stochastische Suchverfahren stark abhängig von der Problemstellung, da die Effektivität dieser Verfahren von der Struktur des jeweiligen Constraint-Graphen und den zum Einsatz kommenden Heuristiken abhängt. Sie sind daher nicht so ,,stabil`` bzw. ,,robust`` wie systematische Suchverfahren, die durch Konsistenztechniken unterstützt werden, insbesondere wenn alle Lösungen eines Problems gesucht werden.
Auf eine genauere Betrachtung von stochastischen und strukturbasierten Verfahren wird daher in dieser Arbeit verzichtet. Konsistenzverfahren und systematische Suchverfahren zur Auflösung von FCSP, bzw. der Kombination beider, wird in den folgenden beiden Abschnitten der Vorzug gegeben. Im nachfolgenden Abschnitt 5.2.3 werden eine Reihe von lokalen Konsistenzgraden und Algorithmen zu deren Herstellung vorgestellt. In Abschnitt 5.2.4 ff. hingegen werden systematische Suchverfahren zum Auffinden von globalen Lösungen beschrieben.