This lecture starts the Optimization branch of Discrete Mathematics. It deals with Algorithmic Graph Theory and Linear Optimization.
Content
- Complexity: Complexity measures, runtime of algorithms, the classes P and NP, NP-completeness
- Matroids and Independence Systems: independence systems, matroids, trees, forests, oracles, optimization overe independence systems, greedy algorithm, Edmonds-Rado Theorem
- Shortest Paths: non-negative weights, potentials, Dijkstra and A* algorithms, general weights, Moore-Bellman-Ford algorithm, minimum mean cycle algorithm, all pairs, Floyd-Warshall algorithm
- Maximum Flows: max flow problem, max-flow-min-cut Theorem, augmenting paths, Ford-Fulkerson and Edmonds-Karp algorithm, flow decompostion and Menger Theorems
- Minimum Cost Flows: minimum mean cycle cancelling algorithm, successive shortest path algorithm, transportation and assignment problems
- Matchings: Hopcroft-Karp and Edmond's blossom shrinking algorithms
- Linear Programs: inequality systems, standard form, transformations, dual LP, Duality Theorem, complementary slackness, geometry of LPs, combinatorial LPs
- Polyhedra and Polytopes: Minkowski sum, linear, affine, convex, conic combinations, hyperplanes and halfspaces, dimension, projections of polyhedra, Fourier-Motzkin elimination
- Alternative Theorems: Farkas Lemma
- Simplex Algorithm: basis, reduced costs, pivot, tableau, optimality criterion, dual solution, revised simplex method, degeneracy, cycling, pivot rules, worst case complexity, phase I/II, dual simplex algorithm, sensitivity and post optimization
- Polyhedral Theory: polar, homogenization, representation Theorems of Weyl and Minkowski, valid and supporting inequaliteis, gamma polar, faces, interior points, dimension formula, redundancy, facets, vertices, edges, extreme rays, extremals, pointed polyhedra, optimal LP vertices, basis of a cone/polytope/polyhedron, representation by few generators, Krein-Milman and Caratheodory Theorems
- Ellipsoid Method: complexity of vertices, minimum volume of polytopes, Löwner-John ellipsoid, polynomail equivalence of optimizuation and feasibility, complexity of linear programming
- Interior Point Methods: strict feasibility, primal-dual problem, KKT system, barrier functions and problems, central path, residau and duality gap, KKT solution by Newton's method, path following methods, complexity of path following methods
Target group
This lecture is intended for mathematics students with prior knowledge in Discrete Mathematics, Linear Algebgra, and Analysis. Some exercises might require the use of a computer.
Videos
Vidoes of the WS 2021 course of DM II (with indentical content) is available via the Vbrick Rev platform of FU. Here is the link to the DM II stream:
https://fu-berlin.eu.vbrickrev.com/#/playlist/4540300f-897f-4859-936c-2fd846816895/videos/
Literature
M. Grötschel, Lineare Optimierung, one of the scripts (I learned it with this script)
V. Chvátal (1983), Linear Programming, Freeman (very accessible)
Additional Literature
Garey & Johnson (1979), Computers and Intractability (complexity theory, fun to read)
Bertsimas & Tsitsiklis (1997) Introduction to Linear Optimization (linear programming)
Korte & Vygen (2006) Combinatorial Optimization (flows, shortest paths, matchings, for advanced and/or ambitious readers)
Cormen, Leiserson, Rivest & Stein (2009), Introduction to Algorithms, MIT Press (data structures and graph algorithms (best for this), linear programming, complexity)
Ahuja, Magnati & Orlin (2014), Network Flows - Theory, Algorihms, and Applications, Pearson (fun to read)
Additional Exercises
- Exercise sheets of ADM I 2014/15 including a test exam (in German).
- Exercise sheets of ADM I 2012/13 (in German).
Network Flows
- The book by Ahuja, Magnanti & Orlin has many exercises. Solutions to the odd numbered ones are available here.
Linear Programming
- The book by Chvátal has many exercises, and solution sketches for selected exercises.
- Lecture notes with 27 exercises by Michel Goemans.
- 102 exercises with some hints by Lieven Vandeberghe.
- 16 exercises from Chalmers.
Credits
Students interested in the conbinatorial aspects of Discrete Mathematics are encouraged to take the Discrete Mathematics II - Extremal Combinatorics course offered by Tibor Szabó and Olaf Parczyk.
It is possible to take both courses (Optimization and Extremal Combinatorics) within the FU Master curriculum: one of them can be designated the Discrete Mathematics II modul, the other one an Ergänzungsmodul Ausgewählte Themen A, B, or C.
Language
This lecture is in English.