Mutzel, PetraBökler, Friedrich Konstantin2018-09-212018-09-212018http://hdl.handle.net/2003/37134http://dx.doi.org/10.17877/DE290R-19130In this thesis, we are concerned with multiobjective combinatorial optimization (MOCO) problems. We attempt to fill the gap between theory and practice, which comes from the lack of a deep complexity theory for MOCO problems. In a first part, we consider a complexity notion for multiobjective optimization problems which derives from output-sensitive complexity. The primary goal of such a complexity notion is to classify problems into easy and hard problems. We show that the multiobjective minimum cut problem as well as the multiobjective linear programming problem are easy problems in this complexity theory. We also show that finding extreme points of nondominated sets is an easy problem under certain assumptions. On the side of hard problems, there are obvious ones like the multiobjective traveling salesperson problem. Moreover, we show that the well-known multiobjective shortest path problem is a hard problem. This is also the case for the multiobjective matching and integer min-cost flow problem. We also identify a class of problems for which the biobjective unconstraint combinatorial optimization problem is a barrier for efficient solvability. In a second part, we are again concerned with the gap between theory and practice. This time, we approach the multiobjective shortest path (MOSP) problem from the practical side. For the application in the planning of power transmission lines, we need to have implementations which can cope with large graphs and a larger number of objectives. The results from the first part suggest that exact methods might be incapable of achieving this goal which we also prove empirically. This is why we decide to study the literature on approximation algorithms for the MOSP problem. We conclude that they do not scale well with the number of objectives in general and that there are no practical implementations available. Hence, we develop a novel approximation algorithm in the second part which leans to the exact approaches which are well tested in practice. In an extensive computational study, we show that our implementation of this algorithm performs well even on a larger number of objectives. We compare our implementation to implementations of the other existing approximation algorithms and conclude that our implementation is superior on instances with more than three objectives.Diese Dissertation ist mit der Komplexität von mehrkriteriellen kombinatorischen Optimierungsproblemen (MOCO) befasst. Hierbei wollen wir die Lücke schließen, die sich aus dem Fehlen einer umfassenden Komplexitätstheorie dieser Probleme ergibt. In einem ersten Teil beschreiben wir einen Komplexitätsbegriff für mehrkriterielle Optimierungsprobleme, der sich von ausgabesensitiver Komplexität ableitet. Das Ziel eines Komplexitätsbegriffes ist die Klassifikation von Problemen in einfache und schwierige Probleme. Wir zeigen, dass die Probleme einen Pareto-optimalen Schnitt in einem Graphen zu bestimmen, sowie mehrkriterielle lineare Optimierung einfache Probleme nach dieser Komplexitätstheorie sind. Auch das Problem Extrempunkte von Pareto-Fronten zu bestimmen ist unter bestimmten Bedingungen ein einfaches Problem. Auf der Seite der schwierigen Probleme können wir über die offensichtlichen Probleme wie das mehrkriterielle Handlungsreisendenproblem hinaus auch zeigen, dass das bekannte mehrkriterielle Kürzeste-Wege-Problem ein schwieriges Problem darstellt. Dies gilt ebenso auch für das mehrkriterielle Zuordnungsproblem in allgemeinen Graphen und das mehrkriterielle Flussproblem mit ganzzahligen Flussvariablen. Wir finden in dieser Arbeit außerdem eine Klasse von Problemen, deren effiziente Lösbarkeit von der effizienten Lösbarkeit des bikriteriellen unrestringierten kombinatorischen Optimierungsproblems abhängt. In einem zweiten Teil beschäftigen wir uns wieder mit der Lücke zwischen Theorie und Praxis. Diesmal nähern wir uns dem mehrkriteriellen Kürzeste-Wege-Problem von der praktischen Seite. Für eine Anwendung in der Stromtrassenoptimierung ist es nötig einen Algorithmus zu finden, der sowohl mit großen Graphen, als auch mit mehreren Zielfunktionen umgehen kann. Aus dem ersten Teil können wir ableiten, dass exakte Methoden dort an ihre Grenzen stoßen, was wir auch empirisch belegen. Wir studieren daher Approximationsalgorithmen aus der Literatur und stellen fest, dass sie in der Anzahl der Zielfunktionen nur schlecht skalieren und auch noch nicht praxiserprobt sind. Daher entwickeln wir im zweiten Teil einen neuen Approximationsalgorithmus, der sich stark an die Errungenschaften der praktischen Algorithmen orientiert. Wir zeigen in einem groß angelegten Experiment, dass unsere Implementierung des Algorithmus auch noch auf einer größeren Anzahl von Zielfunktionen praxistauglich ist. Der Vergleich mit unseren Implementierungen der existierenden Approximationsalgorithmen zeigt zudem, dass unsere Implementierung den anderen auf Instanzen mit mehr als drei Zielfunktionen überlegen ist.enMultiobjective optimizationComputational complexity theoryOutput sensitive complexityLinear programmingShortest path problem004TextMehrkriterielle OptimierungKomplexitätstheorieLineare OptimierungKürzester-Weg-Problem