Optimization methods
The lecture is centered around the theory of linear programming.Basic information
 Name: Optimization methods
 Code: NOPT048
 Hours per week, examination: summer semester 2/2 C+Ex
 Language: English
 Schedule
 Tutorial: Information on a separate page
 Year: 2016/17
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.The first and the second slides presented in czech lectures.
Colleagues
Last year
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
 2. lecture on 2.3.

 Linear programming problem for the shortest path problem
 Linear, affine and convex sets, hulls and combinations
 3. lecture on 9.3.

 Linear and affine independence
 Carathéodory's theorem
 4. lecture on 16.3.

 Basis solutions of a linear programming problem
 5. lecture on 23.3.

 Faces of a polyhedron
 Simplex table and first steps
 6. lecture on 30.3.

 Simplex method in general
 Duality
 7. lecture on 6.4.

 Complementary slackness
 Bland's rule
 8. lecture on 13.4.

 FourierMotzkin elimination
 Farkas lemma
 9. lecture on 20.4.

 Hyperplane separation theorem
 10. lecture on 27.4.

 MinkowskiWeyl theorem
 11. lecture on 4.5.

 Integral polytopes, Unimodularity
 12. lecture on 11.5.

 Applications of unimodularity
 Cutting planes
 Branch and bound
 Approximation algorithms for vertex cover problem
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.
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 2003150, MFF UK, 2003