Syllabus
- Formulation of integer problems
- Integer polyhedron, unimodular matrices, NP-completeness
- Cutting planes and branch & bound methods
- The first and second Gomory algorithms
- Preprocessing. Heuristics
- Knapsack problem
- Set covering
- Travelling salesman problem
It is assumed that the students have a basic knowledge of linear programming.
Annotation
The lecture studies optimization problems with discrete (integer) variables. Integer programming problems often arise in practical problems and many problems can be formulated in terms of integer programming.
Due to high computational complexity, it is still a challenge and in focus of current research.
Remark: The course can be tought once in two years.