Anja Fischer: "Was ist Optimierung = Separierung?"

Zusammenfassung:

In diesem Vortrag wird eines der wichtigsten Ergebnisse der ganzzahligen Optimierung vorgestellt, welches von Grötschel, Lovász und Schrijver gezeigt wurde. Informell besagt es, dass es im Wesentlichen genau so schwer ist, für ein Polytop einen zulässigen Punkt zu bestimmen wie eine lineare Zielfunktion über einem Polytop zu optimieren. Etwas formaler gesprochen, sei P ein gegebenes Polytop. Ein Optimierungsorakel liefert für einen Kostenvektor c einen Punkt x aus dem Polytop P, der die lineare Zielfunktion c'x maximiert, falls P nicht leer ist. Im Gegensatz dazu beantwortet ein Separierungsorakel die Frage, ob ein gegebener Punkt y im Polytop P liegt oder nicht. In diesem Fall gibt es einen Kostenvektor c zurück, so dass c'y gröߟer als der Maximalwert aller Punkte im Polytop P bezüglich c ist. Das grundlegende Resultat von Grötschel, Lovász und Schrijver ist nun, dass man mit einer polynomiellen Anzahl an Aufrufen eines Optimierungsorakels ein Separierungsorakel konstruieren kann und umgekehrt. Ein wichtiges Hilfsmittel beim Beweis dieses bedeutenden Satzes, dessen Idee angedeutet werden soll, ist die aus der konvexen Optimierung bekannte Ellipsoidmethode. Am Ende des Vortrages gehen wir auf Konsequenzen des Ergebnisses im Bereich der kombinatorischen Optimierung, etwa bei der Lösung von Spannbaum- oder Matchingproblemen, ein.