Discrete Optimization
Module MA3502
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Module version of SS 2020
There are historic module descriptions of this module. A module description is valid until replaced by a newer one.
Whether the module’s courses are offered during a specific semester is listed in the section Courses, Learning and Teaching Methods and Literature below.
| available module versions | |||||
|---|---|---|---|---|---|
| SS 2021 | WS 2020/1 | SS 2020 | WS 2019/20 | SS 2012 | WS 2011/2 |
Basic Information
MA3502 is a semester module in English language at Master’s level which is offered in winter semester.
This module description is valid to SS 2021.
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 150 h | 45 h | 5 CP |
Content, Learning Outcome and Preconditions
Content
Introduction to mixed-integer linear optimization, systems of linear Diophantine equations (structure and algorithms, including Hermite normal form), integer hull and integer polyhedral (including characterization of total unimodularity), partition method (Branch-and-bound), cutting plane methods (including Hilbert bases, Gomory-cuts)
Learning Outcome
After successful completion of the module the students are able to understand the underlying structure of tractable and hard problems which allows them to apply advanced methods in optimization. In particular, they will be able to detect relevant structures (e.g. total unimodularity), and derive their properties. Also they will be able to derive and apply advanced methods (e.g. cutting planes) and apply them to specific examples.
Preconditions
MA1001 Analysis 1, MA1002 Analysis 2, MA1101 Linear Algebra and Discrete Structures 1, MA1102 Linear Algebra and Discrete Structures 2, MA2501 Algorithmic Discrete Mathematics, MA2504 Linear and Convex Optimization
Für Studierende für Lehramt an Gymnasien: MA9935 Einführung in die Mathematik 1 LG, MA9936 Einführung in die Mathematik 2 LG, MA9937 Analysis 1 LG, MA9938 Analysis 2 LG, MA9939 Lineare Algebra 1 LG, MA9940 Lineare Algebra 2 LG, MA2501 Algorithmic Discrete Mathematics, MA3501 Linear Optimization (or MA2504 Fundamentals of Convex Optimization)
Für Studierende für Lehramt an Gymnasien: MA9935 Einführung in die Mathematik 1 LG, MA9936 Einführung in die Mathematik 2 LG, MA9937 Analysis 1 LG, MA9938 Analysis 2 LG, MA9939 Lineare Algebra 1 LG, MA9940 Lineare Algebra 2 LG, MA2501 Algorithmic Discrete Mathematics, MA3501 Linear Optimization (or MA2504 Fundamentals of Convex Optimization)
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
WS 2020/1
WS 2019/20
WS 2018/9
WS 2017/8
WS 2016/7
WS 2015/6
WS 2014/5
WS 2013/4
WS 2012/3
SS 2012
SS 2011
SS 2010
| Type | SWS | Title | Lecturer(s) | Dates | Links |
|---|---|---|---|---|---|
| VO | 2 | Discrete Optimization (Combinatorial Optimization: Advanced) | |||
| UE | 1 | Exercises to Discrete Optimization (Combinatorial Optimization: Advanced) |
documents current |
Learning and Teaching Methods
lecture, exercise course, self-study assignments
The module is offered as lectures with accompanying practice sessions. In the lectures, the contents will be presented in a talk with demonstrative examples, as well as through discussion with the students. The lectures should motivate the students to carry out their own analysis of the themes presented and to independently study the relevant literature. Corresponding to each lecture, practice sessions will be offered, in which exercise sheets and solutions will be available. In this way, students can deepen their understanding of the methods and concepts taught in the lectures and independently check their progress.
The module is offered as lectures with accompanying practice sessions. In the lectures, the contents will be presented in a talk with demonstrative examples, as well as through discussion with the students. The lectures should motivate the students to carry out their own analysis of the themes presented and to independently study the relevant literature. Corresponding to each lecture, practice sessions will be offered, in which exercise sheets and solutions will be available. In this way, students can deepen their understanding of the methods and concepts taught in the lectures and independently check their progress.
Media
blackboard
Literature
Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley Interscience, 1998.
Papadimitriou, Steiglitz: Combinatorial Optimization, Dover 2001.
Papadimitriou, Steiglitz: Combinatorial Optimization, Dover 2001.
Module Exam
Description of exams and course work
The module examination is based on a written exam (60 minutes). Students will have to analyze different discrete optimization problems. They should be able to use techniques and concepts presented in the lecture and trained in the exercises and should show an understanding of standard algorithms to solve integer linear optimization problems.
Exam Repetition
The exam may be repeated at the end of the semester.