19234401
Lecture
WiSe 19/20: Optimization I
Ralf Borndörfer
Additional information / Pre-requisites
This course has a significant overlap in material with the Algorithmic Combinatorics course. For this reason, if both of these 10LP courses are taken by a student, then they together can only be accounted for 15LP in the final listing of the student's Master moduls to be presented to the Exam Office. (One of them 10LP Discrete Mathematics II, the other 5LP Ergaenzungsmodul).
Prerequisite: Discrete Math I, Linare Algebra I-II, and Analysis I-II or consent of lecturer.
Some exercises require basic programming and computing capabilities.
The exam will take place during the last lecture of the Semester.
The second exam will take place in the week before the lectures are resumed at the time of the second lecture of a week.
closeComments
This course implements an algorithmic branch of discrete math. It teaches algorithmic graph theory and linear programming.
Overview
Week 1 (Independence Systems): Independence Systems, Rank, Matroids, Greedy Min/Max/Dual, Edmonds-Rado-Thm, Rank Quotient Week 2 (Branchings): Arborescences, Branchings, Edmonds Alg. Week 3 (Complexity): Encoding Length, Run Time of Algorithms, Classes P, NP, co-NP, NP-Completness, SAT, Reductions Week 4 (Shortest Paths): Dijkstra Alg., [A* Alg.], Bellman Recursion, Floyd-Warshall Alg. Week 5 (Minimum Mean Cycles): Karp Alg. Week 6 (Maximum Flows): Menger, Augmenting Paths, Edmonds-Karp Alg. Max Flow Min Cut Thm, [Blocking Flows, Dinics Alg.] Week 7 (Minimum Cost Flows): Generalized Max Flow Min Cut Thm, Equiv. to Transportation Problem, Residual Graph, Min. Mean Cycle Cancelling Alg., Sucessive Shortest Path Alg. Week 8 (Matchings): Alternating and Augmenting Paths, Hopcroft-Karp Alg. (for the Cardinality Case) Week 9 (Polyhedra): Polyhedra, Valid Inequalities, Faces and Facets, Vertices and Extreme Rays, H and V Representation, Caratheodory Thm Week 10 (Fesibility): Fourier-Motzkin Elimination, Alternative Thms, Farkas Lemma, Redundancy, Degeneracy, Transformations of Polyhedra Week 11 (Bases): Equality Set, Dimension, Basis, Vertices and Bases Week 12 (Linear Programs): Primal/Dual LP, Week Duality, Standard Form, Optimality Criterion, Strong Duality, Complementary Slackness Week 13 (Simplex I): Tableau, Revised Simplex Method, Degenerary, Finiteness, Worst-Case Behavior Week 14 (Simplex II): Dual Simplex, Sensitivity Analysis Week 15 (Interior Point Algorithms and Ellipsoid Method, Overview only): Primal-Dual Formulation, Barrier Problem, KKT-Systen, Central Path, Path Following Methods, Run Time, Ellipsoids, Volume, Löwner-John-Ellipsoid, Ellpsoid Method, Run Time Week 16 (Reserve Time, Wrap up, and Exam) close
Overview
Week 1 (Independence Systems): Independence Systems, Rank, Matroids, Greedy Min/Max/Dual, Edmonds-Rado-Thm, Rank Quotient Week 2 (Branchings): Arborescences, Branchings, Edmonds Alg. Week 3 (Complexity): Encoding Length, Run Time of Algorithms, Classes P, NP, co-NP, NP-Completness, SAT, Reductions Week 4 (Shortest Paths): Dijkstra Alg., [A* Alg.], Bellman Recursion, Floyd-Warshall Alg. Week 5 (Minimum Mean Cycles): Karp Alg. Week 6 (Maximum Flows): Menger, Augmenting Paths, Edmonds-Karp Alg. Max Flow Min Cut Thm, [Blocking Flows, Dinics Alg.] Week 7 (Minimum Cost Flows): Generalized Max Flow Min Cut Thm, Equiv. to Transportation Problem, Residual Graph, Min. Mean Cycle Cancelling Alg., Sucessive Shortest Path Alg. Week 8 (Matchings): Alternating and Augmenting Paths, Hopcroft-Karp Alg. (for the Cardinality Case) Week 9 (Polyhedra): Polyhedra, Valid Inequalities, Faces and Facets, Vertices and Extreme Rays, H and V Representation, Caratheodory Thm Week 10 (Fesibility): Fourier-Motzkin Elimination, Alternative Thms, Farkas Lemma, Redundancy, Degeneracy, Transformations of Polyhedra Week 11 (Bases): Equality Set, Dimension, Basis, Vertices and Bases Week 12 (Linear Programs): Primal/Dual LP, Week Duality, Standard Form, Optimality Criterion, Strong Duality, Complementary Slackness Week 13 (Simplex I): Tableau, Revised Simplex Method, Degenerary, Finiteness, Worst-Case Behavior Week 14 (Simplex II): Dual Simplex, Sensitivity Analysis Week 15 (Interior Point Algorithms and Ellipsoid Method, Overview only): Primal-Dual Formulation, Barrier Problem, KKT-Systen, Central Path, Path Following Methods, Run Time, Ellipsoids, Volume, Löwner-John-Ellipsoid, Ellpsoid Method, Run Time Week 16 (Reserve Time, Wrap up, and Exam) close
Suggested reading
B. Korte, J. Vygen, Combinatorial Optimization, Springer 2018
V. Chvátal, Linear Programming, Freeman 1983
32 Class schedule
Additional appointments
Mon, 2020-10-19 10:00 - 12:00Klausur
Regular appointments
Mon, 2019-10-14 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-10-21 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-10-28 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-11-04 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-11-11 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-11-18 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-11-25 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-12-02 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-12-09 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2019-12-16 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-01-06 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-01-13 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-01-20 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-01-27 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-02-03 14:00 - 16:00
Optimierung I (Serientermin 2)
Mon, 2020-02-10 14:00 - 16:00
Optimierung I (Serientermin 2)
Fri, 2019-10-18 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-10-25 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-11-01 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-11-08 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-11-15 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-11-22 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-11-29 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-12-06 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-12-13 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2019-12-20 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-01-10 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-01-17 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-01-24 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-01-31 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-02-07 14:00 - 16:00
Optimierung I (Serientermin 1)
Fri, 2020-02-14 14:00 - 16:00
Optimierung I (Serientermin 1)