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

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.