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.
  • 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

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