Course MAT-50-11-K-4
Integer Programming: Polyhedral Theory and Algorithms (4V+2U, 9.0 LP)
Course Type
SWS | Type | Course Form | CP (Effort) | Presence-Time / Self-Study | |
---|---|---|---|---|---|
- | K | Lecture with exercise classes (V/U) | |||
4 | V | Lecture | 6.0 CP | 56 h | 124 h |
2 | U | Exercise class (in small groups) | 3.0 CP | 28 h | 62 h |
(4V+2U) | 9.0 CP | 84 h | 186 h |
Basedata
Possible Study achievement
- Verification of study performance: proof of successful participation in the exercise classes (ungraded)
- Examination number (Study achievement): 84031 ("Exercise Class Integer Programming")
- Details of the examination (type, duration, criteria) will be announced at the beginning of the course.
Contents
Integer Programming: Polyhedral Theory:
- modelling using Integer Programming,
- polyhedra and polytopes,
- complexity,
- formulations,
- connection between Integer Programming and theory of polyhedra,
- integrality of polyhedra: Unimodularity, total dual integrality,
- matchings.
Algorithms:
- dynamic programming,
- relaxations,
- branch-and-Bound methods,
- cutting planes,
- column generation.
Competencies / intended learning achievements
The students have studied and understand different algorithms and methods to solve integer optimization problems. They have learnt to model real world economic, technical and/or physical problems as integer optimization problems by using mathematical tools. They are able to critically assess the applicability and limitations of the algorithms.
Literature
- G. Nemhauser and L. Wolsey: Integer and Combinatorial Optimization
- A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency
- A. Schrijver: Theory of Linear and Integer Programming
- L. Wolsey: Integer Programming.
Materials
Further literature will be announced in the lecture; Exercise material is provided. Lecture recordings available at https://videoportal.uni-kl.de/
Registration
Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de)
Requirements for attendance (informal)
Modules:
- [MAT-10-1-M-2] Fundamentals of Mathematics (M, 28.0 LP)
- [MAT-14-13-M-3] Linear and Network Programming (M, 9.0 LP)
Requirements for attendance (formal)
None
References to Course [MAT-50-11-K-4]
Module | Name | Context | |
---|---|---|---|
[MAT-30-10L-M-5] | Specialisation Module (Teachers Training Programme Mathematics) | WP: Obligation to choose in Obligatory-Modulteil #A (Lectures) | 4V, 6.0 LP |
[MAT-50-11-M-4] | Integer Programming: Polyhedral Theory and Algorithms | P: Obligatory | 4V+2U, 9.0 LP |
Course-Pool | Name | ||
[MAT-50-4V-KPOOL-4] | Elective Courses Optimisation and Stochastics (4V, B.Sc.) | ||
[MAT-50-KPOOL-4] | Specialisation Optimisation and Stochastics (B.Sc.) |