The topic of this Master’s thesis is robust optimization in the scope of uncertainty, in particular robust and reroutable flows in networks with failing arcs. In the wellknown Maximum Robust Flow problem [DM17], a flow is sent over a directed graph and is then interrupted by the destruction of a known number of arcs. All flow on paths leading through the destroyed arcs is lost. The objective is to maximize the remaining flow after failure of the arcs. We introduce a variation of this problem called Maximum Scaled Robust Flow, where the amount of destroyed flow is scaled with a linear factor. The problem is polynomial if only a single arc is allowed to fail, and NP-hard if the number of failing arcs is unknown. For small absolute values of the scaling factor, all solutions to the problem are maximum network flows. If the scaling factor is larger than a number depending on the connectivity of the underlying graph, the zero-flow is the unique optimal solution. Tightness examples are presented for the proven bounds. A variation with affine scaling is polynomially solvable if only one arc gets destroyed. The same holds for a version defined on arc-based flows for a fixed number of destroyed arcs. In the Maximum Reroutable Flow problem [MMO17], all flow lost to a single failing arc must be rerouted locally in the graph using available capacities. The objective value of the problem is given by the value of the original flow. The strict version of the problem, Maximum Strictly Reroutable Flow, makes more restrictive assumptions on the capacities available for rerouting. We introduce the variations Maximum Optional Reroutable Flow and Maximum Strictly Optional Reroutable Flow, where rerouting after failure of the arc is possible, but not mandatory. The objective value is computed by determining the arc that yields the worst-case flow value after failure and optional rerouting. We prove that the strict problem can be solved in polynomial time and that there exists a 2-approximation for the non-strict version. Compared to the original Maximum Reroutable Flow problem, making rerouting optional can only improve the objective value of the problem. We prove that Maximum Robust Flow always has a smaller objective value than Maximum Optional Reroutable Flow and that there exists a polynomial reduction from the former problem to the latter. Finally, we solve Maximum Optional Reroutable Flow and its strict version on unit capacity networks, giving an explicit objective value.     «

The topic of this Master’s thesis is robust optimization in the scope of uncertainty, in particular robust and reroutable flows in networks with failing arcs. In the wellknown Maximum Robust Flow problem [DM17], a flow is sent over a directed graph and is then interrupted by the destruction of a known number of arcs. All flow on paths leading through the destroyed arcs is lost. The objective is to maximize the remaining flow after failure of the arcs. We introduce a variation of this problem cal...     »

Thema dieser Masterarbeit ist robuste Optimierung im Rahmen von Unsicherheit, insbesondere robuste und umleitbare Flüsse in Netzwerken mit ausfallenden Kanten. Im bekannten Problem Maximum Robust Flow [DM17] wird ein Fluss durch einen gerichteten Graphen geschickt und dann durch die Zerstörung einer bekannten Anzahl von Kanten unterbrochen. Der gesamte Fluss auf Pfaden, die durch zerstörte Kanten führen, geht verloren. Ziel ist es, den übrig gebliebenen Fluss nach Ausfall der Kanten zu maximieren. Wir präsentieren eine Variation dieses Problems namens Maximum Scaled Robust Flow, bei dem die Höhe an zerstörtem Fluss mit einem linearen Faktor skaliert wird. Das Problem ist polynomiell lösbar, wenn nur eine einzige Kante ausfällt, und NP-schwer, wenn die Zahl an ausfallenden Kanten unbekannt ist. Für kleine Beträge des Skalierungsfaktors sind alle Lösungen des Problems maximale Netzwerk-Flüsse. Wenn der Skalierungsfaktor größer ist als eine Zahl abhängig von der Konnektivität des zu Grunde liegenden Graphen, dann ist der Null-Fluss die einzige optimale Lösung. Durch Beispiele wird gezeigt, dass die bewiesenen Schranken scharf sind. Eine Variation mit affiner Skalierung ist polynomiell lösbar, wenn nur eine Kante zerstört wird. Das Gleiche gilt für eine Version, die auf kantenbasierten Flüssen für eine feste Anzahl von zerstörten Kanten definiert ist. Beim Maximum Reroutable Flow-Problem [MMO17] muss der gesamte Fluss, der an den Ausfall einer einzigen Kante verloren geht, lokal im Graphen mit Hilfe der verfügbaren Kapazitäten umgeleitet werden. Der Zielfunktionswert des Problems ist durch den Wert des ursprünglichen Flusses gegeben. Die strikte Version des Problems, Maximum Strictly Reroutable Flow, gibt strengere Bedingungen an die für das Umleiten verfügbaren Kapazitäten vor. Wir führen die Variationen Maximum Optional Reroutable Flow und Maximum Strictly Optional Reroutable Flow ein, bei denen Umleiten nach dem Ausfall der Kante möglich, aber nicht zwingend notwendig ist. Der Zielfunktionswert wird durch die Kante bestimmt, die nach Ausfall und optionalem Umleiten den schlechtesten Flusswert liefert. Wir beweisen, dass das strikte Problem in polynomieller Zeit lösbar ist und dass eine 2-Approximation für das nicht-strikte Problem existiert. Das Umleiten optional zu machen, verbessert im Vergleich zum ursprünglichen Problem, Maximum Reroutable Flow, den Zielfunktionswert. Wir beweisen, dass Maximum Robust Flow immer einen kleineren Zielfunktionswert als Maximum Optional Reroutable Flow hat und dass es eine polynomielle Reduktion von ersterem zu letzterem gibt. Schließlich lösen wir Maximum Optional Reroutable Flow und dessen strikte Version auf Einheitskapazitäts-Netzwerken, indem wir einen expliziten Zielfunktionswert angeben.     «

Thema dieser Masterarbeit ist robuste Optimierung im Rahmen von Unsicherheit, insbesondere robuste und umleitbare Flüsse in Netzwerken mit ausfallenden Kanten. Im bekannten Problem Maximum Robust Flow [DM17] wird ein Fluss durch einen gerichteten Graphen geschickt und dann durch die Zerstörung einer bekannten Anzahl von Kanten unterbrochen. Der gesamte Fluss auf Pfaden, die durch zerstörte Kanten führen, geht verloren. Ziel ist es, den übrig gebliebenen Fluss nach Ausfall der Kanten zu maximiere...     »