Relaxationen für NP-schwere Probleme mittels exakter Untergraphen

Die Klassifizierung von kombinatorischen Optimierungsproblemen in polynomial lösbare und NP-schwere Probleme führt auf die Frage wie man mit letzterer Klasse umgehen sollte. Es gibt eine allgemeine Übereinstimmung in der wissenschaftlichen Gemeinschaft, dass NP- schwere Probleme nicht polynomial lösbar sind, aber dies ist nicht bewiesen. Die Klärung dieses Sachverhaltes rangiert als eines der Milleniumprobleme in der Clay Sammlung offener mathematischer Probleme. Nachdem in den 1970iger Jahren die Computational Complexity in der theoretischen Informatik als Maß für die Schwierigkeit von Entscheidungsproblemen eingeführt wurde, gab es große Anstrengungen, um mit NP-schweren Problemen umzugehen. Dieser Zugang geht von einem worst case Verhalten aus, und lässt unmittelbar keine Aussagen über den Lösungsaufwand eines einzelnen Problems zu. Aber selbst wenn ein Problem als nicht polynomial lösbar angenommen wird, ist es immer noch eine mathematische Herausforderung, solche Probleme mit polynomialen Methoden möglichst gut zu approximieren. Es ist Zweck dieses Projekts, mathematische Methoden zu entwickeln, um einige prominente Klassen von Graphenoptimierungsproblemen möglichst genau zu approximieren. Speziell liegt der Fokus auf Max-Cut, Max-Clique und Graph Coloring. Der innovative Aspekt des Projekts liegt in der Art und Weise, wie eine Hierarchie von immer genaueren Approximationen aufgebaut wird. Die Idee ist, zu verlangen, dass alle k-elementigen Untergraphen in der konvexen Hülle der zulässigen Lösungen liegen. Je größer der Parameter k gewählt wird, umso genauer wird die Approximation sein. Aus praktischer Sicht wird man mit kleinen Werten von k anfangen, sodass die Projektionsbedingungen noch praktisch durchführbar sind. Die Herausforderungen liegen in der Identifikation von Untergraphen, deren Projektion die Relaxation verschärfen würde (Separierungsproblem). Es ist geplant sowohl problem- spezifisch als auch allgemein überkopositive Matrizen zu separieren. Aus algorithmischer Sicht stellt sich die Frage, wie die Projektionsbedingungen am effizientesten behandelt werden können. Hier ist geplant, die Projektionsbedingungen zu dualisieren und die duale Funktion mittels der Bundle-Methode zu optimieren. Schließlich werden die neuen Approximationen in bestehende exakte Methoden für Max- Cut integriert, um auch größere Probleme noch mittels Branch-and-Bound exakt lösen zu können.

Kombinatorische Optimierungsprobleme kann man auch als Entscheidungsprobleme ( im Sinn der theoretischen Informatik) formulieren nach dem Schema: Gibt es eine Lösung mit Wert kleiner oder gleich z, oder haben alle Lösungen einen Wert grösser als z. Diese Entscheidungsprobleme kann man sehr vereinfacht in zwei Gruppen einteilen. Zur ersten Gruppe gehören Probleme bei denen mit 'polynomialem' Aufwand 'Ja'-Instanzen erkannt werden können, in der zweiten Gruppe sind alle anderen Probleme. Es gibt dabei die weitläufige Vermutung, dass Probleme der Klasse zwei im schlimmsten Fall nur mit 'exponentiellem' Aufwand gelöst werden können. Im Projekt wird das 'Bandbreitenproblem' behandelt, welches zur zweiten Klasse von Problemen gehört. Gegeben ist dabei eine symmetrische 0-1 Matrix A und eine Zahl k. Das Entscheidungsproblem besteht jetzt darin, festzustellen ob eine gleichzeitige Umnumerierung der Zeilen und Spalten von A existiert, sodass alle Nichtnullen der Matrix einen Abstand kleiner gleich k von der Hauptdiagonalen haben, oder ob bei jeder Umordnung zumindest ein Nichtnulleintrag einen Abstand grösser als k hat. Dieses Problem liegt bereits für sehr einfache Graphen (Baum mit Knotengrad kleiner gleich drei) in der zweiten Klasse der schwierigen Probleme. Ziel des Projekts ist es, möglichst genaue obere und untere Schranken für die Bandbreite zu bestimmen. Dabei wird dieses Problem zunächst als kombinatorische Optimierungsaufgabe in 0-1 Variablen formuliert. Gegeben ist ein Graph dessen Kanten den Nichtnull-Einträgen der Matrix A entsprechen. Um zu effizienten Lösungsansätzen zu gelangen, werden die Knoten in kleine Gruppen eingeteilt (Knotenpartitionierung), und es werden nur Kanten zwischen den einzelnen Gruppen berücksichtigt. Dies führt auf ein quadratisches Minimierungsproblem in 0-1 Variablen, welches immer noch schwer zu lösen ist. Es kann aber mit Methoden der konvexen Optimierung durch eine 'Lineare Optimierungsaufgabe' mit positiv semidefiniten Matrizen gut approximiert werden. Der Kern des Projekts befasst sich jetzt mit der algorithmischen Behandlung dieser Optimierungsaufgabe. Die Schwierigkeit besteht darin, diese semidefinite Optimierungsaufgabe durch Hinzunahme von zusätzlichen Nebenbedingungen möglichst nahe an die tatsächliche optimale Lösung heranzuführen. Es wird dabei gezeigt, dass die 'Methode der alternierenden Richtungen' auch für grössere Probleme noch gute Approximationen liefert. Der Ansatz wurde zunächst auf einfache Graphenklassen angewendet, die einerseits sehr wenige Kanten besitzen, wo aber die Bandbreite mit steigender Knotenzahl rasch wächst. Hier konnte die Bandbreite entweder exakt bestimmt, oder zumindest viel genauer als bisher bekannt, approximiert werden. Schliesslich wurde dieser Ansatz auch erfolgreich auf Graphen aus der Literatur angewendet. Bei vielen dieser Instanzen gibt es keine Information zur Bandbreite. Mit dem neuen Ansatz konnte jedoch auch hier eine genaue Bandbreitenabschätzung ermittelt werden.