Discrete Mathematics III - Optimization
Ralf Borndörfer
Additional information / Pre-requisites
Requirements
Discrete Mathematics I and II
Videos
In Vbrick Rev via https://fu-berlin.eu.vbrickrev.com/#/playlist/fd62388d-d18c-45a8-9a98-30adb0dee4b4/videos/.
Related lectures
In addition to the exercise, an additional integrated event "Practice of integer programming" is offered. This course is recommended, but not mandatory for participation in the lecture.
closeComments
This lecture is an introdution to integer programming.
Contents
Week 1 (Integer Programming Problems): Introduction, Definitions, Examples, Total Unimodularity
Week 2 (Branch-and-Bound): LP relaxation, tree search
Week 3 (relaxations): Lower bounds, Lagrangian relaxation
Week 4 (Primal Heuristics): Opening and improvement heuristics, approximation, examples
Week 5 (Integer Points in Rational Polyhedra): Integer Polyhedra, Integer Points in Rational Polyhedra, Complexity
Week 6 (Cutting Plane Theory): Elementary Closure, Rank
Week 7 (Cutting Plane Method for IPs): Gomory Cuts of Type I
Week 8 (Cutting Plane Procedure for MIPs): Gomory Cuts of Type II
Week 9 (Polyhedral Combinatorics): Matroid Polytope
Week 10 (Polyhedral Combinatorics): Matching Polytope
Week 11 (Polyhedral Combinatorics): TSP Polytope
Week 12 (General Cutting Plane Method): Equivalence of Separation and Optimization
Week 13 (Section Plane Procedure): 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
close13 Class schedule
Regular appointments