Mathematische Methoden der Algorithmik

Lecture: Tuesday, 9:45 - 11:15, IZ 358
Big Tutorial: Wednesday, 13:15 - 14:45, PK 2.1 (biweekly) (starting 14.11.11)
Small Tutorial: Tuesday, 8:00 - 9:30, IZ 161 (biweekly)

First lecture: Wednesday, 2.11.11
First tutorial: Wednesday, 16.11.11

none

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.

Topics are:

1. Linear optimisation
2. Simplex algorithm
3. Duality
4. Integer optimization

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

• Hausaufgabenblatt Nr. 1: blatt1.pdf.
• Hausaufgabenblatt Nr. 2: blatt2.pdf.
• Hausaufgabenblatt Nr. 3: blatt3.pdf.
• Hausaufgabenblatt Nr. 4: blatt4.pdf, ZIMPL user guide, gerry1.zpl, gerry2.zpl.
• Hausaufgabenblatt Nr. 5: blatt5.pdf.

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:

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!