SoSe 22: Advanced module: Discrete Mathematics III - Integer Programming
Ralf Borndörfer
Additional information / Pre-requisites
Prerequisites
Discrete Mathematics I und Discrete Mathematics II - Optimization
Videos
In Vbrick Rev via https://fu-berlin.eu.vbrickrev.com/#/playlist/fd62388d-d18c-45a8-9a98-30adb0dee4b4/videos/.
Companion Course
An integrated lecture "Practice of Integer Programming" is offered as an optional supplement. This course is recommended, but not mandatory and not related to the DM III exam.
closeComments
This lecture is an introduction to integer programming.
Content
Week 1 (Integer Programming Problems): Introduction, Defnition, Examples, Total Unimodularity
Week 2 (Branch-and-Bound): LP-Relaxation, Tree Search
Week 3 (Relaxations): Lower Bounds, Lagrange Relaxation
Woche 4 (Primal Heuristics): Start and Improvement Heuristics, Approximation, Examples
Woche 5 (Integer Points in Rational Polyhedra): Integer Polyhedram, Integer Points in Rational Polyhedra, Complexity
Woche 6 (Cutting Planes): Elementary Closure, Rank
Woche 7 (Cutting Plane Methods for Integer Programs): Gomory Cuts of Type I
Woche 8 (Cutting Plane Methods for Mixed-Integer Programs): Gomory Cuts of Type II
Woche 9 (Polyhedral Combinatorics): Matroid Polytope
Woche 10 (Polyhedral Combinatorics): Matching Polytope
Woche 11 (Polyhedral Combinatorics): TSP Polytope
Woche 12 (General Cutting Plane Methods): Polynomial Equivalence of Separation and Optimization
Woche 13 (Cutting Plane Methods): Implementation (Tricks)
Week 14: Exam
closeSuggested reading
G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, Wiley 1988
L. Schrijver, Combinatorial Optimization, Springer 2003
B. Korte, J. Vygen, Combinatorial Optimization, Springer 2018
V. Chvátal, Linear Programming, Freeman 1983
close14 Class schedule
Additional appointments
Tue, 2022-10-11 09:30 - 12:30Regular appointments