Semidefinite Optimierung und KombinatorischeOptimierung: eine Symbios...

Bei Kombinatorischen Optimierungsproblemen gilt es, eine optimale Auswahl unter einer großen Menge möglicher Alternativen zu treffen. Etliche Problemstellungen aus der Praxis fallen in diese Kategorie von Optimierungsproblemen, z. B. in der Telekommunikation, in der Produktionsplanung oder in der Routenplanung. Kombinatorische Optimierungsprobleme sind meist NP-schwer und daher wird sich vermutlich kein effizienter Algorithmus finden, der die beweisbar optimale Lösung liefert. Man versucht also mithilfe von Approximationsalgorithmen Näherungslösungen zu ermitteln und mittels eines Enumerationsverfahrens exakte Lösungsalgorithmen zu entwickeln. In den letzten Jahren hat sich die Semidefinite Optimierung als besonders erfolgreiche Methode zum Finden von Approximationslösungen kombinatorischer Optimierungsprobleme herausgestellt. Im Vortrag werden wir sowohl auf die Modellierung kombinatorischer Optimierungsproblem mittels Semidefiniter Methoden eingehen als auch Algorithmen aus dem Bereich der Nichtlinearen Optimierung zur Lösung Semidefiniter Optimierungsprobleme vorstellen.