This lecture is part III of a the optimization course. It covers mixed-integer programming.

Contents

1. Heuristics: Simple Scheduling Problems, Bin Packing, Integer Programming, Start and Improvement Methods
2. Quality Measures: Dual Heuristics, Relaxations, Subdifferential Calculus
3. The Knapsack Problem
4. The Branch-and-Bound Method
5. Integer Programming: Integer Points in Rational Polyhedra, Cutting Plane Methods for Integer and Mixed-Integer Programs, Separation and Optimization
6. Polyhedral Combinatorics: Theory, Examples
7. Min-Max Relations: Polarity, Blocking and Antiblocking, Total Dual Integrality
8. Decomposition: Lagrange-Relaxation, Benders Decomposition

Literature

M. Grötschel, Einführung in die Lineare und Kombinatorische Optimierung, one of the scripts

A. Schrijver, Throry of Linear and Integer Programming, Wiley, 1986

G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999

B. Korte, J. Vygen, Combinatorial Optimization, Springer, 2012

R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice Hall, 1993.

Useful Links

Graph Algorithms Page of TUM

• Preflow-Push Algorithm

Additional Informationen

Target Audience
This lecture is listed as a BMS course, the course language is English.

The course is directed at mathematics students with previous knowledge in Linear Algebra, Analysis, Linear, and (a bit of) Non-Linear Optimization.

Some execrcises require computing skills.

Further information can be found on the lecture's homepage at http://www.zib.de/ss17_Optimierung_III