Seminar "Graphen und lineare Optimierung" (WS 2020/21)

Vergangene Veranstaltung

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

Anmeldung zum Seminar

Die Anmeldung zum Seminar ist ab dem Einführungstreffen geöffnet. Aufgrund der aktuellen Lage findet das Einführungstreffen virtuell statt (siehe: Termine) und wir verteilen die Themen danach via E-Mail. Das Seminar wird online mittels Videovortägen stattfinden.

Hier ist eine Auflistung der Themen mit kurzen Beschreibungen zu finden (Link folgt noch). 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, Frau Bernemann bis zum 9. November eine E-Mail zu schreiben (rebecca.bernemann@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. Aufgrund der hohen Anzahl an TeilnehmerInnen, bitten wir Sie ebenfalls anzugeben, ob sie am Semesterseminar oder am Blockseminar teilnehmen wollen oder keine Präferenz haben.

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

Das Einführungstreffen wird in der ersten Vorlesungswoche am 5. November um 14:00 Uhr auf der Plattform BigBlueButton stattfinden. Hier werden die Themen vorgestellt und Hinweise zum Ablauf des Seminars gegeben. Den dazugehörigen Link finden Sie im Moodle-Kurs.

Die Vorträge werden wöchentlich Donnerstag, 14:00 Uhr, auf der Plattform BigBlueButton stattfinden. Den Link dazu finden Sie ebenfalls im Moodle-Kurs. Falls zusätzliche Termine notwendig sind, werden wir am Ende des Semesters eine Blockveranstaltung an ein bis zwei Tagen anbieten.

Themen und Literatur

Die Themen und dazugehörige Literatur werden am 10. November per Email auf die Teilnehmer verteilt. (siehe: Anmeldung zum Seminar)

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