VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

401-3902-00L 6 Credits BSC , MSC D-MATH , D-INFK

Topics in Discrete Optimization

Lecturers & Examiners: Dr. Maurice Cochand
VVZ CR n/a

Last Updated: 2026-02-05 15:29:27

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
BSC , MSC
Frequency
Yearly recurring

Examination

Type
session examination
Mode
oral 20 minutes
Prüfung auf Deutsch oder auf Englisch

Course Components

Type Title Time & Place Hours
lecture Topics in Discrete Optimization
  • Tue 15:15-17:00 (HG E 1.1)
2 h weekly
exercise Topics in Discrete Optimization
  • Tue 17:15-18:00 (HG F 26.1)
1 h weekly

Offered In