Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Introduction to Linear and Combinatorial Optimization (ADM I)Module description #20087 / Version 1

← Module page Deutsche Fassung
Module / Version#20087 / #1
ValiditySince SS 2014
Available language(s)English, German
Credit points10
Person responsible for the moduleSkutella, Martin
GradingGraded
Exam formatOral exam
Language(s) of instructionGerman

Affiliation

FacultyFakultät II
InstituteInstitut für Mathematik
Academic chairNot specified

Contact

OfficeMA 5-2
Contact personNot specified
E-mail addressskutella@math.tu-berlin.de
WebsiteNot 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%

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.

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)Lecture3236 L 148 Winter semester[de]4 ISIS
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)Tutorial Winter semester[de]2 ISIS
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)Exercise Winter semester[de]2 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

All groups of this course in the catalog

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Tutorial) 5

All groups of this course in the catalog

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Exercise) 1

All groups of this course in the catalog

Workload and credit points

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Lecture)

Workload descriptionMultiplierHoursTotal
Attendance154 h60 h
Preparation and follow-up review158 h120 h
180 h

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Tutorial)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
30 h

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (Exercise)

Workload descriptionMultiplierHoursTotal
Attendance152 h30 h
30 h

Course-independent workload

Workload descriptionMultiplierHoursTotal
Exam preparation160 h60 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

GradingGraded
Exam formatOral exam
LanguageGerman

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 versionSemester(s)Curriculum component
Business Mathematics
StuPO 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module
Business Mathematics
Business Mathematics (M. Sc.) - StuPO 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module
Mathematics
Mathematics (B. Sc.) - Bachelor Mathematik 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module
Mathematics
StuPO 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module
Natural Sciences in the Information Society
StuPO 2018
SS 2025Wahlpflichtbereich › Mathematik
WS 2025/26Wahlpflichtbereich › Mathematik
SS 2026Wahlpflichtbereich › Mathematik
WS 2026/27Wahlpflichtbereich › Mathematik
Natural Sciences in the Information Society
Natural Sciences in the Information Society (B. Sc.) - StuPO 2025
WS 2025/26Wahlpflichtbereich › Wahlpflichtbereich Mathematik
SS 2026Wahlpflichtbereich › Wahlpflichtbereich Mathematik
WS 2026/27Wahlpflichtbereich › Wahlpflichtbereich Mathematik
Scientific Computing
Scientific Computing (M. Sc.) - StuPO 2022 (Beginn WS 2022/23)
WS 2022/23Wahlpflichtmodule › Mathematik
SS 2023Wahlpflichtmodule › Mathematik
WS 2023/24Wahlpflichtmodule › Mathematik
SS 2024Wahlpflichtmodule › Mathematik
WS 2024/25Wahlpflichtmodule › Mathematik
SS 2025Wahlpflichtmodule › Mathematik
WS 2025/26Wahlpflichtmodule › Mathematik
SS 2026Wahlpflichtmodule › Mathematik
WS 2026/27Wahlpflichtmodule › Mathematik
Technomathematics
Technomathematics (M. Sc.) - StuPO 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module
Technomathematics
Technomathematics (B. Sc.) - StuPO 2014
SS 2025Vertiefung Mathematik › Grundlegende Module
WS 2025/26Vertiefung Mathematik › Grundlegende Module
SS 2026Vertiefung Mathematik › Grundlegende Module
WS 2026/27Vertiefung Mathematik › Grundlegende Module

Miscellaneous

[Contains machine generated translations 2026-07-07 11:17, only the German version is legally binding]