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

Mathematische Methoden der Algorithmik

Semester
Winter 2011/2012
Winter 2020/2021Winter 2019/2020Winter 2018/2019Winter 2017/2018Winter 2016/2017Winter 2015/2016Winter 2014/2015Winter 2013/2014Winter 2012/2013Winter 2010/2011Winter 2009/2010Winter 2008/2009
Module #INF-ALG-03
Event #INF-ALG-003, INF-ALG-004
ProgrammesMaster Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik
IBR GroupALG (Prof. Fekete)
TypeVorlesung/Übung
Lecturer
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
Assistant
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
Credits5
Hours2+1+1
Time & Place

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)


Start

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

Prerequisites

none

Certificates

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.

Content

Topics are:

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

References
  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!

last changed 2012-01-31, 19:20 by Dr. Alexander Kröller
printemailtop