VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Topics in Discrete Optimization
Last Updated: 2026-02-05 15:19:51
Abstract
Introduction to polyhedral combinatorics: Minimal spanning trees, branchings, bipartite matching, matroid polytope, intersection of 2 matroids, cutting planes and Lagrangean relaxation with application to the TSP.
Content
Grundlegende Modelle und Methoden der diskreten Optimierung werden behandelt. In einem ersten Teil werden vor allem Probleme in Graphen betrachtet (Gerüste, Arboreszenzen, Matching, Netzwerkflüsse, Chinese Postman), für die effiziente, häufig problemspezifische Lösungsverfahren existieren. Im zweiten Teil werden allgemeine Methoden, heuristische und exakte Verfahren (Lagrange Relaxation, Subgradientenverfahren und Cutting Plane im Zusammenhang mit Branch and Bound) für ganzzahlige und kombinatorische Optimierungsprobleme besprochen.
General Information
- Language
- English
- Levels
- DS , BSC , MSC
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 20 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Topics in Discrete Optimization |
|
2 h weekly |
| exercise | Topics in Discrete Optimization |
|
1 h weekly |