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

Mathematische Methoden der Algorithmik

Semester
Wintersemester 2011/2012
Wintersemester 2019/2020Wintersemester 2018/2019Wintersemester 2017/2018Wintersemester 2016/2017Wintersemester 2015/2016Wintersemester 2014/2015Wintersemester 2013/2014Wintersemester 2012/2013Wintersemester 2010/2011Wintersemester 2009/2010Wintersemester 2008/2009
ModulnummerINF-ALG-03
Veranstaltungsnr.INF-ALG-003, INF-ALG-004
StudiengängeMaster Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR GruppeALG (Prof. Fekete)
ArtVorlesung/Übung
Dozent
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
Assistent
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
LP5
SWS2+1+1
Ort & Zeit

Vorlesung: Dienstag, 9:45-11:15, IZ 358
Große Übung: Mittwoch, 13:15-14:45, PK 2.1 (14-täglich) (ab 14.11.11)
Kleine Übung: Dienstag 8:00-9:30, IZ 161 (14-täglich)


Beginn

Erste Vorlesung: Mittwoch, 2.11.11
Erste Übung: Mittwoch, 16.11.11

Voraussetzungen

keine

Scheinerwerb

Studienleistung: Erfolgreiche Bearbeitung von mindestens 50 Prozent der Hausaufgaben. Es wird fünf Übungsblätter á 10 Punkte geben. 16 der insgesamt 50 erreichbaren Punkte entfallen auf das Lernportfolio.

Prüfungsleistung: Mündliche Prüfung nach dem Semester; der genaue Termin wird gegen Semesterende erdoodelt.

Inhalt

Themenbereiche sind:

  1. Lineare Optimierung
  2. Simplexalgorithmus
  3. Dualität
  4. Ganzzahlige Optimierung

Literatur/Links
  1. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.
  2. V. Chvatal, Linear Programming, Freeman, New York, 1983.
  3. B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2002.
  4. Skript aus dem WS08/09 gibt es im geschützten Bereich.

Einzeltermine

Genaue Termine der großen Übung: 16.11., 30.11., 14.12., 11.1., 25.1., 8.2.

Genaue Termine der kleinen Übung: 22.11., 6.12., 20.12., 17.1., 31.1., 7.2.

Aktuelles

Mailingliste

Es gibt eine Mailingliste zu dieser Vorlesung, in die Ihr vom Dozenten eingetragen werdet. Falls dies nicht passiert ist, meldet Euch bitte bei Dr. Alexander Kröller.

Hausaufgaben

Materialien:

... befinden sich in einem geschützten Bereich.

Hinweise zu LP-Lösern

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 31.01.2012, 19:20 von Dr. Alexander Kröller
printemailtop