Lecturers |
Prof. Komei Fukuda Dr. David Adjiashvili |
||

Assistants |
Stefano Gemin Lorenz Klaus Timm Oertel |

- This lecture is the first course to learn theory and algorithms for optimization rigorously with strong emphasis on proofs and complexity analysis.
- There are three themes that will be covered in this lecture.
- 1. Linear Optimization: Optimality and duality in linear programming, Pivot algorithms (the criss-cross method, the simplex method) and finiteness proofs, Farkas' Lemma and the linear feasibility problem, Sensitivity analysis, Geometry of convex polyhedra and pivot operatons.
- 2. Combinatorial Optimization: Complexity theory (notions of P, NP and NP-complete), Optimization problems in graphs and networks, Integer programming formulations, Polynomial algorithms, Integrality of polyhedra, the Branch-and-Bound algorithm, the column generation algorithm and approximation schemes.
- 3. Interior-Point Methods for Linear Programming: Newton's method, relaxing the optimality, following central paths, polynomial complexity.