Module Handbook

• Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-50-11-M-4

Module Identification

Module Number Module Name CP (Effort)
MAT-50-11-M-4 Integer Programming: Polyhedral Theory and Algorithms 9.0 CP (270 h)

Basedata

CP, Effort 9.0 CP = 270 h 1 Sem. in WiSe [4] Bachelor (Specialization) [EN] English Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT) Ruzika, Stefan, Prof. Dr. (PROF | DEPT: MAT) Schöbel, Anita, Prof. Dr. (PROF | DEPT: MAT) [MAT-OPT] Optimisation [MAT-88.105-SG] M.Sc. Mathematics [NORM] Active

Notice

Without a proof of successful participation in the exercise classes, only 6 credit points will be awarded for the module.

Courses

Type/SWS Course Number Title Choice in
Module-Part
Presence-Time /
Self-Study
SL SL is
required for exa.
PL CP Sem.
4V+2U MAT-50-11-K-4
Integer Programming: Polyhedral Theory and Algorithms
P 84 h 186 h
U-Schein
- PL1 9.0 WiSe
• About [MAT-50-11-K-4]: Title: "Integer Programming: Polyhedral Theory and Algorithms"; Presence-Time: 84 h; Self-Study: 186 h
• About [MAT-50-11-K-4]: The study achievement "[U-Schein] proof of successful participation in the exercise classes (ungraded)" must be obtained.

Examination achievement PL1

• Form of examination: oral examination (20-30 Min.)
• Examination Frequency: each semester
• Examination number: 84310 ("Integer Programming")

Contents

Integer Programming: Polyhedral Theory:
• modelling using Integer Programming,
• polyhedra and polytopes,
• complexity,
• formulations,
• connection between Integer Programming and theory of polyhedra,
• integrality of polyhedra: Unimodularity, total dual integrality,
• matchings.

Algorithms:

• dynamic programming,
• relaxations,
• branch-and-Bound methods,
• cutting planes,
• column generation.

Competencies / intended learning achievements

Upon successful completion of the module, the students have studied and understand different algorithms and methods to solve integer optimization problems. They have learnt to model real world economic, technical and/or physical problems as integer optimization problems by using mathematical tools. They are able to critically assess the applicability and limitations of the algorithms. They will understand the proofs presented in the lecture and are able to comprehend and explain them.

By completing the given exercises, the students have developed a skilled, precise and independent handling of the terms, propositions and techniques taught in the lecture. In addition, they have learnt how to applythese techniques to new problems, analyze them and develop solution strategies independently or by team work.

Literature

• G. Nemhauser and L. Wolsey: Integer and Combinatorial Optimization
• A. Schrijver: Combinatorial Optimization - Polyhedra and Efficiency
• A. Schrijver: Theory of Linear and Integer Programming
• L. Wolsey: Integer Programming.

Registration

Registration for the exercise classes via the online administration system URM (https://urm.mathematik.uni-kl.de)

None

References to Module / Module Number [MAT-50-11-M-4]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science [Core Modules (non specialised)] Formal Fundamentals [WP] Compulsory Elective
[MAT-88.105-SG] M.Sc. Mathematics [Core Modules (non specialised)] Applied Mathematics [WP] Compulsory Elective
[MAT-88.118-SG] M.Sc. Industrial Mathematics [Core Modules (non specialised)] General Mathematics [WP] Compulsory Elective
[MAT-88.276-SG] M.Sc. Business Mathematics [Core Modules (non specialised)] General Mathematics [WP] Compulsory Elective
[MAT-88.706-SG] M.Sc. Mathematics International [Core Modules (non specialised)] Applied Mathematics [WP] Compulsory Elective