Constraintprogrammierung

Die Constraintprogrammierung (englisch Constraint Programming, 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.

Constraints

→ Hauptartikel: Constraint

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: $F=1{,}8\times C+32$. Durch die Belegung der Variablen mit Werten wird das Constraint entweder erfüllt (true) oder nicht erfüllt (false). Die Umrechnung ist beispielsweise mit $F=68$ und $C=20$ erfüllt, während $F=1$ und $C=1$ das Constraint offensichtlich verletzt.

Das Constraint $X^{2}\geq 0\land X\in \mathbb {R}$ ist unabhängig von einer Wertebelegung immer erfüllt, das Constraint $X^{2}<0\land X\in \mathbb {R}$ dagegen nie.

Ein weiteres Beispiel ist ein pythagoreisches Tripel, das von drei natürlichen Zahlen $x$, $y$ und $z$ gebildet wird, welche die Seitenlänge eines rechtwinkligen Dreiecks angeben. Eine Constraint-basierte Modellierung solcher Tripel über dem Definitionsbereich $\{1,\dots ,100\}$ kann durch folgende Constraint-Konjunktion dargestellt werden:

$x^{2}+y^{2}=z^{2}\land x,y,z\in \{1,\dots ,100\}$

Eine mögliche Lösung ist das Tripel $(x,y,z)=(3,4,5)$.

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.

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.

Constraint-Systeme

Aus formaler Sicht stellen Constraints spezielle prädikatenlogische Formeln dar, mit deren Hilfe man Eigenschaften von Problemen und deren Lösung beschreibt. 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.

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.

• 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.

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.

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.

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.

Typische Constraint-logische Sprachen, die eine Generalisierung der logischen Sprachen darstellen, sind zum Beispiel ECLiPSe, CHIP und 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.

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.

Ein Beispiel für eine Constraint-imperative Programmiersprache ist Turtle. 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 angereichert:

• 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.

• Nutzer-definierte Constraints: Diese abstrahieren von Constraints wie Funktionen von Ausdrücken. Sie dienen der Definition häufig auftretender Muster, um den Programmieraufwand zu verringern und die Lesbarkeit der Programme zu verbessern.

• Constraint-Löser: Diese sind dafür verantwortlich, die mit require ausgeführten Constraints zu verwalten und Lösungen zu berechnen. Sind die Constraints im Speicher zusammen unerfüllbar, wird eine Exception ausgelöst.

Die C++-Bibliothek Turtle++ hat viele Konstrukte von Turtle übernommen und für eine harmonische Integration in C++ angepasst.

Constraint-objektorientierte Programmierung

Die Einbettung von Constraints in objektorientierte Programmiersprachen wird als Constraint-objektorientierte Programmierung bezeichnet.

Für die objektorientierte Programmiersprache Java existiert die Bibliothek firstcs zur objektorientierten Constraintprogrammierung. Ihr Kern bildet eine Klasse namens CS (Constraint-Solver). Jedes Objekt dieser Klasse besitzt und verwaltet Variablen über endlichen, ganzzahligen Domänen und Constraints über diesen Variablen. Aufgrund des objektorientierten Designs der Bibliothek ist es möglich, in einem Programm mehrere Constraint-Systeme gleichzeitig zu generieren und zu manipulieren, die jedoch gegenwärtig nur voneinander unabhängige CSP repräsentieren können. Des Weiteren gibt es die Klassen Domain, Variable, Constraint und die Unterklassen von Constraint, die um den Kern herum die grundlegenden Methoden und Verfahren zur Modellierung und Lösung von CSP bereitstellen.

Als ein weiterer Ansatz entstand die Programmiersprache Kaleidoscope, die Constraints in einen imperativen objektorientierten Stil integriert. Es ist eine der ersten Sprachen, bei der Constraints zwischen Attributen verschiedener Objekte spezifiziert werden.

Des Weiteren ist Koalog eine bekannte Java-Bibliothek für Finite-Domain-Constraints und Ilog-Solver eine C++-Bibliothek für verschiedene Domänen.

Anwendungen

Im wissenschaftlichen Bereich findet die Constraint-basierte Programmierung beispielsweise bei der Verarbeitung natürlicher Sprache, im maschinengestützten Beweisen, in der Analyse von Programmen und in der Molekularbiologie Anwendung. In der industriellen Praxis sind typische Anwendungen Optimierungsprobleme und Scheduling-Aufgaben, Schaltkreis-Design und -Verifikation, graphische Systeme und Benutzerschnittstellen.

Literatur

• Frédéric Benhamou, Narendra Jussien, Barry O’Sullivan: Trends in constraint programming. John Wiley and Sons: London/Newport Beach, 2007.
• Thom Frühwirth, Slim Abdennadher: Constraint-Programmierung: Grundlagen und Anwendungen. Springer-Verlag: Berlin/Heidelberg, 1997, ISBN 3-540-60670-X
• Petra Hofstedt, Armin Wolf: Einführung in die Constraint-Programmierung. (Springer eXamen-press) Springer-Verlag: Berlin/Heidelberg, 2007, ISBN 978-3-540-23184-4
• Francesca Rossi, Peter van Beek, Toby Walsh (Hrsg.): Handbook of Constraint Programming. Elsevier: Amsterdam et al., 2006.

Weblinks

• Association for Constraint Programming