Data Reductions in Combinatorial Optimization for Independence Problems

Das Problem eine stabile Menge mit größtem Gewicht in einem gegebenem Graphen zu finden ist ein grundlegendes NP-schweres Problem in der kombinatorischen Optimierung, welchem zusäzlich aufgrund seiner zahlreichen Anwendungen großes Interesse entgegenkommt. Dieses "Schwerste Stabile Menge"-Problem besteht darin, für einen gegebenen, ungerichteten Graphen mit Knotengewichten eine Teilmenge der Knoten zu finden, sodass diese das höchstmögliche Gewicht hat. Dabei dürfern keine zwei Knoten in der Menge benachbart sein. Neben dem "Schwerste Stabile Menge"-Problem, das im Hauptfokus dieser Arbeit steht, befasst sich diese Dissertation auch mit anderen Unabhängigkeitsproblemen, darunter das "Größte 2-Packing Menge"-Problem, dessen gewichtete Veralgemeinerung das "Schwerste 2-Packing Menge"-Problem sowie das "Schwerste b-Matching"-Problem in Hypergraphen. Ein wichtiger Aspekt für die Lösung dieser Probleme sind Datenreduktionsregeln. Diese Dissertation stellt neue Datenreduktionsregeln für Unabhängigkeitsprobleme vor. Zusätzlich werden verschiedene Methoden eingeführt und detailiert diskutiert, welche diese Reduktionsregeln zur Berechnung qualitativ hochwertiger Lösungen verwenden.

Für das "Schwerste Stabile Menge"-Problem tragen wir neben neuen exakten Datenreduktionsregeln einen Screening-Ansatz bei, der mittels maschinellem Lernen die Reduktionsphase beschleunigen kann. Darüber hinaus präsentieren wir zwei Heuristiken, die nahezu optimale Lösungen auf statischen Graphen finden. Um das Problem für dynamische Graphen zu lösen stellen wir eine neue Technik vor, mit der qualitativ hochwertige Lösungen berechnet werden können. Diese Technik ist ebenfalls für das dynamische "Größte Stabile Menge"-Problem geeignet, sowie auf statischen Graphen als Lokale Suche anwendbar. Wir führen auch mehrere neue Datenreduktionsregeln für das "Größte 2-Packing Menge"-Problem und seine gewichtete Verallgemeinerung ein. Die Kombination dieser neuen Datenreduktionsregeln mit einer Reduktion auf das "Größte/Schwerste Stabile Menge"-Problem ermöglicht es uns, bestehende Ansätze für stabile Mengen zu nutzen. Das führt zu mehreren Methoden, die qualitativ hochwertige 2-Packing Mengen berechnen können. In Bezug auf das "Schwerste b-Matching"-Problem in Hypergraphen präsentieren wir eine Reihe neuer Datenreduktionsregeln und neue Greedy Strategien, sowie eine Lokale Suche zur Berechnung qualitativ hochwertiger Lösungen.

Alle vorgestellten Methoden werden ausführlich diskutiert und anhand einer Vielzahl realer Benchmark-Instanzen experimentell evaluiert. Diese experimentellen Ergebnisse zeigen, dass die Verwendung unserer Datenreduktionsregeln die Eingabegröße, von vielen Instanzen erheblich reduzieren kann, was bei allen hier eingeführten Algorithmen aber auch anderen getestete Methoden eine schneller Laufzeit und verbesserte Lösungsqualität ermöglicht. Darüber hinaus demonstrieren wir, dass unsere Ansätze die aktuell besten Methoden in verschiedenen Metriken übertreffen. Insgesamt zeigt diese Dissertation die Wichtigkeit und den starken Einfluss von Datenreduktionsregeln auf das Lösen von verschiedenen Unabhängigkeitsproblemen.