Constraint Programming (CP) ist ein deklaratives Programmierparadigma, das sich besonders zur Lösung kombinatorischer Probleme eignet. Im Gegensatz zur imperativen Programmierung, bei der der Lösungsweg Schritt für Schritt beschrieben wird, beschreibt man in CP die Eigenschaften der gewünschten Lösung in deklarativer Weise durch eine Menge von Variablen, deren Wertebereiche (Domänen) und Beziehungen zueinander (Constraints). Hierbei werden Constraints als Bedingungen verstanden, welche zulässigen Werte oder Kombinationen von Werten in einem bestimmten Problem beschreiben[1].
Ein CP-Solver sucht dann nach einer Belegung aller Variablen, die alle definierten Constraints erfüllt. Dies geschieht typischerweise durch eine Kombination aus Suche[2], z.B. durch Backtracking, und Constraint Propagation.
Propagatoren sind ein wichtiger Teil von CP-Solvern, da ihre Aufgabe es ist, die Domänen der beteiligten Variablen zu reduzieren, indem sie Werte entfernten, die unmöglich Teil einer Lösung sein können.
Beispiel: Für das Constraint mit den Definitionsbereichen und würde der Propagator erkennen, dass niemals sein kann und niemals sein kann. Die Definitionsbereiche werden auf und reduziert. Propagatoren arbeiten lokal, aber durch ihre Interaktion können weitreichende Schlussfolgerungen über den gesamten Suchraum gezogen werden. Wenn ein Propagator einen Definitionsbereich verkleinert, werden alle anderen Constraints, die diese Variable nutzen, versuchen den Suchraum ihrerseits zu reduzieren.
Wüsten, Jana Kristina. (2025). Vergleichende Analyse von A*-Suche und Constraint Programming zur Lösung des Rush-Hour-Puzzles. Bachelorarbeit TU Berlin. https://doc.neuro.tu-berlin.de/bachelor/2025-BA-JanaWüsten.pdf ↩︎
Wikipedia contributors. (n.d.). Constraint satisfaction. In Wikipedia. Retrieved January 14, 2025, from https://en.wikipedia.org/wiki/Constraint_satisfaction ↩︎
Bessiere, Christian. (2006). Constraint Propagation. Technical Report LIRMM 06020, University of Montpellier. https://ics.uci.edu/~dechter/courses/ics-276/spring-19/reading/constraint-propagation-bessiere.pdf ↩︎