SoSe 20: Integer Programming
Ralf Borndörfer
Additional information / Pre-requisites
This course is a continuation of Optimization I.
Prerequisites: Discrete Math I, Algorithmic Graph Theory, Linear Programming.
Some exercises require basic programming and computing capabilities.
The exam will take place during the last lecture of the Semester.
The second exam will take place in the week before the lectures are resumed at the time of the second lecture of a week.
closeComments
This course teaches the basics of integer programming.
Content
Week 1 (Integer Programming Problems): Introduction, Examples, Definitions
Week 2 (Branch-and-Bound): LP-Relaxation, Tree Search
Week 3 (Relaxations): Lower Bounds, Lagrange 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 Methods for IPs): Gomory Cuts of Type I
Week 8 (Cutting Plane Method 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 (Cutting Plane Method): 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
close12 Class schedule
Additional appointments
Mon, 2020-10-26 10:00 - 12:00Regular appointments