Bulk-robust assignment problems: hardness, approximability and algorithms

Abstract

This thesis studies robust assignment problems with focus on computational complexity. Assignment problems are well-studied combinatorial optimization problems with numerous practical applications, for instance in production planning. Classical approaches to optimization expect the input data for a problem to be given precisely. In contrast, real-life optimization problems are modeled using forecasts resulting in uncertain problem parameters. This fact can be taken into account using the framework of robust optimization. An instance of the classical assignment problem is represented using a bipartite graph accompanied by a cost function. The goal is to find a minimum-cost assignment, i.e., a set of resources (edges or nodes in the graph) defining a maximum matching. Most models for robust assignment problems suggested in the literature capture only uncertainty in the costs, i.e., the task is to find an assignment minimizing the cost in a worst-case scenario. The contribution of this thesis is the introduction and investigation of the Robust Assignment Problem (RAP) which models edge and node failures while the costs are deterministic. A scenario is defined by a set of resources that may fail simultaneously. If a scenario emerges, the corresponding resources are deleted from the graph. RAP seeks to find a set of resources of minimal cost which is robust against all possible incidents, i.e., a set of resources containing an assignment for all scenarios. In production planning for example, lack of materials needed to complete an order can be encoded as an edge failure and production line maintenance corresponds to a node failure. The main findings of this thesis are hardness of approximation and NP-hardness results for both versions of RAP, even in case of single edge (or node) failures. These results are complemented by approximation algorithms matching the theoretical lower bounds asymptotically. Additionally, we study a new related problem concerning k-robust matchings. A perfect matching in a graph is $k$-robust if the graph remains perfectly matchable after the deletion of any k matching edges from the graph. We address the following question: How many edges have to be added to a graph to make a fixed perfect matching k-robust? We show that, in general, this problem is as hard as both aforementioned variants of RAP. From an application point of view, this result implies that robustification of an existent infrastructure is not easier than designing a new one from scratch.

Diese Dissertation behandelt robuste Zuordnungsprobleme mit dem Schwerpunkt auf deren komlexitätstheoretischen Eigenschaften. Zuordnungsprobleme sind gut untersuchte kombinatorische Optimierungsprobleme mit vielen praktischen Anwendungen, z. B. in der Produktionsplanung. Klassische Ansätze der Optimierung gehen davon aus, dass die Inputdaten eines Problems exakt gegeben sind, wohingegen Optimierungsprobleme aus der Praxis mit Hilfe von Voraussagen modelliert werden. Daraus folgen unsichere Problemparameter, woran die Robuste Optimierung ansetzt. Die Unsicherheit wird mit Hilfe einer Szenarienmenge modelliert, die alle möglichen Ausprägungen der Problemparameter beschreibt. Eine Instanz des klassischen Zordnungsproblems wird mit Hilfe eines Graphen und einer Kostenfunktion beschrieben. Die Aufgabe besteht darin, eine Zuordnung mit minimalen Kosten zu finden. Eine Zuordnung ist eine Teilmenge an Ressourcen (Kanten oder Knoten des Graphen), die ein kardinalitätsmaximales Matching induziert. In der Literatur sind überwiegend robuste Zuordnungsprobleme untersucht, die Unsicherheit in den Kosten behandeln, in diesem Fall besteht die Aufgabe darin, eine Zuordnung mit minimalen Kosten im Worst-Case-Szenario zu finden. Diese Dissertation dient der Einführung und Untersuchung des Robust Assignment Problem (RAP) welches Kanten- und Knotenausfälle modelliert; wobei die Kosten determinisitsch sind. Ein Szenario ist durch jene Teilmenge an Ressourcen definiert, welche gleichzeitig ausfallen können. Wenn ein Szenario eintritt, werden die jeweils ausfallenden Ressourcen aus dem Graphen entfernt. In RAP besteht das Ziel darin, eine Menge an Ressourcen mit minimalen Kosten zu finden, die robust gegenüber allen möglichen Ereignissen ist, d. h. eine Ressourcenmenge die für alle Szenarien eine gültige Zuordnung enthält. So kann beispielsweise in der Produktionsplanung der Mangel an Materialien, die für einen Auftrag benötigt werden, als Kantenausfall und die wartungsbedingte Abschaltung einer Produktionslinie als Knotenausfall modelliert werden. Die Hauptergebnisse dieser Arbeit sind Nichtapproximierbarkeits- und NP-Schwierigkeitsresultate beider RAP-Versionen, die bereits für die Einschränkung zutreffen, dass nur einzelne Kanten oder Knoten ausfallen können. Diese Ergebnisse werden durch Approximationsalgorithmen ergänzt, die die theoretischen Approximationsschranken asymptotisch erreichen. Zusätzlich wird ein neues, verwandtes Optimierungsproblem untersucht, welches sich mit k-robusten Matchings beschäftigt. Ein perfektes Matching in einem Graphen ist k-robust, wenn der Graph nach dem Löschen von k Matchingkanten weiterhin ein perfektes Matching besitzt. Es wird der Frage nachgegangen, wie viele Kanten zum Graphen hinzugefügt werden müssen, um ein gegebenes Matching k-robust zu machen. Dabei wird gezeigt, dass dieses Problem im Allgemeinen aus komplexitätstheoretischer Sicht genauso schwierig ist, wie die zuvor erwähnten RAP-Varianten. Aus der Anwendungsperspektive bedeutet dieses Resultat, dass die Robustifikation einer bestehender Infrastruktur nicht einfacher ist, als sie von Grund auf neu zu entwerfen.