Combinatorial Optimization
Module MA4502
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 WS 2011/2
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 | |||
|---|---|---|---|
| WS 2021/2 | SS 2020 | SS 2012 | WS 2011/2 |
Basic Information
MA4502 is a semester module in English language at Master’s level which is offered in summer semester.
This Module is included in the following catalogues within the study programs in physics.
- Catalogue of non-physics elective courses
| Total workload | Contact hours | Credits (ECTS) |
|---|---|---|
| 150 h | 45 h | 5 CP |
Content, Learning Outcome and Preconditions
Content
Approximation algorithms, theory of polyhedra (e.g.: finding faces and corresponding dimensions of combinatorial polyhedra), separation algorithms, Branch-and-Cut schemes.
Learning Outcome
At the end of the module students are able to analyze combinatorial polyhedra and apply approximation techniques and Branch-and-Cut methods to solve combinatorial optimization problems in theory and applications.
Preconditions
MA1001 Analysis 1, MA1002 Analysis 2, MA1101 Linear Algebra and Discrete Optimization 1, MA1102 Linear Algebra and Discrete Optimization 2, MA2501 Algorithmic Discrete Mathematics, MA2504 Linear and Convex Optimization
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
SS 2022
SS 2021
SS 2020
SS 2019
SS 2018
SS 2017
SS 2016
SS 2015
SS 2014
SS 2013
WS 2012/3
WS 2011/2
WS 2010/1
| Type | SWS | Title | Lecturer(s) | Dates | Links |
|---|---|---|---|---|---|
| VO | 2 | Combinatorial Optimization [MA4502] | Ramos Vaz, D. |
Fri, 12:15–13:45, MI HS3 and singular or moved dates |
|
| UE | 1 | Exercises for Combinatorial Optimization [MA4502] | Ramos Vaz, D. | dates in groups |
Learning and Teaching Methods
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 animate 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. At the beginning of the module, the practice sessions will be offered under guidance, but during the term the sessions will become more independent, and intensify learning individually as well as in small groups.
Media
Tafelarbeit
Literature
(1) Cook, Cunningham, Pulleyblank, Schrijver: Combinatorial Optimization, Wiley Interscience, 1998.
(2) Korte, Vygen: B15Combinatorial Optimization: Theory and Algorithms, Springer 2002.
(3) Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley Interscience, 1999.
(2) Korte, Vygen: B15Combinatorial Optimization: Theory and Algorithms, Springer 2002.
(3) Nemhauser, Wolsey: Integer and Combinatorial Optimization, Wiley Interscience, 1999.
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 combinatorial optimization problems.
They should by able to use techniques and concepts (e.g. from polyhedral combinatorics) presented in the lecture and should show an understanding of exact and approximation algorithms to solve combinatorial optimization problems.
They should by able to use techniques and concepts (e.g. from polyhedral combinatorics) presented in the lecture and should show an understanding of exact and approximation algorithms to solve combinatorial optimization problems.
Exam Repetition
The exam may be repeated at the end of the semester.