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

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: ${\displaystyle 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 ${\displaystyle F=68}$ und ${\displaystyle C=20}$ erfüllt, während ${\displaystyle F=1}$ und ${\displaystyle C=1}$ das Constraint offensichtlich verletzt.

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

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

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

Eine mögliche Lösung ist das Tripel ${\displaystyle (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 Werten oder beliebigen anderen Mengen wie Buchstaben oder Wörtern.

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

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

Einzelnachweise

1. ↑ 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.
2. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 51–52.
3. ↑ 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.
4. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 58.
5. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 60.
6. ↑ Für eine formale Definition von Constraints siehe Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 54–55.
7. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 53–55.
8. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 177.
9. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 57, 71.
10. ↑ 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.
11. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 127–133.
12. ↑ 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.
13. ↑ The ECLiPSe Constraint Programming System
14. ↑ Coystec: CHIP V5
15. ↑ SICStus: SICStus Prolog
16. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 141–162.
17. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185.
18. ↑ catamorph.de: Turtle – eine constraint-imperative Programmiersprache (Memento des Originals vom 8. April 2016 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/catamorph.de
19. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 185–192.
20. ↑ Hofstedt, Wolf: Einführung in die Constraint-Programmierung. 2007, S. 199–215.
21. ↑ Gus Lopez, Bjorn Freeman-Benson, Alan Borning: Kaleidoscope: A Constraint Imperative Programming Language. In: Brian Mayoh, Enn Tyugu, Jaan Penjam: Constraint Programming. Springer-Verlag, S. 313–329.
22. ↑ 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.