Seminar: Kombinatorische Optimierung (SS 2014)

	Seminar: Bedeutende Artikel der Optimierung
	Sommersemester 2014

LV-Nr.: 3236 L 382

Prof. Dr. Dr. h.c. mult. Martin Grötschel

Inhalt Voraussetzungen Anmeldung Termine Hinweise Themen Programm Kontakt

Inhalt

In diesem Seminar werden zentrale Artikel der Optimierung behandelt, die starken Einfluss auf die Entwicklung dieses Gebietes hatten. Dieses Seminar wird in Form eines Blockseminars am (20.-21. Juni 2014) im Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) durchgeführt.

Basis des Seminars sind die Kapitel des Buchs M. Grötschel (Ed.), Optimization Stories, Documenta Mathematica, Bielefeld, 2012, das von meiner Webseite http://www.zib.de/groetschel/publications/mybooks.html heruntergeladen werden kann. Die Semiarteilnehmer erhalten ein gedrucktes Exemplar (kostenlos). Ausgehend von Artikeln dieses Buches, wobei wir uns vornehmlich auf Kapitel aus dem Bereich lineare und ganzzahlige Optimierung konzentrieren, werden die Seminarthemen vergeben.
Von den Teilnehmern wird natürlich weiteres Quellenstudium erwartet.

Für eine erfolgreiche Teilnahme am Seminar gibt es 6 Punkte (nach ECTS).

Voraussetzungen

Die Vorlesungen Algorithmische Diskrete Mathematik I - III.

Anmeldung

Interessenten am Seminar kommen zur Vorbesprechung oder wenden sich möglichst frühzeitig per E-Mail an mich. Bitte schicken Sie Ihre E-Mails an die E-Mailadresse: kasse@zib.de.

Termine

Die erste Vorbesprechung zum Seminar fand statt am Montag, 10. Februar 2014, 18:00 Uhr (nach der Vorlesung) im Mathematikgebäude der TU Berlin, Raum MA 313.
Eine zweite Vorbesprechung gab es am 23.04.2014, ebenfalls in der TU Berlin, bei der die Vortragsthemen endgültig vergeben wurden.
Die dritte Vorbesprechung fand am 14.05.2014 in der TU Berlin statt.
Bei der Zusammenkunft am 14. Mai hielt jeder Seminarteilnehmer einen etwa 5-minütigen Kurzvortrag über sein Thema, in welchem er/sie den Vortrag kurz skizzieren sollte. Ich wollte mich an diesem Tag vergewissern, dass jede/r Seminarteilnehmer/in das Thema richtig erfasst hat und ein vernünftiger Seminarvortrag zu erwarten ist.
Das Seminar selbst findet als Blockseminar vom 20.-21. Juni 2014, , im Konrad-Zuse-Zentrum, Seminarraum 2006, statt. (Lageplan).

Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:

Die wesentliche Leistung ist ein Vortrag von ca. 60 Minuten über das zugeteilte Thema. Im Vortrag sollen in verständlicher Form wichtige Ergebnisse des (für den Vortrag zentralen) Artikels vorgestellt werden. Ausgewählte Beweise sollen erklärt werden.
Die Vortragsform und -medien kann jeder frei wählen. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Insbesondere bei Beamerbenutzung sollte die Technik vorher geprüft werden.
Zum Vortragstermin ist von den Vortragenden eine etwa 5-seitige Ausarbeitung zum Thema vorzulegen. Diese wird an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen wesentliche Definitionen und Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in "Publikationsqualität" vorliegen. Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley.)

Bei der Literatursuche sind folgende Links nützlich:

Mathematische Artikel: Zentralblatt
Mathematische Webseiten: MathSearch
Mathematische und informatische Abstracts/Bibliographie: CiteSeer
Informatische Artikel/Bibliographie: ACM Portal
Wissenschaftliches Googlen: GoogleScholar

Themen

Stories about the Old Masters of Optimization

Jiu Zhang Suan Shu and the Gauss Algorithm for Linear Equations
Leibniz and the Brachistochrone
Leibniz and the Infinite
A Short History of Newton’s Method
Euler and Infinite Speed
Euler and Variations
Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman

Linear Programming Stories

Who Invented the Interior-Point Method?
Column Generation for Linear and Integer Programming
Who Solved the Hirsch Conjecture?
Pope Gregory, the Calendar, and Continued Fractions
Löwner–John Ellipsoids
A Brief History of Linear and Mixed-Integer Programming Computation

Discrete Optimization Stories

The Origins of Minimal Spanning Tree Algorithms – Boruvka and Jarnik
The Coming of the Matroids
On the History of the Shortest Path Problem
On the History of the Transportation and Maximum Flow Problems
On the History of the Transportation and Maximum Flow Problems
Edmonds, Matching and the Birth of Polyhedral Combinatorics
Flinders Petrie, the Travelling Salesman Problem, and the Beginning of Mathematical Modeling
D. Ray Fulkerson and Project Scheduling
The Ongoing Story of Gomory Cuts
Markowitz and Manne + Eastman + Land and Doig = Branch and Bound
Ronald Graham: Laying the Foundations of Online Optimization

Continuous Optimization Stories

Cauchy and the Gradient Method
William Karush and the KKT Theorem
Nelder, Mead, and the Other Simplex Method
Subgradient Optimization in Nonsmooth Optimization
A Science Fiction Story in Nonsmooth Optimization Originating at IIASA
Broyden Updating, the Good and the Bad!
Caratheodory on the Road to the Maximum Principle
The Cold War and the Maximum Principle of Optimal Control
The Princess and Infinite-Dimensional Optimization

Computing Stories

A brief history of NP-Completeness, 1954–2012
On the Evolution of Optimization Modeling Systems
Who Invented the Reverse Mode of Differentiation?
Gordon Moore and His Law: Numerical Methods to the Rescue

More Optimization Stories

Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins
Around Hilbert’s 17th Problem
From Kepler to Hales, and Back to Hilbert
Vilfredo Pareto and Multi-objective Optimization
Optimisation and Utility Functions

Programm

Die Teilnehmer des Blockseminars wählten die nachfolgend aufgeführten Themen für ihre Vorträge.

Freitag, 20.06.2014

Zeit	Vortragender	Thema
09:00 - 10:00 Uhr	Oleg Höfling	Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins, T. M.Liebling u. L. Pournin
10:00 - 11:00 Uhr	Christoph Schubert	Vilfredo Pareto and Multi-Objective Optimization, Matthias Ehrgott
11:00 - 11:30 Uhr	Pause
11:30 - 12:30 Uhr	Jenia Scheizel	The Princess and infinite-dimensional optimization, Hans Josef Pesch
12:30 - 14:00 Uhr	Mittagspause
14:00 - 15:00 Uhr	William Wischlinsky	Optimization and utility functions, Walter Schachmayer
15:00 - 15:30 Uhr	Kaffeepause
15:30 - 16:30 Uhr	Sylvain Spitz	Ronald Graham: Laying the foundations of online optimization, Susanne Albers
16:30 - 17:00 Uhr	Auswertung der bisherigen Vorträge

Sonnabend, 21.06.2014

Zeit Vortragender Thema
09:00 - 10:00 Uhr Hannes Felsberg The coming of the matroids, William H. Cunningham

10:00 - 11:00 Uhr Andreas Meininger On the history of the transportation and maximum flow problems, Alexander Schrijver

11:00 - 11:30 Uhr Auswertung der Vorträge

Kontakt

	Sprechstunde	Raum	Telefon	email
Prof. Dr. Dr. h.c. mult. Martin Grötschel	n.V.	MA 302 (in TU)	030-314-23266 (TU)	groetschmath.tu-berlin.de
	n.V.	Raum 3025/3026 (im ZIB)	030 84185-210 (ZIB)	groetschelzib.de

Zuletzt aktualisiert: 19. Juni 2014

Zeit	Vortragender	Thema
09:00 - 10:00 Uhr	Hannes Felsberg	The coming of the matroids, William H. Cunningham
10:00 - 11:00 Uhr	Andreas Meininger	On the history of the transportation and maximum flow problems, Alexander Schrijver
11:00 - 11:30 Uhr	Auswertung der Vorträge

Seminar: Bedeutende Artikel der Optimierung

Sommersemester 2014