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

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

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.