Das Problem des maximalen Schnitts
Der maximale Schnitt zerlegt die Knotenmenge eines Graphen in die Teilmengen
und
, so dass das Gesamtgewicht
der zwischen den beiden Teilmengen verlaufenden Kanten maximiert wird.
Dieses Beispiel zeigt, wie SemidefiniteOptimization verwendet werden kann, um eine Funktion zu definieren, die eine Variante dieses NP-vollständigen Problems effizient löst.
Angenommen, hat
Knoten, so dass sie durch einen Index
beschrieben werden können.
sei ein Vektor mit den Komponenten
für
und
für
, so dass
ungleich nur dann null ist (=2), wenn
und
. Somit wird der maximale Schnitt durch Maximierung von
ermittelt, wobei
. Die Zielfunktion kann folgendermaßen formuliert werden:
... wobei die Laplace-Matrix des Graphen und
die gewichtete Adjazenzmatrix ist.
Bei kleineren Graphen kann das Problem des maximalen Schnitts genau gelöst werden, bei größeren Graphen ist diese Methode jedoch unpraktisch, da das Problem im Allgemeinen eine NP-vollständige Komplexität aufweist.
Das Problem minimiert , wobei
eine symmetrische positive semidefinite Matrix mit Rang 1 ist, mit
für jedes
, äquivalent zu
, wobei
die Matrix mit
an der
diagonalen Position und 0 überall sonst ist.
Um die Lösung praktisch zu gestalten, lösen Sie eine Variante des Problems ohne Rang 1-Bedingung, sodass man nur braucht.
Die duale Variante des semidefiniten Problems ist gegeben durch
Das Problem wird gelöst mit SemidefiniteOptimization[c, {a0, a1, …, ak}, {"DualMaximizer" }].
Für die Lösung der Relaxation des Problems wird ein Schnitt durch randomisierte Rundung konstruiert: Zerlegen Sie
,
sei ein gleichmäßig verteilter Zufallsvektor der Einheitsnorm und es gilt
. Zur Veranschaulichung wir eine Funktion definiert, die den "relaxten" Wert, den gerundeten Wert und den Graphen mit den Knoten in
rot darstellt.
Ermitteln Sie anhand der oben besprochenen Methode eine Approximation des maximalen Schnitts und vergleichen Sie diese mit dem exakten Resultat.
Ermitteln Sie den maximalen Schnitt eines Gittergraphen.
Ermitteln Sie den maximalen Schnitt eines Zufallsgraphen.
Vergleichen Sie die Rechenzeiten für die Relaxation und den genauen Algorithmus eines Peterson-Diagramms.