Discrete Optimization (ADM II)Module description #20088 / Version 1
- 10 CP
- Oral exam
- Graded
- Summer semester
- German
| Module / Version | #20088 / #1 |
|---|---|
| Validity | Since SS 2014 |
| Available language(s) | English, German |
| Credit points | 10 |
| Person responsible for the module | Skutella, Martin |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät II |
|---|---|
| Institute | Institut für Mathematik |
| Academic chair | Not specified |
Contact
| Office | MA 5-2 |
|---|---|
| Contact person | Not specified |
| E-mail address | skutella@math.tu-berlin.de |
| Website | Not specified |
Learning outcomes
This course teaches and explores algorithmic and structural methods of linear, combinatorial,
and integer optimization. This includes, in particular, the complexity of linear programs, the treatment of NP-hard optimization problems, and the theory and practice of solving integer optimization problems.
Subject-specific competence: 55% Methodological competence: 30% System competence: 10% Social competence: 5%
and integer optimization. This includes, in particular, the complexity of linear programs, the treatment of NP-hard optimization problems, and the theory and practice of solving integer optimization problems.
Subject-specific competence: 55% Methodological competence: 30% System competence: 10% Social competence: 5%
Content
Simplex method: revised Simplex algorithm, dual Simplex algorithm, pivot rules, exponential examples; polyhedron theory, geometry of the Simplex method; primal-dual algorithms with applications to graphs and networks; polynomial-time methods: Ellipsoid method, interior-point methods
Integer linear optimization: Branch and Bound, Lagrange relaxation, cutting-plane method
Assignment problems, matchings, matroids
Polynomial techniques for handling NP-hard problems: approximation algorithms, goodness-of-cover guarantees. Classification of approximability: strongly and weakly NP-complete, MAX-SNP-hard.
Integer linear optimization: Branch and Bound, Lagrange relaxation, cutting-plane method
Assignment problems, matchings, matroids
Polynomial techniques for handling NP-hard problems: approximation algorithms, goodness-of-cover guarantees. Classification of approximability: strongly and weakly NP-complete, MAX-SNP-hard.
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Diskrete Optimierung (ADM II) (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 4 h | 60 h |
| Preparation and follow-up review | 15 | 8 h | 120 h |
| 180 h | |||
Diskrete Optimierung (ADM II) (Tutorial)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| 30 h | |||
Diskrete Optimierung (ADM II) (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| 30 h | |||
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Exam Preparation | 1 | 60 h | 60 h |
| 60 h | |||
The workload of the module adds up to 300 hours. The module therefore comprises 10 credit points.
Description of teaching and learning methods
Lectures, exercises, programming exercises, small-group exercises
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Calculus, linear algebra, knowledge of a high-level programming language, introduction to linear and combinatorial optimization (ADM I)
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | German |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Summer semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Will be announced in class.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Wird in der Vorlesung bekannt gegeben.
Assigned programs
This module version is used in the following programs:
| Program / program version | Semester(s) | Curriculum component |
|---|---|---|
| Business Mathematics StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Business Mathematics Business Mathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Computer Engineering Computer Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science Computer Science (B. Sc.) - StuPO 2025 | WS 2026/27 | Wahlpflichtbereich › Informatiknahe Bereiche › Informatiknahe Mathematik |
| Computer Science (Informatik) Computer Science (Informatik) (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Electrical Engineering Electrical Engineering (M. Sc.) - StuPO 2015 | SS 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WS 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SS 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WS 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Mathematics Mathematics (B. Sc.) - Bachelor Mathematik 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Mathematics StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Natural Sciences in the Information Society StuPO 2018 | SS 2025 | Wahlpflichtbereich › Mathematik |
| WS 2025/26 | Wahlpflichtbereich › Mathematik | |
| SS 2026 | Wahlpflichtbereich › Mathematik | |
| WS 2026/27 | Wahlpflichtbereich › Mathematik | |
| Natural Sciences in the Information Society Natural Sciences in the Information Society (B. Sc.) - StuPO 2025 | WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik | |
| WS 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Mathematik | |
| Technomathematics Technomathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| Technomathematics Technomathematics (B. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
| WS 2025/26 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| SS 2026 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra | |
| WS 2026/27 | Vertiefung Mathematik › Fortgeschrittene Module - Diskrete Mathematik und Algebra |
Miscellaneous
[Contains machine generated translations 2026-07-07 11:17, only the German version is legally binding]
Reading list will be provided in class.
Reading list will be provided in class.