Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Course MAT-50-11-K-4

Integer Programming: Polyhedral Theory and Algorithms (4V+2U, 9.0 LP)

Course Type

SWS Type Course Form CP (Effort) Presence-Time / Self-Study
- K Lecture with exercise classes (V/U)
4 V Lecture 6.0 CP 56 h 124 h
2 U Exercise class (in small groups) 3.0 CP 28 h 62 h
(4V+2U) 9.0 CP 84 h 186 h

Basedata

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. in WiSe
Level [4] Bachelor (Specialization)
Language [EN] English
Lecturers
Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT)
Ruzika, Stefan, Prof. Dr. (PROF | DEPT: MAT)
Schöbel, Anita, Prof. Dr. (PROF | DEPT: MAT)
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

Possible Study achievement

  • Verification of study performance: proof of successful participation in the exercise classes (ungraded)
  • Examination number (Study achievement): 84031 ("Exercise Class Integer Programming")
  • Details of the examination (type, duration, criteria) will be announced at the beginning of the course.

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

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.

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.

Materials

Further literature will be announced in the lecture; Exercise material is provided. Lecture recordings available at https://videoportal.uni-kl.de/

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 Course [MAT-50-11-K-4]

Module Name Context
[MAT-30-10L-M-5] Specialisation Module (Teachers Training Programme Mathematics) WP: Obligation to choose in Obligatory-Modulteil #A (Lectures) 4V, 6.0 LP
[MAT-50-11-M-4] Integer Programming: Polyhedral Theory and Algorithms P: Obligatory 4V+2U, 9.0 LP
Course-Pool Name
[MAT-50-4V-KPOOL-4] Elective Courses Optimisation and Stochastics (4V, B.Sc.)
[MAT-50-KPOOL-4] Specialisation Optimisation and Stochastics (B.Sc.)