Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In 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.
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.
Description
Table of contents
Keywords
Multiobjective optimization, Computational complexity theory, Output sensitive complexity, Linear programming, Shortest path problem