TU BRAUNSCHWEIG
| Carl-Friedrich-Gauß-Fakultät | Informatik
Informatikzentrum

Algorithm Engineering

Semester Sommersemester 2009 [ Andere Semester: Sommer 16 · Sommer 13 · Sommer 11 ]
Modulnr. INF-ALG-05
Veranst.Nr. INF-ALG-009, INF-ALG-010
Studieng. Master Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR Gruppe(n) ALG (Prof. Fekete)
Art Vorlesung/Übung
Dozent
Photo Dr. Alexander Kröller
Ehemaliger Juniorprofessor
LP 4
SWS 2+1
Ort & Zeit

Vorlesung: Mittwoch, 14:15 - 14:45, IZ 251.
Übung: Montag, 16:45 - 18:15, IZ 251. (Einzelne Termine s.u.!)

Voraussetzungen keine
Scheinerwerb Erfolgreiche Bearbeitung der Hausaufgaben und erfolgreiche Teilnahme an der mündlichen Prüfung.
Inhalt

Algorithm Engineering hat sich in jüngster Zeit als eigenständiges Teilgebiet der Algorithmik etabliert. Die klassische Algorithmik konzentriert sich hauptsächlich auf theoretische Analysen unter oft stark vereinfachenden, unrealistischen Voraussetzungen. Im Algorithm Engineering versucht man dagegen praxisrelevante Aspekte soweit wie möglich bei dem Entwurf, der Implementierung und der Analyse von Algorithmen zu berücksichtigen. Im Mittelpunkt steht dabei ein von falsifizierbaren Hypothesen getriebener Kreislauf aus Entwurf, Analyse, Implementierung, und experimenteller Bewertung von praktikablen Algorithmen. Realistische Modelle, für Maschinen und Anwendungen, sowie Algorithmenbibliotheken und Sammlungen realer Eingabeinstanzen erlauben eine zusätzliche Kopplung an Anwendungen.

Übungstermine

Die Übung findet offiziell "14-tägig" statt. Das ist leider aufgrund von Feier- und Abwesenheitstagen meinerseits so nicht umsetzbar. Daher hier die genauen Daten:

20.4., 11.5., 25.5. 15.6., 29.6., 6.7.

Materialen

Vorlesungen: 01, 02, 03, 04, 05, 06, 07, 08a, 08b, 08c, 08d, 09-10
Übungen: 01
Übungsblätter: 01 (Doodle-Daten, schule.txt), 02

Hinweise zu Linearer Programmierung

Ihr könnt euch hier einen IBR-Account anlegen. Damit könnt ihr euch auf unimator.ibr.cs.tu-bs.de via SSH einloggen. Darauf laufen die diversen Tools, z.T. muss man aber einen Pfad angeben. An der Kommandozeile startet man sie via

cplex
/usr/local/zibopt/bin/scip
/usr/local/zibopt/bin/soplex
/usr/local/zibopt/bin/zimpl

Die ZIB Optimization Suite ist freie Software und kann hier bezogen werden. CPLEX ist kommerziell. Insbesondere die Dokumentation von ZIMPL könnte hilfreich sein.

Die wichtigsten Befehle an der CPLEX/SCIP-Kommandozeile lauten:

read x.lp Liest die Datei x.lp ein
optimize Löst das gelese Problem (oder mit Aküfi: opt)
display solution variables - CPLEX: Zeigt die Lösung an (oder mit Aküfi: di so va -)
display solution SCIP: Zeigt die Lösung an (oder mit Aküfi: di so)

Das CPLEX LP-Format ist im Wesentlichen selbsterklärend. Die Dateiendung muss .lp lautet, da daran manche Solver das Format erkennen.

Hier ist ein erklärendes Beispiel:

Maximize   \ hier kann auch "Minimize" stehen,
           \ Der "\" ist das Kommentarzeichen und dient auch
           \ dazu, Zeilen umzubrechen
  2x + 4 hallo - 0.8172 x_99

Subject To
  \ Hier kommen die Nebenbedingungen:
  2x + 4y   >= 1
  99z - 99a =  4
  2a + 2b   <= 99

Integers
  \ Hier werden die Variablen gelistet, für die eine
  \ ganzzahlige Zuweisung gefordert ist:
  z1
  z2
  z3

Binary
  \ Hier werden Binärvariablen gelistet (die dann
  \ in der Integers-Section oben nicht mehr aufgeführt
  \ werden müssen.
  b1
  b2
  b3

Bounds
  \ Hier wird der zulässige Zahlenbereich der
  \ Variablen definiert:
  x1 >= 0
  0 <= x2 <= 999

End      \ muss am Ende stehen!


aktualisiert am 30.06.2009, 17:48 von Martin Lorek
printemailtop