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

## 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