1.1 Theoretische Grundlagen zur Constraint-Technik

In der Stundenplanung haben wir es mit Veranstaltungen und Räumen und periodischen Zeiträumen von i. d. R. einer Woche zu tun. Gegeben sind eine Anzahl Veranstaltungen wie z. B. Vorlesungen, Übungen usw. und eine Anzahl Räume. Das Ziel besteht nun darin, sämtliche Veranstaltungen (sogenannte Aktivitäten) auf die gegebenen Räume (sogenannte Ressourcen) über der Zeit zu verteilen. Das und nichts anderes ist Stundenplanung (engl. Timetabling). Das wäre ja noch einfach, wäre da nicht folgendes Problem: die Veranstaltungen können nicht einfach irgendwie auf die Räume über der Zeit verteilt werden – bei der Planung sind gewisse Nebenbedingungen (Beschränkungen oder engl. Constraints) zu beachten. Damit wird die Planung zum Planungsproblem. Im folgenden wollen wir unter einem Stundenplanproblem Stundenplanung unter Berücksichtigung von Beschränkungen verstehen.

Beispielsweise gilt es, die zur Zeit gültigen Studien- und Prüfungsordnungen in Betracht zu ziehen. Es ist bei der Planung z. B. zu beachten, daß Pflichtveranstaltungen des gleichen Studiensemesters zeitlich nicht parallel liegen dürfen. Weitere Nebenbedingungen sind die persönlichen Terminwünsche der Dozenten. Einige möchten z. B. nicht vor 10 Uhr morgens lehren, andere nicht montags und/oder freitags.

Doch Verfeinern wir unser Beispiel noch ein wenig: Alle Räume haben nicht die gleiche Ausstattung und unterscheiden sich in der Anzahl der Sitzplätze. Alle Veranstaltungen haben verschiedene Anforderungen an die Raumausstattung. Die Dozenten der Veranstaltungen schätzen die Anzahl ihrer Hörer und die sollte in den zugehörigen Raum hineinpassen.

Diese Nebenbedingungen werden vom jetzigen Stundenplan im großen und ganzen erfüllt und doch ist keiner so recht damit zufrieden Warum? Es gibt halt noch eine Reihe weiterer Nebenbedingungen, die aus einem durchschnittlichen Stundenplan einen guten machen. Darüber haben wir in der Projektgruppe ausgiebig nachgedacht und haben über 30 Arten von Nebenbedingungen gefunden, die ein guter Stundenplan erfüllen sollte. Wie die Situation an der Universität-Gesamthochschule Siegen tatsächlich aussieht, darüber mehr im Kapitel "Analyse".

Das Stundenplanproblem gehört zur Klasse der Zeitplanungsprobleme. Unter Zeitplanung (engl. scheduling) verstehen wir folgendes: Zuweisung von Aktivitäten auf Ressourcen über der Zeit. Bei der Stundenplanung sind die Veranstaltungen die Aktivitäten und die Räume die Ressourcen.

Ein Zeitplanungsproblem ist dann Zeitplanung unter Berücksichtigung von Beschränkungen (Constraints). Falls es bei einem gegebenen Zeitplanungsproblem eine Zeitplanung nach unserer Definition gibt (also eine konkrete Belegung der Ressourcen mit den Aktivitäten über der Zeit), die sämtliche Nebenbedingungen des Zeitplanungsproblems erfüllt, dann ist diese Zeitplanung eine Lösung des Problems.

Wir wollen festhalten, daß Zeitplanung nach der Definition einfach ist, weil Aktivitäten beliebig auf Ressourcen verteilt werden können. Das Lösen eines Zeitplanungsproblems hingegen stellt eine echte Herausforderung dar.

Aufgaben dieser Art sind in der Informatik als "Scheduling-Probleme" bekannt; sie zählen zu den NP-vollständigen Problemen (siehe Informatik-Duden). Für sie gilt allgemein, daß der Aufwand für das Auffinden einer optimalen Lösung exponentiell oder fakultativ mit der Länge der Eingabe (hier: Anzahl der Termine und Veranstaltungen) wächst. Ein Algorithmus, der in angemessener Zeit eine optimale Lösung berechnet, ist daher nicht bekannt.

Zeitplanungsprobleme wiederum gehören zu einer Klasse von Problemen, den sogenannten Constraint-Erfüllungsproblemen (engl. CSP – Constraint satisfaction problem). Alan Mackworth (zitiert in [Quibeldey-Cirkel, 1994]) definiert ein CSP folgendermaßen: Gegeben ist eine Menge V mit n Variablen {v₁, v₂, ..., v_n} ; jede Variable v_i besitzt einen individuellen Wertebereich (Domain) D_i mit den möglichen Werten, die diese Variable annehmen kann. Auf Teilmengen T_i von V sind Constraint-Relationen (im folgenden auch nur: Constraints) gegeben, die Teilmengen des kartesischen Produkts der Wertebereiche der Variablen in T_i sind. Die Lösungsmenge ist die größte Untermenge des kartesischen Produkts der Wertebereiche aller Variablen, so daß jedes n-Tupel in dieser Menge alle gegebenen Constraint-Relationen erfüllt. Wenn die Lösungsmenge leer ist, ist das CSP nicht erfüllbar.

Variablen und Constraints bilden einen Graphen, der auch Constraint-Netz genannt wird: die Variablen bilden die Knoten und die Constraints die Kanten. Constraints, die sich jeweils auf genau eine Variable beziehen, bezeichnet man als unäre Constraints. Ein Constraint, der auf n Variablen auferlegt ist, heißt n-ärer Constraint. Sind in einem Constraint genau zwei Variablen involviert, spricht man von binären Constraints. Einen erfüllten unären Constraint nennt man knotenkonsistent, einen erfüllten n-ärer Constraint pfadkonsistent und einen erfüllten binären Constraint kantenkonsistent.

Einen Algorithmus, der aus dem Anfangszustand eines CSPs eine Lösungsmenge generiert, also eine Lösungsstrategie umsetzt, nennt man einen Constraint-Solver. Man kann sich den Algorithmus eines Constraint-Solvers so vorstellen: Der Solver baut einen Baum auf, in dem jeder Knoten einer Variablen entspricht. Jede Kante, die von einer Variablen ausgeht, repräsentiert einen möglichen Wert aus ihrem Wertebereich. Unter möglichen Werten verstehen wir nur die Werte, die bezüglich aller Constraints noch sinnvoll sind, nachdem die Variablen auf dem Weg von der Wurzel des Baumes instantiiert worden sind. Bei n Constraint-Variablen hat der Baum genau die Höhe n (Knoten haben die Höhe 0 und Kanten einer Ebene die Höhe 1). Alle Knoten einer Ebene des Baumes (bis auf die letzte) entsprechen ein und derselben Variablen aus V. Die Knoten bzw. Blätter der letzten Ebene sind leer (sonst wären dort die Knoten der n+1. Variablen, doch die gibt es ja nicht). Der Solver startet nun einen sogenannten Baumdurchlauf (engl. tree traversal) beginnend an der Wurzel, die v₁ repräsentiert, und versucht einen Weg von der Wurzel bis zu einem Blatt der letzten Ebene zu finden. Jeder dieser Wege entspricht einer Lösung des CSPs.

Aufgrund der Anzahl der Knoten und Kanten (kombinatorische Explosion) in einem solchen Baum ist es unmöglich, den ganzen Baum auf einmal zu erzeugen (Speicher- und Zeitproblem) und dann den Baumdurchlauf durchzuführen. Daher ist es nur möglich, genau einen konkreten Weg durch den Baum zu betrachten und sich bei jeder Verzweigung an einem Knoten die Alternativen zu merken. Das ist notwendig, um eingeschlagene Wege zurückzugehen, falls der gerade betrachtete Weg nicht an einem Blatt auf der letzten Ebene des Baumes endet, sondern schon früher.

Das Ziel eines jeden Constraint-Solvers ist es, daß jeder Variablen v_i aus V ein Wert aus ihrem zugehören Wertebereich D_i so zugeordnet wird, daß alle Constraints erfüllt sind. Zu Beginn eines Lösungs-Algorithmus haben wir ausschließlich Variablen, denen noch kein Wert zugewiesen wurde. Ein allgemeiner Algorithmus eines Constraint-Solvers besteht aus folgender Schleife: Solange Variablen existieren, denen noch kein Wert zugeordnet wurde, wird 1. eine aus diesen Variablen ausgewählt, diese sei v*, 2. ein Wert aus dem Wertebereich von v* ausgewählt und v* zugewiesen (v* wird instantiiert) und 3. die sogenannte Constraint-Propagierung durchgeführt: Die Wertebereiche der noch nicht belegten Variablen, die über Constraint-Relationen mit v* verknüpft sind, werden soweit wie möglich verkleinert; der Suchraum wird reduziert. Tritt der Fall ein, daß der Wertebereich der ausgewählten Variable leer ist, wird das sogenannte Backtracking ausgeführt: die letzte Wertzuweisung und alle Änderungen, die danach erfolgt sind, werden rückgängig gemacht; der zuvor zugewiesene Wert wird aus dem Wertebereich der Variablen herausgenommen und der Algorithmus bei Schritt 2 fortgesetzt.

Bei der Auswahl eines Wertes aus dem Wertebereich einer Variablen wissen wir nicht, ob der Wert konsistent mit den Constraints ist, d.h. ob im Suchbaum die Verzweigung an diesem Knoten überhaupt zu einem Blatt in der letzten Ebene im Baum führt. Die Auswahl des Wertes sowie auch die Auswahl der als nächstes zu belegenden Variablen erfolgt nach einem Prinzip, von dem wir annehmen, daß es recht schnell zu einer Lösung unseres CSPs gelangt. Beispielsweise kann die Auswahl der Variablen nach der Reihenfolge der Variableneingabe erfolgen oder nach dem Prinzip, daß die Variable mit dem kleinsten Wertebereich als nächstes ausgewählt wird. Ebenso kann man bei der Selektion eines Wertes aus dem Wertebereich einer Variablen nach bestimmten Kriterien vorgehen.

Eine solche Lösungsstrategie eines CSP ist eine sogenannte Heuristik [Informatik-Duden, 1993], d. h. die Strategie ist ein Lösungsverfahren, das nicht auf wissenschaftlich gesicherten Erkenntnissen, sondern auf Hypothesen, Analogien oder Erfahrungen aufbaut. Die Güte einer solchen Strategie ist deshalb auch nicht beweisbar, sondern kann nur durch wiederholte Experimente an typischen Problemstellungen geschätzt werden.

Mit Constraint-Programmierung (engl. CP – Constraint Programming oder CLP – Constraint Logic Programming), die von einer Programmiersprache unterstützt werden muß, läßt sich ein CSP rechnergerecht formulieren und lösen. Constraint-Programmierung trennt die Problemrepräsentation von der Problemlösungsstrategie. Ein Constraint-Programmiersystem stellt demnach Mittel zur Verfügung, um ein CSP in Form von Variablen und Constraints darzustellen, und hält Constraint-Solver bereit, die Problemlösungsstrategien umsetzen.

Schließlich werden alle genannten Verfahren und Bezeichnungen unter dem Oberbegriff Constraint-Technik zusammengefaßt.

Die ersten erhältlichen Constraint-Programmiersysteme waren Erweiterungen von Prolog mit Constraint-Solvern. In Prolog werden Anfragen durch Unifikation gelöst. Unifikation ist ein Constraint-Solver für Prolog-spezifische Fragen. Daher ist auch verständlich, warum gerade Prolog durch Constraint-Programmiersysteme erweitert wurde [Puget, 1994] [Informatik-Duden, 1993]. Durch die Ergänzung der Unifikation können Constraint-Solver für andere Problembereiche wie lineare Gleichungssysteme oder Variablen mit endlichen Wertebereichen (z. B. Integer-Variablen) realisiert werden. Die Sprache Prolog ist ein guter Kandidat, um ein solches Constraint-Programmiersystem zu implementieren, da sie bereits logische Variablen und effizientes Suchen mittels Backtracking bietet.

Nachteile einer Prolog-Implementierung eines Constraint-Solvers ist die schwierige Anbindung an grafische Benutzungsoberflächen oder Datenbanken, da Prolog von Natur aus eine Interpretersprache ist und nach wie vor in der Wirtschaft ein Nischendasein führt. Die Ergänzung der weit verbreiteten Sprache C++ mit einem Constraint-Programmiersystem vereinigt die Vorteile der Constraint-Programmierung mit denen der Integration anderen Komponenten einer Applikation, wie etwa Datenbank- und Benutzungsschnittstellen, ohne die Nachteile einer Prolog-Lösung zu übernehmen.

Der einzige zu Projektbeginn verfügbare C++-Aufsatz war das Produkt "Solver" von Ilog. Mittlerweile ist das konkurrierende System "CHIP" von Cosytec ebenfalls als C++-Klassenbibliothek erhältlich. In unserem Projekt setzen wir das Constraint-Programmiersystem Ilog Solver ein.

WWW-Designer: Hans Peter Kunz. Letzte Änderung: 12-03-1998.