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:

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
DateTopic
5.4.2017Introduction, MST heuristic for TSP
6.4.2017Christofides' Algorithm, Makespan Greedy
12.4.2017Greedy Set Cover
13.4.2017Local Search: Max leaf spanning tree
19.4.2017Local Search: k-median
20.4.2017Local Search: k-median, Exercises
26.4.2017Introduction to LPs/ILPs, basic rounding (Vertex Cover)
27.4.2017ILP for Spanning Trees, Cut-Lps, Separation Oracles, Prize Collecting Vertex Cover
03.5.2017LP Rounding : Weighted Sum of Completion Time on Single and Parallel Machines
04.5.2017Exercises
10.5.2017Shmoys, Tardos rounding for Minimizing Makespan
11.5.2017Introdution to primal-dual, vertex cover
17.5.2017Steiner Forest using primal-dual
18.5.2017No lecture
24.5.2017PTAS: Bin-packing, Makespan
25.5.2017No Lectures
31.5.2017FPTAS, Knapsack
01.6.2017Exercises
07.06.2017Randomized Approximation Algorithms, Set Cover, Independent Set
08.06.2017Randomized Approximation Algorithms: Buy At Bulk Steiner Trees
14.06.2017No lectures
15.06.2017No lectures
21.06.2017Randomized Rounding : Max-Sat, Prize-collecting Steiner Trees
22.06.2017Randomized Rounding : Chernoff bounds and applications : Discrepancy, Max Integer Multicommodity flow
28.06.2017Hardness of Approximation : Gap preserving reductions, bin-packing, k-center
29.06.2017Hardness 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.

TeilnehmerBetreuerThemaTermin (tba)
Brannahl, MarcelMegowNourinejad, Zhu, Bahrami, Roorda: Vehicle relocation and staff rebalancing in one-way carsharing systems (2015) 
Finken, BjörnEberleToth und Vigo (2014) 6 - Pickup-and-Delivery Problems for Goods Transportation 
Klassen, AnitaEberleToth und Vigo (2014) 4 - Heuristics for the Vehicle Routing Problem 
Krause, KaiMegowKaspi, Raviv, Tzur und Galili: Regulating vehicle sharing systems through parking reservation policies (2016) 
Kück, JanDasMahony und Shmoys: Data Analysis and Optimization for (Citi)Bike Sharing (2015)