Introduction to Linear and Combinatorial Optimization (ADM I)Module description #20087 / Version 1
- 10 CP
- Oral exam
- Graded
- Winter semester
- German
| Module / Version | #20087 / #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 covers the algorithmic and structural foundations of linear and combinatorial optimization. This includes the fundamentals of graph and polyhedron theory and the development of algorithmic thinking and working methods, such as the complexity of problem classes, the efficiency of algorithms, and approximation, using optimization problems in networks as examples.
Subject-specific competence: 55% Methodological competence: 30% System competence: 10% Social competence: 5%
Subject-specific competence: 55% Methodological competence: 30% System competence: 10% Social competence: 5%
Content
Graphs and directed graphs: bipartite graphs, networks, connectedness, trees, graph search.
Linear programming: structure, modeling, transformation to standard form, bases, primal and dual feasibility, economic interpretation (shadow prices)
Simplex method: basic version/tableaux and geometric interpretation; duality theory, complementary slack
Polynomial-time algorithms for fundamental problems in networks: spanning trees, shortest paths, maximum flows, minimum-cost flows
Complexity Theory: The classes P and NP, NP-completeness.
NP-Hard Problems: Clique, Traveling Salesman, Maximum Cut, and Coloring problems.
Linear programming: structure, modeling, transformation to standard form, bases, primal and dual feasibility, economic interpretation (shadow prices)
Simplex method: basic version/tableaux and geometric interpretation; duality theory, complementary slack
Polynomial-time algorithms for fundamental problems in networks: spanning trees, shortest paths, maximum flows, minimum-cost flows
Complexity Theory: The classes P and NP, NP-completeness.
NP-Hard Problems: Clique, Traveling Salesman, Maximum Cut, and Coloring problems.
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Einführung in die Lineare und Kombinatorische Optimierung (ADM I) | Lecture | 3236 L 148 | Winter semester | [de] | 4 | WS 2026/27 (1) ISIS |
| Einführung in die Lineare und Kombinatorische Optimierung (ADM I) | Tutorial | Winter semester | [de] | 2 | WS 2026/27 (5) ISIS | |
| Einführung in die Lineare und Kombinatorische Optimierung (ADM I) | Exercise | Winter semester | [de] | 2 | WS 2026/27 (1) ISIS |
Courses in the course catalog
Courses created from the teaching units of this module.
Winter semester 2026/27 (7)
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Lecture) 1
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Vorlesung) Termingruppe 1 3236 L 147
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Tutorial) 5
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Tutorium) Di. 20.10 - 15.12.26, wöchentlich, Di. 05.01 - 09.02.27, wöchentlich, 16:15 - 17:45 Charlottenburg, EW 229
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Tutorium) Mi. 21.10 - 16.12.26, wöchentlich, Mi. 06.01 - 10.02.27, wöchentlich, 12:15 - 13:45 Charlottenburg, MAR 0.002 (EG re.)
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Tutorium) Mo. 19.10 - 14.12.26, wöchentlich, Mo. 11.01 - 08.02.27, wöchentlich, 16:15 - 17:45 Charlottenburg, EW 229
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Tutorium) Termingruppe 1
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Tutorium) Termingruppe 3
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Exercise) 1
- Einführung in die lineare und kombinatorische Optimierung (ADM I) (Übung) Termingruppe 1 3236 L 148
Workload and credit points
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 4 h | 60 h |
| Preparation and follow-up review | 15 | 8 h | 120 h |
| 180 h | |||
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Tutorial)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 2 h | 30 h |
| 30 h | |||
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (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
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: Winter semester.
Maximum number of participants
This module is not limited to a number of students.
Registration procedures
Standard.
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 › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module | |
| Business Mathematics Business Mathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module | |
| Mathematics Mathematics (B. Sc.) - Bachelor Mathematik 2014 | SS 2025 | Vertiefung Mathematik › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module | |
| Mathematics StuPO 2014 | SS 2025 | Vertiefung Mathematik › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module | |
| 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 | |
| Scientific Computing Scientific Computing (M. Sc.) - StuPO 2022 (Beginn WS 2022/23) | WS 2022/23 | Wahlpflichtmodule › Mathematik |
| SS 2023 | Wahlpflichtmodule › Mathematik | |
| WS 2023/24 | Wahlpflichtmodule › Mathematik | |
| SS 2024 | Wahlpflichtmodule › Mathematik | |
| WS 2024/25 | Wahlpflichtmodule › Mathematik | |
| SS 2025 | Wahlpflichtmodule › Mathematik | |
| WS 2025/26 | Wahlpflichtmodule › Mathematik | |
| SS 2026 | Wahlpflichtmodule › Mathematik | |
| WS 2026/27 | Wahlpflichtmodule › Mathematik | |
| Technomathematics Technomathematics (M. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module | |
| Technomathematics Technomathematics (B. Sc.) - StuPO 2014 | SS 2025 | Vertiefung Mathematik › Grundlegende Module |
| WS 2025/26 | Vertiefung Mathematik › Grundlegende Module | |
| SS 2026 | Vertiefung Mathematik › Grundlegende Module | |
| WS 2026/27 | Vertiefung Mathematik › Grundlegende Module |
Miscellaneous
[Contains machine generated translations 2026-07-07 11:17, only the German version is legally binding]