Optimization methodsThe lecture is centered around the theory of linear programming.
- Name: Optimization methods
- Code: NOPT048
- Hours per week, examination: summer semester 2/2 C+Ex
- Language: English
- Tutorial: Information on a separate page
- Year: 2016/17
Czech studentsStudents 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.
LectureSlides 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.
- 1. lecture on 23.2.
- 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
- 7. lecture on 6.4.
- Complementary slackness
- Bland's rule
- 8. lecture on 13.4.
- Fourier-Motzkin elimination
- Farkas lemma
- 9. lecture on 20.4.
- Hyperplane separation theorem
- 10. lecture on 27.4.
- Minkowski-Weyl 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
ExaminationStudents 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.
- 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