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 would recommended to attend both lectures and exercises in English.

Colleagues

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 23.2.
  • Introduction
  • Linear programming: Examples, canonical and equation form, graphical method
  • Linear, affine and convex sets, hulls and combinations

2. lecture on 1.3.
  • Theorem: Convex hull equals the set of all convex combinations
  • Linear and affine independence
  • Carathéodory's theorem
  • Hyperplane separation theorem

3. lecture on 8.3.
  • Vertices, edges, facets and faces of polyhedrons
  • Minkovski-Weil theorem

4. lecture on 15.3.
  • Vertices and faces of polytopes

5. lecture on 22.3.
  • Minimal description of a polyhedron

6. lecture on 29.3.
  • Simplex method

7. lecture on 5.4.
  • Complexity of simplex method
  • Duality of linear programming
  • Complementary slackness
  • Fourier-Motzkin elimination
  • Farkas lemma

8. lecture on 12.4.
  • Proof of Farkas lemma
  • Proof of duality
  • Integer linear programming
  • Branch and bound
  • Rational and integral polyhedrons

9. lecture on 19.4.
  • Cutting plane
  • Unimodularity and total unimodularity

10. lecture on 26.4.
  • Network flow
  • Matching in graphs

11. lecture on 3.5.
  • Perfect matching in bipartite graphs
  • Minimial-weight perfect matching in bipartite graphs
  • Perfect matching in general graphs

12. lecture on 10.5.
  • Minimial-weight perfect matching in general graphs
  • Maximal-weight matching in general graphs

13. lecture on 17.5.
  • Ellipsoid method
  • Approximation algorithms for minimum vertex cover problem

14. lecture on 24.5.
  • Matroid

Examination

Students are expected to fulfill the tutorial conditions to obtain "zápočet" and to pass the exam.

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