Mathematische Methoden der Algorithmik

Studienleistung: Erfolgreiche Bearbeitung von mindestens 50 Prozent der Hausaufgaben.

Prüfungsleistung: Mündliche Prüfung nach dem Semester. Details werden noch festgelegt.

Thema ist lineare und ganzzahlige Optimierung. Die Studierenden erlernen, gegebene Probleme als solche Programme zu formulieren und zu lösen, sowie die theoretischen Aspekte dahinter:

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

1. B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, Springer, 2005 (kv-cota-05, BibTeX)
2. A. Schrijver: Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1998 (s-tlip-98, BibTeX)
3. V. Chvátal: Linear Programming, Series of Books in the Mathematical Sciences, W.H. Freeman, 1983 (c-lp-83, BibTeX)
4. Ein Skript aus dem Wintersemester 2008/09

Aktuelles

• Die erste Vorlesung findet am Montag, den 03.11.2015 statt!
• Den Semesterplan findet ihr hier.
• Ein Skript zur linearen Algebra findet ihr hier. Wichtig sind vorallem die Abschnitte 2.2.4-2.2.6, 2.3 und 3.2. Solltet ihr Schwierigkeiten damit haben, kommt am Besten in die nächste große Übung.
• Im obigen Skript ist der Steinitzische Austauschsatz Satz 2.77 und der Basisergänzungssatz Satz 2.80.
• Arne hat für die nächste kleine Übung noch zwei Aufgaben zum Dualisieren vorbereitet. Das Aufgabenblatt findet ihr im Hausaufgabenbereich.
• Die letzte große Übung findet am 10.02.2016 statt.

Hausaufgaben

• 0. Hausaufgabenblatt
• 1. Hausaufgabenblatt
• 2. Hausaufgabenblatt
• 3. Hausaufgabenblatt
• 4. Hausaufgabenblatt
• 5. Hausaufgabenblatt
• Optionales Übungsblatt für die kleine Übung am 12.01.2016.

  Übung

  • Es wird keine Mitschrift veröffentlicht.

  Mailingliste

  Es gibt eine Mailingliste zu dieser Vorlesung, in die sich Teilnehmer bitte eintragen. Bei Problemen bitte an Dr. Frank Quedenfeld wenden.

  Hinweise zu LP-Lösern

  Ihr könnt euch einen IBR-Account anlegen und euch damit via SSH auf einen der Server {x11,x12,algpc05..08}.ibr.cs.tu-bs.de einloggen. Darauf sind die unten genannten Tools bereits eingerichtet. Über die Kommandozeile startet man sie mit:

  cplex
  scip
  soplex
  zimpl
  

  Im Laufe des Kurses werden einige Aufgaben zu CPLEX gestellt. Jedoch kann man diese Aufgaben mit jedem oben genannten LP-Löser bearbeiten. Ein kurzer Einsteiger-Guide ist das CPLEX1x1. Ein guter Startpunkt ist dieses Beispiel. Die offizielle Dokumentation findet ihr hier. Darüber hinaus gibt es eine kurze Einführung in ZIMPL, SoPlex und SCIP.

  IBM ILOG CPLEX (cplex) ist kommerziell, die SCIP Optimization Suite (scip, soplex, zimpl) ist freie Software und kann kostenfrei auf diversen Betriebssystemen installiert werden. Insbesondere ist dort das ZIMPL User Guide verfügbar.