Lecture Course "Linear and Integer Optimization"

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 here.

Time and Place: Th, Tu 16-18, Gerhard-Konow-Hörsaal, Research Institute for Discrete Mathematics, Lennéstr. 2

Exercises: 2 hours, by appointment

Exam: There will be a written exam

Goals: Understanding of the fundamental relationships of polyhedron 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, computer implementation.

Content: Modeling of optimization problems as (integer) linear programs, polyhedra, Fourier-Motzkin elimination, Farkas' lemma, duality theorems, simplex methods, network simplex, ellipsoid method, conditions for integer polyhedra, TDI systems, complete unimodularity, cutting plane methods.

Prerequisites: Linear Algebra and Algorithmical Mathematics

List of References:

• 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.

Prof. Dr. L. Vargas Koch