Forschungsinstitut für Discrete Mathematics
Summer Term 2026
This lecture is suitable for the 4th or 6th semester of the Bachelor's degree course in Mathematics and is a compulsory elective lecture in area C (Discrete Mathematics). The lecture can also be attended as part of the Bachelor's degree program in Computer Science. The lecture can also be used for the module Foundations in Discrete Mathematics (F4C1). Further information can be found on the teaching overview page.
Assignment sheets:
- Sheet 1
- Sheet 2
- Sheet 3
- Programming exercise 1
- Sheet 4
- Sheet 5
- Programming exercise 2
- Sheet 6
- Sheet 7
- Sheet 8
- Sheet 9
- Sheet 10
- Programming exercise 3
- Sheet 11
- Sheet 12
- Sheet 13 (solutions on the eCampus web page)
Data for the first programming exercise
Instances:
Time and Place: Th, Tu 16-18, Gerhard-Konow-Hörsaal, Research Institute for Discrete Mathematics, Lennéstr. 2.
      First lesson: April 14, 2026.
Exercises: 2 hours, by appointment
Exam: There will be a written exam
Goals: Understanding of the fundamental relationships of polyhedral theory and the theory of linear and integer optimization. Knowledge of the most important algorithms, ability to appropriately model practical problems as mathematical optimization problems and their solution.
Content: Modeling of optimization problems as (integer) linear programs, polyhedra, Fourier-Motzkin elimination, Farkas' lemma, duality theorems, simplex methods, ellipsoid method, conditions for integer polyhedra, TDI systems, complete unimodularity, cutting plane methods, interior point method.
Prerequisites: Linear Algebra and Algorithmic Mathematics I
List of References:
There will be written lecture notes. In addition, I recommend the following text books.- V. Chvátal, Linear Programming, Freeman, New York, 1983.
- M. Conforti, G. Cornuéjols, and G. Zambelli: Integer Programming, Springer, 2014.
- B. Gärtner, J. Matousek, Understanding and Using Linear Programming, Springer, Berlin, 2006.
- B. Korte, J. Vygen : Combinatorial Optimization: Theory and Algoriths. sixth edition, Springer, 2018.
- A. Schrijver, Theory of Linear and Integer Programming, Wiley, New York, 1986.
- R.J. Vanderbei, Linear Programming: Foundations and Extentions, Kluwer Academic Publishers, Dordrecht, fifth edition, 2020.
- L.A. Wolsey and G. Nemhauser: Integer and Combinatorial Optimization, Wiley-Interscience, 1988.