Graphenprobleme mit Rucksack Nebenbedingungen

Ein Graph ist ein allgemeines Modell um reale Strukturen, wie z.B. Straßennetze oder Pipelinesysteme darzustellen. Graphen geben aber auch logische Verbindungen unterschiedlichster Objekte wieder, von elektronischen Schaltkreisen bis zu sozialen Netzwerken. Häufig sind die Knoten und Kanten eines Graphen mit numerischen Werten versehen, die z.B. Distanzen, Kosten oder Kapazitäten darstellen können. In diesem Projekt betrachtete Optimierungsprobleme auf Graphen sind der Spann-Baum und das Steinerbaum Problem, das Zuordnungsproblem, independent set in einem Konflikt-Graphen, das orienteering Problem (verwandt zum Rundreiseproblem), und die maximale Clique. Obwohl alle diese Probleme durch Anwendungsszenarien motiviert sind, können praktische Probleme meist nicht durch diese Standardmodelle modelliert werden, sondern erfordern zusätzliche Bedingungen. Eine sehr einfache und zugleich plausible Erweiterung von klassischen Graphenproblemen ist das Hinzufügen einer linearen Nebenbedingung mit einer oberen Schranke als Ressourcen- oder Budgetbeschränkung. Eine derartige Nebenbedingung ist das Grundelement des Rucksackproblems, dem elementarsten diskreten Optimierungsproblem. Aus der Kombination ergibt sich das general knapsack constrained graph problem, welches im Mittelpunkt dieses Projekts steht. Viele Graphenprobleme sind bereits in der Standardversion schwierig im Sinne der theoretischen Informatik. Andere werden erst durch die hinzugefügte Rucksackbedingung schwierig. Im ersten Teil des Projekts werden wir Eigenschaften des Graphen identifizieren, die die Grenze zwischen effizient (also polynomiell) lösbar und schwierig definieren. Für die nicht polynomiell lösbaren Fälle entwickeln wir Approximationsalgorithmen und untersuchen die theoretischen Grenzen der Approximierbarkeit. Im zweiten Teil des Projekts wollen wir strukturelle Ähnlichkeiten zwischen unterschiedlichen Einzelproblemen des allgemeinen Problemtyps ausnützen um allgemein verwendbare Methoden der Approximation zu entwickeln. Im Speziellen werden wir Graphklassen betrachten, für die es eine baum-artige Zerlegung gibt, aus der Approximationsalgorithmen gewonnen werden können. Beispiele dafür sind Graphen von beschränkter treewidth und chordale Graphen. Weiters werden wir planare Graphen untersuchen und basierend auf der Separationseigenschaft und der Zerlegbarkeit in outerplanare Teilgraphen Approximationsalgorithmen entwerfen. Für die Konstruktion von exakten Lösungsverfahren legt die Struktur des knapsack constrained graph problem die Lagrange Relaxation der Rucksackbedingung nahe. Im dritten Teil des Projekts werden wir die Komplexität der dadurch entstehenden Unterprobleme untersuchen und in Abhängigkeit davon unterschiedliche Suchstrategien für das Lagrange Dualproblem aus allgemeiner Sicht vergleichen. Dadurch entwickeln wir wertvolle Richtlinien für den Entwurf von exakten Algorithmen in allgemeinen Branch-and-Bound Systemen.

Dieses Projekt verbindet zwei interessante Grundelemente der kombinatorischen Optimierung. Einerseits werden viele praktische Sachverhalte durch Graphen modelliert. Ein Graph besteht aus Knoten, welche Objekte oder Orte der realen Welt repräsentieren, und aus Kanten, die jeweils zwei Knoten verbinden und eine reale Beziehung der beiden verbundenen Objekte wiedergeben. Andererseits sind bei vielen praktischen Entscheidungsproblemen zusätzliche Einschränkungen in Form von limitierten Budgets oder beschränkten Ressourcen zu berücksichtigen. Diese werden als Rucksack Nebenbedingungen bezeichnet; in Analogie zur Gewichtsbeschränkung beim Einpacken eines Rucksacks.In diesem Forschungsprojekt wurden einige grundlegende Graphenprobleme mit zusätzlichen Rucksack - Nebenbedingungen behandelt. Ziele waren dabei die Entwicklung von approximativen Lösungsverfahren, also Lösungen, die einen vorgegebenen Maximalabstand von der unbekannten Optimallösung haben, sowie der Beweis von Komplexitätsresultaten, welche die Existenz einer derartigen Approximation grundsätzlich ausschließen. Ob ein gegebenes Problem noch approximativ gelöst werden kann oder nicht, hängt dabei meist von gewissen Struktureigenschaften des vorliegenden Graphen ab. Wir konnten für viele bekannte Graphklassen derartige Klassifizierungen und sofern möglich Approximationsalgorithmen entwickeln und dadurch wertvolle neue Erkenntnisse über Möglichkeiten und Limitierungen von Lösungsalgorithmen liefern.Im Fokus des Projekts stand speziell das Quadratische Rucksackproblem, eine Problemstellung, bei der Abhängigkeiten zwischen Einzelentscheidungen besonders berücksichtigt werden. Die Struktur dieser Abhängigkeiten kann wiederum durch einen Graphen dargestellt werden. Abhängig von den Eigenschaften dieses Graphen konnten zahlreiche neue Approximationsalgorithmen und theoretische Komplexitätsresultate entwickelt und erfolgreich publiziert werden. Eine konkrete Verwendung des Quadratischen Rucksackproblems in einer Praxisanwendung zur Bestimmung des optimalen Marketing-Mix in einem Entscheidungstool für Marketing Manager baute auf diesen Erkenntnissen auf.Einen zweiten Schwerpunkt bildeten Rucksackprobleme mit paarweisen Konflikten, bei denen sich gewisse Dispositionsentscheidungen gegenseitig ausschließen. Diese werden durch einen Konfliktgraphen dargestellt. Die Problemstellung entspricht einem sehr bekannten Graphenproblem, dem Weighted Independent Set Problem, mit einer zusätzlichen Budgetrestriktion. Wir konnten dafür Approximationsalgorithmen für zahlreiche sehr allgemeine Graphklassen entwickeln und auch allgemeine, generische Algorithmen entwerfen, die für verschiedene Zerlegungen von Graphen oder auch für allgemeine Überklassen von planaren Graphen verwendet werden können.