Lecture "Linear and Network Optimization"

This page is currently under construction. 

Lecture (Dr. David Willems)

Monday 08:30 - 10:00 in G 409

Thursday 08:30 - 10:00 in G 209

Tutorials (Florian Gensheimer)

Monday 16:15 - 17:45 in K 107

Friday 12:15 - 13:45 in E 414

Exams

1. Exam on Monday, 16.07.2018 from 10:00 - 12:00 in E 011

2. Exam on Monday Wednesday, 31.10.2018 from 12:00 - 14:00 in E 011

Material

• Slides for the first part of the lecture (available only with university id, updated version of 30.04.):

• Slides 1 on 1
• Slides 2 on 1
• Slides 3 on 1
• Slides 4 on 1

• (Preliminary) slides for the second part of the lecture (available only with university id):

• Slides 1 on 1
• Slides 2 on 1
• Slides 3 on 1
• Slides 4 on 1

Do not hesitate to send me an email if you find an error in the slides.

• Handout 1 (Motivational Example)
• Handout 2 (Simplex Algorithm)
• Handout 3 (2-Phase-Method)
• Handout 4 (Cycling of the Simplex Algorithm)
• Handout 5 (Dual Simplex Algorithm)
• Handout 6 (Kruskal's algorithm and the algorithm of Prim)
• Handout 7 (Framework for shortest path algorithms, Dijkstra's algorithm)
• Handout 8 (Algorithm of Bellman and Ford)
• Handout 9 (Algorithm of Floyd and Warshall), Example
• Some notes about Heaps (taken from Cormen et al. Introduction to Algorithms)
• Handout 10 (Algorithm of Ford and Fulkerson)
• Handout 11 (Algorithm of Edmonds and Karp)
• Handout 12 (Algorithm of Klein)
• Handout 13 (Successive shortest path algorithm)

Exercise Sheets

Beginning with exercise sheet 1, there will be one “Presentation Only” exercise on each exercise sheet. You should prepare it at home and present it in class. If nobody prepares or presents the exercise, it will not be discussed in class.

Tutorial 1

Tutorial 2

Tutorial 3

Tutorial 4

Tutorial 5

Tutorial 6

Tutorial 7

Tutorial 8

Tutorial 9

Tutorial 10

Tutorial 11

Tutorial 12

Literature and Software

Literature for the first part of the lecture (linear optimization)

• Hamacher, H. W., & Klamroth, K. (2006). Lineare Optimierung und Netzwerkoptimierung. Wiesbaden: Vieweg. (This is a bilingual textbook!)

• Schrijver, A. (1998). Theory of linear and integer programming. John Wiley & Sons.

• Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6, pp. 479-530). Belmont, MA: Athena Scientific.

Literature for the second part of the lecture (network optimization)

• Hamacher, H. W., & Klamroth, K. (2006). Lineare Optimierung und Netzwerkoptimierung. Wiesbaden: Vieweg.

• Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (2014). Network flows. Pearson Education.

• Krumke, S. O., & Noltemeier, H. (2009). Graphentheoretische Konzepte und Algorithmen. Springer-Verlag. (German only)