Hörsaal M/E28, Mathematik-Gebäude

Diskrete Optimierungsprobleme sind im Allgemeinen nicht polynomial lösbar und werden meist mit Branch-and-Bound oder ähnlichen Algorithmen gelöst. Für diese Verfahren ist es essentiell, gute Schranken zur Verfügung zu haben. Neben den klassischen LP-Relaxierungen haben sich semidefinite Relaxierungen als sehr erfolgreich erwiesen. Dabei werden lineare Probleme über dem Kegel der semidefiniten Matrizen gelöst. Im Vortrag sollen die Vor- und Nachteile dieses Ansatzes diskutiert und mögliche alternative Matrixkegel vorgestellt werden. Als besonders vielversprechend erweist sich dabei der Kegel der so genannten copositiven Matrizen. Dieser Ansatz hat zudem den Vorteil, dass er auf ganzzahlige Probleme mit Polynomfunktionen erweitern lässt.

Vor dem Fachvortrag, welcher um 17.15 Uhr beginnt, findet noch ein Lehrvortrag von 16.30 - 17.00 Uhr mit dem Thema ``Totale Unimodularität und ganzzahlige Polyeder `` statt.

Prof. Dr. Mirjam Dür

TU Darmstadt