Optimization methods

The lecture is centered around the theory of linear programming.

Basic information

Czech students

Students in Czech language are also welcomed to lectures and exercises in English. In case of interest, I recommend to attend both lectures and exercises in English.

Lecture

Slides from lectures and their compact version are regularly updated. Warning: Slides are only supplement materials for my lectures. These slides do not replace lecture notes or books. See literature for detail explanations of studied topics and complete proofs.

Past lectures

1. lecture on 20.2.
• Introduction
• Linear programming: Examples, canonical and equation form, graphical method

2. lecture on 27.2.
• Linear programming problem for the shortest path problem
• Linear, affine and convex sets, hulls and combinations

3. lecture on 6.3.
• Linear, affine and convex sets, hulls and combinations
• Linear and affine base
• Carathéodory's theorem
4. lecture on 13.3.
• Hyperplane separation theorem
• Minimal defining system of a polyhedron
5. lecture on 20.3.
• A bijection between faces and inequalities
• Minkowski-Weyl theorem
6. lecture on 27.3.
• Minkowski-Weyl theorem
• Vertices and faces of polytopes
7. lecture on 3.3.
• Simplex method: geometrical interpretation, basis solutions and an example
8. lecture on 10.3.
• Simplex method in general: pivot step, optimality, unboundedness, initial table, infeasibility
• Duality: example and theorem
9. lecture on 17.3.
• Duality and complementarity
• Fourier-Motzkin elimination
• Farkas lemma
10. lecture on 23.3.
• Farkas lemma
• Ellipsoid method
no lecture on 1.4. (state holidays)
no lecture on 8.4. (state holidays)
11. lecture on 15.4.
• Matchings in bipartite graphs
12. lecture on 23.4.
• Matchings in general graphs

Examination

Students are expected to fulfill the tutorial conditions to obtain "zápočet" and then pass the exam. The exam has a written and an oral part. The written part contains the three parts.
• Model a given problem using Linear or Interger Linear Programming.
• Solve a given linear program using the simplex method.
• For a given linear program write its dual program and the complementary slackness conditions.
The oral part examines definitions, statements and proves presented during lectures.

Literature

• A. Schrijver: Theory of linear and integer programming. John Wiley, 1986
• W.J.Cook, W.H. Cunningham W.R.Pulleyblank, A. Schrijver: Combinatorial Optimization. John Wiley, 1997
• J. Matoušek, B. Gärtner: Understanding and using linear programming. Springer, 2006.
• J. Matoušek: Introduction to Discrete Geometry. ITI Series 2003-150, MFF UK, 2003