WS 92/93: VL Kombinatorische Optimierung

Allgemeine Resultate zur ganzzahligen und gemischt-ganzzahligen Optimierung, Überblick über Graphentheorie und Komplexitätstheorie, effiziente Algorithmen für polynomial lösbare kombinatorische Optimierungsprobleme (aufspannende Bäume, kürzeste Wege, Flüsse, Matroid-Probleme), Heuristiken für NP-schwere Probleme und ihre Analyse (u.a. für das Rucksack-Problem, das Travelling-Salesman-Problem, Bin-Packing), Relaxierungen und duale Heuristiken, exakte Verfahren zur Lösung NP-schwerer Probleme (Branch-and-Bound, Schnittebenenverfahren, Lagrange-Relaxierungen)

Übungsblätter zur Vorlesung: 1. Übungsblatt
2. Übungsblatt
3. Übungsblatt
4. Übungsblatt
5. Übungsblatt
6. Übungsblatt
7. Übungsblatt
8. Übungsblatt
9. Übungsblatt
10. Übungsblatt
11. Übungsblatt
12. Übungsblatt
13. Übungsblatt
14. Übungsblatt