Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-50-11-M-4

Integer Programming: Polyhedral Theory and Algorithms (M, 9.0 LP)

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
Position of the semester 1 Sem. in WiSe
Level [4] Bachelor (Specialization)
Language [EN] English
Module Manager
Lecturers
Area of study [MAT-OPT] Optimisation
Reference course of study [MAT-88.105-SG] M.Sc. Mathematics
Livecycle-State [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")

Evaluation of grades

The grade of the module examination is also the module grade.


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)

Requirements for attendance (informal)

Modules:

Requirements for attendance (formal)

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 Formal Fundamentals [WP] Compulsory Elective
[MAT-88.105-SG] M.Sc. Mathematics Applied Mathematics [WP] Compulsory Elective
[MAT-88.706-SG] M.Sc. Mathematics International Applied Mathematics [WP] Compulsory Elective
[MAT-88.118-SG] M.Sc. Industrial Mathematics General Mathematics [WP] Compulsory Elective
[MAT-88.276-SG] M.Sc. Business Mathematics General Mathematics [WP] Compulsory Elective