SS 93: VL Schnittebenenverfahren und Polyedrische Kombinatorik

Ein Ansatz zur exakten Lösung kombinatorischer Optimierungsprobleme (insbesondere NP-schwerer Probleme), der sich in den letzten Jahren als besonders erfolgreich erwiesen hat, ist der folgende. Man transformiere das gegebene kombinatorische Problem in ein lineares Programm und zwar so, daß jede optimale Ecklösung des linearen Programms eine optimale Lösung des kombinatorischen Problems ist und umgekehrt. Bei dieser Transformation treten Polyeder enormer Komplexität auf. Die polyedrische Kombinatorik beschäftigt sich mit dem Studium dieser Polyeder und der Umsetzung der Erkenntnisse über facetten-definierende Ungleichungen etc. in praktisch verwendbare Verfahren. Typischerweise wird dies durch Schnittebenenverfahren der linearen ganzzahligen Optimierung mittels Separierungsalgorithmen verbunden mit Branch & Bound geleistet. In dieser Vorlesung wird ein Einblick in die Methodik dieses Gebietes gegeben und anhand realer Anwendungsfälle des Travelling-Salesman-Problems, des Max-Cut-Problems etc. gezeigt, welche praktischen Probleme dieser Art heutzutage gelöst werden können. Die Studenten der Vorlesung sollen im Rahmen der Übungen selbständig (unter Anleitung) ein Schnittebenenverfahren für ein kombinatorisches Optimierungsproblem implementieren.