![[Translate to English:]](/fileadmin/user_upload/fachbereiche/fb3/infcon/CSLog/CSLog.png)
Summer 2017
Einführung in die lineare Optimierung
Vorlesung im Sommersemester 2017
Viele praktische Fragestellungen lassen sich als lineare Optimierungsprobleme formulieren, bspw. in der Logistik (Warenfluss und Planung von Produktionsprozessen) oder in der Finanzwelt (Portfoliotheorie und Risikomanagement). In einem linearen Optimierungsproblem sind sowohl die Zielfunktion als auch die Nebenbedingungen, die die Menge der zulässigen Lösungen beschreiben, linear. Die Vorlesung gibt eine Einführung in die Theorie und Praxis der linearen Optimierung und behandelt Grundzüge der ganzzahligen Optimierung. Vorlesungsthemen sind u.a.: Modellierung und Struktur linearer Programme, Polyedertheorie, Optimalitätskriterien, Dualität, Simplex-Algorithmus, die Ellipsoid-Methode, und die Branch-and Bound Methode.
Dozent: Prof. Dr. Nicole Megow
Assistent: Dr. Franziska Eberle
Zeit & Raum:
- VL: Di 14-16 Uhr in Raum MZH 1090 (Megow)
ab 16.5. in Raum MZH 6210 (zu erreichen über den verlängerten Flur vorbei an Raum 6240) - UE: Mo 12-14 Uhr in Raum MZH 1090 (Eberle)
- UE: Di 16-18 Uhr in Raum MZH 1100 (Eberle)
Start: Mittwoch, 11. April 2017. Die erste Übung dient der Wiederholung und findet am 11. April 2017 statt.
Prüfung/Fachgespräch: Terminvereinbarung bitte per Email.
Literatur:
- [BT] Bertsimas, Tsitsiklis: Introduction to Linear Optimization, Athena Scientific, 1997.
- [GKT] Guenin, Könemann, Tuncel: A Gentle Introduction to Optimization, Cambridge University Press, 2014.
Approximation Algorithms
Course in Summer 2017
A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial time algorithms and proving bounds on their worst case performances.,
Instructors:
- Prof. Dr. Nicole Megow
- Dr. Syamantak Das
Time & room:
- Wed 12-2 in room MZH 1090 (kurse)
- Thu 10-12 in room MZH 5210 (kurse)
Start: Wednesday, April 5th, 2017
Resources:
- [1] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys
online version - [2] Approximation Algorithms, Vijay V. Vazirani
online version
| Date | Topic |
|---|---|
| 5.4.2017 | Introduction, MST heuristic for TSP |
| 6.4.2017 | Christofides' Algorithm, Makespan Greedy |
| 12.4.2017 | Greedy Set Cover |
| 13.4.2017 | Local Search: Max leaf spanning tree |
| 19.4.2017 | Local Search: k-median |
| 20.4.2017 | Local Search: k-median, Exercises |
| 26.4.2017 | Introduction to LPs/ILPs, basic rounding (Vertex Cover) |
| 27.4.2017 | ILP for Spanning Trees, Cut-Lps, Separation Oracles, Prize Collecting Vertex Cover |
| 03.5.2017 | LP Rounding : Weighted Sum of Completion Time on Single and Parallel Machines |
| 04.5.2017 | Exercises |
| 10.5.2017 | Shmoys, Tardos rounding for Minimizing Makespan |
| 11.5.2017 | Introdution to primal-dual, vertex cover |
| 17.5.2017 | Steiner Forest using primal-dual |
| 18.5.2017 | No lecture |
| 24.5.2017 | PTAS: Bin-packing, Makespan |
| 25.5.2017 | No Lectures |
| 31.5.2017 | FPTAS, Knapsack |
| 01.6.2017 | Exercises |
| 07.06.2017 | Randomized Approximation Algorithms, Set Cover, Independent Set |
| 08.06.2017 | Randomized Approximation Algorithms: Buy At Bulk Steiner Trees |
| 14.06.2017 | No lectures |
| 15.06.2017 | No lectures |
| 21.06.2017 | Randomized Rounding : Max-Sat, Prize-collecting Steiner Trees |
| 22.06.2017 | Randomized Rounding : Chernoff bounds and applications : Discrepancy, Max Integer Multicommodity flow |
| 28.06.2017 | Hardness of Approximation : Gap preserving reductions, bin-packing, k-center |
| 29.06.2017 | Hardness of Approximation : Unrelated Machine Scheduling, Approximation preserving reductions |
Vehicle Routing und Mobility Sharing
Seminar im Sommersemester 2017
4 ECTS
Die Mobilitätsbranche ist heute einer der Wirtschaftsbereiche mit dem stärksten Wachstum. Ressourcenknappheit in Ballungszentren und ein zunehmendes Interesse an umweltfreundlicheren und kostengünstigeren Mobilitätslösungen führen zum Trend Autos, Fahrräder, Parkplätze, etc. zu teilen – Shared Mobility.
Thema dieses Seminars sind Optimierungsfragestellungen und Lösungsmethoden rund um Vehicle Routing und Mobility Sharing. Es werden aktuelle Forschungsartikel studiert und präsentiert.
Die Themenvergabe fand im Juni statt. Die Seminarvorträge werden in einer Blockveranstaltung im Oktober präsentiert. Auch Nicht-Vortragende Gäste sind herzlich eingeladen. Ein genauer Zeitplan erscheint hier im August.
Dozent: Prof. Dr. Nicole Megow
Kick-Off Meeting:18. September um 10:00 im MZH 3150 (5-min Vorträge)
Verbindliche An-/Rückmeldung: bis 31. Juli per Email und in PABO.
Seminartermine: Blockveranstaltung am 11. und 12. Oktober jeweils ab 9:00 Uhr im Raum MZH 3150.
Das erste Kapitel aus dem Buch Toth und Vigo: The Vehicle Routing Problem (2014), siehe Seafile, stellt einen guten Einstieg in das Thema dar und es wird jedem Teilnehmer empfohlen, dieses Kapitel zu lesen. Im folgenden findet sich die Themen- und Betreuerzuordnung.
| Teilnehmer | Betreuer | Thema | Termin (tba) |
|---|---|---|---|
| Brannahl, Marcel | Megow | Nourinejad, Zhu, Bahrami, Roorda: Vehicle relocation and staff rebalancing in one-way carsharing systems (2015) | |
| Finken, Björn | Eberle | Toth und Vigo (2014) 6 - Pickup-and-Delivery Problems for Goods Transportation | |
| Klassen, Anita | Eberle | Toth und Vigo (2014) 4 - Heuristics for the Vehicle Routing Problem | |
| Krause, Kai | Megow | Kaspi, Raviv, Tzur und Galili: Regulating vehicle sharing systems through parking reservation policies (2016) | |
| Kück, Jan | Das | Mahony und Shmoys: Data Analysis and Optimization for (Citi)Bike Sharing (2015) |