Die Constraintprogrammierung (, CP) ist ein Programmierparadigma, das seit Mitte der 1980er Jahre entwickelt wird und als Weiterentwicklung der logischen Programmierung entstanden ist. Die Constraint-basierte Programmierung erlaubt die Integration von Constraints und ihren Lösungsmechanismen in eine Programmiersprache. Mittlerweile ist sie ein eigenständiger Bereich der künstlichen Intelligenz und hat vielfältige Anwendungsgebiete in Praxis und Wissenschaft.
Bei der Constraintprogrammierung beschreibt der Nutzer das Problem auf deklarative Weise, während der Lösungsprozess aus Nutzersicht in den Hintergrund tritt. Dieser wird vom Constraint-Löser übernommen. Für Eugene Freuder stellt das Paradigma deshalb die bisher größte Annäherung an den „Heiligen Gral“ der Programmierung dar: Der Nutzer statuiert das Problem, der Computer löst es.Eugene C. Freuder: In Pursuit of the Holy Grail. In: Constraints 2 (1), 1997, S. 57–61; Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 206.
Constraints
Der Begriff Constraint bedeutet in etwa Zwang oder Nebenbedingung. Es handelt sich um spezielle prädikatenlogische Formeln, die Bedingungen oder Einschränkungen beschreiben. Im mathematischen Sinn sind damit auch Nebenbedingungen gemeint, wie sie beispielsweise bei der Lösung mathematischer Optimierungsprobleme Anwendung finden.
Man kann zum Beispiel die Umrechnungsformel von Grad Celsius in Grad Fahrenheit als ein Constraint auffassen: . Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit und erfüllt, während und das Constraint offensichtlich verletzt.
Das Constraint ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint dagegen nie.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 51–52.
Ein weiteres Beispiel ist ein pythagoreisches Tripel, das von drei natürlichen Zahlen , und gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem Definitionsbereich kann durch folgende Constraint-Konjunktion dargestellt werden:
Eine mögliche Lösung ist das Tripel .Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 205.
Erfüllbarkeit und Lösungen Nachdem man ein Problem durch Constraints beschrieben hat, möchte man herausfinden, ob die Constraints erfüllbar sind. Zusätzlich können mögliche Lösungen von Interesse sein. Die Fragen nach der Erfüllbarkeit von Constraints und nach konkreten Lösungen sind eng miteinander verbunden. Ist ein Constraint erfüllbar, so gibt es mindestens eine Lösung. Allerdings gestaltet sich die Berechnung einer Lösung oft komplizierter als die Feststellung der Erfüllbarkeit.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 58.
Eine „naive“ Herangehensweise zur Entscheidung der Erfüllbarkeit und zur Berechnung konkreter Lösungen wäre, alle möglichen Belegungen der Variablen mit Werten durchzuprobieren. Allerdings ist die Anzahl möglicher Belegungen oft sehr groß oder unendlich, sodass diese Vorgehensweise scheitert. Deshalb kommen in vielen Situationen spezielle Algorithmen zur Behandlung von Constraints zum Einsatz.
Constraint-Löser sind Algorithmen, die Tests und Operationen auf Constraints zur Verfügung stellen. Diese können häufig nicht nur die Erfüllbarkeit prüfen und konkrete Lösungen berechnen, sondern auch weitere Operationen auf Constraints durchführen.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 60.
Constraint-Systeme Aus formaler Sicht stellen Constraints spezielle prädikatenlogische Formeln dar, mit deren Hilfe man Eigenschaften von Problemen und deren Lösung beschreibt.Für eine formale Definition von Constraints siehe Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 54–55. Dazu gehören Gleichungen und Ungleichungen über Zahlen, aber auch andere Ausdrücke über Zahlen, boolesche Werte oder beliebige andere Mengen wie Buchstaben oder Wörter.
Constraint-Löser funktionieren in der Regel nur auf einer speziellen Klasse von Constraints. Diese werden durch Constraint-Systeme klassifiziert. Dadurch lassen sich den Constraint-Systemen passende Lösungsmechanismen zuordnen.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 53–55.
Typische Constraint-Systeme sind:
Lineare Gleichungssysteme: eine Menge linearer Gleichungen mit einer oder mehreren Unbekannten, die alle gleichzeitig erfüllt sein sollen. Um ein Gleichungssystem zu lösen, kann auf eine Vielzahl von Lösungsverfahren zurückgegriffen werden, z. B. das gaußsche Eliminationsverfahren.
Lineare Optimierung: die Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Ein Algorithmus, der in der Praxis häufig zur Lösung solcher Probleme Anwendung findet, ist das Simplex-Verfahren.
Boolesche Constraints: Boolesche Gleichungen, deren Variable entweder die Gültigkeit einer Aussage (true) oder deren Ungültigkeit (false) repräsentieren. Ein Löser für Boolesche Constraints ist grundlegend für alle Probleme, die als aussagenlogische Erfüllbarkeitsprobleme formuliert sind. Normalerweise unterstützt ein Boolescher Constraint-Löser logische Operationen wie Negation, Konjunktion, Disjunktion, Implikation und Äquivalenz.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 177.
Finite-Domain-Constraints: Diese haben die Eigenschaft, dass den beteiligten Variablen von vornherein endliche Wertebereiche (engl. finite domains) zugeordnet sind. Dieses Constraint-System wurde in der Forschung eingehend untersucht. Es hat in der Praxis große Bedeutung bei der Lösung kombinatorischer Probleme, z. B. zur Behandlung von Planungs-, Diagnose- und Konfigurationsproblemen.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 57, 71.
Constraint-basierte Programmierung Die Constraint-basierte Programmierung erlaubt die Integration von Constraints und ihren Lösungsmechanismen in eine Programmiersprache. Darüber hinaus ermöglicht sie in der Regel die Definition neuer Constraints. Constraint-Bibliotheken erlauben die funktionale und syntaktische Erweiterung einer existierenden Sprache um Constraints unter Ausnutzung existierender Sprachkonzepte. Eine Constraint-basierte Sprache ist eine semantische Erweiterung einer existierenden Sprache um neue Konzepte und Auswertungsmechanismen bis hin zu einem vollständigen Neuentwurf.Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 220.
Ursprünglich entwickelte sich die Constraint-basierte Programmierung als Erweiterung der logischen Programmierung. Mittlerweile ist sie ein eigenständiger Bereich der künstlichen Intelligenz und hat vielfältige Anwendungsgebiete in Praxis und Wissenschaft.
Constraint-logische Programmierung Die logische Programmierung arbeitet auf Basis einer Wissensdatenbank, aus der die Lösung von Anfragen hergeleitet wird. Bei der Auswertung von Anfragen werden die Prädikate mit Hilfe der Resolution abgeleitet. Constraint-logische Programme unterscheiden sich von logischen Programmen nur insofern, als sie in den rechten Seiten der Klauseln und in Anfragen neben logischen Prädikaten auch Constraints zulassen, die mit Hilfe von Constraint-Lösern auf Erfüllbarkeit überprüft werden.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 127–133.
Die Syntax Constraint-logischer Programme unterscheidet sich nicht wesentlich von logischen Programmen. Es sind lediglich auch Constraints in den rechten Seiten der Regeln und in den Anfragen zulässig. Während logische Prädikate weiterhin durch Unifikation behandelt werden, werden die zusätzlichen Constraints gesammelt, in den Constraint-Speicher übertragen und von einem Constraint-Löser behandelt. Constraint-logische Programme lassen oft verschiedene Constraint-Domänen (z. B. FD-Constraints, arithmetische Constraints oder boolesche Constraints) mit entsprechenden Lösungsverfahren zu, die dann beispielsweise in Form von Bibliotheken vorliegen.Petra Hofstedt: Kapitel Constraints. In: Günther Görz, Josef Schneeberger, Ute Schmid (Hrsg.): Handbuch der Künstlichen Intelligenz. 5. überarbeitete und aktualisierte Auflage. Oldenbourg Verlag: München, 2014, S. 221.
Typische Constraint-logische Sprachen, die eine Generalisierung der logischen Sprachen darstellen, sind zum Beispiel ECLiPSeThe ECLiPSe Constraint Programming System, CHIPCoystec: und SICStus-PrologSICStus: SICStus Prolog.
Nebenläufige Constraint-logische Programmierung Die nebenläufige Constraint-logische Programmierung (engl. Concurrent Constraint Logic Programming, CCLP) integriert das Konzept der Nebenläufigkeit in die Constraint-logische Programmierung. Nebenläufigkeit ist die Eigenschaft eines Systems, mehrere Berechnungen, Anweisungen oder Befehle gleichzeitig ausführen zu können. Das System verzichtet dadurch auf Sequentialisierung. Dies ist dann möglich, wenn die betreffenden Aktionen voneinander kausal unabhängig sind, d. h. keine Aktion das Resultat einer anderen benötigt. Unabhängige Aktionen können entweder in beliebiger Reihenfolge sequentiell abgearbeitet werden oder echt parallel auf mehreren Rechnern gleichzeitig ausgeführt werden.
Das Modell der nebenläufigen Constraint-Programmierung kann auch mit partiellen Informationen über Variablenbelegungen arbeiten. Statt konkreter Daten für Variablen können auch Bedingungen auf diesen festgelegt werden.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 141–162.
Eine multiparadigmatische Programmiersprache, die unter anderem deklarative, parallele und Constraint-basierte Ansätze vereint, ist beispielsweise Oz.
Constraint-imperative Programmierung Die Constraint-imperative Programmierung vereinigt die beiden Paradigmen Constraintprogrammierung und imperative Programmierung. In imperativen Sprachen beschreibt der Programmierer, wie ein gegebenes Problem durch eine Sequenz von Anweisungen gelöst wird. Sie eignet sich besonders zur Modellierung von zeitlichen Abläufen. Dagegen konzentriert sich der Programmierer in der Constraintprogrammierung auf das Was, d. h., er beschreibt das Problem durch deren Eigenschaften in Form von Constraints. Die Kombination der imperativen Programmierung mit deklarativen Constraints stellt somit eine besondere Herausforderung dar.Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185.
Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle.catamorph.de: Diese entstand als eine einfache imperative Basissprache und wurde zunächst um funktionale Konzepte wie Funktionen höherer Ordnung erweitert. Danach wurde sie mit vier wesentlichen Konzepten zur Constraint-Programmierung angereichertHofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185–192.:
Constraint-Variablen: Diese unterscheiden sich von „normalen“ imperativen Variablen, deren Werte durch Zuweisungen festgelegt werden, dadurch, dass ihre Werte durch Constraints festgelegt bzw. eingeschränkt werden. Constraint-Variablen werden auch als deklarative Variablen bezeichnet.
Constraint-Anweisungen: Eine Constraint-Anweisung kann mehrere durch den and-Operator verknüpfte Constraints enthalten. Mit Ausführung der require-Anweisung werden die Constraints zum Constraint-Speicher des Constraint-Lösers hinzugefügt. Der Löser prüft die Erfüllbarkeit der Constraint-Konjunktionen und weist eine Lösung den Constraint-Variablen zu.