ISBN 9783843908467

978-3-8439-0846-7, Reihe Mathematik

Stephanie Heller
Matroid Flows: Interdiction and Location Problems

187 Seiten, Dissertation Technische Universität Kaiserslautern (2012), Softcover, A5

Zusammenfassung / Abstract

In dieser Arbeit werden Flussprobleme und Standortprobleme kombiniert. Dies geschieht im Kontext von Matroiden. Flussprobleme für gerichtete und ungerichtete Matroide werden definiert. Es wird gezeigt, dass jedes maximale Matroidflussproblem in einem ungerichteten Matroid in ein maximales Flussproblem in einem gerichteten Matroid überführt werden kann.

Ein betrachtetes Problem ist das Matroid Interdiction Problem. Hier soll durch Verringern der Kapazitäten um ein gegebenes Gewicht der maximale Fluss bezüglich eines Elements im Matroid minimiert werden. Das Minimieren der Kapazität führt zu Kosten. Diese Kosten sind nach oben durch ein gegebenes Budget beschränkt, dass nicht überschritten werden darf.

Das Matroid Interdiction Problem verallgemeinert das Netzwerk Interdiction Problem. Für den Spezialfall von kographischen Matroiden lässt sich das Matroid Interdiction Problem als ressourcenbeschränktes kürzeste Wege Problem formulieren. Eine IP Formulierung des Problems wird angegeben, sowie exakte und heurisitische Algorithmen. Die Komplexität des Problems für unterschiedliche Matroidklassen wird untersucht.

Ein weiteres betrachtetes Problem ist das Matroid Location Problem, welches das Flow Location und das Tension Location Problem auf reguläre Matroide erweitert. Ziel ist es, eine gegebene Menge Standorte mit fester Größe auf einer Teilmenge der Elemente zu platzieren. Das Platzieren eines Standorts auf einem Element führt dazu, dass die Kapazität des Elements um die Größe des Standorts verringert wird. Ziel ist es, eine Zuordnung der Standorte zu den Elementen zu finden, die den maximale Matroidfluss so wenig wie möglich verringert.

Die Komplexität des Problems wird für verschiedene Matroidklassen analysiert. IP Formulierungen, exakte und heuristische Algorithmen werden entwickelt. Die Laufzeiten der verschiedenen Lösungsmethoden, sowie die Qualität der heuristischen Lösungen werden untersucht und verglichen. Desweiteren werden Spezialfall betrachtet: das Finden von nur einem Standort, sowie das Platzieren von gleich großen Standorten. Es wird gezeigt, dass das Matroid Location Problem für graphische Matroide dem Flow Location Problem entspricht und für kographische Matroide dem Tension Location Problem.

Ideen für zukünftige Forschungsideen werden genannt, wie zum Beispiel die Erweiterung der Probleme auf mehrere Knotenpaare als Quellen und Senken, das Betrachten von dynamischen Matroidflüssen oder von minimalen Matroidkostenflüssen.