Seminar "Graphen und lineare Optimierung" (SS 2020)

Vergangene Veranstaltung

Diese Seite bezieht sich auf eine Vorlesung aus vorherigen Jahren. Aktuelle Termine und Arbeitsmaterialien sind hier zu finden.

Anmeldung zum Seminar


Aufgrund der aktuellen Lage verteilen wir die Themen via E-Mail. Zudem ist noch nicht klar, wie und wann das Seminar stattfinden wird. Voraussichtlich beginnt das Seminar in der vierten Semesterwoche, d.h. am Dienstag, den 19. Mai. Unter Umständen wird das Seminar als Blockveranstaltung oder mittels Videovorträgen stattfinden. Im Moment können wir uns leider noch nicht festlegen; wir werden aber so früh wie möglich bekanntgeben, wie wir verfahren werden. 

Hier ist eine Auflistung der Themen mit kurzen Beschreibungen zu finden (Themenliste). Meist ist eine kurze Wikipedia-Suche auch schon recht aufklärend, ob einem das Thema liegen könnte oder nicht. Bei Interesse an einer Teilnahme am Seminar würden wir Sie bitten, Herrn Eggert bis zum 27.04 eine E-Mail zu schreiben (richard.eggert@uni-due.de), bei der Sie folgende Angaben machen:
• 1. Themenwunsch:
• 2. Themenwunsch:
• 3. Themenwunsch:
Hierbei wird ihr 1. Themenwunsch Ihnen eher zugeordnet als der 2 und 3. Bitte geben Sie auch an, ob Sie sich im Bachelor- oder Masterstudium befindet. Einige Themen sind deutlich schwieriger als andere, deshalb würden wir es bevorzugen, einfache Themen an Bachelorstudenten und sehr schwierige an Masterstudenten zu vergeben.

Die Folien der Einführungsveranstaltung (die nicht stattfinden wird) sind hier zu finden (Folien der Einführungsveranstaltung). Dort gibt es Hinweise bezüglich Fristen und Benotung in dieser Veranstaltung. Am Ende sind auch nützliche Vortragtipps zu finden.

Aufgrund der Covid-19-Epidemie und der Verschiebung des Semesterbeginns auf den 20.4. gilt für dieses Seminar:

  • Die Themenverteilung findet am 21.4. statt, entweder durch eine Präsenzveranstaltung (falls möglich) oder durch eine Online-Verteilung der Themen (Einzelheiten folgen rechtzeitig).
  • Anschließend können alle Teilnehmer in (Online-)Interaktion mit ihren Betreuern die Vorträge vorbereiten.
  • Die Vorträge finden statt, sobald wieder Präsenzlehre möglich ist, evtl. als Blockveranstaltung. Falls dies nicht der Fall sein sollte, weichen wir darauf aus, die Vorträge per Video zu halten.

Dozenten:

Inhalt

Viele Probleme der Graphtheorie lassen sich als lineares Optimerungsproblem darstellen. In diesem Sinne ist es von großen Interesse ein effizientes Lösungsverfahren zu erstellen, womit man lineare Programme lösen kann. Somit ist es nur von Nöten, die unterschiedlichen Probleme in lineare Optimierungsprobleme umzuformen, um dann mit einem Lösungsverfahren für lineare Programme direkt eine Lösung zu erhalten. In diesem Sinne werden wir das Simplex-Verfahren betrachten, welches in der Praxis gute Laufzeitergebnisse aufweist.

Wir werden eine Vielzahl an Graphenproblemen betrachten, die sich mittels linearer Programmierung lösen lassen. Für diese Probleme gibt es allerdings spezielle Lösungsverfahren, die wir auch betrachten werden. Diese speziellen Verfahren sind in der Laufzeit meistens dem Lösen mittels linearer Programmierung überlegen. Zum Beispiel ist der Dijkstra-Algorithmus deutlich effizienter, um kürzeste Wege in einem Graphen zu bestimmen.

Es stellt sich heraus, dass manche Graphprobleme nicht mittels linearer Optimierung gelöst werden können. Somit werden wir im zweiten Teil des Seminars auf Probleme der ganzzahligen Optimierung eingehen. Hierbei erlauben wir die Beschränkung von Variablen auf ganze Zahlen. Leider sind solche ganzzahligen Programm deutlich schwieriger zu lösen.

Auch gibt es einen kurzen Einschub zum Zeichnen von Graphen und dynamischem Programmieren. Dynamisches Programmieren wird im zweiten Teil des Seminars Anwendung finden.

Jeder Teilnehmer des Seminars bereitet einen Vortrag zu einem von mehreren Themen vor, die in den Bereich "Graphen und (ganzzahlige) lineare Optimierung" fallen.  Außerdem muss jeder Teilnehmer eine Ausarbeitung von 5-10 Seiten zu dem Thema schreiben.

Termine

Sobald Präsenzlehre wieder stattfinden kann, werden die Vorträge wöchentlich Dienstag, 14:15-15:45 Uhr, in Raum LB 113 stattfinden. Falls zusätzliche Termine notwendig sind, werden wir am Ende des Semesters eine Blockveranstaltung an ein bis zwei Tagen anbieten.

Falls die Präsenzlehre im gesamten Semester ausfallen sollte, können die Vorträge auch per Video gehalten werden.

Themen und Literatur

Die Themen und dazugehörige Literatur werden im Einführungstreffen am Dienstag, den 21.04.2020, auf die Teilnehmer verteilt. Falls bis zu diesem Zeitpunkt noch kein Präsenztreffen möglich ist, werden wir hier bekanntgeben, wie man sich online zum Seminar anmelden kann.

Betreuung

Jeder Teilnehmer und jede Teilnehmerin wird von einem Dozenten oder einer Dozentin betreut. Der Betreuer oder die Betreuerin steht zur Verfügung für inhaltliche und Verständnisfragen, sowie für Hilfe bei der Bearbeitung der Vortragsfolien, dem Schreiben der Ausarbeitung und der Vorbereitung des Vortrags.

Downloads und Links