312603 BI - Projekt (BI-Pjs) (SoSe 2005)

BI-Projekt SS 2005: Constraint Programming
Ausgangssituation:
Zur Lösung von kombinatorischen Optimierungsproblemen existieren verschiedene Ansätze. Die traditionellen optimierenden Verfahren, wie z.B. Branch & Bound-Verfahren, Dynamische Programmierung oder Schnittebenenverfahren liefern zwar optimale Lösungen, sind aber mit akzeptablen Aufwand nur für kleine Instanzen einsetzbar. Heuristische Verfahren sind entweder als Tailored Heuristics (d.h. auf eine Problemstellung spezialisiert) oder als Meta-Heuristiken formuliert. Mit ihnen können zwar größere Instanzen gelöst werden, allerdings kann i.d.R. keine Aussage über die Qualität der gefundenen Lösung gegeben werden. Vor diesem Hintergrund wird in den letzten Jahren wieder eine Technik diskutiert, die ihre Ursprünge in der Logik-Programmierung der späten 70er Jahre hat: das Constraint Programming. Die Grundidee besteht darin, die in den Restriktionen implizit enthaltenen Informationen zur Verkleinerung des Lösungsraums einzusetzen. Insbesondere können schnell scharfe Schranken ermittelt werden, die eine Suche, z.B. mittels eines Branch & Bound-Verfahrens oder eines lokalen Suchverfahrens wesentlich effektiver gestalten. Mittlerweile ist dieses Forschungsgebiet so stark erschlossen worden, dass die Standardsolver durchgängig Schnittstellen zum Constraint Programming anbieten, Tagungen dazu stattfinden und eine Zeitschrift ?Constraints-An International Journal' herausgegeben wird.

Aufgabe:

• Erarbeiten der theoretischen Grundlagen des Constraint Programming
• Einarbeiten in das Programm ECLIPSE
• Implementieren ausgewählter kleiner Problemstellungen mit ECLIPSE

Zielsetzung:
Die Teilnehmer sollen sich gemeinsam den Funktionsumfang von ECLIPSE erschließen, kleinere Anwendungen nachvollziehen und zum Abschluss eigene Programme schreiben.

Vorgehen:
Ende Februar wird eine Vorbesprechung durchgeführt, bei der die Teilnahme verbindlich festgelegt wird.

Zu erbringende Leistungen:

• Vorträge zur generellen Vorgehensweise des Constraint Programming
• Vorträge zur Umsetzung in ECLIPSE
• Beteiligung an der Diskussion und aktive Mitarbeit
• Programmierung 'Ihrer' Modelle
• Schriftliche, abschließende Ausarbeitung, in der Sie

a) Ihre Vorgehensweise begründen
b) Ihr Modell verständlich dokumentieren
c) die mit Ihrem Ansatz erreichten Ergebnisse darstellen

Linkliste

Homepage und Beispiele zu Eclipse:
http://www-icparc.doc.ic.ac.uk/eclipse/examples/index.html

Material zum Buch von Marriott/Stuckey:
http://www.cs.mu.oz.au/~pjs/
http://www.cs.mu.oz.au/~pjs/book/book.html
http://www.cs.mu.oz.au/~pjs/book/progs.html

Im Gegensatz zu unseren bisherigen BI-Projekten soll dieses Projekt bereits zum Ende des Sommersemesters abgeschlossen sein, d.h. die Abschlusspräsentation ist für Ende Juli vorgesehen. Das Programm ECLIPSE kann ab sofort am Lehrstuhl entliehen werden. Neben den mit dem Programm gelieferten Handbüchern (im pdf-Format) stehen auf den in der Linkliste angegebenen Seiten weitere und umfassende Informationen, Beispiel-Dateien und Power-Point-Präsentationen zur Verfügung.

Teilnahmevoraussetzungen, notwendige Vorkenntnisse

Voraussetzungen:

• Vordiplom und Grundlagen BI
• Erfolgreiche Teilnahme an der Vorlesung: Optimierungsmethoden
• Für Studenten mit Wahlfach UFO genügt es, wenn sie die Vorlesungen Netzplantechnik oder Lagerhaltungstheorie erfolgreich absolviert haben.

Anmeldung:
Parallel zur Anmeldung über die Homepage Spitta bitten wir die Interessenten sich im Sekretariat U9-141 bei Frau Becker bis zum 4. Februar in die dort ausliegende Interessentenliste einzutragen.
Achtung: Die Anmeldung über die Homepage Spitta ist unbedingt erforderlich. Die in Sekretariat ausliegende Interessentenliste dient nur unserer Planung.
Teilnehmerzahl: 16

Literaturangaben

Klein, R., Constraint Programming, in: Stadtler, H./Kilger, C., Supply Chain Management and Advanced Planning, Springer, Berlin/Heidelberg/New York, 2000, S. 353-359

Marriot, K., Stuckey, P.J., Programming with Constraints-An Introduction, MIT Press, Cambrige u.a., 1998

Milano, M. (Ed.), Constraint and Integer Programming, Kluwer Academic Publishers, Boston/Dordrecht/London, 2004

Tsang, E., Foundations of Constraint Satisfaction, Academic Press, London u.a., 1993

Wallace, M., Novello, S., Schimpf, J., ECLiPSe: A Platform for Constraint Logic Program-ming, Working Paper, Imperial College, London 1997, http://www-icparc.doc.ic.ac.uk/-eclipse/reports