Mathematische Methoden der Algorithmik

Semester Winter 2011/2012 [ Other terms: Winter 19/20 · Winter 18/19 · Winter 17/18 · Winter 16/17 · Winter 15/16 · Winter 14/15 · Winter 13/14 · Winter 12/13 · Winter 10/11 · Winter 09/10 · Winter 08/09 ]

Module # INF-ALG-03

Event # INF-ALG-003, INF-ALG-004

Programmes Master Informatik, Master Informations-Systemtechnik, Master Wirtschaftsinformatik

IBR Group(s) ALG (Prof. Fekete)

Type Vorlesung/Übung

Lecturer

Dr. Alexander Kröller
Ehemaliger Juniorprofessor

Assistant

Dr. Alexander Kröller
Ehemaliger Juniorprofessor

Credits 5

Hours 2+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:

Linear optimisation
Simplex algorithm
Duality
Integer optimization

References

A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.
V. Chvatal, Linear Programming, Freeman, New York, 1983.
B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2002.
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:

`read x.lp`	Liest die Datei x.lp ein
`optimize`	Lö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 solution`	SCIP: 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