Mathematische Methoden der Algorithmik

Vorlesung: Mittwoch, 13:15-14:45, PK 2.2
Große Übung: Montag, 15:00-16:30, PK 2.2 (14-täglich) (ab 8.11.10)
Kleine Übung: Donnerstag 15:00-16:30 IZ 251 (14-täglich start am 18.11.10) and Freitag 11.30-13.00 IZ 251

Erste Vorlesung: Mittwoch, 03.11.10
Erste Übung: Montag, 08.11.10
Erste kleine Übung: Donnerstag, 18.11.10

keine

Erfolgreiche Bearbeitung von mindestens 50 Prozent der Hausaufgaben und erfolgreiche Teilnahme an der Klausur bzw. mündlichen Prüfung.

Themenbereiche sind:

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

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.

Aktuelles

Mailingliste

Vorlesungsnotizen

• VL Nr. 1: [PDF] (03.11.; p.1-6)
• VL Nr. 2: [PDF] (10.11.; p.7-15)
• VL Nr. 3: [PDF] (17.11.; p.15-22)
• VL Nr. 4: [PDF] (24.11.; p.23-26)
• VL Nr. 5: [PDF] (01.12.; p.27-34)
• VL Nr. 6: [PDF] (15.12.; p.35-43)
• VL Nr. 7: [PDF] (05.01.; p.44-46)
• VL Nr. 8: [PDF] (12.01.; p.47-51)
• VL Nr. 9: [PDF] (19.01.; p.52-56)
• VL Nr. 10: [PDF] (26.01.; p.57-61)
• VL Nr. 11: [PDF] (02.02.; p.61-66)
• VL Nr. 12: [PDF] (09.02.; p.67-69)

Hausaufgaben

• Hausaufgabenblatt Nr. 1: [PDF]
• Hausaufgabenblatt Nr. 2: [PDF]
• Hausaufgabenblatt Nr. 3: [PDF]
• Hausaufgabenblatt Nr. 4: [PDF] [ ZIMPL User guide ] [gerry1.zpl] [gerry2.zpl] [ZIMPL Folien aus der großen Übung] [Ein Beispiel] [ZIMPL, SoPlex und SCIP]
• Hausaufgabenblatt Nr. 5: [PDF]

weitere Materialien:

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:

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!