Polyhedral Combinatorics

What it is about

You learn how to approach combinatorial optimization problems through the geometry of polyhedra: representation of polytopes, the connection between geometry and optimization of linear functions, as well as modern algorithms such as branch-and-cut and separation/optimization. In the end you will be able to apply the methods to typical problems (e.g., matching, TSP polytopes) and assess their limits in the context of NP-hardness.

What you will be able to do

• Understanding of the representation and properties of polytopes
• Knowledge of simplex run-time aspects and polytope diameters
• Application of Branch-and-Cut methods and separation algorithms
• Linking geometric structure and optimization of linear objective functions
• Assessment of limits due to NP-hardness
• Familiarity with facet descriptions of fundamental combinatorial polytopes
• Insight into extended formulations

What the module consists of

• VorlesungDelivery of theory and concepts; lecture materials are provided as PDFs
• Übungen / Hands-onApplication of the methods in exercises and assignments

Teaching method

• Vorlesung (PC-based, handwritten notes created)Explanation of the theory and provision of lecture notes as PDFs
• Übungsaufgaben / HausaufgabenConsolidation of the material through practical tasks and applications