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

Algorithm Engineering

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)
ArtVorlesung/Übung
Dozent
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
LP4
SWS2+1
Ort & Zeit

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

Voraussetzungenkeine
ScheinerwerbErfolgreiche 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.lpLiest die Datei x.lp ein
optimizeLö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 solutionSCIP: 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