Combinatorial Online-Optimization

This was the first "official" course of the PPAM. It consisted of ten working sessions, each one containing a lecture followed by exercises. Various fundamental subjects in Combinatorics were explored, within the frame of modeling and solving a "real" world problem: the online dispatching of automobile service units. This problem has been studied at ZIB during the last years as part of a currently running research project. (More information here)

Course structure:

1. Modeling combinatorial optimization problems
2. Easy and hard problems
3. Polynomial algorithms
4. Geometric descriptions of optimization problems
5. Basic concepts on polyhedrons
6. Linear programming
7. Integer programming
8. Solving Large Scale Integer Programs
9. Online Optimization

Course materials:

1. Exercises ( PS 359K, PDF 121K)
2. Homeworks ( PS 219K, PDF 68K)

Photos

Recommended literature:

• Vasek Chvatal "Linear Programming"
• William J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver "Combinatorial Optimization"
• Martin Grötschel, László Lovász, Alexander Schrijver "Geometric Algorithms and Combinatorial Optimization"
• Bernhard Korte, Jens Vygen "Combinatorial Optimization"
• Alexander Schrijver "Theory of Integer and Linear Programming"
• Günter M. Ziegler "Lectures on Polytopes"