Vorlesung Constraint-Programmierung
Dozent
Dr. Sebastian Will
Termine
-
V: wöchentlich Di 11-13 Uhr in MMR, Geb.106 (ab 24.10.06)
-
Ü: wöchentlich Do 16-17 Uhr in SR 02 006, Geb. 106 (Erste
Übung am 02.11.06)
Thema und Ziel
Die Constraint-Programmierung (CP) ist eine Technik zur Modellierung und
Lösung
kombinatorischer (Optimierungs-)probleme.
CP wurde von der ACM als eine der strategischen Richtungen in der
Informatik identifiziert.
Kombinatorischen Probleme sind allgegenwärtig. Einige Beispiele sind
Assigning und Scheduling von
Ressourcen oder Design von Prozessorinstruktionen.
Am unserem Lehrstuhl wird CP auf Probleme aus der Bioinformatik, insbesondere
Proteinstrukturvorhersage und Sequenzalignment unter Nebenbedingungen, angewandt.
Die Vorlesung wird einen Einblick in Grundlagen und Anwendung der
Constraint-Programmierung bieten. Neben einem Verständnis der fundamentalem
Konzepte, werden Fähigkeiten in der Modellierung und der Lösung
kombinatorischer Probleme mit CP vermittelt, sowie ein Verständnis der
Vorteile und Grenzen dieser Technik.
Für die praktischen Übungen kommt das moderne
Constraintprogrammiersystem Gecode mit seinem Java-Interface Gecode/J zum
Einsatz.
Die Vorlesung lehnt sich an die Vorlesung Constraint-Programming (2G1515)
an, die im Frühjahr 2006 von Christian Schulte am KTH - Royal
Institute of Technology gehalten wurde.
Voraussetzungen
Von Vorteil bzw. voraussgesetzt sind
- Grundlegende Kenntnisse in Algorithmen
- Grundkenntnisse in Logik
- Programmierkenntnisse in Java
Software
- Gecode/J
Gecode/J wird für die Bearbeitung der praktischen Übungsaufgaben
benötigt.
Das System wird auf den Poolrechnern im &Uumbungsraum zur Verfügung
stehen.
Um das System auf dem eigenen Rechner zu installieren, finden sich
hier
eine Installationsanleitung und die benötigten Dateien.
Benutzung auf den Poolrechnern:
- Setze Umgebungsvariablen (am besten in .bash_profile)
- export PATH=/usr/local/java/64/1.5/bin:$PATH
- export CLASSPATH=.:/usr/local/gecode/64/1.1.0/GecodeJava.jar
- export LD_LIBRARY_PATH=/usr/local/gecode/64/1.1.0
Übung
In der Übung werden Übungsaufgaben besprochen und es wird zu den Aufgaben
Hilfestellung gegeben.
-
Übung am 2.11.06
Die erste Übungsstunde soll vor allem in das System Gecode/J
einführen.
Geplant ist mit dem Problem SEND+MORE=MONEY (Money) und Erweiterungen
dieses Problems zu experimentieren. Insbesondere wird das bestehende
Beispiel-Programm zu Money auf die Optimierungsvariante SEND+MOST=MONEY
erweitert. Ausserdem soll das Problem DONALD+GERALD=ROBERT implementiert werden.
Zusätzlich biete ich bei Bedarf Hilfestellung an, die Software
Gecode/J auf mitgebrachten Notebooks zu installieren.
-
Übung am 9.11.06 und 16.11.06
Aufgaben bis zur nächsten Übung am 16.11.06/23.11.06:
Die Aufgaben sind diesem Übungsblatt von Christian Schulte und Mikael Lagerkvist entnommen.
Die Bearbeitung der Aufgaben ist freiwillig. Ich rate aber dringend
dazu, wenigstens einige der
Aufgaben zu bearbeiten. Dies dient dem Verständnis der Vorlesung und
ist für das Erlernen der praktischen Anwendung der
Constraintprogrammierung notwendig.
-
Schreibe ein Programm das 9x9 Sudokus löst. (Dies entspricht Aufgabe 5
des Übungsblatts.)
In SudokuSpecs.java finden sich
einige Beispielsudokus sowie brauchbare Hilfsfunktionen.
- Modelliere n-Queens mit 0/1 Variablen.
- Implementiere das Modell für n-Queens mit 0/1
Variablen. (Enstpricht Aufgabe 7)
- Ist Propagation "compositional"? Bearbeite Aufgabe 8.
In der Übung soll mit den Aufgaben begonnen werden.
-
Übung am 23.11.06
Geplant ist die Besprechung der Hausaufgaben und Definition von
Propagatoren für max(x,y)=z und x+y=z.
Here is a solution for both
propagators, please have a look and think about the included questions.
-
Übung am 06.12.06
We are discussing the solutions of the propagators for max and addition
again. Then, we discuss the following:
-
How can we generalize the propagator for x+y=z to arbitrary
linear equations?
-
Is propagation order relevant?
-
If a propator p is not idempotent by itself, is p^n idempotent for some n>1?
-
Propagate "x less than y" and "y less than x" on paper.
The assignments of the last two lessons are adopted from this
Assignment of Christian Schulte and Mikael Lagerkvist.
-
Übung am 18.01.07
We discuss the assignment 2 about magic sequences from this
Work sheet of Christian Schulte and Mikael Lagerkvist.
In the (last part of the) assignment you shall implement a special
propagator, you can use this scaffold for your implementation.
Fertige Bearbeitungen werden auf Wunsch korrigiert oder können mit mir
besprochen werden.
Folien
Es werden in der Vorlesung die (englischsprachigen) Folien von Christian
Schulte verwendet.
Literatur
Krzystof R. Apt. Principles of Constraint Programming. Cambridge University
Press, 2003.
Christian Schulte. Programming Constraint Services. LNAI 2302, Springer,
2002.
Sebastian Will
