TU BRAUNSCHWEIG
| Carl Friedrich Gauß Faculty | Department of Computer Science
Informatikzentrum

Algorithm Engineering

SemesterSummer 2009 [ Other terms: Sommer 16 · Sommer 13 · Sommer 11 ]
Module # INF-ALG-05
Event #INF-ALG-009, INF-ALG-010
ProgrammesMaster Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR Group(s)ALG (Prof. Fekete)
TypeVorlesung/Übung
Lecturer
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
Credits4
Hours2+1
Time & Place

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

Prerequisiteskeine
CertificatesErfolgreiche Bearbeitung der Hausaufgaben und erfolgreiche Teilnahme an der mündlichen Prüfung.
Content

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!

last changed 2009-06-30, 17:48 by Martin Lorek
printemailtop